PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Successive Cancellation Decoding of Reed–Solomon Codes
P. V. Trifonov
pp. 303–312

Abstract—A novel soft-decision decoding algorithm for Reed–Solomon codes over $GF(2^m)$ is proposed, which is based on representing them as polar codes with dynamic frozen symbols and applying the successive cancellation method. A further performance improvement is obtained by exploiting multiple permutations of codewords which are taken from the automorphism group of Reed–Muller codes. It is also shown that the proposed algorithm can be simplified in the case of decoding a binary image of the Reed–Solomon code.

Optimal Almost Equisymbol Codes Based on Difference Matrices
L. A. Bassalygo and V. A. Zinoviev
pp. 313–319

Abstract—A method for constructing optimal almost equisymbol codes based on difference matrices is proposed. Some of these codes generate previously unknown optimal equidistant codes satisfying the Plotkin bound. As a consequence, they generate new resolvable balanced incomplete block designs.

Upper Bounds on the Smallest Size of a Complete Arc in $PG(2,q)$ under a Certain Probabilistic Conjecture
D. Bartoli, A. A. Davydov, G. Faina, A. A. Kreshchuk, S. Marcugini, and F. Pambianco
pp. 320–339

Abstract—In the projective plane $PG(2,q)$, we consider an iterative construction of complete arcs which adds a new point in each step. It is proved that uncovered points are uniformly distributed over the plane. For more than half of steps of the iterative process, we prove an estimate for the number of newly covered points in every step. A natural (and well-founded) conjecture is made that the estimate holds for the other steps too. As a result, we obtain upper bounds on the smallest size $t_2(2,q)$ of a complete arc in $PG(2,q)$, in particular, \begin{align*} & t_2(2,q)<\sqrt{q}\sqrt{3\ln q+\ln \ln q+\ln 3}+\smash[b]{\sqrt{\frac{q}{3\ln q}}+3},\\ & t_2(2,q)<1.87\sqrt{q\ln q}. \end{align*} Nonstandard types of upper bounds on $t_2(2,q)$ are considered, one of them being new. The effectiveness of the new bounds is illustrated by comparing them with the smallest known sizes of complete arcs obtained in recent works of the authors and in the present paper via computer search in a wide region of $q$. We note a connection of the considered problems with the so-called birthday problem (or birthday paradox).

Minimum Number of Edges in a Hypergraph Guaranteeing a Perfect Fractional Matching and the MMS Conjecture
V. M. Blinovsky
pp. 340–349

Abstract—In this paper we prove the Ahlswede–Khachatrian conjecture [1], up to a finite number of cases, which can be checked using modern computers. This conjecture implies the conjecture from [2], and the Manickam–Miklós–Singhi conjecture.

Interlacing and Smoothing: Combinatorial Aspects
M. L. Blank
pp. 350–363

Abstract—We study functional consequences of the interlacing property consisting in that a new configuration of “particles” occurs in gaps between elements of a previous configuration. This property was introduced by I.M. Gelfand in terms of spectra of sequences of matrices of increasing dimensions and turned out to be highly needed in many areas of modern mathematics. We examine conditions under which the next generation is “on average smoother” than the previous one and discuss issues related to “complexity” of the set of pairs of interlacing functions.

On the Number of 1-Factorizations of a Complete Graph
D. V. Zinoviev
pp. 364–370

Abstract—We study 1-factorizations of a complete graph with $n$ vertices. The lower bound on the number of such factorizations is refined. A new proof of the upper bound is given.

Gaussian Ornstein–Uhlenbeck and Bogoliubov Processes: Asymptotics of Small Deviations for $L^p$-Functionals, $0\lt p\lt\infty$
V. R. Fatalov
pp. 371–389

Abstract—We prove results on sharp asymptotics of probabilities $$ \mathbf{P} \Biggl\{\int\limits_0^1 |X(t)|^p\,dt<\varepsilon^p \Biggr\},\quad \varepsilon\to0, $$ where $0\lt p\lt\infty$, for three Gaussian processes $X(t)$, namely the stationary and nonstationary Ornstein–Uhlenbeck process and the Bogoliubov process. The analysis is based on the Laplace method for sojourn times of a Wiener process.

Universal Coding for Memoryless Sources with Countably Infinite Alphabets
B. D. Kudryashov and A. V. Porov
pp. 390–399

Abstract—We present an asymptotically efficient coding strategy for a stationary countably infinite source determined over a set of nonnegative integers. If the $k$th moment $\mu_k$ of the source data is finite, then asymptotic average coding redundancy for length-$n$ blocks, $n\to\infty$, is upper bounded by $C\left(\log n/n\right)^{k/(k+1)}$, where $C$ is a nonnegative constant. The coding efficiency is demonstrated via an example of scalar quantization of random variables with generalized Gaussian distribution.