PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

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