PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Shannon Capacity in Poisson Wireless Network Model
P. Jacquet
pp. 193–203

Abstract—We consider a realistic model of a wireless network where nodes are dispatched in an infinite map with uniform distribution. Signals decay with distance according to attenuation factor $\alpha$. At any time we assume that the distribution of emitters is $\lambda$ per square unit area. From an explicit formula of the Laplace transform of a received signal, we derive an explicit formula for the information rate received by an access point at a random position, which is $\smash[b]{\frac{\alpha}{2}(\log 2)^{-1}}$ per Hertz. We generalize to network maps of any dimension.

Erasure Correction by Low-Density Codes
V. V. Zyablov and P. S. Rybin
pp. 204–220

Abstract—We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

Fourier-Invariant Pairs of Partitions of Finite Abelian Groups and Association Schemes
V. A. Zinoviev and T. Ericson
pp. 221–231

Abstract—We consider partitions of finite abelian groups. We introduce the concept of Fourier-invariant pairs and demonstrate that this concept is equivalent to the concept of an association scheme in an abelian group. It follows that Fourier-invariant pairs of partitions might be viewed as a very natural approach to abelian association schemes.

On Asymptotic Description of a Probabilistic Change-Point Model for a Two-State Discrete Markov Process
V. V. Khutortsev
pp. 232–241

Abstract—For jump variation of parameters of a two-state discrete Markov process, we obtain an asymptotic representation of the likelihood ratio. Its use in the joint change-point detection and estimation problem is illustrated by an example.

The Smallest Known Length of an Ordered System of Generators of a Symmetric Group
S. A. Kalinchuk and Yu. L. Sagalovich
pp. 242–257

Abstract—We consider a recursive algorithm for constructing an ordered system of generators of a symmetric group of degree $n$. We show that the number of transpositions that form this system is $O(n \log_2^2{n})$. This is only by a factor of $\log_2{n}$ greater in order than the lower bound on the number of transpositions in such a system.

On Symmetric Matrices with Indeterminate Leading Diagonals
A. V. Seliverstov and V. A. Lyubetsky
pp. 258–263

Abstract—We consider properties of the matrix of a real quadratic form that takes a constant value on a sufficiently large set of vertices of a multidimensional cube centered at the origin given that the corresponding quadric does not separate vertices of the cube. In particular, we show that the number of connected components of the graph of the matrix of such a quadratic form does not change when one edge of the graph is deleted.

A Proof of One Correlation Inequality
V. M. Blinovsky
pp. 264–269

Abstract—We prove a correlation inequality that was conjectured in [1]. This result yields a proof of a conjecture from [2].

The $\mathit{MAP}/M/N$ Retrial Queueing System with Time-Phased Batch Arrivals
S. A. Dudin
pp. 270–281

Abstract—We consider a retrial queueing system with batch arrival of customers. Unlike standard batch arrival, where a whole batch enters the system simultaneously, we assume that customers of a batch (session) arrive one by one in exponentially distributed time intervals. Service time is exponentially distributed. The batch arrival flow is MAP. The number of customers in a session is geometrically distributed. The number of sessions that can enter the system simultaneously is a control parameter. We analyze the joint probability distribution of the number of sessions and customers in the system using the techniques of multidimensional asymptotically quasi-Toeplitz Markov chains.

On One Top News List Model
A. V. Lebedev
pp. 282–288

Abstract—We introduce a top news list model based on extremal shot noise with Poisson arrival flow. We find one- and multi-dimensional distributions of popularity of current news (at arbitrary time and at infinity), as well as distributions of places of news in a top list and their sojourn times in a stationary regime. We consider in detail the case where the popularity of a news item is Pareto distributed at the initial time and then decreases exponentially.

Coverings, Centered Codes, and Combinatorial Steganography
F. Galand and G. A. Kabatiansky
pp. 289–294

Abstract—It is shown that steganography with a given distortion criteria, which we call combinatorial steganography, is equivalent to coverings of Hamming spaces or to so-called centered error-correcting codes, depending on whether an opponent is passive or active, respectively. A construction of centered error-correcting codes based on Reed–Solomon and algebraic geometry codes is proposed.