PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Universal Code Families
V. A. Zinoviev and G. L. Katsman
pp. 95–100

Abstract—Let $E$ be a finite alphabet of $q$ elements and let $U_i$ be a subset of $E^n$, i.e., a $q$-ary code of length $n$ with a certain minimum Hamming distance $d_i=d(U_i)$. We call a family of such codes $U_1,\dots,U_s$ of length $n$ with distances $d_1,\dots, d_s$ universal if for any $i,j\in\{1,\dots, s\}$, $i\ne j$, and any code vectors $u\in U_i$, $u'\in U_j$, the distance $d(u,u')$ between them satisfies the condition $$ d(u,u')\ge (d_i+d_j)/2. $$ We construct asymptotically optimal universal code families.

Spectrum Invariancy Under Output Approximation for Full-Rank Discrete Memoryless Channels
T. S. Han and S. Verdú
pp. 101–118

Abstract—Given a channel, the resolvability of an input process is the minimum randomness of those input processes whose output statistics approximate the original output statistics with arbitrary accuracy. We give a formula for the resolvability of any input process when the channel is full-rank discrete memoryless. When the input process is stationary and ergodic, its resolvability is equal to its mutual information rate. This result is obtained as a corollary of a theorem that shows that if two input processes result in approximately the same output statistics, then their corresponding information spectra (distributions of normalized information density) are almost identical.

Distance Spectra of Lattice-Based Codes
A. N. Trofimov
pp. 119–131

Abstract—We consider the problem of finding the distance spectrum for a finite subset of a lattice. As basic examples of such subsets, we consider the codes with constant norm (spherical codes) and the codes with bounded norm (spherical clusters). The problem is solved using the extended lattice generating function. The computational results for particular examples are presented. The asymptotics of the distance spectrum is investigated.

New Bounds for the Minimum Length of Binary Linear Block Codes
S. M. Dodunekov, S. B. Encheva, and A. N. Ivanov
pp. 132–139

Abstract—Let $n(k,d)$ be the smallest integer $n$ for which a binary linear code of length $n$, dimension $k$ and minimum distance $d$ exists. We prove that $n(9,24)\ge 54$, $n(9,28)\ge 62$, $n(9,30)\ge 66$, $n(9,56)\ge 117$, $n(10,44)\ge 95$, $n(10,60)\ge 125$, $n(13,56)\ge 122$, $n(14,48)\ge 107$ and review known results for $n(9,d)$.

A New Version of the Creeper Algorithm
S. A. Popov
pp. 140–146

Abstract—A new modification of the creeper algorithm, which presents a further development of this kind of algorithm, is described. We also compare the algorithm with known sequential decoding procedures.

Branch and Bound Method for Design of Recurrent Signal Reception Algorithms
S. A. Belous and D. D. Klovsky
pp. 147–153

Abstract—Two algorithms of recurrent-signal reception (for the maximum likelihood metric and that of Fano) are synthesized with the branch and bound technique. These two algorithms require a moderate amount of memory. In their computational performance they are inferior only to the stack-algorithm of Zigangirov.

Empirical Spectral and Bispectral Analyses of Periodically Nonstationary Stochastic Processes
V. G. Alekseev
pp. 154–162

Abstract—Nonparametric estimates of spectral and bispectral densities are constructed and investigated for a periodically nonstationary (in the narrow sense) stochastic process $\xi(t)$ with mean $\operatorname{\bf E}\xi(t)\equiv 0$.

On a Random Process in the Multiple Access Problems
B. S. Tsybakov
pp. 163–175

Abstract—A random process that is reasonable to use in multiple access problems is presented.

Lower Bounds of Connectedness Probability for Some Classes of Random Graphs
V. P. Polessky
pp. 176–185

Abstract—Efficiently computable lower bounds of connectedness probability for classes of random graphs generated by 2-connected multigraphs with frameness or forestness 2 are established.

Algorithmic Approach to the Prediction Problem
B. Ya. Ryabko
pp. 186–193

Abstract—A problem on prediction of the elements of an arbitrary sequence $x_1 x_2 x_3\dots$ is considered; the element $x_{t+1}$ is to be predicted from $x_1 x_2\dots x_t$. No assumption is made about the probability structure of the sequence. The game-theoretic approach proposed by J. Kelly is used; the prediction efficiency is estimated by a gain value in a certain game. The relation of the maximal gain value to the Kolmogorov complexity is found. The Hausdorff dimension of the sets of effectively predictable sequences is also estimated. An optimal method of prediction is found for the class of finite automata.

Lower Bound on the Probability of Successful Substitution of Messages
L. A. Bassalygo
pp. 194–198

Abstract—We prove that the probability of successful substitution of messages for the optimal strategy is not less than $K^{-1/2}$ for an arbitrary probability distribution of messages provided the probability of each message is less than or equal to $1/2$. Here $K$ is the number of keys.

New Upper Bounds on Cardinality of Separating Systems
Yu. L. Sagalovich
pp. 199–202

Abstract—We give a survey of all presently existing upper and lower bounds for $(2,2)$ separating systems obtained by the author. In this paper we obtain updated values of the upper bounds using the best known upper bounds for error-correcting block codes.