PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

As We Approach the Sixtieth Anniversary of the October Revolution
pp. 165–166

Problems of Complexity in the Theory of Correcting Codes
L. A. Bassalygo, V. V. Zyablov, and M. S. Pinsker
pp. 166–175

Abstract—An analysis is made of the complexity of solving such coding-theory problems as the creation of codes with good correcting properties and the encoding and decoding of such codes. The best available bounds on the complexity of solving these problems are given.

On Existence of Good Cyclic Almost Linear Codes over Nonprime Fields
G. A. Kabatyanskii
pp. 175–177

Abstract—Kasami’s recent result regarding the existence of good systematic quasicyclic codes with rates $1/l$ and $(l-1)/l$ is generalized to the case of rates $v/l$, $1\le v\le l-1$. As a corollary, it is shown that good group cyclic codes over nonprime fields exist.

Remark on Uniformly Packed Codes
L. A. Bassalygo and V. A. Zinoviev
pp. 178–180

Abstract—Necessary and sufficient conditions are obtained for a code to be uniformly packed, as well as necessary and sufficient conditions for this property to be preserved when binary codes are expanded. For expanded binary codes, the familiar Delsarte bound for the order of the tactical configuration formed by code vectors of fixed weight is improved by $1$.

On One Informational Lower Bound
M. B. Nevel'son
pp. 181–185

Abstract—An asymptotic locally minimax lower bound is computed for the risk of an arbitrary estimate of a functional of an unknown distribution, under the assumption that this functional is the solution of some system of equations.

On Problems of Estimation with Limited Resources
V. V. Zyablov, A. M. Samarov, and R. Z. Khas'minskii
pp. 185–194

Abstract—Some lower bounds on the mean-square estimation quality are given for independent observations with constraints on the number of operations $m$ the the observer (the “statistician”) can use to extract information from observations and on the number of possible values of the statistic $L$. These bounds depend on the combined action of two factors: the finite nature of the number of observations and the necessity of considering a quantized sample. It is shown that, under the given conditions, these bounds are asymptotically attainable.

Multiple Hypothesis Discrimination Using Finite-State Automata
K. Sh. Zigangirov
pp. 194–202

Abstract—A multiple-alternative generalization of the familiar two-armed bandit problem is considered. A finite-state automaton that is asymptotically optimal in terms of complexity and that can solve the hypothesis-discrimination problem is created.

Upper Bound on the Redundancy of Self-correcting Arrangements of Unreliable Functional Elements
R. L. Dobrushin and S. I. Ortyukov
pp. 203–218

Abstract—The redundancy of self-correcting arrangements of functional elements that realize Boolean vector-valued functions is investigated. All functional elements of which the arrangements are composed are assumed to be unreliable; specifically, all elements make errors with probability ε independently of one another and of the signals fed to them. The error probability for a particular output can be made close to ε. Upper bounds are obtained for the redundancy of such arrangements.

Consistent Systems of Conditional Distributions of a Random Field
O. K. Kozlov
pp. 218–228

Abstract—To describe uniformly almost Markovian discrete random fields for which not all the finite-dimensional probabilities are strictly positive, the author introduces the notion of a consistent system of conditional distributions that are not defined for all conditions, generalizing the earlier notion of system of conditional distributions. The possibility of specifying such consistent systems of conditional distributions that are not everywhere defined by using the Gibbs potential is investigated.

Proper Bernstein Populations
Yu. I. Lyubich
pp. 228–235

Abstract—An effective algebraic criterion is obtained for a quadratic evolutionary operator to belong to the class of solutions of the Bernstein problem [Yu.I. Lyubich, Usp. Mat. Nauk, 26, No. 5, 51–116 (1971)] that admit a genetic interpretation [Yu.I. Lyubich, Genetika, 9, No. 10, 139–144 (1973)].

Two Problems Associated with Abelian Generalizations of Reed–Muller Codes
I. I. Grushko
pp. 236–240

Abstract—It is shown that for semisimple Reed–Muller codes it is possible to choose the basis of the code in such a way that the number of orthogonalization steps is reduced by $1$. A class of majority-decodable linear codes embedded in semisimple Reed–Muller codes is set up.

Capacity of One Broadcast Channel
S. I. Gel'fand
pp. 240–242

Abstract—The capacity region of one discrete memoryless broadcast channel is determined.

K. Sh. Zigangirov. Sequential Decoding Procedures
Reviewed by E. M. Gabidulin
pp. 243–244

Fourth All-Union Workshop on Algebraic Coding Theory and Its Applications
p. 245