PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Nonstochastic Objects
V. V. V'yugin
pp. 77–83

Abstract—According to Kolmogorov, a finite object $x$ is called $(\alpha,\beta)$-stochastic, i.e., it satisfies stochastic dependences, if there exists a finite set $A$ such that $x\in A$, $K(A)\leq\alpha$ and $K(x)\geq\log_2|A|-\beta$, where $K$ is the ordinary Kolmogorov entropy (complexity), and $|A|$ is the number of elements of a set $A$. To define the concept of quasi-Kolmogorov stochasticity, the author examines the problem of the proportion of sequences that are not $(\alpha,\beta)$-stochastic. The principal results are as follows: Upper and lower bounds are obtained for the a priori countable measure of all sequences of length $n$ ($\geq n$) that are not $(\alpha,\beta)$-stochastic.

On Code Distances of Some Classes of $(p,p)$-Codes
B. Brindza
pp. 83–91

Abstract—The author derives an exact formula for the code distance of the direct sum of three minimal ideals of the group algebra of group $G=(a)\times(b)$, $a^p=b^p=1$, over a field of characteristic $2$ for primes $p$ of the form $4t-1$. The proposed method of proof yields an efficient way of calculating the elements of the code of minimal nonzero weight.

New Upper Bounds for Decoding Error Probability for Convolutional Codes
K. Sh. Zigangirov
pp. 92–101

Abstract—The author obtains new random-coding bounds for the probability of incorrect decoding of convolutional codes. They are in the nature of the product of the code limitation of the term, exponential with respect to length (with optimal exponent), and a constant.

Statistical Synthesis of Optimal Processing Algorithms for Series of Atmospherically Distorted “Speckle” Images of Astronomical Objects
P. A. Bakut, S. D. Pol'skikh, A. D. Ryakhin, K. N. Sviridov, and N. D. Ustinov
pp. 102–110

Abstract—The authors propose and investigate a statistical model of the spatial spectrum of a “speckle” image of an astronomical object. This model is used as a basis for obtaining the maximum-likelihood equation for estimating the spatial spectrum of the object on the basis of a series of speckle images. Analytic solution of the maximum-likelihood equation for the case of observation of bright and weak astronomical objects leads to synthesis of algorithms for optimal estimation of the square of the modulus and phase of the spatial spectrum of the object. The conditions are determined under which the quasioptimal Labeyrie and Knox–Thompson methods coincide with the synthesized ones and become optimal. Ways of optimally modifying quasioptimal methods are indicated.

On Spectral Density Estimates for Some Models of Stationary Stochastic Processes
V. G. Alekseev
pp. 110–116

Abstract—The article describes numerical experiments aimed at calculating the spectral densities of two models of stationary stochastic processes on the basis of samples consisting of $n=2^{11}$ readings each. The effect on estimation quality of multiplying out the realization by some data window that smoothes the edges of the realization and of using the higher-order weighting functions proposed by the author in [Probl. Peredachi Inf., 1973, vol. 9, no. 4, pp. 42–48; 1980, vol. 16, no. 1, pp. 42–49; Comput. Appl. Math., no. 44, Vishcha Shkola, Kiev, 1981, pp. 32–40] is investigated.

Uniform Estimation of an Unknown Probability Distribution Density
M. B. Nevel'son
pp. 117–124

Abstract—Independent observations with common probability distribution density are used as a basis for constructing estimates of this density that converge with probability 1 in the metrics of the corresponding normed spaces, uniformly with respect to natural classes of distributions. Similar estimates can be constructed in the case in which an interfering parameter is present in the observation.

On Properties of Estimation Algorithms for Binary Sequences
S. T. Grinchenko and N. D. Tarankova
pp. 125–134

Abstract—The authors investigate the quality of current and interpolation estimation algorithms for binary sequences, characterized by the average error probability per symbol. The elements of a binary sequence are generated by a Markov source and are observed against a background of mod 2 noise. General conditions for singlet decoding are given.

Some New Random Multiple-Access Algorithms
B. S. Tsybakov and N. B. Likhanov
pp. 134–153

Abstract—The authors propose random multiple-access algorithms with rates all the way to 0.487, the algorithms being independent of the previous history. The delays and the coefficients of variability are calculated for algorithms of practical interest with initial delays on the order of one or two packet lengths, and rates in the range 0.419–0.475.

Analysis of a Fully Connected Message-Switching Communication Network with a Large Number of Nodes, Bypass Routes, and a Limited Number of Waiting Places at Nodes
V. V. Marbukh
pp. 154–161

Abstract—The author obtains the asymptotic values as $N\to\infty$ of some characteristics of a fully connected message-switching network with $N$ nodes, bypass routes, and a limited number of waiting places at nodes. It is shown that there is a “phase transition of the first kind” in the network as $N\to\infty$. The interrelationship between the phase transition and purposeful load-limiting discipline as $N\to\infty$ is considered. The results are obtained under the assumption that as $N\to\infty$ the queues at the nodes are statistically independent and can be approximated by queues in $M|M|1$ queuing systems with a limited number of waiting-places and with intensities of the incoming flows determined from the self-consistency conditions.

Necessary and Sufficient Conditions for Recurrency of a Markov System in Terms of Liapunov Functions
V. A. Lazarev
pp. 99–102 (Russian issue)

Abstract—We prove the existence of an auxiliary function for a recurrent time-homogeneous Markov chain with a countable number of states. This function is found as the expectation of a certain function defined on trajectories of the process.

Optimum Codes Correcting Lattice Errors
E. M. Gabidulin
pp. 103–108 (Russian issue)

Abstract—In binary transmission through a system of parallel channels, a message can be viewed as a $(0,1)$-matrix of size $N\times n$, where $N$ is the number of channels and $n$ is the transmission length. We describe a construction of optimal codes which correct any error located in $m$ rows and $s$ columns (lattice errors) provided that $m+s\leq t$, where $t$ is the error-correcting capability of the code.