PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS

On the Twenty-Fourth Congress of the Communist Party of the Soviet Union
pp. 1–2

An Estimate of the Complexity of Constructing Binary Linear Cascade Codes
V. V. Zyablov
pp. 3–10

Abstract—The author considers the construction of binary linear cascade codes for which the ratio of the code distance to the code length tends to a positive quantity which depends on the transmission rate as the code length and transmission rate constant increase. The number of operations necessary to specify such a code, for arbitrary code length, is bounded from above by the square of the length of a code combination. A lower bound is found for the code distance of a cascade code.

Weight Spectrum of Binary Bose–Chaudhuri–Hoquinghem Codes
V. M. Sidel'nikov
pp. 11–17

Abstract—The author obtains, for certain constraints on the ensured code distance of a Bose–Chaudhuri–Hoquinghem code, asymptotic formulas for the number of points of specified weight.

Complexity of Circuit Implementation of Reed’s Algorithm and Decoding in an Automaton
Yu. L. Sagalovich
pp. 18–22

Abstract—The author obtains upper bounds for the number of functional elements in circuits which implement Reed’s decoding algorithm and threshold decoding of maximum-length codes. It is shown that decoders are inapplicable for error correction in an automaton memory unit when there are races between the internal elements.

Sequential Decoding in a Channel with Error Bursts
K. Sh. Zigangirov and V. V. Ovchinnikov
pp. 23–29

Abstract—The authors consider a binary channel with memory in which the noise may be represented by a recurrent renewal process. Sequential decoding procedures for this channel are proposed and studied.

Uniformly Packed Codes
N. V. Semakov, V. A. Zinoviev, and G. V. Zaitsev
pp. 30–39

Abstract—Perfect and a particular kind of quasi-perfect binary block codes (in particular, nonlinear Preparata codes) are combined into a class of uniformly packed codes, on the basis of certain considerations about the packing of the code vectors. The authors consider the invariant properties of these codes, the necessary conditions for their existence, and the relationship between the codes and tactical configurations. They give combinatorial relationships between the sets of code vectors of different weight and the resulting formulas for determining the spectrum of weights and distances in the code. It is shown that in a uniformly packed code with zero vector the set of vectors of any one weight always forms a tactical configuration whose parameters are completely defined by the code parameters.

An Information-Theoretic Approach to Statistical Decision Problems
P. A. Bakut
pp. 40–45

Abstract—The author discusses a scheme for using information-theoretic concepts in statistical decision problems. It is shown that the average risk of making decisions is related to the quantity of information contained in the observations. This yields estimates for the minimum average risk in decision making. Certain examples are considered.

Optimum Reception of Pulse Radio Signals with Secondary Frequency Modulation
M. S. Yarlykov
pp. 46–52

Abstract—With the theory of conditional Markov processes as a basis, the method of optimum nonlinear filtration in the Gaussian approximation is used to synthesize optimum pulse signal receivers of the PAM/FM, PWM/FM, and PTM/FM types. Expressions are obtained for the mean-square filtration errors and graphs of the errors are plotted. Noise stability is compared for pulse receivers with different primary and secondary modulation.

Approximation Possibilities of Minimum-Phase Networks
A. A. Lanne and N. I. Zhivitsa
pp. 53–58

Abstract—The article investigates the limiting approximation properties of the functions of minimum-phase networks and signals.

A Program which Constructs a Multistage Classification
A. V. Rashkinis
pp. 59–68

Abstract—In recognition problems in which learning takes place for a large number of classes it is frequently not possible to separate them in terms of stable features in one stage. The author proposes an algorithm which divides according to stable features in such cases (without recourse to probabilistic methods). The algorithm divides in several stages. Stability of the features is required only on the subset of classes which remains undivided at the preceding stage of the classification tree and which is to be divided in the given stage. Certain examples are given and experiments on comparing multistage and one-stage classifications are evaluated.

Formal Grammars and Constraints on Derivation
E. D. Stotskii
pp. 69–81

Abstract—Formal generative grammars in the sense of Chomsky are considered. A certain type of constraint on the method of derivation is investigated; this results in the concept of a generalized grammar. The most important results are surveyed.

A Strong Converse of Shannon’s Theorem for Memoryless Channels with Synchronization Errors
O. K. Kozlov
pp. 82–84

Abstract—The author formulates and proves a strong converse of Shannon’s theorem for channels with synchronization errors.

Relationship between Chromatic Number and Branch Connectivity in a Finite Graph
V. P. Polesskii
pp. 85–87

Abstract—A new upper bound is established for the chromatic number of an arbitrary finite graph; for a large number of graphs it is better than the Brooks bound.

One Queueing System with Nonstationary Incoming Flow
D. G. Polyak
pp. 88–90

Abstract—A formula is obtained for the generating function of the number of requests in a queueing system with an infinite number of lines. It is assumed that the requests come in groups of random size and that the moments of arrival of the groups form a nonstationary Poisson flow. The service time for the request has an arbitrary distribution.