PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 44, Number 3, July–September, 2008
Back to contents page

CONTENTS                   Powered by MathJax

 

Entanglement-Breaking Channels in Infinite Dimensions
A. S. Holevo
pp. 171–184

Abstract—In the first part of the paper we give a representation for entanglement-breaking channels in separable Hilbert space that generalizes the “Kraus decomposition with rank-one operators” and use it to describe complementary channels. We also note that coherent information for antidegradable channel is always nonpositive. In the second part, we give necessary and sufficient condition for entanglement breaking for the general quantum Gaussian channel. Application of this condition to one-mode channels provides several new cases where the additivity conjecture holds in the strongest form.

 

Mutual Information, Variation, and Fano’s Inequality
V. V. Prelov and E. C. van der Meulen
pp. 185–197

Abstract—Some upper and lower bounds are obtained for the maximum of the absolute value of the difference between the mutual information $|I(X;Y)-I(X';Y')|$ of two pairs of discrete random variables $(X,Y)$ and $(X',Y')$ via the variational distance between the probability distributions of these pairs. In particular, the upper bound obtained here substantially generalizes and improves the upper bound of [1]. In some special cases, our upper and lower bounds coincide or are rather close. It is also proved that the lower bound is asymptotically tight in the case where the variational distance between $(X,Y)$ and $(X',Y')$ tends to zero.

 

On the Zero-Rate Error Exponent for a BSC with Noisy Feedback
M. V. Burnashev and H. Yamamoto
pp. 198–213

Abstract—For information transmission, a binary symmetric channel is used. There is also another noisy binary symmetric channel (feedback channel), and the transmitter observes (without delay) all outputs of the forward channel via the feedback channel. Transmission of nonexponentially many messages is considered (i.e., the transmission rate is zero). The achievable decoding error exponent for this combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than a certain positive value, then the achievable error exponent is better than the similar error exponent of the no-feedback channel. The described transmission method and the corresponding lower bound for the error exponent can be improved, as well as extended to positive transmission rates.

 

On the Error-Correcting Capability of LDPC Codes
K. Sh. Zigangirov, A. E. Pusane, D. K. Zigangirov, and D. J. Costello, Jr.
pp. 214–225

Abstract—We consider the ensemble of low-density parity-check (LDPC) codes introduced by Gallager [Low-Density Parity-Check Codes, Cambridge: MIT Press, 1963]. The Zyablov–Pinsker majority-logic iterative algorithm [2] for decoding LDPC codes is analyzed on the binary symmetric channel. An analytical lower bound on the error-correcting capability $\tau_{\max}$ that grows linearly in the code block length is obtained.

 

On Fragments of Words over a $q$-ary Alphabet
V. K. Leont'ev and S. A. Mukhina
pp. 226–232

Abstract—We consider several combinatorial problems concerning fragments of words over a $q$-ary alphabet. We obtain a number of new facts, some of them being previously known in the binary case only.

 

Optimal Filtering of a Random Background in Image Processing Problems
A. V. Bernstein and A. P. Kuleshov
pp. 233–242

Abstract—We describe a recurrent construction procedure for mean-square optimal linear spatio-temporal filtering of a random background, which makes it possible to construct filtered frames using explicitly written compact analytical expressions.

 

Some Lower Bounds on the Algebraic Immunity of Functions Given by Their Trace Forms
V. V. Bayev
pp. 243–265

Abstract—The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field $\operatorname{\it GF}(2^n)$, as well as for larger classes of functions defined by their trace forms. In particular, for $n\ge 5$, the algebraic immunity of the function $\operatorname{Tr}_n (x^{-1})$ has a lower bound $\bigl\lfloor {2\sqrt {n+4}} \bigr\rfloor -4$, which is close enough to the previously obtained upper bound $\left\lfloor {\sqrt {n}} \right\rfloor +\left\lceil {n/\left\lfloor {\sqrt {n}} \right\rfloor} \right\rceil -2$. We obtain a polynomial algorithm which, given a trace form of a Boolean function $f$, computes generating sets of functions of degree $\le d$ for the following pair of spaces. Each function of the first (linear) space bounds $f$ from below, and each function of the second (affine) space bounds $f$ from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables.

 

On Quadratic Approximations in Block Ciphers
N. N. Tokareva
pp. 266–286

Abstract—We consider quadratic approximations (of Boolean functions) of a special form and their potential applications in block cipher cryptanalysis. We show that the use of $k$-bent functions as ciphering functions extremely increases the resistance of ciphers to such approximations. We consider examples of 4-bit permutations recommended for use in S-boxes of the algorithms GOST 28147-89, DES, and $s^3$DES; we show that in almost all cases there exist more probable (than linear) quadratic relations of a special form on input and output bits of these permutations.