PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Polar Codes with Higher-Order Memory
H. Afşer and H. Deliç
pp. 301–328

Abstract—We introduce a construction of a set of code sequences $\{\mathscr{C}_n^{(m)}:\: n\ge 1,\: m\ge 1\}$ with memory order $m$ and code length $N(n)$. $\{\mathscr{C}_n^{(m)}\}$ is a generalization of polar codes presented by Arıkan in [1], where the encoder mapping with length $N(n)$ is obtained recursively from the encoder mappings with lengths $N(n-1)$ and $N(n-m)$, and $\{\mathscr{C}_n^{(m)}\}$ coincides with the original polar codes when $m=1$. We show that $\{\mathscr{C}_n^{(m)}\}$ achieves the symmetric capacity $I(W)$ of an arbitrary binary-input, discrete-output memoryless channel $W$ for any fixed $m$. We also obtain an upper bound on the probability of block-decoding error $P_e$ of $\{\mathscr{C}_n^{(m)}\}$ and show that $P_e=O (2^{-N^\beta})$ is achievable for $\beta<1/[1+m(\phi-1)]$, where $\phi\in (1,2]$ is the largest real root of the polynomial $F(m,\rho)=\rho^m-\rho^{m-1}-1$. The encoding and decoding complexities of $\{\mathscr{C}_n^{(m)}\}$ decrease with increasing $m$, which proves the existence of new polar coding schemes that have lower complexity than Arıkan's construction.

Refinements of Levenshtein Bounds in $q$-ary Hamming Spaces
P. Boyvalenkov, D. Danev, and M. Stoyanova
pp. 329–342

Abstract—We develop refinements of the Levenshtein bound in $q$-ary Hamming spaces by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. We investigate the first relevant cases and present new bounds. In particular, we derive generalizations and $q$-ary analogs of the MacEliece bound. Furthermore, we provide evidence that our approach is as good as the complete linear programming and discuss how faster are our calculations. Finally, we present a table with parameters of codes which, if exist, would attain our bounds.

On the Complexity of Fibonacci Coding
I. S. Sergeev
pp. 343–350

Abstract—We show that converting an $n$-digit number from a binary to Fibonacci representation and backward can be realized by Boolean circuits of complexity $O(M(n)\log n)$, where $M(n)$ is the complexity of integer multiplication. For a more general case of $r$-Fibonacci representations, the obtained complexity estimates are of the form $2^{O(\sqrt{\log n})}n$.

Noise Level Estimation in High-Dimensional Linear Models
G. K. Golubev and E. A. Krymova
pp. 351–371

Abstract—We consider the problem of estimating the noise level $\sigma^2$ in a Gaussian linear model $Y=X\beta+\sigma \xi$, where $\xi\in\mathbb{R}^n$ is a standard discrete white Gaussian noise and $\beta\in\mathbb{R}^p$ an unknown nuisance vector. It is assumed that $X$ is a known ill-conditioned $n\times p$ matrix with $n\ge p$ and with large dimension $p$. In this situation the vector $\beta$ is estimated with the help of spectral regularization of the maximum likelihood estimate, and the noise level estimate is computed with the help of adaptive (i.e., data-driven) normalization of the quadratic prediction error. For this estimate, we compute its concentration rate around the pseudo-estimate $\|Y-X\beta\|^2/n$.

Exponentially Ramsey Sets
A. A. Sagdeev
pp. 372–396

Abstract—We study chromatic numbers of spaces $\mathbb{R}^n_p=(\mathbb{R}^n, \ell_p)$ with forbidden monochromatic sets. For some sets, we for the first time obtain explicit exponentially growing lower bounds for the corresponding chromatic numbers; for some others, we substantially improve previously known bounds.