PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Ergodicity of Stochastic Processes Describing the Operation of Open Queueing Networks
A. N. Rybko and A. L. Stolyar
pp. 199–220

Abstract—We consider stochastic processes that model the operation of open queueing networks with calls of different types. Each call type has its own route. A new ergodicity criterion is proposed for continuous-time countable Markov chains. This criterion is applied to reduce the problem of finding the ergodicity conditions of the Markov process that describes the operation of the queueing network to the analysis of the behavior of a special (limiting) deterministic process obtained from the original process by normalization and a change of time scale. For the simplest nontrivial network of this class—a two-node network with two types of calls moving in opposite directions, the natural condition of “less than unit load at each node” is sufficient for ergodicity of the modeling Markov process under the FIFO discipline. An example of a simple priority discipline is considered for which the corresponding Markov process is nonrecurrent under this condition.

Multiple Access with Collision Resolution by Station Indices
B. S. Tsybakov, S. P. Fedortsov, and N. A. Ryleeva
pp. 221–231

Abstract—A multiple access system with collisions is considered. An efficient access algorithm is proposed which resolves collisions using station indices. The mean packet delay is determined and the algorithm is compared by delay measures with other access algorithms.

A Class of Mixed Markov Processes and Their Application in Teletraffic Theory
M. Ya. Postan
pp. 232–243

Abstract—We introduce and constructively define a class of mixed homogeneous Markov processes which, in addition to a discrete component, also contain a continuous evolving component. A system of differential equations and boundary conditions is derived for state densities and state probabilities of this process. An existence theorem is proved for the limit distribution. These stochastic processes are applied to some problems of teletraffic theory.

Asypmtotically Optimal Decision among Several Hypotheses for Nonhomogeneous Gaussian Processes
N. V. Verdenskaya
pp. 244–249

Abstract—We consider the problem of testing several simple hypotheses for a nonhomogeneous Gaussian process with different probabilities of an incorrect decision. An asymptotically optimal nonsequential decision rule is obtained assuming that the error probabilities tend to zero at an arbitrary rate. The characteristics of the decision rule are determined and it is compared with the maximum likelihood algorithm.

Exact Asymptotic Expression for the Density of Multiple Stochastic Integrals
E. I. Ostrovskii
pp. 250–257

Abstract—We consider the exact asymptotic expression for the density of multiple stochastic integrals of the form $$ I_m(h)=\int\limits_{X^m}h(x_1,x_2,\ldots,x_m)\prod_{i=1}^m Z_G(dx_i), $$ where $Z_G$ is the Gaussian orthogonal stochastic measure. In the two-dimensional case the result is general; for $m\gt 2$, the kernel $h$ is required to satisfy the orthogonal symmetry condition.

Change-Point Detection in a Linear Stochastic System from Noisy Observations
S. E. Vorobeichikov and V. V. Konev
pp. 258–264

Abstract—We consider the problem of detecting the change point in the parameters of a discrete-time multivariate stochastic process described by stochastic difference equations. Only part of the process components are observable. A sequential change-point detection procedure is proposed. Formulas are derived for the procedure characteristics: mean time between false alarms and mean change-point detection delay. The asymptotic relationship between these characteristics is established.

Sequential Experimental Design for Nonparametric Estimation of Smooth Regression Functions
G. K. Golubev
pp. 265–268

Abstract—For estimation of a function from a ball in a Sobolev space, the minimax integral mean-square error of the sequential experimental design is asymptotically not less than the equidistant design error.

Decoding of Reed–Muller Codes with a Large Number of Errors
V. M. Sidelnikov and A. S. Pershakov
pp. 269–281

Abstract—New $O(n^{r-1}N^2)$, $r\ge 2$, soft-decoding algorithms are constructed for $RM_r$ codes of order $r$ and length $N=2^n$. Although the complexity of these algorithms is somewhat higher than that of known algorithms, they almost always correct a corrupted codeword for $r=\operatorname{const}$, $n\to\infty$ when the number of errors $(1-\varepsilon)N/2$ is much greater than half the code distance. Bounds on the number of almost always corrected errors are obtained for the proposed algorithm and the minimum-distance correlation decoding algorithm. In particular, it is shown that for $r=2$ and $n\to\infty$ the proposed decoding algorithm corrects almost all errors of multiplicity $t\le(N-Cn^{1/4}N^{3/4})/2$, $C\gt\ln 4$. Experimental results on decoding of $RM_r$ codes for $r=2,3$ and $N\le 2^{10}$ indicate that the proposed algorithms are effective for a much greater number of errors than the standard majority algorithms for these codes.

Switching Discrete Sources and Their Universal Encoding
Yu. M. Shtarkov
pp. 282–296

Abstract—We consider a model of switching discrete source and its relationship to a model of a source with a finite number of states. For some sets of switching sources, we derive upper bounds on the redundancy of universal coding by the maximum probability method. The redundancy bounds are refined for various sets of sources with a finite number of states. For these sources, the bounds can be achieved by sequential coding with polynomial (in block length) complexity.

Erratum
p. 296