PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

A Bound on Decoding Error Probability in a Noisy Multiple-Access Channel
A. N. Trofimov and F. A. Taubin
pp. 159–169

Abstract—We derive upper bounds on the decoding error probability in a multiple-user channel with concentrated and impulse noise and white Gaussian noise. The concentrated noise is defined by a sum of harmonics with random frequencies and phases. The impulse noise is modeled by a Poisson stream of short pulses. All the users are independent, using common-format compound signals with frequency and phase jumps. For each receiver, the signals of other stations are treated as interference. The decision procedure includes correlative reception with subsequent decoding using a continuous output.

Noiseless Coding of Combinatorial Sources, Hausdorff Dimension, and Kolmogorov Complexity
B. Ya. Ryabko
pp. 170–179

Abstract—We consider the problem of noiseless coding of combinatorial (nonstochastic) sources. The cost of the optimal code is shown to be equal to the Hausdorff dimension of the source. The same problem is solved with algorithmic constraints on the code in two settings: coding and decoding realized by Turing machines and by finite automata. The lower bounds on the cost of the code in these cases are expressed in terms of the Kolmogorov complexity and the quasi-entropy, respectively. Optimal codes are constructed for sources generated by formal grammars.

Matching Block Codes to a Channel with Phase Shifts
E. E. Nemirovskii and S. L. Portnoi
pp. 179–185

Abstract—We investigate the characteristics of block codes in a phase telegraphy channel with phase shifts. Various known classes of codes are considered, namely, BCH codes, majority codes, and generalized concatenated codes. A transparency and phasability condition is given for code constructions. A new notion of automatic phasability is introduced for majority codes. The use of nonbinary codes in multiposition phase telegraphy channels with phase shifts is described.

Two Classes of Minimum Generalized Distance Decoding Algorithms
S.I. Kovalev
pp. 186–192

Abstract—We consider two classes of erasure, choosing algorithms for decoding in the generalized distance metric with $l<\lceil(d+1)/2\rceil$ decoding attempts. In each class, we identify and investigate algorithms that minimize the loss of distance compared with the Forney algorithm.

On Nonparametric Estimation of a Linear Functional of the Regression Function in Observation Planning
R. Z. Khas'minskii
pp. 192–208

Abstract—We construct an asymptotically optimal observation plan and a corresponding asymptotically efficient nonparametric estimator of a linear functional of the regression function under various assumptions about the observation noise. This estimation plan is asymptotically best both when we have very poor prior (compactness) information about the regression function as well as when sufficiently detailed information is available and the function is smooth.

Self-Tuning Algorithm for Minimax Nonparametric Estimation of Spectral Density
S. Yu. Efroimovich and M. S. Pinsker
pp. 209–221

Abstract—We consider an adaptive algorithm for minimax nonparametric estimation of an unknown spectral density, which is assumed to be a point in an ellipsoid with unknown axes in the Hilbert space.

On Optimal Estimation of Scale Parameters
A. G. Tartakovskii
pp. 222–231

Abstract—We solve the problem of optimal estimation (in the class of regular estimators) of a scale parameter defined as the inverse of the observation mean with quadratic and nonquadratic loss functions. The general results are applied to construct point and interval estimators of the parameter of the gamma distribution.

Median Filtering of Deterministic and Stationary Stochastic Signals
L. I. Piterbarg
pp. 232–239

Abstract—The notion of media filtering (MF) of a continuous time process was introduced in [L.I. Piterbarg, Probl. Peredachi Inf., 1984, vol. 20, no. 1, pp. 65–73], where we determined the rate of convergence of the statistical characteristics of the output signal to the corresponding characteristics of the input signal with the window width going to zero for some normal processes. In this paper, the previous results are generalized to arbitrary stationary processes. We investigate the robustness of the media with respect to a thinning stream of impulse noise. The analysis of the stochastic case is preceded by a number of propositions relating to MF of deterministic signals.

Packet Transmission Using a Blocked Unmodified RMA Stack-Algorithm
B. S. Tsybakov and S. P. Fedortsov
pp. 239–245

Abstract—We derive an upper bound on packet delay in a random multiple access system with an unmodified tree algorithm. This bound is linear for low intensities of the incoming packet stream.

Analysis of the Language of Ants by Information-Theoretical Methods
Zh. I. Reznikova and B. Ya. Ryabko
pp. 245–249

Abstract—The information transmission time in ants is shown to be proportional to the amount of information in the messages. An experiment was developed in which the ants were required to transmit a known amount of information before reaching food. Ants were found to be capable of the simplest techniques of information compression when transmitting a “text.”

Decoding Algorithm for the Golay $(24, 12, 8)$ Code
S. V. Bezzateev
pp. 109–112 (Russian issue)

Abstract—We propose a decoding algorithm, which corrects triple errors and detects quadruple errors. The algorithm uses a $6\times 4$ matrix composed of positions of a codeword and a permutation from the Mathieu group $M_{24}$.