PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Asymptotics of the Epsilon-Entropy of Discrete Stationary Processes
K. Marton
pp. 91–102

Abstract—The aim of the article is to obtain upper and lower asymptotic bounds for ε-entropy of stationary sources and discrete time, with a finite number of states, and with a criterion of reproduction accuracy specified in terms of an additive loss function. In general the estimates obtained by us may be in asymptotic disagreement. They necessarily agree in the case of Markov sources. In §1 we define concepts needed in formulating the problems and we introduce some notation. In §2 we formulate the results; proofs of the results are contained in §3, §4, and §5.

Epsilon-Entropy of Continuous Time Random Processes in Discrete Phase Space
Yu. N. Lin'kov
pp. 103–111

Abstract—An asymptotic formula $$ H_\varepsilon(\xi)=M\nu\log\frac{M\nu}{2e\varepsilon}+H(\nu)+MH(\xi_{0\nu}\,|\,\nu) +Mh(\tau_{i\nu}\,|\,\nu,\varepsilon_{0\nu})+o(1) $$ is obtained for the $\varepsilon$-entropy $H_{\varepsilon}(\xi)$ of a random process $\xi$ with continuous time and discrete phase space. An analogous formula is obtained for the $\varepsilon$-entropy of a Poisson process.

Shannon’s Principle for Classes of Data Sources
S. Z. Stambler
pp. 112–122

Abstract—A quantization theorem and its inverse are proved for source classes, both with discrete and continuous time, which satisfy the matching and complete regularity conditions.

Optimum Linear Transmission through a Memoryless Gaussian Channel with Full Feedback
A. G. D'yachkov and M. S. Pinsker
pp. 123–129

Abstract—Described is a linear method of transmission of discrete messages through a memoryless, stationary Gaussian channel with full feedback under the assumption that the input signal energy is limited. It is shown that for all transmission rates less than the channel capacity, the exponent of the probability of error (reliability) coincides with exponent of the dense-packing limit for both discrete and continuous times.

Efficiency of a Discrimination Algorithm for Signals with Unknown Parameters
V. G. Repin and G. P. Tartakovskii
pp. 130–138

Abstract—Probabilities of correct decisions are found for an algorithm for discrimination of signals with unknown parameters which are observed in mixture with Gaussian noise. The loss in efficiency owing to ignorance of the parameters is estimated.

Continuous Procedures of Stochastic Approximation
M. B. Nevel'son and R. Z. Khas'minskii
pp. 139–148

Abstract—It was shown in [R.Z. Khas'minskii, Stability of Systems of Differential Equations with Random Disturbances of Their Parameters, Nauka, Moscow, 1969] that the continuous variant of the Robbins–Monro stochastic approximation procedure with “white noise” inputs can be considered from the point of view of stability of the solution of a system of ordinary differential equations with damped random inputs. In the present work these as well as other procedures of stochastic approximation are studied in the case of continuous time. To this end the stability theorem in the case of damped random inputs proved in [Khas'minskii] is somewhat extended. Similarly as in [Khas'minskii], the conditions are given for convergence of the procedures under consideration in terms of the existence of the corresponding stochastic Lyapunov functions. The conditions for convergence of the stochastic-approximation procedures were proved in [J.R. Blum, Ann. Math. Stat., 1954, vol. 25, no. 2; T.A. Sakrison, Ann. Math. Stat., 1964, vol. 35, no. 2; T. Morozan, Stabilitiea Sistemelor Parametri Aleatori, Editura Acad. Rep. Socialiste România, Bucharest, 1969; E.M. Braverman and L.I. Rozonoer, Avt. Telemekh., 1969, no. 3, pp. 57–77, 87–103] in a similar manner.

Markov Processes with a Large Number of Locally Interacting Components: Existence of a Limit Process and Its Ergodicity
R. L. Dobrushin
pp. 149–164

Abstract—Markov processes with continuous time are considered. Elements of the phase space of these processes constitute a collection of a large number of components, each of which assumes a discrete series of values. It is assumed that these components are compared with points of a discrete grid in space and that the statistical relationships of individual component variations are determined by the states of the neighboring components. Such processes appear in various cybernetic problems. Their investigation is carried out with the aid of a transition to a limiting case, when the number of components is infinite.

A Lower Boundary for the Reliability of Information Networks
V. P. Polesskii
pp. 165–171

Abstract—The investigated network is a random graph for which the article considers the lower evaluation of the probability of the connectedness, based on the use of the maximal system of frameworks of the given graph in pairs not having common edges.

Rate of Modeling of Computing Media on a Grid with a Reduction of Dimensionality
A. V. Koganov
pp. 172–179

Abstract—This article considers computing media on a grid having elements with a limited number of states and a limited neighborhood for the sorting of information. Consideration is given to the possibility of modeling such media by media of the same form but having lesser dimensionality. It is shown that with a reduction of dimensionality from $n$ to $m\le n$ it is possible to provide an information processing slowdown $c\cdot t^{[n/m]}$ and that for each $n$ there is a medium of dimensionality $n$ which cannot be modeled more rapidly than with a slowdown $ct^{n/m}$ ($c>0$, $t$ is time).

A Bulk Service System with Service Rate Dependent on the Number of Calls in the System and with Periodic Channel Disconnection
I. N. Kovalenko
pp. 180–184

Abstract—We investigate a bulk service system with losses, in which groups of channels are periodically disconnected. The interrupted service of the calls is concluded after the channel is connected. The service rate for the calls depends on the number of calls in the system. The loss rates are calculated for the cases where the losses come from system overload and from latent refusals of the system to transmit information.

Theorem on Coverage
L. M. Libkind^†
pp. 185–187

Abstract—Evaluations are found for the least size of $\alpha$-nets on a unit sphere in $N$-dimensional Euclidean space. The first terms of asymptotic (for $N\to\infty$) decompositions of the logarithms of these evaluations coincide.

Sequential Transmission from a Source Having a Variable Rate
K. Sh. Zigangirov
pp. 188–191

Abstract—The transmission of an information sequence in which the symbols enter the coder at random time intervals is examined.