PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels
A. G. D'yachkov and D. Yu. Goshkoder
pp. 301–320

Abstract—The aim of the paper is to revive and develop results of an unpublished manuscript of A.G. D'yachkov. We consider a discrete memoryless channel (DMC) and prove a theorem on the exponential expurgation bound for list decoding with fixed list size $L$. This result is an extension of the classical exponential error probability bound for optimal codes over a DMC to the list decoding model over a DMC. As applications of this result, we consider a memoryless binary symmetric channel (BSC) and a memoryless binary asymmetric channel (Z-channel). For the both channels, we derive a lower bound on the fraction of correctable errors for zero-rate transmission over the corresponding channels under list decoding with a fixed list size $L$ at the channel output. For the Z-channel, we obtain this bound for an arbitrary input alphabet distribution $(1-w,w)$; we also find the optimum value of the obtained bound and prove that the fraction of errors correctable by an optimal code tends to  1 as the list size $L$ tends to infinity.

On the Maximum $f$-Divergence of Probability Distributions Given the Value of Their Coupling
V. V. Prelov
pp. 321–330

Abstract—The paper is a supplement to the author's paper [1]. Here we present explicit upper bounds (which are optimal in some cases) on the maximum value of the $f$-divergence $D_f(P\,\|\, Q)$ of discrete probability distributions $P$ and $Q$ provided that the distribution $Q$ (or its minimal component $q_{\min}$) and the value of the coupling of $P$ and $Q$ are fixed. We also obtain an explicit expression for the maximum value of the divergence $D_f(P\,\|\, Q)$ provided that only the value of the coupling of $P$ and $Q$ is given. Results of [1] concerning the Kullback–Leibler divergence and $\chi^2$-divergence are particular cases of the results proved in the present paper.

On the Generalized Concatenated Construction for the Nordstrom–Robinson Code and the Binary Golay Code
V. A. Zinoviev and D. V. Zinoviev
pp. 331–340

Abstract—We show that the Nordstrom–Robinson code and the extended binary Golay code are generalized concatenated codes of order 3.

On List Decoding of Certain $\mathbb{F}_q$-Linear Codes
N. A. Polyanskii
pp. 341–356

Abstract—We present a list decoding algorithm for $\mathbb{F}_q$-linear codes that generalize the Reed–Solomon $s$-codes.

On Intersections of Reed–Muller Like Codes
F. I. Solov'eva
pp. 357–367

Abstract—A binary code that has the parameters and possesses the main properties of the classical $r$th-order Reed–Muller code $RM_{r,m}$ will be called an $r$th-order Reed–Muller like code and will be denoted by $LRM_{r,m}$. The class of such codes contains the family of codes obtained by the Pulatov construction and also classical linear and $\mathbb{Z}_4$-linear Reed–Muller codes. We analyze the intersection problem for the Reed–Muller like codes. We prove that for any even $k$ in the interval $0\le k\le 2^{2\sum\limits_{i=0}^{r-1}\binom{m-1}{i}}$ there exist $LRM_{r,m}$ codes of order $r$ and length $2^m$ having intersection size $k$. We also prove that there exist two Reed–Muller like codes of order $r$ and length $2^m$ whose intersection size is $2k_1 k_2$ with $1\le k_s\le |RM_{r-1,m-1}|$, $s\in\{1,2\}$, for any admissible length starting from 16.

On Data Compression and Recovery for Sequences Using Constraints on the Spectrum Range
N. G. Dokuchaev
pp. 368–372

Abstract—We investigate the possibility of data recovery for finite sequences with constraints on their spectrum defined by a special discretization of the spectrum range. These sequences are dense in the space of all sequences. We show that uniqueness sets for them can be singletons.

New Turán Type Bounds for Johnson Graphs
N. A. Dubinin
pp. 373–379

Abstract—We obtain a new bound on the number of edges in induced subgraphs of Johnson graphs.

New Modularity Bounds for Graphs $G(n,r,s)$ and $G_p(n,r,s)$
N. M. Derevyanko and M. M. Koshelev
pp. 380–401

Abstract—We analyze the behavior of the modularity of $G(n,r,s)$ graphs in the case of $r=o(\sqrt{{n}})$ and $n\to\infty$ and also that of $G_p(n,r,s)$ graphs for fixed $r$ and $s$ as $n\to\infty$. For $G(n,r,s)$ graphs with $r\ge cs^2$, we obtain substantial improvements of previously known upper bounds. Upper and lower bounds previously obtained for $G(n,r,s)$ graphs are extended to the family of $G_p(n,r,s)$ graphs with $p=p(n)=\omega\bigl(n^{-\frac{r-s-1}{2}}\bigr)$ and fixed $r$ and $s$.