PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

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.

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.