PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

Volume 32, Number 2, April–June, 1996
Back to contents page

CONTENTS

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.