PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Volume of Additive Matched Error- and Defect-Correcting Codes
T. Kasami, S. Yamamura, and A. V. Kuznetsov
pp. 79–84

Abstract—Upper and lower bounds are obtained for the volume of additive matched error- and defect-correcting codes.

Lower Bound for Rate of Optimum Error- and Defect-Correcting Code
B. S. Tsybakov
pp. 85–96

Abstract—A new lower bound is obtained for the minimax transmission rate in channels with errors and defects. This bound is better than the available ones.

Capacity of Noiseless Broadcast Channel
M. S. Pinsker
pp. 97–102

Abstract—The capacity region for an arbitrary noiseless broadcast channel with $l$ output is determined.

On Exact Block $\varepsilon$-Approximation of Equiprobable Messages
V. N. Koshelev
pp. 102–105

Abstract—It is shown that for sources of equiprobable discrete symbols and a symmetrical error function there exist block codes in which exact $\varepsilon$-approximation of each message is attained. With increasing block length $n$, the rate of these codes tends to the $\varepsilon$-entropy at a rate $n^{-1}\ln n$, i.e., at the same rate as in the customary estimation of $\varepsilon$-error on average with respect to all messages. An estimate is obtained for the block length beginning with which exact $\varepsilon$-approximation is attained.

Multistage Universal Coding in Discrete Channels with Feedback
L. M. Fink and V. I. Korzhik
pp. 105–109

Abstract—A multistage stochastic encoding and decoding procedure in systems with feedback is given; it is suitable for arbitrary discrete ergodic channels. The decoding algorithm is maximally simple, since it employs only error detection at a given stage. It is shown that, in any discrete ergodic channel with noiseless feedback, this procedure (without adaptation to the channel state) ensures that the error probability decreases exponentially for a constant mean transmission rate.

Decoding of Nonlinear Generalized Concatenated Codes
V. A. Zinov'ev and V. V. Zyablov
pp. 110–114

Abstract—The authors propose a multistage decoding algorithm for generalized concatenated codes that can be employed for both linear and nonlinear concatenated codes. On the basis of decoding with respect to the code distance of external and internal codes separately, the algorithm makes possible decoding with respect to the code distance of the concatenated code as a whole.

Reconstruction of a Finite-Spectrum Field on the Basis of Samples of Filtering-System Signals
S. P. Efimov
pp. 114–119

Abstract—The article investigate the possibility of reconstructing a field (function of several variables) on the basis of of samples of signals at the outputs of a fixed number of independent filters. Samples are taken at points forming a regular spatial lattice. Constraints are found on the dimensions and shape of the finiteness region of the spectrum, such that the field can be represented as an analog of the Kotel'nikov–Shannon expansion.

Estimation of Spectral Functions
B. Ya. Levit and A. M. Samarov
pp. 120–124

Abstract—Lower bounds are obtained in the problem of estimating the spectral function of a stationary Gaussian sequence. As a corollary, a result to the effect that known spectral estimates are asymptotically unimprovable is formulated.

Antagonistic Games of Automata Made Up of Asymptotically Optimal Sequences
E. T. Gurvich
pp. 124–132

Abstract—A graph description of the game process is used to investigate antagonistic games of two automata. This approach makes possible a new formulation of available results and a treatment of cases not previously covered. The results can be used to make a comparison of the efficiency of the behavior of different automata in antagonistic games.

Concatenated Codes of Automaton States
Yu. L. Sagalovich
pp. 132–138

Abstract—It is shown that Reed–Solomon states of suitable dimension are automaton state codes; i.e., they simultaneously possess both noise-stable and antiracing properties. If they are employed as external codes in constructing concatenated codes, and when the internal codes are specially chosen, we also obtain automaton state codes for which the transmission rate remains bounded from below with increasing length and constant correction capacity. New specific automaton state codes are set up. The results are strengthened upon changing over to assignments of input states.

On Dominational Ambiguity of Context-Free Languages
L. S. Modina
pp. 138–147

Abstract—The article considers so-called generalized tree domination grammars that assign subordination trees to the generated strings. It is shown that the class of languages generated by unambiguous generalized tree domination grammars (i.e., grammars that associate a unique subordination tree with each generated string), are strictly intermediate between the classes of unambiguous CF-languages and all CF-languages.

Optimal Discrete Representation of Nonstationary Random Processes
V. A. Medvedev, B. I. Oleinikov, B. M. Stepanov, and V. N. Filinov
pp. 148–152

Abstract—The article examines the issue of exact discrete representation of actual signals for which an adequate mathematical model is provided by nonstationary stochastic processes with a nonfinite spectrum. Expressions are obtained for the composition functions of the optimal expansion.

On a Two-Rate Servicing Problem
Yu. I. Ryzhikov
pp. 152–157

Abstract—A method is proposed for recursive calculation of the stationary distribution of state probabilities of an $M|G|1|R$ system in which the servicing-time distribution $F(\tau)$ is replaced by $\Phi(\tau)$ when $m\ge 1$ requests accumulate, but servicing initiated prior to the threshold transition point is completed with the earlier distribution.