PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

FROM THE EDITORS

The vital role of information as the organizing principle of all purposeful activity is now widely understood and the new branch of the exact sciences that deals with the problems of transmitting, storing, processing, and distributing information has aroused universal interest. In recent years papers devoted to these problems have been published in ever-increasing numbers in a variety of regular and irregular periodicals.

As far as possible this research should be concentrated between the covers of specialized periodicals, one of which is the new scientific journal “Problems of Information Transmission.”

This quarterly is intended to replace the earlier (1958–1964) irregular journal of the same name published by the Institute for Problems of Information Transmission of the Academy of Sciences of the USSR. The character and subject matter of the new journal are naturally influenced by the circumstances of its origin.

“Problems of Information Transmission” is a theoretical journal publishing original and review articles on the following topics: information theory, coding theory, signal transmission theory, random interferences, signal detection, the theory and control of information networks, pattern recognition, learning, and the problems of information transmission in living organisms.

Three Approaches to the Quantitative Definition of Information
A. N. Kolmogorov
pp. 1–7

Abstract—There are two common approaches to the quantitative definition of  “information”: combinatorial and probabilistic. The author briefly describes the major features of these approaches and introduces a new algorithmic approach that uses the theory of recursive functions.

Binary Codes Capable of Correcting Spurious Insertions and Deletions of Ones
V. I. Levenshtein
pp. 8–17

Abstract—The author investigates binary codes of length $n$ capable of correcting spurious insertions and omissions of ones by means of the same techniques as used in [V.I. Levenshtein, Dokl. Akad. Nauk SSSR, 1965, vol. 163, no. 4, pp. 845–848] to investigate binary codes capable of correcting spurious insertions and deletions of arbitrary symbols ($0$ or $1$). A method is given for constructing an asymptotically optimal ($n\to\infty$) code capable of correcting one spurious insertion or deletion of one, along with a method for constructing codes with asymptotically minimal redundancy capable of correcting $s$ or fewer insertions or deletions of ones. Moreover, a method is given for optimal selection of a separating word that makes it possible to decode automatically the output of a channel in which each segment of length $n$ has not more than $s$ spurious deletions or insertions of ones.

The Capacity of a Memoryless Gaussian Vector Channel
B. S. Tsybakov
pp. 18–29

Abstract—The author considers a so-called vector channel with several outputs at the receiving end and several inputs at the transmitting end. A mathematical model for a time-discrete vector channel is described with allowance for interference, filtering of input signals, and the relation between the noise values at the various outputs. The capacity of a memoryless Gaussian vector channel is found for very general average power constraints on the input signals. Conditions under which the capacity of such a channel is infinitely large are given.

Realization of a Boolean Function of $n$ Variables by a Network of $n$-Input Threshold Devices
E. A. Butakov
pp. 30–37

Abstract—The author presents a method for synthesizing a multicomponent circuit composed of threshold devices that realizes an arbitrary Boolean function of $n$ variables. The method is semi-intuitive and makes use of the special properties of visual perception of information.

The Reaction of a Single-Cycle Discrete Automaton to an Input Change
V. N. Roginskii
pp. 38–41

Abstract—The author considers the transient behavior of single-cycle discrete automata (relay devices) with delays. He introduces the notions of transfer functions for such automata and the reaction of outputs to changes in input signals. A method is given for finding the reaction to both single input changes and given sequences of changes. A special six-valued calculus is developed for computating these reactions.

Certain Properties of Symmetric Functions in Three-Valued Logic
B. L. Ovsievich
pp. 42–47

Abstract—The author discusses the properties of symmetric functions in three-valued logic and the class of so-called “layered” functions. Methods are proposed for detecting whether functions are symmetric and layered and for synthesizing circuits realizing symmetric and layered functions in a majority basis.

The Behavior of Automata in Periodic Random Media and the Problem of Synchronization in the Presence of Noise
V. I. Varshavskii, M. V. Meleshina, and M. L. Tsetlin
pp. 48–52

Abstract—The authors investigate the behavior of automata in random media with periodically changing probability characteristics and describe automata that minimize the mathematical expectation of a penalty for a known switching period and when the switching period is determined by the automaton. They also consider the possibility of describing a synchronization process in, for example, systems for transmitting telemetry with time division of channels in the presence of noise in terms of the behavior in periodic random media. The possibility of using the design principles of the automata discussed for constructing the corresponding synchronizers is demonstrated.

The Inherent Order of Texts as a Means of Improving Optical Readers
V. S. Fain
pp. 53–57

Abstract—The author consider ways and means of using the order inherent in a meaningful text in the design of improved optical readers. He shows that it is possible to increase the reliability of character recognition and substantially reduce the number of standards required for reading a large number of different fonts.

A System for Optimal Message Routing
A. V. Butrimenko and V. G. Lazarev
pp. 58–62

Abstract—This paper describes a method for decentralized control of a communications network. During operation of the network, messages are optimally routed. The method proposed ensures a high degree of viability. Technical realization of the method with available equipment is also discussed.

On the Dissipativity of Random Processes Defined by Differential Equations
R. Z. Khas'minskii
pp. 63–77

Abstract—The random processes encountered in information-transmitting systems can frequently be described by differential equations with random right sides. This paper deals with the conditions for the dissipativity and stability of such processes, as well as the conditions for the existence of periodic and stationary solutions.

Role of the Sexes in the Transmission and Transformation of Genetic Information
V. A. Geodakyan
pp. 78–83

Abstract—The role of the sexes in the evolutionary process is discussed. A new point of view on the differentiation of the sexes, as a separation of constant and operative “memory” type, according to which females perform the function of the constant “memory” – the tendency for conservatism, while the males perform the operative function – the tendency for variability, is proposed. In this system, evolutionary changes in type primarily affect the males, and then are transmitted to the females. The discovery of such specialization makes it possible to explain the increased death rate and excess birth rate of the male sex, the greater variety of males, and other phenomena related to sex differentiation. The new approach relates sex dimorphism to the phylogenetic tendency of characteristics and makes it possible to predict the direction of change in a characteristic.

On the Complexity of Decoding
M. S. Pinsker
pp. 84–86

Abstract—For a very general class of channels operating below capacity it is possible to construct a code in such a way that the number of operations required for decoding is less than some constant that is independent of the error probability.

Cyclic Codes Capable of Correcting Uniform Error Bursts
Yu. L. Sagalovich
pp. 87–90

Abstract—The author introduces the notion of error bursts that are uniform with respect to some number. He proves that the number of control symbols required for correction of such bursts is considerably less than that required for the general case.

An Ideal Physical Communication Channel
L. B. Levitin
pp. 91–93

Abstract—The principle of entropy defect is used to introduce the notion of an ideal physical communication channel. An ideal physical channel with additive statistically independent noise is discussed. A number of information properties of such a channel are established, and it is shown that they can be defined on the basis of a thermodynamic description of the physical system carrying the information.