PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Improved Upper Bound on the Probability of Decoding Error for Codes of Complex Structure
G. Sh. Poltyrev
pp. 251–262

Abstract—Two methods without expurgation are proposed for constructing an upper bound of the probability of decoding error in a memoryless discrete channel, which is better than the random coding bound for low rates. Although in general the bounds obtained by these methods are worse than the expurgated bound, they are applicable to codes with structure constraints. We examine the application of these bounds to trellis codes, to codes for multiple access channels, to $(s,t)$-designs, and to $B_s$-codes.

Spectra of Algebraic-Geometric Codes
G. L. Katsman and M. A. Tsfasman
pp. 262–275

Abstract—We derive bounds on the enumerator of an arbitrary algebraic-geometric code. We calculate in full the weight distribution of the code constructed from all the points of an elliptical curve. The weight distribution (the enumerator) is found to depend on the group of points of this curve and on an element of this group. The number of minimum-weight vectors is minimized both by elements and by curves. The possibility that such a code is an MDS code is explored.

Optimal Decoding of Convolutional Codes in Channels with Additive Markov Noise
V. I. Korzhik and Yu. P. Lopato
pp. 276–280

Abstract—We formulate the conditions when the maximum of a certain function can be found by a generalized Viterbi algorithm (GVA). We prove that GVA can be used for optimal decoding of convolutional codes in channels with additive Markov noise. The complexity of the algorithm is estimated. Some simulation results supporting the efficiency of GVA are presented.

On Sequential Decoding of Linear Convolutional Codes
V. B. Balakirskii
pp. 281–287

Abstract—We analyze the complexity of the sequential decoding algorithm using a time- varying linear convolutional code. An asymptotic upper bound is obtained for the number of computations performed by the decoder in the initial node of the code trellis, which coincides up to a constant with the known bound for linear tree codes [T. Hashimoto and S. Arimoto, IEEE Trans. Inf. Theory, 1979, vol. 25, no. 5, pp. 584–591].

Encoding of Poisson Streams with Unknown or Inaccurately Known Parameters
V. K. Trofimov
pp. 288–295

Abstract—We obtain redundancy bounds for universal encoding of messages generated by a Poisson stream. The bounds coincide up to an additive constant.

Bounds for the Number of Mappings of Graphs and for the Number of Subgraphs
A. M. Leontovich
pp. 296–311

Abstract—We obtain bounds for the number of mappings of one graph to another and for the number of connected subgraphs of a graph. The bounds are expressed in terms of quantities that depend only on the degrees of the vertices in the graph.

Hybrid Switching Networks on an Infinite One-Dimensional Lattice
Yu. M. Sukhov and R. N. Shamsiev
pp. 312–322

Abstract—We present a family of random point sources describing the operation of a switching network with a finite number of serially connected nodes. The transmission rule includes elements of both channel and message switching. The relevant family of streams is defined as the solution of a system of equations satisfying the transmission rule. Existence and uniqueness (in a certain class) of the solution is proved.

Performance of a RMA Stack Algorithm in a Local Network
B. S. Tsybakov and S. P. Fedortsov
pp. 323–336

Abstract—Two generalizations of the RMA stack algorithm for local networks are considered. We obtain a general expression of the packet transmission delay for a memoryless input stream with an arbitrary packet length distribution. For a Poisson input and packet length taking one of two possible values, we compare the two generalized stack algorithms by transmission rate and mean delay.

Optimal Choice of Structural Parameters of Satellite Communication Systems with Multistation Access
G. P. Basharin, L. A. Vigulis, and B. E. Kurenkov
pp. 337–343

Abstract—We analyze a model of a satellite communication system with circuit switching. An effective algorithm is proposed for computing its probabilistic operating characteristics. The results of a computer experiment are presented.

Greismer Codes with Maximum Covering Radius
S. M. Dodunekov
pp. 344–346

Abstract—Let $C$ be a $(k,d)$ Greismer code with covering radius $\rho(C)$. We prove that if $d\gt 2^k$ or $d$ belongs to Belov intervals of dimension $k+1$, then $\rho(C)\leq d-2$. All Greismer codes $C$ with $\rho(C)\leq d-1$ are described.

Block Information Transmission in a Multiple Access Adder Channel with Feedback
A. Ya. Belokopytov and V. N. Luzgin
pp. 347–351

Abstract—We consider zero-error encoding in a noiseless summing multiple access channel with feedback. A constructive encoding algorithm is given which exceeds the capacity of the same channel without feedback.

On the Designed Distance of the Best Known $(55,16,19)$ Goppa Code
S. V. Bezzateev and N. A. Shekhunova
p. 352

Abstract—For the $(55, 16, 19)$ binary Goppa code we give the Goppa polynomial whose degree specifies the designed code distance equal to its true minimum distance of $19$.

INDEX
pp. 353–358