PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 31, Number 1, January–March, 1995
Back to contents page

CONTENTS                   Powered by MathJax

 

An Effective Method for Encoding Information Sources Using the Fast Muliplication Algorithm
B. Ya. Ryabko
pp. 1–9

Abstract—We consider the problem of encoding information sources with a priori known and unknown symbol probabilities. For both cases, we study the complexity of encoding and decoding depending on the redundancy $r$ that is defined as the difference between the average code length and the entropy. The known coding methods can be split into two classes. For codes of one class, where the redundancy $r$ is reduced, $r\rightarrow 0$, the memory $S$ and the average encoding/decoding time per symbol $T$ grow as $O(\exp (1/r))$ and $O((-\log r)^{\operatorname{const}})$, respectively (if we implement the encoder and decoder in a computer). For the other codes, $S=O(r^{-\operatorname{const}})$ and $T=O(r^{-\operatorname{const}})$ as $r\rightarrow 0$. We suggest a method combining the advantages of both classes of codes, where the memory grows as a power of $1/r$ and the encoding/decoding time does not exceed a power of $-\log r$ with decrease in the redundancy $r$: $S=O(r^{-\operatorname{const}})$ and $T=O((-\log r)^{\operatorname{const}})$. (Everywhere in this paper, $\operatorname{const}$ is some number greater than or equal to $1$.) The same method is used for constructing a fast enumerative encoding (see the definition in [T. M. Cover, IEEE Trans. Inf. Theory, 19, No. 1, 73–77 (1973); R. Ye. Krichevskii, Information Compression and Retrieval, Radio i Svyaz, Moscow (1989) ]).

 

Upper Bounds on the Probability of Nondetected Error
G. L. Katsman
pp. 10–13

Abstract—An assertion is proved which yields upper bounds on the probability of nondetected error in a binary symmetric channel. The previously known bounds [Levenstein, Probl. Peredachi Inf., 13, No. 1, 3–18 (1997); Kasami et al., IEEE Trans. Inf. Theory, 24, 76–80 (1978) ] can be obtained as special cases of this assertion.

 

Asymptotics of Fisher Information Under Weak Perturbation
V. V. Prelov and E. C. van der Meulen
pp. 14–22

Abstract—An asymptotic expression as $\varepsilon\to 0$ is derived for the Fisher information of a random variable $Y=X+Z_\varepsilon$, where $X$ and $Z_\varepsilon$ are mutually independent, under some regularity conditions on the probability density function of $X$ and the assumption that $\operatorname{\bf E}Z_{\varepsilon}^2=\varepsilon^2$ and $\operatorname{\bf E}|Z_{\varepsilon}/\varepsilon|^k\leq c\lt\infty$ for some $k\gt2$. Using this result an asymptotic generalization of De Bruijn's identity is obtained.

 

Application of Formal Grammars for Encoding Information Sources
E. V. Kourapova and B. Ya. Ryabko
pp. 23–26

Abstract—To increase the efficiency of data compression methods, we suggest describing the structure of data by means of formal grammars. This approach helps to compress even small files for which known adaptive and nonadaptive codes are usually ineffective. Based on this approach, some data compression systems for data bases and program libraries in several programming languages have been built and experimentally investigated. The codes constructed permit one to increase the compression ratio by 10–30% compared to other methods.

 

Image Processing for Plane Domains: Change-Point Problems for the Domain's Area
M. I. Freidlin and A. P. Korostelev
pp. 27–45

Abstract—Image models are considered for growing domains observed in Gaussian white noise. The “jump” and “kink” change-point problems are studied for the domain's area. When noise is small the minimax rates of convergence are found for Markov stopping rules in different classes of growing domains. The peculiarity of the problem is this: the domain's shape is unknown and plays the role of an infinite-dimensional “nuisance parameter” which strongly influences the precision of the estimators.

 

Lower Information Bounds for Adaptive Tracking of a Linear Discrete Plant
A. V. Nazin and A. B. Juditski
pp. 46–56

Abstract—The problem of adaptive tracking is considered for a linear discrete stochastic SISO control plant. Information bounds are obtained under a variety of conditions imposed on the disturbances and the control strategy.

 

Filtration of Time-Continuous Stochastic Signals by Discrete Observations With Memory
O. L. Abakumova, N. S. Demin, and T. V. Sushko
pp. 57–71

Abstract—The problem of filtration of a multidimensional stochastic signal of the Markov diffusion type is considered under the condition that the observed time-discrete multidimensional random process depends not only on the current value of the useful signal, but also on an arbitrary number of its past values. For a particular case, the efficiency of a channel with memory of multiplicity two with respect to a channel without memory is investigated.

 

Unimodality of the Distribution of the Number of Pulses for Gaussian Optical Fields
Yu. P. Virchenko and A. S. Mazmanishvili
pp. 72–77

Abstract—The statistics of detected pulses is considered when recording optical radiation. On the basis of Mandel's formula for the probability $P(n)$ to detect $n$ photons during an observation time interval, it is shown that the probability distribution $P(n)$ is unimodal provided the radiation field is Gaussian. The unimodality property makes it possible to apply the theory of statistical decisions that makes use of a unique threshold to the design of optical information transmission systems.

 

On the Limit Distribution of the Distance Between a Random Vector and Some Binary Codes
S. I. Chechiota
pp. 78–85

Abstract—We obtain theorems on the limit distribution of the Hamming distance between a random vector and some binary codes. We assume that the codes that we consider are distance-invariant; the conditions of the theorems are expressed in terms of the weight (distance) spectrum. The results are applied to obtain a lower bound on the covering radius of a code. As examples, we consider some well-known codes.

 

Recurrence Method for Teletraffic Evaluation in Serial-Parallel Telecommunication Nets
A. V. Klimov, S. A. Kolbasyuk, and V. I. Neiman
pp. 86–97

Abstract—The paper discusses serial-parallel telecommunication nets formed by pooling several collective channels into a bundle of channels. Each channel in the bundle can be independently used and reused in various spatial sections. An exact recurrence method for calculating state probabilities of the system is developed. Using these probabilities one can obtain an explicit expression for the capacity of a bundle of channels as a function of given blocking probabilities. The peculiarities of the method for a single channel and for a bundle of channels as well as for subscriber and trunk channels are described.