PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Maximum-Likelihood List Decoding Using Trellises
V. V. Zyablov, V. G. Potapov, and V. R. Sidorenko
pp. 299–305

Abstract—Let the Viterbi algorithm be applied for maximum-likelihood decoding of a block code or a terminated convolutional code using a code trellis. We propose an additional procedure that constructs a list of $L$ most likely code words, rather than a single estimate. The procedure uses information from the Viterbi decoder. The complexity of the procedure is of order $nL(L+t)$, where $n$ is the length of a codeword, $t$ is the number of branches that enter one node of the code trellis, $L\ll n$.

Generalized Convolutional-Block Concatenated Constructions Based on 4FM Signals
V. V. Zyablov and S. A. Shavgulidze
pp. 306–312

Abstract—We consider various concatenated and generalized concatenated coded modulation constructions with inner convolutional codes and outer Reed–Solomon codes. We study questions of their combination with signals of the quaternary phase modulation and investigate their probabilistic and energy performance in Gaussian communication channels.

Decoding Complexity of Linear Block Codes
S. V. Fedorenko
pp. 313–317

Abstract—We suggest a method of constructing a nonrandom covering with complexity asymptotically equal to the size of this covering. We also present an implementation of a nonprobabilistic decoding algorithm with nonexponential space complexity.

Nonparametric Recursive Estimation in Nonlinear ARX Models
P. Doukhan and A. B. Tsybakov
pp. 318–327

Abstract—Consider the general $\operatorname{ARX}(k, q)$ nonlinear process defined by the recurrence relation $y_n=f(y_{n-1},\dots, y_{n-k},x_n,\dots,x_{n-q+1}) + \xi_n$, where $\{x_n\}$, $\{\xi_n\}$ are sequences of independent identically distributed random variables. We propose a recursive nonparametric estimator of the function $f$ and we prove its strong consistency under general assumptions on the model. We study the model properties guaranteeing that these assumptions are satisfied.

Method of Averaging Along Trajectories in Passive Stochastic Approximation (Linear Algorithm)
A. V. Nazin and P. S. Shcherbakov
pp. 328–338

Abstract—The problem of the recursive estimation of a root of a regression equation is considered in the situation of a passive experiment. The asymptotic behavior of kernel estimates of a stochastic approximation type with averaging along trajectories is studied. The asymptotic normality and optimality of such estimates are established in the class of algorithms without transformation of observations.

A Method for Differentiating Functions With Finite Domain of Definition on the Basis of Spline-Extensions and the Kotelnikov Series
Yu. G. Bulychev and I. V. Burlai
pp. 339–349

Abstract—We propose a unified matrix-differential approach to synthesis of messages with a finite spectrum and to $N$-time differentiation of such messages. This approach is based on spline-extensions and the Kotelnikov series with a finite number of terms. It provides high numerical stability with respect to systematic and random errors.

Lower Bounds on Full Rank Probability in Random Matroids
V. P. Polesskii
pp. 350–357

Abstract—Let $M$ be a matroid on the set $E$ whose elements are missing jointly independently with probability $q$. The probability $P(M,q)$ of full rank of a random matroid $(M,q)$ is the probability that the random set $(E,q)$ contains a base of this matroid. It is proved that every partition of $E$ into independent sets of $M$ that contains a base of $M$ generates an effectively computable lower estimate of $P(M,q)$ in terms of the conjugate partition. A partition that yields the best such estimate is determined.

Packet Delay in a DQDB Network
B. S. Tsybakov and A. Yu. Privalov
pp. 358–380

Abstract—A mathematical model of a station acting in a network with distributed queue and dual bus (DQDB) is considered. A stability condition and the average packet delay are found for the model. Numerical calculations are made for a network with 10 and 100 stations.

Generalized Information-Set Decoding of $(L,g)$-codes
E. T. Mironchikov and S. V. Fedorenko
pp. 381–385

Abstract—We describe a decoding of $(L,g)$-codes (generalized Goppa codes) via iterated decoding of their shortenings that also belong to the class of $(L,g)$-codes. We give a decoding algorithm of $(L,g)$-codes in the erasure channel.

Two Extremal Codes of Length 42 and 44
V. Yorgov and R. Ruseva
pp. 385–388

Abstract—Two new self-dual codes with the parameters $(42,21,8)$ and $(44,22,8)$ are constructed. These codes are intimately related to the extended Golay code of length $24$. Weight enumerators of these codes are found.

Vladimir Ivanovich Siforov (Obituary)
pp. 389–390

On the Centenary of Aksel Ivanovich Berg
pp. 391–392