PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Capacity of the Arbitrarily Varying Channel under List Decoding
V. M. Blinovsky, P. Narayan, and M. S. Pinsker
pp. 99–113

Abstract—We find necessary and sufficient conditions under which the capacity $C_L$ of an arbitrarily varying channel (AVC), for deterministic codes with decoding into a list of size $L$ and for the average error probability criterion, equals the capacity $C_r$ of the AVC for random codes. For binary AVCs, we prove the existence of a finite $L^\ast\lt\infty$ such that $C_L=C_r$ for all $L\gt L^\ast$.

Multi-Alphabet Universal Coding of Memoryless Sources
Yu. M. Shtarkov, Tj. J. Tjalkens, and F. M. J. Willems
pp. 114–127

Abstract—The universal coding of memoryless sources is considered in the case where its redundancy depends on the number of different letters in the message to be encoded. The coding method is analyzed and shown to be close to optimal. Some modifications of this method for sequential arithmetic coding are developed and compared with known algorithms.

On the Decoding of Some Exceptional Ternary Codes
S. M. Dodunekov and J. E. M. Nilsson
pp. 128–134

Abstract—We present an algebraic decoder for the ternary Gashkov–Sidel'nikov (GS) codes. The GS codes are the best known family of double-error-correcting ternary codes. We devise a step-by-step decoder for the ternary Golay code.

Bounded Minimum Distance Decoding of (P)UM Codes Based on RS Codes
U. Dettmar and U. K. Sorger
pp. 135–142

Abstract—In this paper, we describe the construction of (partial) unit memory ((P)UM) codes based on RS codes and discuss an algorithm for bounded minimum distance decoding of these codes up to half the “designed” extended row distance. The complexity of this algorithm is upper bounded by $4k_1K_B$, where $k_1$ denotes the memory of the (P)UM code and $K_B$ is the complexity for a bounded minimum distance decoder of a component block code of the (P)UM code considered.

Decoding by Generalized Information Sets
E. A. Kruk and S. V. Fedorenko
pp. 143–149

Abstract—An algorithm is suggested for decoding linear block codes by generalized information sets. A construction of coverings by codewords is considered, and a table of such coverings for binary codes is presented.

Construction of a Constant-Weight Code of Weight 2 Correcting One Localized Error
V. S. Lebedev
pp. 150–153

Abstract—We find the explicit value of the cardinality of an optimal binary code correcting one localized error for the case where each codeword has weight 2.

On the Construction of Trellis Codes Based on (P)UM Codes over $\mathbb{Z}_4$
R. Kötter, U. Dettmar, and U. K. Sorger
pp. 154–161

Abstract—The construction of some binary trellis (partial) unit memory ((P)UM) codes based on codes over the ring $\mathbb{Z}_4$ is proposed. Estimates of the distance properties of these codes are obtained.

Asymptotically Optimal Binary Codes of Polynomial Complexity Correcting Localized Errors
R. Ahlswede, L. A. Bassalygo, and M. S. Pinsker
pp. 162–168

Abstract—The asymptotically optimal transmission rate of binary codes correcting localized errors is known when the number of errors grows linearly in the code length. Here we prove that this rate can be attained by codes with polynomial complexity of encoding, decoding, and code construction.

Nonbinary Convolutional Coding in Channels with Jamming
K. Sh. Zigangirov, S. A. Popov, and V. V. Chepyzhov
pp. 169–183

Abstract—The characteristics of $q$-ary convolutional codes are investigated for the ensemble of codes where the codes are used for information transmission under the condition that there is artificial signal-like noise (jamming) in the channel and additive noise is absent. As a model of this channel, we consider the J-channel described below, which is a particular case of a discrete memoryless channel. A decoding algorithm of the convolutional codes is proposed. Upper estimates for the decoding error probability and the decoding complexity are derived for the ensemble of convolutional codes. Exponential-type estimates for the distribution function of the decoding complexity for the ensemble of trellis codes are derived as well. Results of simulation of convolutional codes based on the Reed–Solomon codes are presented.

A Random Multiple Access Algorithm with Finite Stack and Packet Loss
S. P. Fedortsov and N. A. Ryleeva
pp. 184–193

Abstract—The performance analysis of a random multiple access algorithm with finite stack is developed. Packets that come out of the stack are considered to be lost for the system. The throughput and the delay of successfully transmitted packets are obtained. It is shown how the algorithm characteristics depend on the stack size. The results obtained can be used in the design of communication systems with random multiple access of users to a shared channel.