PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Series of Formulas for Bhattacharyya Parameters in the Theory of Polar Codes
S. G. Kolesnikov and V. M. Leontiev
pp. 1–13

Abstract—Bhattacharyya parameters are used in the theory of polar codes to determine positions of frozen and information bits. These parameters characterize rate of polarization of channels $W_N^{(i)}$, $1\le i\le N$, which are constructed in a special way from the original channel $W$, where $N=2^n$ is the channel length, $n=1,2,\ldots.$ In the case where $W$ is a binary symmetric memoryless channel, we present two series of formulas for the parameters $Z\bigl(W_N^{(i)}\bigr)$: for $i=N-2^k+1$, $0\le k\le n$, and for $i=N/2-2^k+1$, $1\le k\le n-2$. The formulas require of the order of $\binom{2^{n-k}+2^k-1}{2^k}2^{2^k}$ addition operations for the first series and of the order of $\binom{2^{n-k-1}+2^k-1}{2^k}2^{2^k}$ for the second. In the cases $i=1,N/4+1,N/2+1,N$, the obtained expressions for the parameters have been simplified by computing the sums in them. We show potential generalizations for the values of $i$ in the interval $(N/4,N)$. We also study combinatorial properties of the polarizing matrix $G_N$ of a polar code with Arıkan's kernel. In particular, we establish simple recurrence relations between rows of the matrices $G_N$ and $G_{N/2}$.

Codes for Exact Support Recovery of Sparse Vectors from Inaccurate Linear Measurements and Their Decoding
M. Fernandez, G. A. Kabatiansky, S. A. Kruglik, and Y. Miao
pp. 14–21

Abstract—We construct codes that allow to exactly recover the support of an unknown sparse vector with almost equal absolute values of all nonzero coordinates given results of linear measurements in the presence of noise with $\ell_p$-norm bounded from above. We propose a decoding algorithm with asymptotically minimum complexity.

Design and Decoding of Polar Codes with Large Kernels: A Survey
P. V. Trifonov
pp. 22–40

Abstract—We present techniques for the construction of polar codes with large kernels and their decoding. A crucial problem in the implementation of the successive cancellation decoding algorithm and its derivatives is kernel processing, i.e., fast evaluation of the log-likelihood ratios for kernel input symbols. We discuss window and recursive trellis processing methods. We consider techniques for evaluation of the reliability of bit subchannels and for obtaining codes with improved distance properties.

Overparameterized Maximum Likelihood Tests for Detection of Sparse Vectors
G. K. Golubev
pp. 41–56

Abstract—We address the problem of detecting a sparse high-dimensional vector against white Gaussian noise. An unknown vector is assumed to have only $p$ nonzero components, whose positions and sizes are unknown, the number $p$ being on one hand large but on the other hand small as compared to the dimension. The maximum likelihood (ML) test in this problem has a simple form and, certainly, depends of $p$. We study statistical properties of overparametrized ML tests, i.e., those constructed based on the assumption that the number of nonzero components of the vector is $q$ ($q>p$) in a situation where the vector actually has only $p$ nonzero components. We show that in some cases overparametrized tests can be better than standard ML tests.

Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements
M. N. Vyalyi
pp. 57–62

Abstract—We construct a probabilistic polynomial algorithm for testing the satisfiability of algebraic formulas of depth 3 over the two-element field, with addition as the top operation in the formulas. An algorithm with the same characteristics exists for the problem of testing whether a polynomial given by formulas of this type is identically zero (PIT problem). However, these problems and algorithms for their solution are essentially different. The probabilistic algorithm for the PIT problem is based on the Schwartz–Zippel lemma, whereas the satisfiability testing algorithm proposed in this paper is based on the Valiant–Vazirani lemma.

Batch Poissonian Arrival Models of Multiservice Network Traffic
B. Ya. Lichtzinder, A. Yu. Privalov, and V. I. Moiseev
pp. 63–70

Abstract—The emergence of packet-switched communication networks has made it clear that Poissonian arrival flow models are not quite adequate and required the development of new models based on non-Poisson distributions. This paper is devoted to the analysis of a particular case of a batch Markovian flow, namely, batch (nonordinary) Poissonian arrivals. Such a flow is stationary and memoryless but not ordinary. We consider a class of queueing systems with constant service time. We present results of analytical computations of arrival flow parameters and also simulation results. We show that the variance of the queue depends on the third moment of the batch size in a batch Poissonian arrival flow.