PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Relation between the Code Spectrum and the Decoding Error Probability
M. V. Burnashev
pp. 285–304

Abstract—We show how to lower bound the best decoding error probability (or upper bound the reliability function) given some estimates for the code spectrum. Bounds thus obtained are better than previously known ones.

On the Additivity Conjecture in Quantum Information Theory
G. G. Amosov, A. S. Holevo, and R. F. Werner
pp. 305–313

Abstract—A class of problems in quantum information theory, which have elementary formulations but still resist solutions, concerns the additivity properties (with respect to tensor products of channels) of various quantities characterizing quantum channels such as the “classical capacity” or “maximal output purity.” All known results, including extensive numerical work, are consistent with this conjecture. A proof of this conjecture would have important consequences in quantum information theory. In particular, according to this conjecture, the classical capacity or the maximal purity of outputs cannot be increased by using entangled inputs of the channel. In this paper, we state some additivity/multiplicativity problems, give relations between them, and prove some new partial results, which also support the conjecture.

Mathematical Analysis of an Iterative Decoding Algorithm for Low-Density Codes
K. Sh. Zigangirov and M. Lentmaier
pp. 314–324

Abstract—A two-phase iterative decoding algorithm for low-density (LD) codes suggested by the authors of the paper is analyzed for transmission over a binary symmetric channel (BSC). A lower bound on the maximal error probability $p$ of the BSC for which the decoding error probability of iterative decoding goes to zero as the code length goes to infinity is derived.

Entropy of an Ellipsoid in a Hamming Space
M. S. Pinsker
pp. 325–330

Abstract—The logarithmic asymptotics of the cardinality of certain sets defined as ellipsoids in a Hamming space is considered.

On Automorphism Groups of Perfect Binary Codes and Steiner Triple Systems
F. I. Solov'eva and S. T. Topalova
pp. 331–335

Abstract—We prove that the order of the automorphism group of an arbitrary perfect binary code with $d=3$ is not greater than that of the automorphism group of the Hamming code of the same length. We also obtain an upper estimate for the order of the automorphism group of an arbitrary Steiner system $S(t,t+1,n)$.

On Generalized Concatenated Constructions of Perfect Binary Nonlinear Codes
V. A. Zinoviev and A. C. Lobstein
pp. 336–348

Abstract—Using variations of the generalized concatenation of appropriately chosen codes, we give new constructions of binary nonlinear perfect codes with minimum distance $3$ and lower bound the number of different codes obtained by these constructions.

Combining Construction of Perfect Binary Codes
D. S. Krotov
pp. 349–353

Abstract—A construction is proposed, which makes it possible to assemble a perfect binary code using components of various known perfect binary codes. As a corollary, generalizations of some known constructions of perfect binary codes are obtained.

How to Improve the Nonparametric Density Estimate in S-PLUS
L. L. Boiko and G. K. Golubev
pp. 354–361

Abstract—Some properties of nonparametric estimates of probability density used in the interactive statistical data analysis package S-PLUS are discussed. A simple and efficient (from computational point of view) method for constructing nonparametric density estimates is suggested. In many situations, this method (based on splines) substantially dominates kernel estimates and, in particular, the estimate used in S-PLUS.

On Error-Free Filtering of Singular Processes under Nonstationary Distortions
M. S. Pinsker and V. V. Prelov
pp. 362–369

Abstract—The problem of filtering for a singular stationary stochastic process under nonstationary distortions is considered. For certain models of nonstationary distortions, sufficient conditions under which error-free filtering of such processes is possible are obtained.

Asymptotically Optimal Sequential Hypothesis Testing
M. B. Malyutov and I. I. Tsitovich
pp. 370–382

Abstract—We study sequential strategies ($\alpha$-strategies) of controlled discrimination between nonparametric hypotheses with an indifference zone and error probability not greater than $\alpha\gt 0$ under any true distribution from the hypotheses. We construct $\alpha$-strategies with asymptotically minimal mean length under any true distribution including those from the indifference zone.

Boolean Functions with External Parameters
V. V. Tarasov
pp. 383–386

Abstract—In this paper, we consider Boolean functions $f(\widetilde{x}, \widetilde{z})$ depending on two groups of variables, $\widetilde{x}$ and $\widetilde{z}$. The first group contains standard Boolean variables, which are subjected to the operations of renaming, identification, and substitution of formulas. No operations are allowed on the variables $\widetilde{z}$ of the second group. The variables $\widetilde{z}$ represent the influence of the environment on the function $f$. Let $\gamma$ be a finite system of such functions. Assume that $g(\widetilde{x})$ is a standard Boolean function. We study the conditions for realizability of the function $g(\widetilde{x})$ by a circuit of functional elements in the basis $\gamma$.

On Optimal Prior Learning Time in the Two-Armed Bandit Problem
A. V. Kolnogorov
pp. 387–396

Abstract—For the two-armed bandit problem considered on a known finite time segment $T$, a strategy with a priori determined learning time is proposed. Based on the loss balance equation, its exact asymptotic estimate is established, which is found to be of order $T^{2/3}$. For near distributions, the estimate changes: for a Bernoullian two-armed bandit, the learning time in this case approximately equals $T/3$.

Large Deviations of the Shape of a Random Young Diagram with the Bell Distribution
V. M. Blinovsky
pp. 397–402

Abstract—We state the local large deviation principle (LLDP) in $L^{1}$ metric for the shape of random Young diagrams with the Bell distribution and derive an explicit formula for the rate function.

Improving the Reliability of Switching Circuits
V. A. Garmash
pp. 403–407

Abstract—We consider the design of a switching circuit tolerant to $k$ faults of type “break” or “sticking.” The number of redundant elements added to the circuit grows as $k^{2}$. When a circuit is constructed from several subcircuits whose faultless operation is necessary for the faultless operation of the circuit as a whole, uniform reliability of the whole circuit is ensured.

Letter to the Editor
M. E. Haroutunian
p. 408

INDEX
pp. 409–412