PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Separating Codes and a New Combinatorial Search Model
V. S. Lebedev
pp. 1–6

Abstract—We propose a new group testing model, which is related to separating codes and cover-free codes.

On Volumes of Spheres for the Stem Distance
A. N. Voronina
pp. 7–16

Abstract—For any two $q$-ary sequences $\boldsymbol{x}$ and $\boldsymbol{y}$, the stem similarity between them is defined as a total number of stems (blocks of length 2 consisting of adjacent elements of $\boldsymbol{x}$ and $\boldsymbol{y}$) in their longest common Hamming subsequence. For $q=4$ this similarity function and the corresponding distance function arise in molecular biology in describing an additive mathematical model of thermodynamic distance between DNA sequences. In the present paper, we derive explicit formulas for sphere sizes in this metric and consider their asymptotics in the case of spheres of a constant radius. Based on these results, we also obtain a random coding bound and Hamming bound for the optimal size of the so-called DNA codes for the case of a constant distance.

Binary Perfect and Extended Perfect Codes of Lengths 15 and 16 and of Ranks 13 and 14
V. A. Zinoviev and D. V. Zinoviev
pp. 17–21

Abstract—Inaccuracies in computations in the paper of the authors on classification of perfect binary codes of lengths $15$ and $16$ and of rank $13$ are fixed. An explicit construction of all extended perfect codes of length $16$ and rank $13$ with a given kernel size is presented. Perfect binary codes of length $15$ and rank $14$ obtained by the general doubling construction are classified.

Nonparametric Semirecursive Identification in a Wide Sense of Strong Mixing Processes
A. V. Kitaeva and G. M. Koshkin
pp. 22–37

Abstract—We find principal parts of asymptotic mean-square errors of semirecursive nonparametric estimators of functionals of a multidimensional density function under the assumption that observations satisfy a strong mixing condition. Results are illustrated by an example of a nonlinear autoregression process.

Stability of Properties of Kolmogorov Complexity under Relativization
An. A. Muchnik^† and A. E. Romashchenko
pp. 38–61

Abstract—Assume that a tuple of binary strings $\bar a =\langle a_1,\ldots,a_n\rangle$ has negligible mutual information with another string $b$. Does this mean that properties of the Kolmogorov complexity of $\bar a$ do not change significantly if we relativize them to $b$? This question becomes very nontrivial when we try to formalize it. In this paper we investigate this problem for a special class of properties (for properties that can be expressed by an $\exists$-formula). In particular, we show that a random (conditional on $\bar a$) oracle $b$ does not help to extract common information from the strings $a_i$.

Small Deviations for Two Classes of Gaussian Stationary Processes and $L^p$-Functionals, $0\lt p\le\infty$
V. R. Fatalov
pp. 62–85

Abstract—Let $w(t)$ be a standard Wiener process, $w(0)=0$, and let $\eta_a(t)=w(t+a)-w(t)$, $t\ge 0$, be increments of the Wiener process, $a\gt 0$. Let $Z_a(t)$, $t\in[0, 2a]$, be a zero-mean Gaussian stationary a.s. continuous process with a covariance function of the form $\operatorname{\bf E} Z_a(t) Z_a(s)={\displaystyle\frac 1 2} [a-|t-s|]$, $t, s\in [0, 2a]$. For $0\lt p\lt\infty$, we prove results on sharp asymptotics as $\varepsilon\to 0$ of the probabilities $$ \operatorname{\bf P} \left\{\int\limits_0^T |\eta_a(t)|^p \,dt\le \varepsilon^p\right\} \quad \mbox{for}\ T\le a,\qquad \operatorname{\bf P} \left\{\int\limits_0^T |Z_a(t)|^p \,dt\le \varepsilon^p\right\}\quad \mbox{for}\ T<2a, $$ and compute similar asymptotics for the sup-norm. Derivation of the results is based on the method of comparing with a Wiener process. We present numerical values of the asymptotics in the case $p=1$, $p=2$, and for the sup-norm. We also consider application of the obtained results to one functional quantization problem of information theory.

Method of Asymptotic Semiinvariants for Studying a Mathematical Model of a Random Access Network
A. A. Nazarov and E. A. Sudyko
pp. 86–102

Abstract—To study a mathematical model of a random access network with a finite number of sources, retrials, and a conflict warning stage, we propose a method of asymptotic semiinvariants under a growing number of sources, which allows us to find the asymptotic probability distribution of the number of requests in a retrial pool. We present results of numerical implementation of a prelimit distribution of the number of requests in the retrial pool. We compare the prelimit and asymptotic semiinvariants.