PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Capacity and Coding for Degraded Broadcast Channels
R. G. Gallager
pp. 185–193

Abstract—The capacity region of discrete memoryless degraded broadcast channels with two receivers is defined. A converse to the coding theorem is then proved, which shows that small error probability is not possible for transmission rates outside of this capacity region. An earlier coding theorem of Bergmans [IEEE Trans. Inf. Theory, 1973, vol. 2, no. 19, pp. 197–207] showing that arbitrarily small error probability is achievable within the capacity region is strengthened by obtaining bounds on error probability that are exponential in block length and analogous to the results for single receiver channels.

Asymptotic Representation of the Capacity of a Continuous Channel with Small Nonadditive Noise
V. A. Gorbunov
pp. 194–199

Abstract—An information channel described by a conditional probability density function $g_\varepsilon(y\,|\,x)$ is investigated, where $y$ is the value of the channel output signal, $x$ is the input signal value, and $\varepsilon$ is a parameter that suitably characterizes the noise power. Asymptotic expressions are derived for the capacity of the given channel as $\varepsilon$ tends to zero, with various constraints on the conditional density and on the input signal. The asymptotically optimal distribution functions for the input signal are also determined.

Estimate of the Probability of Exceeding the Delay Time in a Feedback System with Recall
V. Ya. Turin
pp. 200–205

Abstract—A Markov chain model of an error source is used to calculate the erasure probability for a message in a feedback system with a recall facility when an upper limit is placed on the delay time of the message.

Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory
L. A. Levin
pp. 206–210

Abstract—A new alternative definition is given for the algorithmic quantity of information defined by Kolmogorov. The nongrowth of this quantity is proved for random and certain other processes, The established properties are used to investigate problems related to the approach of [A.N. Kolmogorov, Probl. Peredachi Inf., 1965, vol. 1, no. 1, pp. 3–7; P. Martin-Löf, Inf. Control, 1966, vol. 9, no. 6, pp. 602–619] with bearing on the foundation of probability theory.

Construction of a Class of Linear Binary Codes Achieving the Varshamov–Griesmer Bound
B. I. Belov, V. N. Logachev, and V. P. Sandimirov
pp. 211–217

Abstract—A class of optimal (in the sense of achieving the Varshamov–Griesmer bound) linear binary codes is described; it is strictly included in the class of Solomon–Stiffler codes. A subclass of the given class of codes is constructively defined for the case of relatively small code distances.

Coding of Generalized Concatenated Codes
E. L. Blokh and V. V. Zyablov
pp. 218–222

Abstract—A concatenated coding scheme that defines generalized concatenated codes is discussed. The code distance of the new codes is estimated. It is shown that most of the known concatenated coding schemes as well as error-locating coding schemes are special cases of the scheme described here.

An Interval Estimation Problem for Controlled Observations
M. V. Burnashev and K. Sh. Zigangirov
pp. 223–231

Abstract—The problem of estimating the confidence interval of an unknown parameter $\theta\in[0,1]$ from $n$ observations is investigated. The conditional probabilities of measurement results depend on which side of the measurement point the measured parameter $\theta$ is situated. A measurement technique is devised for which the reliability function satisfies the “random coding bound.”

Extension of the Kač–Murdock–Szegö Theorem to $N$-Dimensional Space
B. Kh. Barladyan
pp. 232–238

Abstract—An $N$-dimensional analog is obtained for the theorem of Kač, Murdock, and Szegö on the asymptotic distribution of the eigenvalues of an integral operator for arbitrary domains $S_\alpha$ tending to infinity in the Van Hove sense as $\alpha\to\infty$.

Nonergodic Multidimensional System of Automata
A. L. Toom
pp. 239–246

Abstract—Identical stochastic automata having a finite number of states are positioned at all points of a $d$-dimensional integer-valued space. At any instant of discrete time each automaton can go to any one of its states with never-vanishing probabilities depending on its own states and those of a finite number of its “neighbors” at the preceding instant. A system of this type is synthesized which is capable of “remembering” its initial state for an infinitely long time when the system commences operation in one of $n$ distinct states of the type “all automata are in state $k$,” where $1\le k\le n$.

Simulation of Parallel Automata in Growing Iterative Nets
Ya. Ya. Kalninsh
pp. 247–257

Abstract—The article describes a two-dimensional growing iterative net suitable for the simulation of a universal parallel automaton. The net has $L(n)\asymp n\cdot\log_2n$ active elements and a simulation dilation $T(n)\asymp\sqrt{n\log_2n}$, where $n$ is the number of elements of the parallel automaton in the simulated operating cycle.

Gibbs Description of a System of Random Variables
O. K. Kozlov
pp. 258–265

Abstract—Necessary and sufficient conditions are given for a joint-distributed countable set of random variables, all of whose conditional distribution functions are absolutely continuous with respect to a certain finite measure, to be representable in Gibbs form with a potential whose strong norm is pointwise finite.

Analysis of a Switching System Subject to Malfunction and Repair of Control Units
V. A. Ivnitskii, A. B. Kasumov, and M. N. Ibragimov
pp. 266–272

Abstract—A switching circuit with two control units (CU I and CU II), each acting as standby for the other, is analyzed; the standby mode is active. The switching circuit services calls arriving from $N$ transmitters according to a definite distribution function. The task of CU I and CU II is to set up the connections by which the subsequent “conversation” is to take place (i.e., servicing of calls). If one CU malfunctions in the course of operation, the remainder of the task is executed by the other CU. The failure-free operating times and repair times of the CU have exponential distribution functions. The probabilistic characteristics (distribution of the number of calls in the system and number of operative CU) of the given system are analyzed by the embedded Markov chain model. The transition and end-state probabilities of the chain are determined. The principal term is found in the expansion of the expectation value of the increase in the switching time relative to the case in which both control units are 100% reliable.

Proof of a Conjecture of I. Vaida
N. P. Salikhov
pp. 273–274

Abstract—The author proves Vaida’s sharp lower bound for the minimal mean error probability for the testing of a finite number of statistical hypotheses.

Sequency of Walsh Functions and Their Generalizations
S. L. Blyumin and A. M. Shmyrin
pp. 275–276

Abstract—The sequency concept, slightly modified in application to Walsh functions from Harmuth’s original definition, is generalized to the case of functions forming an arbitrary periodic Vilenkin-multiplicative orthonormal system.

Correction of Arbitrary Noise by Irreducible Codes
V. D. Goppa
pp. 277–278

Abstract—A lower bound is obtained for the power of irreducible codes correcting arbitrary noise.