PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii
On Message Transmission over a Discrete
Channel with Noiseless Feedback
B. D. Kudryashov
AbstractLower 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
AbstractAn 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
AbstractThe 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 g is bounded in the mean square by some constant, the capacity C is asymptotically proportional to T1/(2g + 1) if the transmission time T is large.
I. M. Boyarinov and G. A. Kabatyanskii
AbstractThe 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
AbstractThe 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
AbstractThe article investigates the behavior of the risk of the Bayesian estimate of a signal q 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
AbstractThe 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 N ® ¥ and t ® ¥ is demonstrated (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
AbstractRelationships 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
M. G. Shnirman
AbstractThe 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
AbstractThe 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
AbstractIt 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
AbstractThe 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