PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 32, Number 2, April–June, 1996

Back to contents page

**Estimate for the Probability of Undetected Error**

V. M. Blinovskii

pp. 139–144

**Abstract**—We obtain a new bound on the probability of
undetected error, which is valid for all values of symbol-inversion
probability. This bound is the best known.

**On the Trellis Complexity of Block and Convolutional Codes**

U. Dettmar, R. Raschhofer, and U. K. Sorger

pp. 145–155

**Abstract**—We study maximum likelihood decoding of convolutional
codes. We show how to calculate the complexity of the syndrome trellis using
the parity-check matrix and prove that this trellis contains the minimum
possible number of states. We compute the decoding complexity of PUM codes
and apply these results to convolutional codes. An upper bound on the minimal
trellis complexity of convolutional codes is given. Finally, we compare
ordinary and punctured convolutional codes.

**Data Compression Using an “Imaginary Sliding Window”**

B. Ya. Ryabko

pp. 156–163

**Abstract**—Methods of adaptive coding that use the scheme of a sliding
window are well known in data compression. In such methods, the code of the next
letter $x_t$ is determined by the analysis of the window's contents, i.e., of the
word $x_{t-w}x_{t-w+1}\ldots x_{t-1}$, where $w\geq 1$ is the window's size. After
encoding $x_t$, it is written into the window from the right, and $x_{t-w}$ is
removed. The advantages of these methods are the ability to estimate the source
statistics accurately enough and a rapid adaptation to the varying statistics. In the
paper, we propose a new scheme for organizing the sliding window, where a random
element, instead of the left-most one, is removed from the window. This conserves all
the properties of the sliding window, but enables one not to keep the window, which
in turn allows the memory capacity of the encoder and decoder to be essentially
decreased.

**Difference Sets and Codes Correcting Single Localized Errors of Known Value**

G. A. Kabatianskii and V. S. Lebedev

pp. 164–167

**Abstract**—We consider codes correcting localized errors of
known value. An upper bound for the maximal number of messages which can be
transmitted by such a code is obtained and codes attaining this bound are
constructed.

**Codes Detecting Localized Errors**

L. A. Bassalygo and M. S. Pinsker

pp. 168–170

**Abstract**—An asymptotically optimal code rate is found for
codes that detect a linearly growing number of localized errors.

**Optimal Sets of Binary Sequences**

B. Zh. Kamaletdinov

pp. 171–175

**Abstract**—We suggest an efficient method for designing families
of binary sequences that are optimal in the sense of packing bounds. We show
that the new classes of ensembles compare favorably to the known ones in a
greater variety of methods for forming the fine structure of a code and a
very representable collection of existence lengths.

**On the Averaging Principle for Nonlinear Filtering Problems with Random
Contamination**

M. L. Kleptsina and A. P. Serebrovski

pp. 176–183

**Abstract**—The averaging principle for the family of optimal
filtering estimates is proved for the case of diffusion-type signal and
observation under rapidly oscillating contamination affecting their drift
coefficients.

**Asymptotically Minimax Criteria for Testing Complex Nonparametric
Hypotheses**

M. S. Ermakov

pp. 184–196

**Abstract**—Asymptotically minimax criteria are constructed for
testing complex nonparametric hypotheses of symmetry, homogeneity, and
independence. Here the sets of alternatives have a natural nonparametric
representation. The traditional technique of reducing the problem to the
corresponding problem for uniform distribution is not used in this study. At
the same time, the specification of test statistics does not depend upon the
hypothesis density.

**Local Asymptotical Normality for Stationary Gaussian Sequences with
Degenerate Spectral Density**

N. K. Bakirov

pp. 197–204

**Abstract**—The property of local asymptotical normality (at a point
$\theta_0$) is proved for a stationary Gaussian sequence with spectral density
$f(\lambda,\theta)$, $\theta\in {\Bbb R}^1$, which may have zeros, or, more
specifically, $\operatorname{mes}\{\lambda\mid f(\lambda,\theta_0=0\}=0$, where
$\operatorname{mes}$ denotes the Lebesgue measure. In addition, we prove standard
inequalities, the validity of which, along with the property of local asymptotical
normality, assures “good” asymptotical properties of the estimates of
maximal likelihood and Bayesian estimates for the parameter $\theta$.

**Improving Parameter Estimates and Shortening the Procedure of Design of
Efficient Diagnostic Polynomials**

Yu. L. Sagalovich

pp. 205–215

**Abstract**—The vector of a lexicographically arranged Boolean
elementary interval can belong to no cyclic code whose generator polynomial
has roots distinct from unity. Therefore, under some additional conditions
upon the scheme to be tested and the sequence of test actions, the cyclic
code a priori detects all faulty schemes from a rather wide class. The
conditions mentioned lead to the consideration of a new class of separating
systems.

**On Rank Distributions of Letter Frequencies in Human Languages**

M. S. Gelfand and Zhao Ming

pp. 216–221

**Abstract**—The dependence between letter frequencies and letter
ranks (positions in the alphabet reordered by decrease of frequencies) in
human languages was described both as a linear function of rank and frequency
logarithm and as a linear function of rank logarithm and frequency. Both
models were used to draw analogies with other information systems. We
demonstrate that neither model is superior as compared to the other one, and
thus the problem of rank distribution of letter frequencies remains open.