PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Capacity of a Quantum Communications Channel
A. S. Holevo
pp. 247–253

Abstract—An example is constructed that shows that the additive property $C_{n+m}=C_n+C_m$ that is characteristic of the capacities in classical information theory need not obtain for a quantum communications channel. In view of this, the definition itself of capacity of a quantum communications channel is in need of refinement. By using the property of subadditiveness, $C_{n+m}\le C_n+C_m$, which is maintained in the quantum case, it is natural to define the capacity as $C=\lim\limits_{n\to\infty}C_n/n$. Generally speaking, $C>C_1$ in this case. An analog of the classical coding theorem obtains for $C$. Some bounds are obtained for the capacity $C$.

Sequential Decoding for Channels with Synchronization Errors
K. Sh. Zigangirov
pp. 254–257

Abstract—Sequential decoding in a channel with synchronization errors is considered. The basic decoding characteristics are obtained.

Error Probability Bounds for Two Models of Randomized Design of Screening Experiments
A. G. D'yachkov
pp. 258–269

Abstract—The article considers the statement of the problem that arises upon investigating Boolean and linear models of the design of screening experiments. From the standpoint of information theory, this problem is the familiar coding-theory problem of the error probability bounds for two special classes of block codes. Paper [A.G. D'yachkov, Probl. Peredachi Inf., 1979, vol. 15, no. 2, pp. 23–35] obtained upper and lower bounds for the ensemble-mean error probability for such codes for transmission over an arbitrary discrete memoryless channel and maximum-likelihood decoding. In the present paper, the expressions for the exponents of these bounds are investigated for some particular cases of memoryless channels.

Metric Functionals on a Unit $n$-Dimensional Cube
V. K. Leont'ev
pp. 269–275

Abstract—The article investigates one class of metric optimization problems whose formulation is related to coding theory, pattern recognition, and a number of other areas of applied mathematics. A number of results characterizing the behavior of the extrema of functionals of this type and the behavior of some gradient-descent-type optimization procedures are obtained.

Stochastic Models of Self-Assembly of Linear Chains
M. L. Tai
pp. 276–285

Abstract—The article investigates a stochastic model of self-assembly of linear chains, these being arbitrarily long sequences of pairwise linked elements, of which only n are different. Under the assumption that the elements can combine in arbitrary order, descriptions of the self-assembly process by concentrations of chains and links are introduced. It is shown that, under one condition on the intensity of formation and rupture of links between elements, the concentration dependencies of the chain can be found recursively in terms of the solutions of a system containing $n^2$ nonlinear differential equations. Examples are given.

On One Class of Star-Shaped Communication Networks with Packet Switching
M. Ya. Kel'bert and Yu. M. Sukhov
pp. 286–300

Abstract—A model of a star-shaped network consisting of a central unit and a large number $N$ of corresponding message sources is investigated. It is assumed that each source gives rise to a homogeneous Poisson message stream, whose lengths are mutually independent and exponentially distributed. At the moment it arises, each message is broken down into packets, which are then transmitted through the network as individual messages. The moment of termination of a message transmission is taken to be the moment that the addressee receives the last packet of the message. It is demonstrated that in the limit as $N\to\infty$ (and for sufficiently large $N$, the mean message delivery time is less than in an analogous network with message switching in which messages are not broken down into packets.

Ergodicity of a Slotted ALOHA System
B. S. Tsybakov and V. A. Mikhailov
pp. 301–312

Abstract—A slotted ALOHA system is one of the best-known methods of random access to a broadcast channel. The paper proposes a new mathematical model of this system, and obtains sufficient existence conditions for the steady-state mode as well as some of its parameters.

Open Network with Two Service Centers and Recursive Input Stream
V. A. Ivnitskii and Ya. L. Shraiberg
pp. 312–318

Abstract—The article considers an open two-center queueing network with a recursive input flow and exponential distribution of the servicing time at both centers. An algorithm is proposed for finding the nonstationary state probabilities of the network; characteristics are determined that are useful for evaluating the operation of the network in question as a model of an information and computing system.

Language Recognition Using Probabilistic Turing Machines in Real Time, and Automata with a Push-Down Store
R. V. Freivald
pp. 319–323

Abstract—For each of the two classes of machines, the following result is obtained: There exists a language that can be recognized with probability $1-\varepsilon$ for any $\varepsilon>0$, but which cannot be recognized deterministically.

Shifted Discrete Fourier Transforms
L. P. Yaroslavskii
pp. 324–327

Abstract—The author introduces the concept of shifted discrete Fourier transforms (SDFT) as a discrete representation of a continuous Fourier transform. It is shown that the SDFT is advantageous in computing the convolution, in signal interpolation, and in estimating signal spectra and correlation functions. The relationship between SDFT and earlier proposed modifications of the standard discrete Fourier transform is pointed out.

Optimal Processing of an Optical Signal Distorted by a Randomly Inhomogeneous Medium
A. B. Aleksandrov, P. A. Bakut, and V. A. Loginov
pp. 327–330

Abstract—In the limiting cases of a weak and strong signal, the likelihood ratio is obtained for the light field from a point source observed through a turbulent medium and distorted by level and phase fluctuations. The meaning of optimum processing in extracting information from this field is discussed.

INDEX
pp. 331–337