PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Some Extremal Problems for Mutual Information and Entropy
V. V. Prelov
pp. 319–328

Abstract—The problem of determining the maximum mutual information $I(X;Y)$ and minimum entropy $H(X,Y)$ of a pair of discrete random variables $X$ and $Y$ is considered under the condition that the probability distribution of $X$ is fixed and the error probability $\Pr\{Y\ne X\}$ takes a given value $\varepsilon$, $0\le\varepsilon\le 1$. Precise values for these quantities are found, which in several cases allows us to obtain explicit formulas for both the maximum information and minimum entropy in terms of the probability distribution of $X$ and the parameter $\varepsilon$.

List Decoding for a Multiple Access Hyperchannel
V. Yu. Shchukin
pp. 329–343

Abstract—We obtain bounds on the rate of (optimal) list-decoding codes with a fixed list size $L\ge 1$ for a $q$-ary multiple access hyperchannel (MAHC) with $s\ge 2$ inputs and one output. By definition, an output signal of this channel is the set of symbols of a $q$-ary alphabet that occur in at least one of the $s$ input signals. For example, in the case of a binary MAHC, where $q=2$, an output signal takes values in the ternary alphabet $\{0, 1, \{0, 1\}\}$; namely, it equals $0$ ($1$) if all the $s$ input signals are $0$ ($1$) and equals $\{0, 1\}$ otherwise. Previously, upper and lower bounds on the code rate for a $q$-ary MAHC were studied for $L\ge 1$ and $q=2$, and also for the nonbinary case $q\ge 3$ for $L=1$ only, i.e., for so-called frameproof codes. Constructing upper and lower bounds on the rate for the general case of $L\ge 1$ and $q\ge 2$ in the present paper is based on a substantial development of methods that we designed earlier for the classical binary disjunctive multiple access channel.

On Risk Concentration for Convex Combinations of Linear Estimators
G. K. Golubev
pp. 344–358

Abstract—We consider the estimation problem for an unknown vector $\beta\in\mathbb{R}^p$ in a linear model $Y=X\beta+\sigma \xi$, where $\xi\in\mathbb{R}^n$ is a standard discrete white Gaussian noise and $X$ is a known $n\times p$ matrix with $n\ge p$. It is assumed that $p$ is large and $X$ is an ill-conditioned matrix. To estimate $\beta$ in this situation, we use a family of spectral regularizations of the maximum likelihood method $\tilde{\beta}^\alpha(Y)= H^\alpha(X^\top X)\hat{\beta}^\circ(Y)$, $\alpha\in\mathbb{R}^+$, where $\hat{\beta}^\circ(Y)$ is the maximum likelihood estimate for $\beta$ and $\{H^\alpha(\cdot)\colon \mathbb{R}^+\to [0,1],\: \alpha\in\mathbb{R}^+\}$ is a given ordered family of functions indexed by a regularization parameter $\alpha$. The final estimate for $\beta$ is constructed as a convex combination (in $\alpha$) of the estimates $\tilde{\beta}^\alpha(Y)$ with weights chosen based on the observations $Y$. We present inequalities for large deviations of the norm of the prediction error of this method.

Derivation of Fast Algorithms via Binary Filtering of Signals
M. S. Bespalov, A. S. Golubev, and A. S. Pochenchuk
pp. 359–372

Abstract—We present a new way to derive a fast algorithm realizing the discrete Walsh transform (DWT), which can be applied both in the traditional form, i.e., to a one-dimensional numerical array, and to a multi-dimensional array, as well as for a signal of a continuous argument in the form of a function or an image. The algorithm is presented as iterated application of the primitive discrete Haar transform (DHT) over two variables. Two standard ways of arranging the results of this simplest transform lead to the fast DWT in the Hadamard or Paley enumeration in the case of splitting the signal into equal parts. Application of the algorithm to analogous shifts of the periodic source signal results in longitudinal filtering of a signal via decomposing it into a sum of simpler signals. In an incomplete version of the last algorithm, we come to an analog of the fast DHT.

On Chromatic Numbers of Close-to-Kneser Distance Graphs
A. V. Bobu and A. E. Kupriyanov
pp. 373–390

Abstract—We study a family of distance graphs whose structure is close to that of Kneser graphs. We give new lower and upper bounds on the chromatic numbers of such graphs and consider the question of their interrelation. We also describe the structure of some important independence sets for this family of graphs and explicitly compute their cardinalities.

A Triangular Class of Skew Maximum-Period Polynomials
S. N. Zaitsev
pp. 391–399

Abstract—Skew maximum-period polynomials (MP polynomials) are a kind of pseudorandom sequence generators with good cryptographic properties and efficient implementation on modern processors using parallelism technologies. There are two known classes of MP polynomials, presented in various papers (actually coinciding, as will be shown below), obtained constructively. Here we describe a wider class of skew MP polynomials.