PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Message Transmission over a Discrete Channel with Noiseless Feedback
B. D. Kudryashov
pp. 1–9

Abstract—Lower bounds are obtained for the exponent of the error probability for the case of nonblock message transmission over a discrete memoryless channel with noiseless feedback, and with random decoding delay.

Relationship between Shannon and Fisher Information in a Diffusion Process
A. F. Taraskin
pp. 9–18

Abstract—An asymptotic formula is obtained that relates the Shannon and Fisher quantities of information in the realization of a diffusion process relative to a message that appears in the drift as a random parameter. For some special cases, exact formulas are given that express the Shannon quantity of information in terms of the Fisher information, and it is shown that maximum-likelihood decoding is sufficient in the sense of Pinsker.

Channel Capacity with a Constraint on the Smoothness of the Transmitted Signal
I. A. Ibragimov and R. Z. Khas'minskii
pp. 18–26

Abstract—The authors determine the asymptotic behavior of the capacity of a channel with white Gaussian noise under constraints on the mean power and the smoothness of the periodic transmitted signal $S(t)$. It is shown that the capacity depends very strongly on the degree of smoothness of $S(t)$. In particular, for a periodic function $S(t)$ whose derivative of order $\gamma$ is bounded in the mean square by some constant, the capacity $C$ is asymptotically proportional to $T^{1/(2\gamma+1)}$ if the transmission time $T$ is large.

Iterative Arithmetic Independent-Error-Correcting Codes
I. M. Boyarinov and G. A. Kabatyanskii
pp. 27–36

Abstract—The properties of iterative arithmetic codes are described. Two decoding algorithms for these codes are proposed, a majority algorithm and a stage-by-stage algorithm. A class of optimal multiresidue arithmetic codes is constructed.

Complexity of Constructing Codes with Specified Correction Properties
V. Yu. Krachkovskii
pp. 36–41

Abstract—The article investigates the complexity with which it is possible to construct codes that satisfy familiar asymptotic bounds for the error probability. Procedures for nonrandom choice of a binary linear code lying on the Gallager bound and for construction of a cascade code lying on the Forney bound are examined. It is shown that, for any code length $n$, the complexity of constructing a linear code is bounded from above by an exponent, while that for a cascade code is similarly bound by a power-law function of $n$.

On Estimation of the Mean in a Multivariate Normal Population with Discontinuous a priori Density
E. K. Trishchenko
pp. 42–45

Abstract—The article investigates the behavior of the risk of the Bayesian estimate of a signal $\theta$ in additive Gaussian noise up to turns of second-order smallness inclusive. It is assumed that the a priori density of the parameter is $0$ outside of some compactum and is discontinuous on the boundary of this compactum.

Asymptotic Approach to the Investigation of Message Switching Networks of Linear Structure with a Large Number of Nodes
R. L. Dobrushin and V. V. Prelov
pp. 46–55

Abstract—The article examines message switching networks of linear structure with a large number of nodes at which messages arrive and are received. Under the assumption that the loading of the network is low, the existence of a limiting process of message arrival as $\mathscr N\to\infty$ and $t\to\infty$ is demonstrated ($\mathscr N$ being the number of a node in a linear network and $t$ the time).

Stochastic Model of Self-assembly of Segments with Breaks
M. L. Tai
pp. 56–64

Abstract—Relationships are obtained between the segment concentrations, on the one hand, and the intensity of bond formation and the initial concentrations, on the other, for a system of self-assembly of segments. Under the assumption that the intensities of bond formation and rupture for adjacent segments are independent of the bonds for the remaining elements, it is shown that the system of equations describing processes of self-assembly with breaks is integrable. For this case the author obtains the macroscopic characteristics introduced and representations of the segment concentrations of the self-assembly system in quadratures.

On Quasiinvariant Distributions on Uniform Arrays
M. G. Shnirman
pp. 64–68

Abstract—The article examines Markov chains of a special type with a continual set of states, which describe the behavior of multicomponent systems. A small stochastic noise is superimposed on the deterministic transformation that eliminates any finite perturbations of some initial state. It is shown that for such chains there exist probability distributions that are “similar” to the initial state and that change only slightly with time.

Long-Lived States of Finite Systems
A. N. Chetaev
pp. 68–74

Abstract—The concept of phase for finite systems described by Markov chains in discrete time is introduced.

On One Class of Grammars with Broken Context Conditions for Employing Productions
B. E. Kats
pp. 75–79

Abstract—It is shown that in the class of languages of type $EL+NL$ introduced by Lomkovskaya, the intersection of an arbitrary finite number of languages of the same type is representable in some sense. This implies that the problems of emptiness and finiteness of a language in the class of grammars of type $EL+NL$ and of nonclosedness of the class of languages of type $EL+NL$ relative to homomorphisms are not solvable.

On One Class of Queuing Systems
M. Ya. Kel'bert, A. Ya. Kreinin, and S. A. Troitskii
pp. 80–81

Abstract—The article considers a multiphase queuing system (QS) in which the message transmission time is maintained constant in all phases. It is shown that the mean waiting time in this QS is greater than in the classical system. A similar fact was established experimentally for a model of a linear message switching network.

The 75th Birthday of Aleksandr Aleksandrovich Kharkevich
pp. 82–83