PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Normalized Information-Based Divergences
J.-F. Coeurjolly, R. Drouilhet, and J.-F. Robineau
pp. 167–189

Abstract—This paper is devoted to the mathematical study of some divergences based on mutual information which are well suited to categorical random vectors. These divergences are generalizations of the “entropy distance” and “information distance.” Their main characteristic is that they combine a complexity term and the mutual information. We then introduce the notion of (normalized) information-based divergence, propose several examples, and discuss their mathematical properties, in particular, in some prediction framework.

Interpolation in List Decoding of Reed–Solomon Codes
P. V. Trifonov
pp. 190–198

Abstract—We consider the problem of efficient implementation of two-dimensional interpolation in the Guruswami–Sudan list decoding algorithm for Reed–Solomon codes. We show that it can be implemented by computing the product of ideals of interpolation polynomials constructed for subsets of interpolation points. A method for fast multiplication of coprime zero-dimensional ideals is proposed.

Conflict-Avoiding Codes and Cyclic Triple Systems
V. I. Levenshtein
pp. 199–212

Abstract—The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length $n$ and Hamming weight $3$ and having the following property: any $3\times n$ matrix whose rows are cyclic shifts of three different code vectors contains a $3\times 3$ permutation matrix as a submatrix. This property (in the special case $w=3$) characterizes conflict-avoiding codes of length $n$ for $w$ active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of $w$ active users to transmit a data packet successfully in one of $w$ attempts during $n$ time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length $n$ with $w=3$ is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for $w=3$ which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.

Tilings of Nonorientable Surfaces by Steiner Triple Systems
F. I. Solov'eva
pp. 213–224

Abstract—A Steiner triple system of order $n$ (for short, $\operatorname{STS}(n)$) is a system of three-element blocks (triples) of elements of an $n$-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple $(i,j,k)\in\operatorname{STS}(n)$ a topological triangle with vertices $i$, $j$, and $k$. Gluing together like sides of the triangles that correspond to a pair of disjoint $\operatorname{STS}(n)$ of a special form yields a black-and-white tiling of some closed surface. For each $n\equiv 3\pmod 6$ we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order $n$. We also show that for half of the values $n\equiv 1\pmod 6$ there are nonisomorphic tilings of nonorientable closed surfaces.

List Decoding of the First-Order Binary Reed–Muller Codes
I. I. Dumer, G.A. Kabatiansky, and C. Tavernier
pp. 225–232

Abstract—A list decoding algorithm is designed for the first-order binary Reed–Muller codes of length $n$ that reconstructs all codewords located within the ball of radius $\displaystyle\frac{n}{2}(1-\varepsilon)$ about the received vector and has the complexity of $\smash[t]{O(n\ln^{2}(\min \{\varepsilon^{-2},n\}))}$ binary operations.

Exact Asymptotics of Distributions of Integral Functionals of the Geometric Brownian Motion and Other Related Formulas
V. R. Fatalov
pp. 233–254

Abstract—We prove results on exact asymptotics of the probabilities $$ \operatorname{\bf P}\Biggl\{\int\limits_0^1 e^{\varepsilon \xi(t)}\,dt\gt b\Biggr\},\quad \operatorname{\bf P} \Biggl\{\int\limits_0^1 e^{\varepsilon |\xi(t)|}\,dt\gt b\Biggr\},\quad \varepsilon\to 0, $$ where $b\gt1$, for two Gaussian processes $\xi(t)$, namely, a Wiener process and a Brownian bridge. We use the Laplace method for Gaussian measures in Banach spaces. Evaluation of constants is reduced to solving an extreme value problem for the rate function and studying the spectrum of a second-order differential operator of the Sturm–Liouville type with the use of Legendre functions.

Modal Logics of Some Geometrical Structures
I. B. Shapirovsky
pp. 255–262

Abstract—We study modal logics of regions in a real space ordered by the inclusion and compact inclusion relations. For various systems of regions, we propose complete finite modal axiomatizations; the described logics are finitely approximable and PSPACE-complete.

Multi-Access System with Many Users: Stability and Metastability
N. D. Vvedenskaya and Yu. M. Suhov
pp. 263–269

Abstract—A model of random multi-access system with an ALOHA-type protocol is analyzed when the number $N$ of users is large and the system is overloaded. In the limit as $N\to\infty$, the behavior of the system is described by a nonrandom dynamical system. We give a condition for the dynamical system to have an attractive fixed point and outline cases of several fixed points. The presence of several fixed points indicates that the finite system may exhibit a metastability phenomenon.