PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Codes Associated with the Linear Fractional Group
I. B. Gashkov and V. M. Sidel'nikov
pp. 1–11

Abstract—Standard MDS codes are considered from a new angle (these codes are associated with three maximal Abelian subgroups of the linear fractional group).

List Decoding of Convolutional Codes
V. B. Balakirsky and B. D. Kudryashov
pp. 11–17

Abstract—An algorithm for list decoding of convolutional codes is proposed. The asymptotic tradeoff between decoding error probability and decoder complexity with that attainable in sequential decoding. Examples of codes are given for which the proposed decoding method produces better relationships than the Viterbi algorithm.

Two Decoding Algorithms for Linear Codes
I. I. Dumer
pp. 17–23

Abstract—We propose an algorithm to compute the nearest codeword in a BSC. For a linear code of length $n$ and rate $R$, the algorithm executes in time of order $2^{n(1-R)/2}$. For codes with distance $d$ increasing linearly with length, we propose an algorithm capable of correcting $[(d-1)/2]+\mathrm{const}$ errors which involves a linearly increasing number of attempts to correct $[(d-1)/2]$ errors.

On the Straight-Line Bound for the Undetected Error Exponent
V. I. Levenshtein
pp. 24–27

Abstract—We derive a one-parametric family of lower bounds for the undetected error probability of a code in a binary symmetric channel. With an optimally chosen parameter, these bounds lead to the so-called straight-line bound for the undetected error exponent. The straight-line bound is asymptotically exact if the Varshamov–Gilbert bound for the distance of binary codes is asymptotically exact.

Covering Radius for Long BCH Codes
S. G. Vlǎduţ and A. N. Skorobogatov
pp. 28–34

Abstract—We calculate the covering radius of sufficiently long primitive and also nonprimitive BCH codes.

Invariance of Stationary Ergodic Distributions of Homogeneous Markov Processes under Random Interrupts
M. Ya. Postan
pp. 35–41

Abstract—For a Markov chain controlled by a semi-Markov process and for a piecewise-linear process describing the operation of a multiserver system with a bounded queue in a random environment, the stationary ergodic distributions are shown to be independent of random interruption of transitions from one state to another. The results make it possible to ignore, under certain conditions, the effect of interrupts on data transmission in calculating the performance measures of communication devices and networks.

Asymptotic Stabilization in the Decentralized ALOHA Algorithm. Diffusion Approximation
A. A. Borovkov
pp. 42–49

Abstract—We consider a synchronous communication system controlled by a decentralized ALOHA algorithm. Such a system is not ergodic [1–5]. However, as the basic parameter of the algorithm is reduced, the system reveals the property of being asymptotically stable (ergodic) on increasing time intervals. The diffusion approximation on these intervals is obtained.

Locally Interacting Processes and Communication Networks
I. A. Ignatyuk and V. A. Malyshev
pp. 50–59

Abstract—We consider communication systems with weakly interacting message streams and derive an explicit expression for the stationary probabilities in the form of a series in diagrams. The results fit in the general scheme of locally interacting processes.

A Poisson Limit Theorem for Hybrid Star Networks: the Mean Field Approximation
M. Ya. Kelbert and Yu. M. Sukhov
pp. 60–67

Abstract—We present an asymptotic analysis of the equipped marked point process describing the stationary operation of a star network with hybrid switching, including elements of both message switching and circuit switching. Asymptotic formulas are given for the distribution of the delivery time of a single message. The results may be considered as a variant of the Poisson conjecture originally proposed by L. Kleinrock for message switching networks. In the language of physics, this corresponds to passage to the limit in the mean field approximation.

Randomized and Nonrandomized Algorithms of Random Multiple Access
B. S. Tsybakov
pp. 67–76

Abstract—For any randomized random multiple access algorithm with a Poisson input, we construct an equivalent nonrandomized algorithm with equal rate, delay time, and other parameters.

The Dimension of BCH Codes
I. E. Shparlinsky
pp. 77–80

Abstract—We derive an upper bound on the number of information symbols of arbitrary $q$-ary BCH codes with a given constructive distance $d$ and length $n$. A similar result has been previously available only for codes of length $n=qm-1$, $m=1,2,\ldots\strut$.

Ergodicity of One Locally Interacting System of Automata
K. L. Vaninskii
pp. 80–84

Abstract—We consider a system of locally interacting automata and derive sufficient conditions of ergodicity of the Markov chain describing its states. Necessary and sufficient conditions of ergodicity are obtained for a system with an odd number of automata.

OBITUARY. Lev Matveevich Fink
p. 85