PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Stationary Channels with a Random Parameter Which Is a Completely Singular Process
M. S. Pinsker, V. V. Prelov, and E. C. van der Meulen
pp. 1–9

Abstract—A stationary channel with a random parameter $U=\{U_j\}$ which is a completely singular stationary process independent of an input signal $X=\{X_j\}$ is considered. It is shown that under rather weak additional conditions, the information rate $\overline{I}(X;Y)$ between the input signal $X=\{X_j\}$ and output signal $Y=\{Y_j\}$ of such a channel coincides with the conditional information rate $\overline{I}(X;Y|U)$. A special case of such a channel is investigated in more detail, where $Y=UX+Z$ and $Z=\{Z_j\}$ is an additive noise independent of $X$ and $U$.

Information Transmission over Continuous-Time Gaussian Channels with Feedback
S. Ihara
pp. 10–24

Abstract—We consider continuous-time Gaussian channels with feedback and investigate problems on the mutual information and the channel capacity. Whereas in most previous works some conditions are imposed on the Gaussian noise, in this paper we do not require any special conditions on the Gaussian noise. We derive a formula for the mutual information transmitted over the Gaussian channel with feedback. Then we show that the capacity of the channel is achieved in linear schemes, more precisely, achieved by sending a Gaussian message with the help of linear feedback. We also show some inequalities concerning the capacity of the channel.

Centered Error-Correcting Codes
L. A. Bassalygo and M. S. Pinsker
pp. 25–31

Abstract—Assume that during writing new information to the memory we are allowed to change only a limited number of symbols of a word stored there. Then a condition occurs in which we have to choose codewords in a sphere, where the center of the sphere (old information) is known to the encoder only. The situation becomes complicated in the presence of errors which can be considered both as ordinary and as localized.

Correction of a Single Localized Error by Nonbinary Constant-Weight Codes of Weight One
V. S. Lebedev
pp. 32–36

Abstract—The precise value of the cardinality of an optimal nonbinary single-localized-error-correcting code is found for the case where all codewords have weight 1 and the length is a multiple of 3.

On Algebraic Decoding of Cyclic Codes
E. T. Mironchikov and S. V. Fedorenko
pp. 37–41

Abstract—Decoding of some cyclic codes up to the actual distance is considered. For this, additional identities are introduced that connect power sums with coefficients of the locator polynomial. Examples are given.

Fast Encoding of Low-Entropy Sources
B. Ya. Ryabko and M. P. Sharova
pp. 42–51

Abstract—We consider the problem of coding for low-entropy information sources. Since the run-length code was proposed by Shannon about fifty years ago, it has been known that such sources can be coded by much simpler methods than arbitrary sources can. However, the known coding methods for low-entropy sources are unable to achieve a preassigned redundancy. In the paper, we suggest a new method of encoding low-entropy sources, for the cases of known and unknown statistics, which enables us to reach any predefined redundancy. The encoding/decoding rate in this method, which is measured by the number of binary operations on one-bit words, is considerably higher than in the general methods.

Large Deviation Principle for the Border of a Random Young Diagram
V. M. Blinovsky
pp. 52–62

Abstract—The local large deviation principle for a random Young diagram is proved. An explicit expression for the corresponding action functional is obtained.

Multiplicativity of a Stationary Distribution of an Open Queueing Network with Standard Nodes and Single-Type Calls
Yu. V. Malinkovsky
pp. 63–75

Abstract—We consider open queueing networks with Markov routing, standard nodes, and one type of completely random arrivals. We assume that nodes with Poisson flow of arrivals, being isolated from the network, are described by continuous-time Markov chains. Under certain conditions, we establish necessary, sufficient, and necessary-and-sufficient conditions for the stationary distribution of the process describing the network to be representable as a product of factors characterizing the separate nodes.

Formal Models of Reflexive Structures
Yu. A. Shreider
pp. 76–84

Abstract—Formal models for reflexive structures are suggested.

Algorithms for Generation of a Common Key Using a Quantum Communication Channel
V. M. Sidelnikov
pp. 85–92

Abstract—Subscribers $A$ and $B$, with the help of a quantum communication channel, obtain binary sequences ${\mathbf{a}}$ and ${\mathbf{b}}$ close in Hamming metric. The channel is eavesdropped by a subscriber $E$. Each of $A$ and $B$ must generate a common secret key ${\mathbf{k}}$, which should be inaccessible to $E$. In this paper, on the basis of error-correcting codes, we propose an original algorithm for generating ${\mathbf{k}}$, which requires only one round of exchange over a noiseless public communication channel. Using the physical assumptions about the possibilities of intercepting information in a quantum channel, we can prove rigorously that the eavesdropper $E$ will be able to obtain almost no information about the common key ${\mathbf{k}}$ if a “good” error-correcting code is exploited with the algorithm proposed.

Letter to the Editor (M. V. Burnashev and A. S. Holevo)
pp. 93–94