PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Reliability Function for a BSC with Noiseless Feedback at Zero Rate
M. V. Burnashev
pp. 203–216

Abstract—We consider the transmission of nonexponentially many messages through a binary symmetric channel with noiseless feedback. We obtain an upper bound for the best decoding error exponent. Combined with the corresponding known lower bound, this allows us to find the reliability function for this channel at zero rate.

On One Extremal Problem for Mutual Information
V. V. Prelov
pp. 217–230

Abstract—We address the problem of finding the maximum of the mutual information $I(X;Y)$ of two finite-valued random variables $X$ and $Y$ given only the value of their coupling, i.e., the probability $\Pr\{X=Y\}$. We obtain explicit lower and upper bounds on this maximum, which in some cases are optimal.

On Weight Distributions for a Class of Codes with Parameters of Reed–Muller Codes
I. Yu. Mogilnykh and F. I. Solov'eva^†
pp. 231–241

Abstract—We present a new construction method for a doubly exponential class of binary codes with the parameters of Reed–Muller codes. We investigate the weight spectrum and the distance-invariance property of the proposed codes. In the constructed class of codes with the parameters of Reed–Muller codes, we show the existence of codes with the same weight distribution as for a Reed–Muller code and of codes with weight distributions other than this. We establish that all codes with the parameters of the Reed–Muller code which are obtained by the Vasil'ev–Pulatov construction but are distinct from extended perfect codes either are equivalent to the original Reed–Muller codes or have distance distributions different from those.

Improved Upper Bounds for the Rate of Separating and Completely Separating Codes
I. V. Vorob'ev and V. S. Lebedev
pp. 242–253

Abstract—A binary code is said to be an $(s,\ell)$-separating code if for any two disjoint sets of its codewords of cardinalities at most $s$ and $\ell$ respectively, there exists a coordinate in which all words of the first set have symbol 0 while all words of the second have 1. If, moreover, for any two sets there exists a second coordinate in which all words of the first set have 1 and all words of the second have 0, then such a code is called an $(s,\ell)$-completely separating code. We improve upper bounds on the rate of separating and completely separating codes.

Partitions into Perfect Codes in the Hamming and Lee Metrics
F. I. Solov'eva^†
pp. 254–264

Abstract—We propose new combinatorial constructions of partitions into perfect codes in both the Hamming and Lee metrics. Also, we present a new combinatorial construction method for diameter perfect codes in the Lee metric, which is further developed to a construction of partitions into such codes. For the Lee metric, we improve previously known lower bounds on the number of perfect and diameter perfect codes proposed by Etzion in 2011.

On Minimax Detection of Gaussian Stochastic Sequences with Imprecisely Known Means and Covariance Matrices
M. V. Burnashev
pp. 265–278

Abstract—We consider the problem of detecting (testing) Gaussian stochastic sequences (signals) with imprecisely known means and covariance matrices. An alternative is independent identically distributed zero-mean Gaussian random variables with unit variances. For a given false alarm (1st-kind error) probability, the quality of minimax detection is given by the best miss probability (2nd-kind error probability) exponent over a growing observation horizon. We study the maximal set of means and covariance matrices (composite hypothesis) such that its minimax testing can be replaced with testing a single particular pair consisting of a mean and a covariance matrix (simple hypothesis) without degrading the detection exponent. We completely describe this maximal set.

Recoverable Formal Language
M. L. Blank
pp. 279–283

Abstract—We study the problem of recovering distorted arbitrarily long messages written in some dynamically specified formal language. We obtain necessary and sufficient conditions on the language definition for an admissible message to exist in a neighborhood of a distorted message provided that local perturbations occur rarely.

Fast Evaluation Algorithms for Elementary Algebraic and Inverse Functions Using the FEE Method
E. A. Karatsuba
pp. 284–296

Abstract—We construct new fast evaluation algorithms for elementary algebraic and inverse functions based on application of two methods: A.A. Karatsuba's method of 1960 and the author's FEE method of 1990. The computational complexity is close to the optimal. The algorithms admit partial parallelization.