PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Simple Methods for Deriving Lower Bounds in Coding Theory
L. A. Bassalygo, S. I. Gelfand, and M. S. Pinsker
pp. 277–281

Abstract—We consider various methods of deriving lower bounds on the cardinality of a code. A new asymptotic expression is obtained for the maximum cardinality $L(n,t)$ of a length-$n$ binary code correcting $t$ localized errors: $$ L(n,t)=\frac{2^n}{\sum\limits^t_{j=0}C_n^j}(1+o(1)),\quad t^3n^{-1}\ln n\to 0. $$

Relative-Redundancy Universal Coding of Memoryless Sources
Yu. M. Shtarkov
pp. 282–288

Abstract—A relative-redundancy criterion of coding efficiency is proposed. A universal code construction is described and its efficiency is estimated by this criterion.

Lower Bound on Error Probability in Fixed-Volume List Decoding
V. M. Blinovskii
pp. 288–302

Abstract—An upper bound is obtained for the error exponent in fixed-volume list decoding at low rates in memoryless BSC. The bound is asymptotically tight at low rates.

Concatenation Method for Construction of Spherical Codes in $n$-Dimensional Euclidean Space
S. M. Dodunekov, V. A. Zinoviev, and Th. Ericson
pp. 303–307

Abstract—A new construction is proposed for spherical codes of finite dimension $n$, based on two families of binary codes: constant-weight codes and ordinary block codes. This construction produces, in particular, some known optimal constructions with Euclidean distance $\rho=1$. For smaller $\rho$, the spherical codes constructed by this method essentially improve the existing lower bounds on cardinality of best codes obtained in previous studies for finite $n$.

Fast Maximum-Likelihood Decoding of Reed–Muller Codes
V. V. Zyablov and S. L. Portnoi
pp. 307–317

Abstract—We describe a maximum-likelihood algorithm for Reed–Muller codes and some suboptimal decoding algorithms. The complexity of the algorithms and some estimates of error tolerance are considered.

Decoding of Low-Density Codes
S. I. Kovalev
pp. 317–321

Abstract—We consider decoding of low-density parity-check codes by the Zyablov–Pinsker algorithm. We show that the transition from majority logic decoding to threshold decoding increases the distance realized by the algorithm without affecting the order of complexity. We analyze a version of the algorithm designed for machine implementation which requires $n$ votings, where $n$ is the code length.

On Some Interpolation Procedures for a Partially Observed Markov Process
B. V. Lazareva
pp. 322–333

Abstract—A mean-square optimal interpolation procedure for a two-state Markov process observed in the presence of Gaussian white noise of intensity $\sigma^2$ was obtained in [R.Sh. Liptser and A.N. Shiryaev, Statistics of Random Processes I. General Theory, Appl. Math., 5, Springer, New York (1977)]. In this paper, we investigate the asymptotic behavior of the risk of mean-square and mean-error-probability best interpolation estimators as $\sigma\to0$. Simplified interpolation procedures are constructed and their asymptotic efficiency for $\sigma\to0$ is shown to be $0.924$ for mean-square risk and $0.926$ for error-probability risk.

Nonstationarity Criterion for a Gaussian Time-Series Autoregressive Model with a Close Alternative
J. Kormos and V. I. Piterbarg
pp. 334–338

Abstract—The limiting distribution is derived for the likelihood ratio in testing the hypothesis of stationarity of an autoregressive time series.

Fast Evaluation of Transcendental Functions
E. A. Karatsuba
pp. 339–360

Abstract—A new method is proposed for fast evaluation of transcendental functions and classical constants. The computational complexity is nearly final. The proposed algorithms can be parallelized.

Asymptotic Behavior of Nonanticipative Epsilon-Entropy for Gaussian Processes
A. K. Gorbunov and M. S. Pinsker
pp. 361–365

Abstract—We describe a class of stationary Gaussian processes for which the nonanticipative epsilon-entropy per unit time [A.K. Gorbunov and M.S. Pinsker, Probl. Peredachi Inf., 23, No. 2, 3–8 (1987)] is asymptotically ($\varepsilon^2\to0$) identical with the Shannon rate distortion.

Distortion-free Compression of Telephone Signals in Multichannel Communication Lines
V. R. Zvonkovich, I. V. Pertsev, B. Ya. Ryabko, and I. V. Sitnyakovskii^†
pp. 366–369

Abstract—We consider the compression of digital telephone signals transmitted by multichannel communication lines. In principle, the capacity of such communication lines can be doubled by compression, using the existing hardware. The symbol error rate does not increase, so that universality of the communication channel is preserved (i.e., not only telephone signals, but any digital data can be transferred without corruption). The compression methods are based on known classes of universal codes.

INDEX
pp. 371–377