PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii
Universal Code Families
V. A. Zinoviev and G. L. Katsman
pp. 95100
AbstractLet $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. 101118
AbstractGiven 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. 119131
AbstractWe 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. 132139
AbstractLet $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. 140146
AbstractA 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. 147153
AbstractTwo 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. 154162
AbstractNonparametric 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. 163175
AbstractA 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. 176185
AbstractEfficiently 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. 186193
AbstractA 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. 194198
AbstractWe 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. 199202
AbstractWe 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.