PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Concatenated Decoding Algorithm with Incomplete Inspection of Code Vectors
A. M. Barg and I. I. Dumer
pp. 1–7

Abstract—The authors consider a decoding algorithm for concatenated codes in binary symmetrical memoryless channels (BSC), for which the error probability does not exceed twice the maximum-likelihood decoding error probability, while the complexity of implementation has the smallest known exponent in the class of codes that meet the Varshamov–Gilbert bound. The proposed algorithm is a modification of the concatenated list decoding algorithm of Zyablov and Pinsker [Probl. Peredachi Inf., 1981, vol. 17, no. 4, pp. 29–33].

Bounds for Codes in the Case of Finite-Volume List Decoding
V. M. Blinovskii
pp. 7–19

Abstract—The author obtains asymptotic upper and lower bounds for the cardinality of a binary code that is decoded by a list of fixed volume, for the case in which the average radius or radius of the decoding sphere of the code is specified. The resultant bounds are asymptotically exact in the case of zero rate.

Noise-Stable Encoding of “Unique” Messages
V. I. Korzhik
pp. 19–24

Abstract—The author defines the concepts of unique message, which can be reconstructed by the recipient by means of total inspection. To abridge the inspection process, noise-stable encoding of the message, transmission over a channel, and list decoding, is performed. An optimal list-decoding algorithm for linear codes, bounds for the error probabilities, and constructive decoding methods, are investigated.

Robust Filtration of Random Fields
L. I. Piterbarg
pp. 24–30

Abstract—For one type of nonlinear filtration of random fields on a plane, the author establishes the degree of proximity of the statistical characteristics of the input and output signals for the case of a filtration window of small area. The resultant limiting relations are unaltered if a random flux of “pikes” is superimposed on the input signal.

On the Behavior of Moments of Arbitrary Order of Multivariate Stochastic Approximation Processes
E. Kh. Mustafaev and M. B. Nevel'son
pp. 30–37

Abstract—Papers [J. Komlós and P. Révész, Stud. Sci. Math. Hung., 1973, no. 8, pp. 329–340; M.B. Nevel'son, Avtomat. Telemekh., 1973, no. 2, pp. 83–92] proposed modification of the univariate or one-dimensional Robbins–Monro (RM) procedure, which possess bounded moments of some particular order under proper normalization. It was assumed in these studies that the modulus of the regression function is bounded from below for all sufficiently large values of the modulus of the argument. This condition was subsequently removed in [M.B. Nevel'son, Properties of moments of stochastic approximation processes, Teor. Veroyatn. Primen., 1984]. In this paper, which generalizes the results of [Nevel'son, Teor. Veroyatn. Primen., 1984], we propose a method of investigating the moments of arbitrary order of a truncated KM procedure, that enables us also to consider vector-valued regression functions that decrease as the modulus of the argument increases.

Gaussian Diffusion Approximation of Closed Markov Models of Computer Networks
Ya. A. Kogan, R. Sh. Liptser, and A. V. Smorodinskii
pp. 38–51

Abstract—The authors consider a model of a computer network in which (because of the flow control mechanism that is selected) there are always $N$ messages. The model is described by a closed network of queues that form a multivariate birth and death process. Under conditions of heavy traffic, it is shown that as $N\to\infty$, the queue length vector, normed by the number $N$, converges uniformly in probability to the solution of a system of differential equations, while deviations of the queue lengths of order $\sqrt{N}$ from a deterministic limit converge weakly to a Gaussian diffusion process. The martingale methods of proof that are employed yield results under very natural constraints.

Capacity Region for Circuit-Switched Networks
A. N. Rybko and V. A. Mikhailov
pp. 51–66

Abstract—The authors obtain necessary and also sufficient ergodicity conditions for the Markov processes describing the operation of circuit-switched networks with queues. The region of values of the continuous parameters, intensities of message arrival, and average message servicing times for which these processes are ergodic is called the capacity region of the network.

Variances and Covariances of Statistical Estimates of the Characteristics of Semi-Markov Systems with a Finite Set of States
E. I. Shkol'nyi
pp. 67–76

Abstract—The author proves the central limit theorem for the vector of statistical estimates of a semi-Markov process with a finite set of states. The estimates are in the form of ratios of accumulation processes. Formulas are obtained for the covariances of the estimates in the form of functions of one-step random variables of a semi-Markov process in the general case and in particular cases.

Lower Bound on the Ensemble Average Error Probability in a Multiple Access Channel
A. G. Dyachkov
pp. 98–103 (Russian issue)

Abstract—Developing the methods of [R.G. Gallager, IEEE Trans. Inf. Theory, 1973, vol. 19, no. 22, pp. 244–246; A.G. D'yachkov, Probl. Peredachi Inf., 1980, vol. 16, no. 2, pp. 18–24; 1979, vol. 15, no. 2, pp. 23–35; A.G. D'yachkov and G.Sh. Poltyrev, Probl. Upravl. Teor. Inf., 1982, vol. 11, no. 5, pp. 365–372], we construct a lower asymptotic bound on the ensemble error probability of maximum likelihood decoding for a multiple access channel. This bound allows us to find a range of rates where the known upper bound [H. Liao, PhD Thesis, Univ. of Hawaii, 1972] is asymptotically tight.

Multi-Threshold Decoding
V. V. Zolotarev
pp. 104–109 (Russian issue)

Abstract—We consider a multiple adjustment algorithm for a random-error-correcting majority decoder. Simulation results of the decoder operation in a memoryless BSC are presented.