PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

BSC Reliability Function under List Decoding
V. M. Blinovsky
pp. 273–282

Abstract—We complete deriving a formula for the reliability function of a binary symmetric channel (BSC) for list decoding in the case of zero rate.

Transition Points in the Capacity-Achieving Distribution for the Peak-Power Limited AWGN and Free-Space Optical Intensity Channels
N. Sharma and S. Shamai (Shitz)
pp. 283–299

Abstract—The capacity-achieving input distribution for many channels like the additive white Gaussian noise (AWGN) channel and the free-space optical intensity (FSOI) channel under the peak-power constraint is discrete with a finite number of mass points. The number of mass points is itself a variable, and figuring it out is a part of the optimization problem. We wish to understand the behavior of the optimal input distribution at the transition points where the number of mass points changes. To this end, we give a new set of necessary and sufficient conditions at the transition points, which offer new insights into the transition and make the computation of the optimal distribution easier. For the real AWGN channel case, we show that for the zero-mean unit-variance Gaussian noise, the peak amplitude $A$ of 1.671 and 2.786 mark the points where the binary and ternary signaling, respectively, are no longer optimal. For the FSOI channel, we give transition points where binary gives way to ternary, and in some cases where ternary gives way to quaternary, in the presence of the peak-power constraint and with or without the average-power constraint.

Decoding of Random Network Codes
E. M. Gabidulin, N. I. Pilipchuk, and M. Bossert
pp. 300–320

Abstract—We consider the decoding for Silva–Kschischang–Kötter random network codes based on Gabidulin's rank-metric codes. The model of a random network coding channel can be reduced to transmitting matrices of a rank code through a channel introducing three types of additive errors. The first type is called random rank errors. To describe other types, the notions of generalized row erasures and generalized column erasures are introduced. An algorithm for simultaneous correction of rank errors and generalized erasures is presented. An example is given.

Special Sequences as Subcodes of Reed–Solomon Codes
A. A. Davydov, V. V. Zyablov, and R. E. Kalimullin
pp. 321–345

Abstract—We consider sequences in which every symbol of an alphabet occurs at most once. We construct families of such sequences as nonlinear subcodes of a $q$-ary $[n,k,n-k+1]_q$ Reed–Solomon code of length $n\le q$ consisting of words that have no identical symbols. We introduce the notion of a bunch of words of a linear code. For dimensions $k\le 3$ we obtain constructive lower estimates (tight bounds in a number of cases) on the maximum cardinality of a subcode for various $n$ and $q$, and construct subsets of words meeting these estimates and bounds. We define codes with words that have no identical symbols, observe their relation to permutation codes, and state an optimization problem for them.

Complete and Incomplete Boolean Degrees
S. S. Marchenkov
pp. 346–352

Abstract—We study the partially ordered set of Boolean $P_2$-degrees. We introduce the notions of complete and incomplete Boolean degrees. We show that for each complete $P_2$-degree there exist both a countable decreasing chain of $P_2$-degrees and a countable antichain of $P_2$-degrees. We prove that above each incomplete $P_2$-degree there is a continuum of $P_2$-degrees. Thus, in total we show that in the partially ordered set of $P_2$-degrees there are no maximal elements.

Discrete Chrestenson Transform
M. S. Bespalov
pp. 353–375

Abstract—The discrete Chrestenson–Kronecker transform is a linear transform whose matrix is a Kronecker power of the matrix of the discrete Fourier transform. The matrix of the discrete Chrestenson–Lévy transform is represented as a power of the matrix of the discrete Fourier transform with respect to a new direct product of matrices. We study properties of and analyze fast algorithms for these two main kinds of the discrete Chrestenson transform. We consider properties of and construction methods for other types of the discrete Chrestenson transform.

On Enumeration of $q$-ary Sequences with a Fixed Number of Occurrences of the Subblock $00$
V. S. Lebedev
pp. 376–381

Abstract—We propose a method for computing the number of $q$-ary sequences that contain the subblock $00$ precisely $r$ times.

On the Rate of Beta-Mixing and Convergence to a Stationary Distribution in Continuous-Time Erlang-Type Systems
A. Yu. Veretennikov
pp. 382–389

Abstract—We establish sufficient conditions for polynomial rate of convergence to a stationary distribution and of beta-mixing in continuous-time Erlang-type systems. Our results are a natural complement both to results of Erlang himself, dating back to the beginning of the 20th century, and to exponential estimates established later.

Fast Enumeration Algorithm for Words with Given Constraints on Run Lengths of Ones
Yu. S. Medvedeva and B. Ya. Ryabko
pp. 390–399

Abstract—We propose an algorithm for enumeration and denumeration of words with given constraints on run lengths of ones ($dklr$-sequences). For large $n$, operation time of the algorithm (per symbol of a sequence) is at most $O(\log^3 n \log \log n)$, where $n$ is the length of enumerated words, whereas for the best known methods it is at least $cn$, $c>0$.

International Symposium on Information Theory (ISIT’2011). Call for Papers
pp. 400–401

INDEX
pp. 402–405