PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 37, Number 4, October–December, 2001

Back to contents page

** 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