PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Number of Correctable Errors for Transmission over a Binary Symmetrical Channel with Feedback
K. Sh. Zingangirov
pp. 85–97

Abstract—It is shown that, in a binary symmetrical channel with complete feedback, the Hamming bound is the asymptotically optimum bound for the number of correctable errors at transmission rates that exceed some rate $R_0$.

Fisher Information Contained in a Finite-Dimensional Linear Space, and a Correctly Posed Version of the Method of Moments
A. M. Kagan
pp. 98–115

Abstract—The paper offers a construction of a linear Fisher information theory when the initial entity is not a family of distributions on a space of observations, but rather a family of scalar products on a finite-dimensional (abstract) linear space. It is shown that all the basic properties if Fisher information (monotonicity, invariance under contraction onto a sufficient subspace, additivity in changing over to the tensor product of spaces, and the Rao–Cramer inequality) are preserved in the linear theory as well. A linear analog of the maximum-likelihood method is created; a particular case of this analog is a correctly posed version of the method of moments that makes it possible to utilize an arbitrarily large number of general and sample moments for parameter estimation (unlike the classical method of moments).

On Hypothesis Discrimination with Loss Functions That Depend on Decisions
A. L. Bol'shev and R. S. Lom
pp. 116–118

Abstract—The authors consider the problem of hypothesis discrimination with concave loss functions of an error matrix. It is shown that decision functions in this case minimize the average risk for some constant loss matrix. A relationship that defines the matrices is given. The results are in a problem involving minimization of average information loss for a specified a priori distribution.

Stable Detection of Signal That Is Not Precisely Known
V. P. Kuznetsov
pp. 119–129

Abstract—The paper considers the testing of a simple hypothesis with a complex alternative. It is assumed that the alternative is specified as a class of densities within fixed boundaries; the minimax Neyman–Pearson rule is determined. This rule is applied to the problem of detecting a signal with unknown parameters, where it corresponds to replacement of the unknown parameters in the likelihood ratio by the maximum-likelihood estimate of the minimum-likelihood statistic. Examples are considered.

Intersymbol Interference and Transmission Reliability in Multiple-PM Systems
K. L. Chaiko
pp. 130–135

Abstract—The article presents a procedure for computing transmission reliability in multiple-PM systems that operate with intersymbol interference and fluctuation noise.

Two Results Regarding Noncomputability for Univariate Cellular Automata
A. L. Toom and L. G. Mityushin
pp. 135–141

Abstract—Operator $P$ with local interaction acts on an ensemble of islands, i.e., finite subsets of an integer-valued straight line. Two assertions regarding algorithmic noncomputability for such operators are proved.

Covering a Finite Graph by a Minimum Number of of Forests
V. P. Polesskii
pp. 141–146

Abstract—The author proposes an algorithm that provides minimum covering of a finite graph by forests.

On Certain Calculi That Generate Subordinate Trees
L. S. Modina
pp. 147–155

Abstract—The article introduces the concept of generalized domination grammar, and domination system. The scope of these concepts is investigated, as well as their relation to the familiar notions of dependency grammar [D. G. Hays, in Proc. Nat. Symp. Machine Translation, 1961, Englewood Cliffs, pp. 258–266] and domination grammar [M. I. Beletskii, Kibernetika, 1967, no. 4, pp. 90–97; A. V. Gladkii, Formal Grammars and Languages (in Russian), Nauka, Moscow, 1973].

Superstructures of Generative Grammars and the Property of Semilinearity
B. E. Katz and E. D. Stotskii
pp. 156–158

Abstract—The authors give a property that is necessary for a language to be generated by some grammar with a context-free superstructure (associate language). Grammars that generate semilinear languages are characterized in terms of superstructure.

Nonuniform Distribution of Entropy of Processes with a Countable Set of States
B. S. Pitskel'
pp. 159–164

Abstract—In an ergodic stationary (in the narrow sense) process with a finite alphabet, the modulus of the logarithm of the probability of a word divided by its length tends with probability unity to the same constant (specifically, to the entropy) as the length increases. This fact is valid if the alphabet is infinite but has finite entropy. The article constructs a stationary (in the narrow sense) ergodic process with an alphabet whose entropy is infinite and for which the sequence of random quantities made up of the moduli of the logarithms of the probabilities of words of fixed length divided by this length does not have a limiting distribution as the word length tends to infinity.