PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Upper-Bound Estimates for Fixed-Weight Codes
V. I. Levenshtein
pp. 281–287

Abstract—New upper bounds are obtained for the maximum number of binary vectors having a fixed number of unit symbols and forming a code with a specified code distance. The resulting estimates lead to more precise asymptotic relations than the corresponding estimates of Johnson and Berger and permit Johnson’s estimate to be analyzed for arbitrary codes.

A Universal Encoding Method with Nonexponential Work Expenditure for a Source of Independent Messages
V. F. Babkin
pp. 288–294

Abstract—A method is proposed for the encoding of a source of independent messages the statistical distribution of which is unknown and the redundancy of which tends to zero as the length of the encoding block is increased. The method is distinguished by the simplicity of its computational procedure, and its work expenditure is a power function of the block length. A slight modification of the universal encoding method makes it possible to construct an asymptotically optimal statistical code for a source having a known distribution.

Optimal Decoding in Semicontinuous Channels with a Variable Parameter
V. I. Korzhik and L. M. Fink
pp. 295–300

Abstract—A semicontinuous variable-parameter channel (VPC) is defined, and an optimal decoding algorithm is determined. It is shown that this algorithm reduces to a comparison of quadratic forms depending on the correlation of the parameters.

Characteristics of the Conditionally Optimal Detection of Signals Having Random Amplitude and Initial Phase
D. R. Kerkenyakov
pp. 301–307

Abstract—The problem of correct detection under the condition that the parameters of the high-frequency useful signal $S(t,\varphi)$ are estimated beforehand. The dependence of this probability on the accuracy of the preliminary estimates of the individual parameters is demonstrated in an example.

Decision Invariance under a Nuisance Parameter
V. P. Kuznetsov
pp. 308–312

Abstract—Methods are considered for the synthesis of decision systems that completely eliminate the influence of nuisance parameters. The methods are based on maximum invariants under an appropriately selected group of transformations of the sample space. The problem of synthesizing invariant decision systems is stated in application to a broad class of communication channels.

Choosing the Spectral Window in the Estimation of the Spectrum of a Gaussian Stationary Stochastic Process
V. G. Alekseev
pp. 313–319

Abstract—Estimates of the spectral density of a discrete-time Gaussian stationary process are investigated. Weighting functions (spectral windows) are found for the estimates, permitting the mean-square error of estimation (or the upper bound thereof) to be minimized under specified assumptions regarding the degree of smoothness of the estimated density.

A Universal Random-Sequence Transformer
L. V. Makarevich
pp. 320–322

Abstract—The feasibility of transforming certain random sequences into others by means of finite automata is explored. A method which departs significantly form any known previously is proposed. The suggested approach makes it possible to synthesize a universal transformer of nearly minimal complexity.

Complexity Estimation for the Coloring of Graphs on a Turing Machine
A. A. Kalnin'sh
pp. 323–331

Abstract—The paper presents a discussion of $c$-graphs, i.e., undirected graphs having neither loops nor multiple edges with numbered vertices and having $c$ times as many edges as vertices. As already proved by the author in [Latv. Mat. Ezhegodnik, vol. 7, Riga: Zinatne, 1970, pp. 111–125], for almost all $c$-graphs $G$ the chromatic number $\gamma(G)$ satisfies the inequality $$ \frac{c}{\ln c}\lt\gamma(G)\le 4c. $$ The object of investigation here is the complexity (in the sense of the number of steps required) of the proper coloring of the vertices of a $c$-graph on a single-head single-tape Turing machine. The complexity of the computerized coloring of a graph for the case in which all information is located in working storage has been analyzed in [A.A. Kalnin'sh, Kibernetika, 1971, no. 4, pp. 103–111]. A graph is naturally encoded on a Turing machine tape as a list of its edges, and the coloring of the graph as a list of colors. Suppose that $k$ is such that almost all $c$-graphs can be $k$-colored; in particular, let it be said that $k=4c$. It is proved that for any Turing machine properly $k$-coloring almost all $c$-graphs at least $n^2\log n$ steps in order of magnitude are required for almost all $c$-graphs, where $n$ is the number of vertices of the graph. On the other hand, it is shown that almost all $c$-graphs can be colored on a Turing machine by no more than $4c$ colors in an order of $n^2\log^2n$ steps.

Relationship between the Simulation of Computational Media from a Fixed Initial State and from an Arbitrary Initial State
A. V. Koganov
pp. 332–336

Abstract—Different modes of simulating media on nets by means of media of fewer dimensions are investigated. In particular, a study is made of the extent to which information processing is retarded when it is required that simulation take place from one fixed initial state. It is shown that the estimates found in [A.V. Koganov, Probl. Peredachi Inf., 1971, vol. 7, no. 2, pp. 97–105] are equally sharp for all the types of simulation investigated. It is proved that for the simulation of an arbitrary automaton by media on a net the retardations in simulation from an arbitrary or fixed initial state are close to one another, given an unfavorable state-selection mode.

An Upper Bound for the Reliability of Information Networks
M. V. Lomonosov and V. P. Polesskii
pp. 337–339

Abstract—An upper bound is established for the reliability of an information network on the basis of the size of a certain family of cuts.

The Classification of One-Dimensional Homogeneous Networks
N. B. Vasil'ev and I. I. Pyatetskii-Shapiro
pp. 340–346

Abstract—The results of a computer simulation of one-dimensional homogeneous networks of two-state elements dependent on two adjacent elements are systematized.

Simulation of Inversion in Volvox
E. B. Vul and I. I. Piatetskii-Shapiro
pp. 347–351

Abstract—The motion of a line on a plane, simulating the inversion Volvox, is analyzed. The analysis is based on the postulate that the motion of each individual cell is dictated by “knowledge” of the positions of its nearest neighbors.

Noise Immunity of Optimum Incoherent Diversity Reception in Channels with Fluctuating and Concentrated Noise Functions
A. A. Sikarev
pp. 352–355

Abstract—The potential noise immunity of square-additive binary diversity-reception systems optimum under the simultaneous effects of fluctuating and concentrated noise is analyzed. Examples are discussed for the case sinusoidal noise. It is shown that concentrated noise can be virtually annihilated in such systems.

INDEX
pp. 357–363