PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Decoding Complexity for Linear Codes
G. S. Evseev
pp. 1–6

Abstract—The article describes a decoding algorithm for linear binary codes; it is shown that for “almost all” codes the exponent of the complexity of this algorithm is less than the available exponent of the complexity for the case of maximum-likelihood decoding, while the error probability does not exceed twice the error probability for the case of maximum-likelihood decoding.

Random-Coding Bounds for Some Broadcast Channels
G. Sh. Poltyrev
pp. 6–16

Abstract—The author establishes upper bounds for random coding for the decoding error probabilities in a discreet memoryless broadcast channel with two receivers, for the case of transmission of common and only private information. The bounds are more precise than those given in [B.D. Kudryashov and G.Sh. Poltyrev, Probl. Peredachi Inf., 1979, vol. 15, no. 3, pp. 3–17].

Combined Decoding Methods for Linear Codes with Unequal Protection of Information Symbols
I. M. Boyarinov
pp. 17–25

Abstract—The article considers methods of decoding linear codes with unequal protection of information symbols (UP codes), which are compounds, products, and direct sums of products of codes. Majority-decoding algorithms and combined majority-decoding and arbitrary-decoding algorithms are constructed for the classes of UP codes under consideration.

Analysis of the Efficiency of Some Controlled Search Procedures
N. A. Ivanchuk
pp. 25–33

Abstract—The author considers four signal-search procedures in a multiline system, namely uniform uncontrolled search and controlled search employing the criteria of maximum a posteriori probability, maximum information increase, and minimum current risk. Estimates are obtained for the basic probability characteristics of these procedures, and a comparative analysis of them is made.

Investigation of Monotonicity of Various Criteria of Informativeness
L. G. Malinovskii
pp. 33–39

Abstract—In classification problems, an important property is the monotonicity of the criteria employed, relative to the error probability, in the process of constructively choosing informative measurements and subspaces. This property is investigated in the present paper. It is shown that a widely employed criterion, namely the Kullback divergence, is markedly inferior to other criteria in this respect.

Class of Fast Fourier Transform Algorithms for a Real Sequence
G. V. Zaitsev and N. E. Nagulin
pp. 40–49

Abstract—The authors propose a class of fast Fourier transform algorithms for a real sequence, whose structures display complete succession in relation to the structures of standard algorithms for a complex sequence. The use of these algorithms makes it possible to halve the required amount of main and readonly memory, and to more than halve the amount of computation as compared to algorithms for a complex sequence.

Bounds for Packet Transmission Rate in a Random-Multiple-Access System
B. S. Tsybakov, V. A. Mikhailov, and N. B. Likhanov
pp. 50–68

Abstract—The article considers a system of random multiple access (RMA) of packets to a broadcast channel. It is assumed that a conflict is the superposition of transmission of $n$ or more packets. Most earlier studies have considered the case $n=2$. Upper and lower bounds are found for the capacity of a system with a large number of stations in relation to $n$, for Poisson incoming packet traffic.

Properties of Probability Characteristics of a Communications Network with Repeat Calls
S. N. Stepanov
pp. 69–76

Abstract—Using the example of a communications network consisting of a finite number of points with Poisson streams of primary and repeat calls and a general scheme of subscriber behavior after receiving a refusal for service, the author proposes a method of expanding the principal probability characteristics of the model in powers of the intensity of arrival of primary calls, as this quantity tends to infinity.

Stable Single-Locus Polyallele Populations
L. A. Kun and L. N. Lupichev
pp. 77–85

Abstract—The paper deals with mathematical evolutionary genetics and is closely allied to [Yu.I. Lyubich, G.D. Maistrovskii, and Yu.G. Ol'khovskii, Dokl. Akad. Nauk SSSR, 1976, vol. 226, no. 1, pp. 58–60, Probl. Peredachi Inf., 1980, vol. 16, no. 1, pp. 93–104; L.A. Kun and Yu.I. Lyubich, Dokl. Akad. Nauk SSSR, 1979, vol. 249, no. 5, pp. 1052–1054, Probl. Peredachi Inf., 1980, vol. 16, no. 2, pp. 92–102, Kibernetika, 1980, no. 2, pp. 137–138]. It considers $\Omega$-stable infinite single-locus polyallele populations and polylocus polyallele populations with small crossing-over, under the action of stationary selection.

On Computability of the Parameter in a Bernoulli Scheme
V. V. V'yugin
pp. 100–105 (Russian issue)

Abstract—We study the dependence of a priori (universal semicomputable) measure of the set of all $\theta$-Bernoullian sequences on the value of the parameter $\theta$. We prove that for a fixed $\theta$, the a priori measure of the set of all $\theta$-Bernoullian sequences equals $0$ (which is equivalent to unsolvability of the problem on generating a $\theta$-Bernoullian sequence with the use of a probabilistic machine) if and only if the parameter $\theta$ is noncomputable; however, this measure of the set of all $\theta$-Bernoullian sequences will be greater than $0$ if $\theta$ runs over a set of random (with respect to some computable measure) sequences.

Equivalence of Hierarchies of Index Grammars and Macrogrammars
A. N. Maslov
pp. 106–111 (Russian issue)

Abstract—We prove the equivalence of the hierarchy of finite-level index grammars and hierarchy of macrogrammars.