PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Reliability Function of a Binary Symmetrical Channel with Feedback
M. V. Burnashev
pp. 1–7

Abstract—We derive a new lower bound on the reliability function of a binary symmetrical channel with noiseless feedback.

On the Number of Minimum-Weight Words in Block Codes
A. A. Davydov and L. M. Tombak
pp. 7–18

Abstract—Lower bounds on the number of minimum distances are considered for arbitrary block codes of given length, size, and base. These are lower bounds on the number of minimal-weight words for distance-invariant codes containing the null word. We apply the notion of uniformly packed code and MacWilliams's transform of the distance distribution of a code to derive the conditions when these bounds are attainable. Examples of codes attaining this bound are given.

Sequential Decoding in a Channel with Spelling Errors
A. S. Dolgopolov
pp. 19–24

Abstract—The article examines automatic error correction in man-machine communication channels. A model of a channel with spelling errors is proposed and decoding rules are developed for comma codes in these channels. We consider the speedup achieved by the application of sequential decoding and report some applied findings.

Asymptotically Efficient Recursive Estimation of a Nonparametric Signal
A. P. Korostelev
pp. 25–32

Abstract—We consider the problem of asymptotically efficient (in minimax sense) estimation of a signal at the output of a linear system using noisy observations with random error of an input signal from a nonparametric function set. The sought estimator is constructed from a recursive estimator of the input signal using Tukey pseudo-values.

Nonparametric Estimation of Signals Corrupted by Noise with Sharp Peaks
L.I. Piterbarg
pp. 32–38

Abstract—Filters analogous to $L$- and $M$-estimators of an unknown location parameter of a distribution are proposed for estimating a deterministic continuous-time signal from noisy observations. Assuming white noise, we prove that the proposed estimators are asymptotically normal for a finite observation period. The estimators have finite bias and variance even when the noise is of infinite variance. Minimax optimization of the procedures is considered.

Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators
G. A. Margulis
pp. 39–46

Abstract—For every prime $p$, we construct an infinite sequence $\{Y_m\}$ of finite undirected regular graphs of degree $p+1$ such that $$ c(Y_m)\ge(4/3+o(1))\log_pn(Y_m), $$ where $c(X)$ and $n(X)$ are respectively the girth and the number of vertices in the graph $X$. We show that the graphs $\{Y_m\}$ may be applied for explicit construction of expanders and concentrators. Similar constructions are noted for regular graphs of degree $p^l+1$, where $p$ is prime and $l\ge 1$ is a natural number.

Geometrical Analysis of the Stability of Markov Chains in $\mathbb{R}_+^n$ and Its Application to Throughput Evaluation of the Adaptive Random Multiple Access Algorithm
V. A. Mikhailov
pp. 47–56

Abstract—The method of stochastic Lyapunov functions is applied to derive sufficient conditions of recurrence and nonrecurrence of Markov chains with values in a many-dimensional Euclidean space. In the two-dimensional case, the stability conditions are stated in terms of the limit mean drift vector function. The results are applied to evaluate the throughput of an adaptive random multiple access algorithm for packets in a broadcasting channel with feedback.

Ergodicity, Stability, and Insensitivity for One Class of Circuit Switching Networks
G. I. Falin
pp. 56–67

Abstract—We consider communication networks defined by a graph of arbitrary structure. The information between the calling and the called nodes is transmitted by a uniquely determined path in circuit switched mode with loss of blocked calls. We prove the theorems of ergodicity and stability of the stationary mode under broad assumptions on the probabilistic structure of the stream of arriving calls. For $M/GI$ networks we further prove insensitivity of the stationary distribution of the number of transmitted messages to the form of the transmission time distribution function with a fixed mean. We additionally investigate the asymptotic behavior of the number of transmitted calls for large stellar $M/GI$ networks.

Toward a Mathematical Theory of Hypercycles
Yu. I. Lyubich
pp. 68–78

Abstract—A theory of abstract hypercycle [Die Naturwiss., 1971, vol. 58, pp. 465–523; 1977, vol. 64, pp. 541–565; 1978, vol. 65, pp. 7–41, 341–369] is developed. A general approach to the problem of exact solutions is proposed. Local stability of cooperative choice is fully investigated.

On One Property of the Hamming Code
Yu. L. Sagalovich
pp. 79–81

Abstract—We derive a necessary and sufficient condition for correction of all byte errors of length 2 by the code formed by lengthening the extended cyclic Hamming code by one bit while preserving the parity check. The problem is shown to be noninvariant relative to various primitive polynomials generating the Hamming code.

On Ergodicity and Nonrecurrence Conditions of a Homogeneous Markov Chain in the Positive Quadrant
K. L. Vaninskii and B. V. Lazareva
pp. 82–86

Abstract—Maximally homogeneous Markov chains in the positive quadrant, first studied by Malyshev in [Dokl. Akad. Nauk SSSR, 1972, vol. 202, no. 3, pp. 526–528; Tr. Mosk. Mat. Obshch., 1979, vol. 39, pp. 3–48], play a central role in the application of the theory of Markov chains to ALOHA random multiple access systems. A theorem that provides conditions of positive recurrence and nonrecurrence of a two-dimensional maximally homogeneous chain with bounded jumps was proved in [Dokl. Akad. Nauk SSSR, 1972, vol. 202, no. 3, pp. 526–528]. In [V.A. Mikhailov, Methods of Random Multiple Access, Cand. Sci. (Tekhn.) Dissertation, Dolgoprudnyi, 1979] this result was generalized to chains whose jumps have finite second moments. The main result of this note is to prove that finiteness of only the first moments of the jumps is sufficient for Malyshev's theorem.