PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Asymptotically Optimal Linear Codes Correcting Defects of Linearly Increasing Multiplicity
I. I. Dumer
pp. 93–104

Abstract—Asymptotically optimal linear codes are proposed for defect correction. A method of correcting defects of linearly increasing multiplicity $t$ for block length $n\to\infty$ is considered. The method constructs an asymptotically optimal code with redundancy $r(n,t)\sim t$ in polynomial time and requires $O(n\log_2^3n)$ coding–decoding operations.

Decoding of Block Codes Obtained from Convolution Codes
B. D. Kudryashov
pp. 104–111

Abstract—We consider block codes obtained from convolution codes by truncation with “tail biting.” A decoding algorithm is proposed. We show that for these codes the asymptotic tradeoff relationships between error probability and decoding complexity are the same as for convolution codes with Viterbi decoding.

Capacity Bounds for a Channel with Synchronization Errors
A. S. Dolgopolov
pp. 111–120

Abstract—We analyze the problem of computing the capacity of a symmetrical channel with independent streams of symbol insertions, deletions, and replacements. Lower bounds on capacity are derived for a channel without insertions and for a channel without deletions. Using a certain combinatorial conjecture, we derive bounds for a channel with only insertions and for a channel with only deletions, which to a high degree of accuracy coincide with the experimental data of Vvedenskaya and Dobrushin [Probl. Peredachi Inf., 4, No. 3, 92–95 (1968)].

Generalized Correlation Metric for Decoding in a Multiple Access Channel
I. E. Bocharova and F. A. Taubin
pp. 121–126

Abstract—We consider transmission by a vector adder channel with two independent inputs and additive white Gaussian noise. Decisions on the channel output are made by individual decoders. A new metric for decoding in such a channel is proposed, which is a generalization of the correlation metric and is close to the optimal metric in some cases. Bounds on decoding error probability are given. A procedure for optimization of system characteristics is discussed.

Optimal Order of Accuracy of Search Algorithms in Stochastic Optimization
B. T. Polyak and A. B. Tsybakov
pp. 126–133

Abstract—A new optimum-seeking method is proposed and its asymptotic optimality is proved.

Estimators of the Correlation Region Area of a Gaussian Homogeneous Random Field
V. G. Alekseev
pp. 133–140

Abstract—The notion of correlation region area (CRA) is defined for a homogeneous random field $\{\xi(\mathbf k),\:\mathbf k\in\mathbb Z^2\}$. A statistical estimator is introduced for one of the simplest definitions of CRA. Its asymptotic properties (with sample size increasing to infinity) are investigated for the simplest case where $\xi(\mathbf k)$ is a Gaussian random field with mean $\operatorname{\bf Ì}\xi(\mathbf k)\equiv 0$.

Random Multiple Access with Known Appearance Times of Successfully Transmitted Packets
B. S. Tsybakov and N. B. Likhanov
pp. 141–151

Abstract—We consider a communication network with many stations sharing one channel for packet transmission by a random multiple access (RMA) algorithm. Packets may carry information about their appearance times, and this information is used in order to increase the rate of the channel. We show that if a single bit is dedicated in the packet to this information, the record rate of 0.487, previously attained only with the splitting algorithm, can be raised to 0.490 with the algorithm proposed in this paper. However, the rate remains below 0.578 for any algorithm with knowledge of the appearance times of successfully transmitted packets.

A Simple Stable RMA Algorithm for LAN
B. S. Tsybakov, V. B. Fayngold, and S. P. Fedortsov
pp. 151–160

Abstract—The paper examines a simple version of the random multiple access (RMA) stack algorithm, which is used in a LAN controller. Expressions are derived for the maximum data rate and mean packet delay in the network. The simple stack algorithm is compared with other RMA algorithms for LAN.

Bounds on Probability of Group Connectedness of a Random Graph
V. P. Polesskii
pp. 161–169

Abstract—Effective and exact upper bounds are proved on the probability of connectedness of a distinguished group of vertices in a random graph. These results generalize previous bounds on the probability of connectedness of all vertices in a graph.

Controllable Connector
L. A. Bassalygo and M. S. Pinsker
pp. 170–172

Abstract—The sufficient conditions of expander controllability obtained in [P. Feldman et al., SIAM J. Discr. Math., 1, No. 2, 158–173 (1988)] are weakened.

A Comment on the Weight Structure of Generator Matrices of Linear Codes
S. M. Dodunekov
pp. 173–176

Abstract—We prove that for any linear $q$-ary $[n,k,d]$-code with $n=t+g_q(k,d)$ where $$ g_q(k,d)=\sum\limits_{j=0}^{k-1}\biggl\lceil\dfrac d{q^j}\biggr\rceil $$ is the Griesmer function, a generator matrix can be selected from code vectors of weight not exceeding $d+t$.

On Adaptive Conflict Resolution Algorithms in a Multiple Access Channel
A. Ya. Belokopytov
pp. 176–180

Abstract—A new upper bound is derived on the minimum of the maximum time to resolve a conflict of multiplicity $k$ for adaptive algorithms. This bound asymptotically coincides with the lower bound for nonadaptive protocol lengths. For an a priori known $k=4$, an adaptive algorithm is constructed which is asymptotically more efficient than any nonadaptive algorithm.