PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 18, Number 2, April–June, 1982

Back to contents page

** Methods of Constructing Lower Bounds for Redundancy of Universal
Coding
**

Yu. M. Shtar'kov

pp. 85–92

**Abstract**—The article proposes a new approach to the
construction of lower bounds for the redundancy of universal coding. A
relationship to the problem of choosing reliably discriminable hypotheses is
established, and some examples are considered.

** Quasioptimal Methods of Correlational Reception of Reed–Solomon Codes
**

E. E. Nemirovskii

pp. 92–100

**Abstract**—The article poses the problem of developing quasi-optimal
methods of decoding Reed–Solomon and Forney codes that almost realize their
potential properties in operation in a Gaussian channel, but that are less
complicated than parallel correlational reception. The following methods are
investigated: inspection and comparison in Euclidean metric of $C_n^{d-1}$ erasures
with $d-1$ symbols in each erasure; a new “sliding subgraph” method, and
three versions of list subsets of the Viterbi algorithm. Analytic estimates are given
for the complexity and noise stability of the first two methods, and results of
statistical simulation of subsets of the Viterbi algorithm are given.

** On Nonparametric Estimates of Probability Density and Its Derivatives
**

V. G. Alekseev

pp. 100–106

**Abstract**—Nonparametric estimates for the probability
distribution density and its derivatives up to third order inclusive are
investigated. Estimates of both the probability density itself and of its
derivatives are constructed by using weighted functions of various orders,
the order being determined by conditions imposed on the moments. Using the
example of two specific probability densities having derivatives of all
orders, it is shown that the use of higher-order weighting functions leads to
an impressive gain in accuracy for a sample of large volume, and, conversely,
results in a loss in accuracy when the sample size is modest.

** On Properties of Deep Frequency Modulation with a Threshold Effect
**

M. V. Burnashev

pp. 106–116

**Abstract**—A mathematically rigorous investigation is made of
the behavior of estimates of the unknown parameter when deep frequency
modulation is employed. In particular, the depth at which the threshold
effect occurs is demonstrated, in relation to the quality criterion employed,
and it is shown how the modulation depth can be optimally chosen.

** Nonparametric Signal Estimation when There Is Incomplete Information
on the Noise Distribution
**

A. B. Tsybakov

pp. 116–130

**Abstract**—The article proposes a class of nonparametric signal
estimates on the basis of observations in noise with probability
characteristics that are not precisely known. The consistency conditions for
these estimates are given, and their rate of convergence is determined. The
problem of choosing estimates that are optimal in the sense of rate of
convergence is solved.

** On the Minimax Nonparametric Detection of Signals in White Gaussian
Noise
**

Yu. I. Ingster

pp. 130–140

**Abstract**—The article considers a minimax version of the problem of
detection of a signal from a specified functional set $V$ in white Gaussian noise of
intensity $\varepsilon\gt0$, under the condition that the signal energy is not less
than a specified value $\rho(\varepsilon)\gt0$. Lower and upper bounds are obtained
for the minimax detection efficiency, which are determined by characteristics of $V$
such as its internal radii and diameters at point $0$. If $V$ is a set of functions of
specified degree of smoothness, the resultant estimates make it possible to obtain
necessary and sufficient conditions for asymptotically nontrivial or consistent
minimax signal detection as $\varepsilon\to0$.

** Completely Separating Systems
**

Yu. L. Sagalovich

pp. 140–146

**Abstract**—The author introduces a definition of binary codes
that are redundant completely separating systems, with the aim of employing
them for antirace and simultaneously noise-stable state assignment for
asynchronous discrete automata. The limits of the parameters of these codes
are determined. Concatenated codes with the above properties are constructed
on the basis of Reed–Solomon codes. It is shown
that the requirement of noise stability does not conflict with the property
of monotonicity of the logical functions of the combination unit of the
automaton, which obtains upon state assignment by completely separating
systems that are not redundant.

** Algebra of Invariant Properties of Binary Sequences
**

V. V. V'yugin

pp. 147–161

**Abstract**—The author investigates properties of infinite
binary sequences that are invariant relative to algorithmic equivalence of
sequences. Any two properties that differ on a set for which some natural
measure is equal to 0 are identified with one another. It is shown that the
class of all computable subsequences and the class of all random subsequences
cannot be separated into nontrivial subclasses by such properties. The
principal technical results of the paper are associated with the study of the
invariant properties that may be possessed by noncomputable sequences that
are algorithmically not equivalent to any random sequences.

BRIEF COMMUNICATIONS

** Performance Evaluation of the Collision Resolution for a Random-Access
Noisy Channel
**

G. S. Evseev and N. G. Ermolaev

pp. 101–105 (Russian issue)

**Abstract**—We derive bounds for the average time of collision
resolution in a random-access channel with synchronous noise and estimate the
transmission rate when a binary symmetric algorithm of collision resolution is
used.

** Estimation of the Hypothesis on a Noninformation Subspace in a
Classification Problem
**

L. G. Malinovskii

pp. 105–109 (Russian issue)

**Abstract**—We obtain maximum-likelihood estimates for vectors
from the subspaces in a hypothesis with information and noninformation
subspaces. We present two practical methods for estimating the number of
vectors in the subspaces.