PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 7, Number 4, October–December, 1971

Back to contents page

** 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