PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Use of Defect-Correcting Codes to Restrict Access to a Broadcast Channel
A. V. Kuznetsov
pp. 217–222

Abstract—The article describes a way of employing additive defect-correcting codes to limit access to information in a broadcast channel with two sources and two recipients of information. It is demonstrated that there exist additive codes such that, when they are employed in the broadcast channel in question with large code lengths, the overall transmission rate is equal to unity, and the average indeterminacy of one of the recipients with respect to a message intended for the other is maximized.

Nonasymptotic Estimates for Efficiency of Code Jamming in a Wire-Tap Channel
V. I. Korzhik and V. A. Yakovlev
pp. 223–228

Abstract—In 1975, Wyner first introduced the concept of wire-tap channel, and proved a theorem regarding the permissible region of pairs (transmission rate/indeterminacy in the tap) such that the information content in the tap decreases to zero asymptotically over the code block length. In the present paper, we obtain bounds for the information content for finite block lengths. Problems of code optimization are considered.

Bound on Admissible Transmission Rates in a Broadcast Channel with Errors in Both Components
L. A. Bassalygo
pp. 228–236

Abstract—Bounds are obtained for the admissible transmission rates over a Blackwell channel with errors in both components.

List Concatenated Decoding
V. V. Zyablov and M. S. Pinsker
pp. 236–240

Abstract—The article considers decoding of ordinary concatenated codes such that the inner and outer codes are decoded onto lists, while the result of decoding is determined by inspection of the resultant list of concatenated-code words. It is shown that for transmission rates $R\le0.02$ there exist concatenated codes for which the Varshamov–Gilbert bound is realized with this decoding algorithm, and with a decoding complexity that increases not more rapidly than the exponent of the square root of the code length.

Analytic Bounds for Quasioptimal Block Code Reception Methods in the Large
E. E. Nemirovskii, G. V. Romanenko, and L. G. Mikhailovskaya
pp. 240–244

Abstract—The article investigates the so-called Chase's second algorithm, which has achieved some renown and is a quasioptimal version of reception “in the large” of block codes with a complexity proportional to $2^{d/2}$. A new lower bound for the noise stability of this method is derived; it is more exact for large $n$ than the one proposed by Chase. Computer calculations for this bound are compared with data of statistical experiments (the authors' own and experiments analogous to the numerical experiments of Baumert and McEliece).

Bounds for Error Probability for a Symmetrical Model in Designing Screening Experiments
A. G. Dyachkov
pp. 245–253

Abstract—The paper examines a generalization of the information-theoretic statements of the problem described in [1–7] that arises in designing screening experiments. The generalization involves the fact that, in analyzing the results of experiments, significant factors are recovered by the method of lift decoding [R.G. Gallager, Information Theory and Reliable Communication, Wiley, New York, 1968], with a lift of fixed length.

Generalized Concatenated Codes for Channels with Error Bursts and Independent Errors
V. A. Zinoviev
pp. 254–260

Abstract—The article proposes a somewhat more general approach to the description of the correcting capabilities of generalized concatenated codes for channels with complex error behavior (when error bursts may occur in the channel in addition to independent errors). The concatenated decoding algorithm for generalized concatenated codes is presented in simplified form.

To the Optimization of Shortened Hamming Codes
A. A. Davydov, L. N. Kaplan, Yu. B. Smerkis, and G. L. Tauglikh
pp. 261–267

Abstract—Optimization is treated as reduction of the number of words of weight $d$, where $d$ is the code distance. For $d=3$, the authors propose methods of synthesizing codes of arbitrary length with minimum number of words of weight $3$. For extended codes with $d=4$, asymptotically coincident upper (guaranteed attainable) and lower bounds are constructed for the minimum number of words of weight $4$. Classes of codes that attain the lower bound or are close to it are indicated.

On Predictions under Conditions of Uncertainty
A. S. Nemirovskii
pp. 268–275

Abstract—A method is created for predicting the trajectory of a difference equation with constant coefficients that is observed under noisy conditions; the method does not require a priori knowledge of the coefficients of the equation. It is shown that the method realizes optimal behavior (in terms of the nature of the dependence on the observation time) of the standard prediction error.

Method of Synthesizing Asymptotically Optimal Self-Correction Networks That Correct a Quasilinear Proportion of Errors
S. I. Ortyukov
pp. 276–286

Abstract—A method of synthesizing self-correcting networks of functional elements is proposed. Two approaches to the description of networks of unreliable functional elements are considered. In the first approach it is assumed that the networks consist of elements of two types, reliable and unreliable. The second approach considers networks that consist only of unreliable elements. It is shown that in both cases it is possible to achieve correction of a quasilinear proportion of errors with the customary asymptotic behavior of the Shannon function.

Team of Automata with Universal Passability
G. L. Kurdyumov
pp. 286–297

Abstract—Consider an integer-valued plane part of whose points are obstacles, while finite automata may be situated (and move about) at the remaining free points. The total number of automata on the plane is finite; each of these automata, at any free point, “knows” the direction toward point $(0,0)$ (to within $90^\circ$), and also the presence and state of other automata at the same point. It is shown that there exists a team of four automata such that, if the automata are initially situated at any point $(i_0,j_0)$ such that there exists a path from $(i_0,j_0)$ to $(0,0)$, all automata will arrive at $(0,0)$. No single automaton with this property exists.

INDEX
pp. 301–304

Additive Codes for Correction of Multiple Defects
Yu. D. Karyakin and V. V. Losev
pp. 113–115 (Russian issue)

Abstract—We describe a new class of additive nongroup codes for correction of multiple defects.

Equidistant Codes and Equidistant Permutation Arrays
L. G. Khachatrian
pp. 116–119 (Russian issue)

Abstract—Using equidistant codes and difference matrices, we present two ways of constructing equidistant permutation arrays.

On Some Properties of $Q$-Complexity of Finite Objects
E. Z. Dyment
pp. 119–123 (Russian issue)

Abstract—We introduce and examine the notion of a $Q$-complexity of a word $x$ (complexity of finding a word to which $x$ is related with respect to relation $Q$).