PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii
On the Number of Correctable Errors for
Transmission over a Binary Symmetrical Channel with Feedback
K. Sh. Zingangirov
AbstractIt 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
A. M. Kagan
AbstractThe 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 RaoCramer 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
AbstractThe 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
AbstractThe 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 NeymanPearson 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
AbstractThe 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
AbstractOperator $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
AbstractThe author proposes an algorithm that provides minimum covering of a finite graph by forests.
On Certain Calculi That Generate Subordinate Trees
L. S. Modina
AbstractThe 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. 258266] and domination grammar [M. I. Beletskii, Kibernetika, 1967, no. 4, pp. 9097; 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
AbstractThe 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'
AbstractIn 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.