PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 42, Number 2, April–June, 2006

Back to contents page

** Remark on the Additivity Conjecture for
a Quantum Depolarizing Channel
**

G. G. Amosov

pp. 69–76

**Abstract**—We consider bistochastic quantum channels generated by
unitary representations of a discrete group. We give a proof of the additivity
conjecture for a quantum depolarizing channel $\Phi$ based on the decreasing property
of the relative entropy. We show that the additivity conjecture holds for a channel
$\Xi=\Psi\circ\Phi$, where $\Psi$ is a phase damping channel.

** Spectral Approach to Linear Programming
Bounds on Codes
**

A. M. Barg and D. Yu. Nogin

pp. 77–89

**Abstract**—We give new proofs of asymptotic upper bounds of
coding theory obtained within the frame of Delsarte’s linear programming
method. The proofs rely on the analysis of eigenvectors of some
finite-dimensional operators related to orthogonal polynomials. Examples of
the method considered in the paper include binary codes, binary
constant-weight codes, spherical codes, and codes in projective spaces.

** Two-Dimensional Array Codes Correcting
Rectangular Burst Errors
**

I. M. Boyarinov

pp. 90–105

**Abstract**—Two-dimensional array codes correcting rectangular burst
errors are considered. We give a construction and examples of linear two-dimensional
array codes correcting rectangular burst errors of size $b_1\times b_2$ with minimum
redundancy $r=2b_1b_2$. We present constructions of cyclic two-dimensional array
codes correcting phased and arbitrary rectangular burst errors; their encoding and
decoding algorithms are also given. A class of cyclic two-dimensional array codes
correcting rectangular burst errors with asymptotically minimal redundancy is
described. We construct a class of linear two-dimensional array codes correcting
cyclic rectangular $b_1\times b_2$ burst errors with asymptotic excess redundancy
$\tilde r_{C}(b_1,b_2)=2b_1b_2-3$.

** Decoding of Low-Density Codes with
Parity-Check Matrices Composed of Permutation Matrices in an Erasure Channel
**

D. K. Zigangirov and K. Sh. Zigangirov

pp. 106–113

**Abstract**— A lower bound for the number of iteratively correctable
erasures is given, with application to the ensemble of LDPC codes with parity-check
matrices composed of permutation matrices [Sridharan, A., Lentmaier, M.,
Truhachev, D.V., Costello, D.J., Jr., and Zigangirov, K.Sh.,
*Probl. Peredachi Inf.*, 2005, vol. 41, no. 1, pp. 39–52;
*Probl. Inf. Trans.* (Engl. Transl.), 2005, vol. 41, no. 1,
pp. 33–44]. We assume that the Zyablov–Pinsker iterative decoding
algorithm [Zyablov, V.V., and Pinsker, M.S., *Probl. Peredachi Inf.*,
1974, vol. 10, no. 1, pp. 15–28; *Probl. Inf. Trans.* (Engl.
Transl.), 1974, vol. 10, no. 1, pp. 10–21] is used. Its
complexity is $O(N\log N)$, where $N$ is the block length.

** A New Class of Nonlinear Senary Codes
**

S. A. Stepanov

pp. 114–122

**Abstract**—In this paper we construct two new families of
nonlinear senary codes derived from the corresponding families of modified
Butson–Hadamard matrices. These codes have easy construction and decoding
procedures, and their parameters are very close to the Plotkin bound.

** Binary Extended Perfect Codes of Length
16 and Rank 14
**

V. A. Zinoviev and D. V. Zinoviev

pp. 123–138

**Abstract**—All extended binary perfect $(16,4,2^{11})$ codes of rank
$14$ over the field $\mathbb{F}_2$ are classified. It is proved that among all
nonequivalent extended binary perfect $(16,4,2^{11})$ codes there are exactly $1719$
nonequivalent codes of rank $14$ over $\mathbb{F}_2$. Among these codes there are
$844$ codes classified by Phelps (Solov'eva–Phelps codes) and $875$ other codes
obtained by the construction of Etzion–Vardy and by a new general doubling
construction, presented in the paper. Thus, the only open question in the
classification of extended binary perfect $(16,4,2^{11})$ codes is that on such codes
of rank $15$ over $\mathbb{F}_2$.

** A Method for Computation of the
Discrete Fourier Transform over a Finite Field
**

S. V. Fedorenko

pp. 139–151

**Abstract**—The discrete Fourier transform over a finite field
finds applications in algebraic coding theory. The proposed computation
method for the discrete Fourier transform is based on factorizing the
transform matrix into a product of a binary block circulant matrix and a
diagonal block circulant matrix.

** To the Problem of Realizability of
Boolean Functions by Circuits in a Basis of Unreliable Functional Elements
**

V. V. Tarasov

pp. 152–157

**Abstract**—Maximal extensions of Post classes containing $0$, $1$, and
$x$ in the algebra of partially unreliable Boolean functions are described. Based on
these extensions, criteria of expressibility of Boolean functions by circuits in a
basis of partially unreliable elements are proved.

** Probability Distribution in
Varying-Structure Queueing Networks
**

G. Sh. Tsitsiashvili and M. A. Osipova

pp. 158–165

**Abstract**—The paper is devoted to the computation of stationary
distributions of queueing systems in random media. Results obtained for
considered models follow from a theorem proved in the paper. As an
application of the theorem, we consider Jackson networks whose structure (the
set of working nodes, service and input flow intensities, routing matrix,
state set) and type (open/closed network) varies as the state of another
network or of the environment changes. Product-form formulas for the
computation of stationary distributions of the considered networks are
obtained, and algorithms for the solution of auxiliary problems are
developed.

** Letter to the Editor** (Remark on
“On DNA Codes” Published in *Probl. Peredachi Inf.*, 2005,
no. 4)

A. G. D'yachkov, P. A. Vilenkin,
I. K. Ismagilov, R. S. Sarbaev, A. Macula,
D. Torney, and S. White

p. 166