PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Error Probability Exponent of List Decoding at Low Rates
V. M. Blinovsky
pp. 277–287

Abstract—We prove that the expurgation bound on the error probability exponent for list-of-$L$ decoding is tight at zero rate.

To the Theory of Low-Density Convolutional Codes. II
M. Lentmaier, D. V. Truhachev, and K. Sh. Zigangirov
pp. 288–306

Abstract—A theoretical and experimental analysis of iterative decoding of low-density convolutional (LDC) codes is given. Two families are investigated: homogeneous LDC codes and a convolutional code version of turbo-codes.

On Upper Bounds for the Decoding Error Probability of Convolutional Codes
M. V. Burnashev
pp. 307–324

Abstract—A new approach to upper bounding the decoding error probability of convolutional codes is proposed. Its idea is, instead of evaluating the individual contribution of each fundamental path, to compare it with contribution of another (lighter) fundamental path. This allows us to (1) take into account the dependence between different fundamental paths based on the code tree structure; (2) represent the decoding error probability through the contribution of the first fundamental paths and a correction factor; (3) get much more accurate estimates.

Correction of Ordinary and Localized Errors
L. A. Bassalygo and M. S. Pinsker
pp. 325–328

Abstract—We present upper and lower bounds on the cardinality of a code that corrects both localized and ordinary errors.

On Pair-Separating Codes
G. A. Kabatiansky
pp. 329–331

Abstract—The known lower bound of Körner and Simonyi [SIAM J. Discrete Math., 1988, vol. 1, no. 3, pp. 355–359] on the rate of binary codes with the property of simultaneous separation of any two pairs of codewords is improved by a factor of 1.5.

An Isoperimetric Theorem for Sequences Generated by Feedback and Feedback-Codes for Unequal Error Protection
R. Ahlswede, N. Cai, and C. Deppe
pp. 332–338

Abstract—We derive an isoperimetric theorem for sequences generated by feedback and consider block codes for a binary broadcast channel with two receivers and noiseless feedback. By applying the isoperimetric theorem, we get an upper bound on the achievable rates for special cases of these codes with unequal error protection. We get a lower bound with a generalized Varshamov–Gilbert construction.

Binary Codes Formed by Functions with Nontrivial Inertia Groups
O. V. Denisov
pp. 339–352

Abstract—Let $K$ be a permutation group acting on binary vectors of length $n$ and $F_K$ be a code of length $2^n$ consisting of all binary functions with nontrivial inertia group in $K$. We obtain upper and lower bounds on the covering radii of $F_K$, where $K$ are certain subgroups of the affine permutation group $\operatorname{\it GA}_n$. We also obtain estimates for distances between $F_K$ and almost all functions in $n$ variables as $n\to\infty$. We prove the existence of functions with the trivial inertia group in $\operatorname{\it GA}_n$ for all $n\ge7$. An upper bound for the asymmetry of a $k$-uniform hypergraph is obtained.

A Class of Composite Codes with Minimum Distance $8$
I. M. Boyarinov, I. Martin, and B. Honary
pp. 353–364

Abstract—We consider linear composite codes based on the $|a+x\,|\,b+x\,|\,a+b+x|$ construction. For $m \ge 3$ and $r \le 4m+3$, we propose a class of linear composite $[3\cdot 2^{m},3\cdot 2^{m}-r,8]$ codes, which includes the $[24,12,8]$ extended Golay code. We describe an algebraic decoding algorithm, which is valid for any odd $m$, and a simplified version of this algorithm, which can be applied for decoding the Golay code. We give an estimate for the combinational-circuit decoding complexity of the Golay code. We show that, along with correction of triple independent errors, composite codes with minimum distance $8$ can also correct single cyclic error bursts and two-dimensional error bytes.

Parametric Filtering: Optimal Synthesis on a Nonlinear Dynamic Variety
V. Yu. Tertychnyi-Dauri
pp. 365–379

Abstract—We analyze the optimal parametric filtering problem for a wide class of nonlinear stochastic systems. Much attention is paid to validation of formed models of observation and estimation since derivation of equations that determine the mean-square optimal filter directly depends on a rational choice of the models. We find conditions under which the original optimal filtering problem is equivalent to the dual optimal control problem. Synthesis of the optimal filter is accompanied by the analysis of properties of solutions of filtering equations obtained.

On Bounds for the Monotone-Structure Reliability
V. G. Krivulets and V. P. Polesskii
pp. 380–396

Abstract—At present, two types of attainable bounds on the reliability of a general monotone structure are known. Packing bounds are trivial. Untying bounds were obtained by Polesskii in 1997. Their special case, the classical Esary–Proschan bounds, are known since 1963. In the present paper, we introduce the third type of attainable bounds on the reliability of a general monotone structure. We call them difference-untying bounds. They are generalization and improvement of the Oxley–Welsh bounds on the reliability of a homogeneous monotone structure obtained in 1979. An example demonstrating the high quality of difference-untying bounds is given. As a consequence, we obtain new bounds on the number of members of an arbitrary simplicial complex.

On a Retrial Single-Server Queueing System with Finite Buffer and Multivariate Poisson Flow
P. Bocharov, C. D’Apice, R. Manzo, and N. H. Phong
pp. 397–406

Abstract—We consider a single-server queueing system with a finite buffer, $K$ input Poisson flows of intensities $\lambda_i$, and distribution functions $B_i(x)$ of service times for calls of the $i$th type, $i=\overline{1,K}$. If the buffer is overflowed, an arriving call is sent to the orbit and becomes a repeat call. In a random time, which has exponential distribution, the call makes an attempt to reenter the buffer or server, if the latter is free. The maximum number of calls in the orbit is limited; if the orbit is overflowed, an arriving call is lost. We find the relation between steady-state distributions of this system and a system with one Poisson flow of intensity $\lambda=\sum\limits_{i=1}^K\lambda_i$ where type $i$ of a call is chosen with probability $\lambda_i/\lambda$ at the beginning of its service. A numerical example is given.

INDEX
pp. 407–410