PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Enumerative Coding for Constant-Weight Binary Sequences with Constrained Run-Length of Zeros
O. F. Kurmaev
pp. 249–254

Abstract—We suggest a method for computing the number of $dklr$-sequences with given number of ones. Based on these results and the well-known method of Babkin and Cover, enumerative encoding and decoding for constant-weight $dklr$-sequences is obtained.

New Sequences with Zero Autocorrelation
E. M. Gabidulin and V. V. Shorin
pp. 255–267

Abstract—New families of unimodular sequences of length $p=3f+1$ with zero autocorrelation are described, $p$ being a prime. The construction is based on employing Gauss periods. It is shown that in this case elements of the sequences are algebraic numbers defined by irreducible polynomials over $\mathbb{Z}$ of degree $12$ (for the first family) and $6$ (for the second family). In turn, these polynomials are factorized in some extension of the field $\mathbb{Q}$ into polynomials of degree, respectively, $4$ and $2$, which are written explicitly. For $p=13$, using the exhaustive search method, full classification of unimodular sequences with zero autocorrelation is given.

Some Constructions of Conflict-Avoiding Codes
B. S. Tsybakov and A. R. Rubinov
pp. 268–279

Abstract—Constructions of conflict-avoiding codes are presented. These codes can be used as protocol sequences for successful packet transmission over a collision channel without feedback. We give a relation between codes that avoid conflicts of different numbers of colliding users. Upper bounds on the maximum code size and three particular code constructions are presented.

A Distance Measure Tailored to Tailbiting Codes
M. Handlery, S. Höst, R. Johannesson, and V. V. Zyablov
pp. 280–295

Abstract—The error-correcting capability of tailbiting codes generated by convolutional encoders is described. In order to obtain a description beyond what the minimum distance $d_{\min}$ of the tailbiting code implies, the active tailbiting segment distance is introduced. The description of correctable error patterns via active distances leads to an upper bound on the decoding block error probability of tailbiting codes. The necessary length of a tailbiting code so that its minimum distance is equal to the free distance $d_{\rm free}$ of the convolutional code encoded by the same encoder is easily obtained from the active tailbiting segment distance. This is useful when designing and analyzing concatenated convolutional codes with component codes that are terminated using the tailbiting method. Lower bounds on the active tailbiting segment distance and an upper bound on the ratio between the tailbiting length and memory of the convolutional generator matrix such that $d_{\min}$ equals $d_{\rm free}$ are derived. Furthermore, affine lower bounds on the active tailbiting segment distance suggest that good tailbiting codes are generated by convolutional encoders with large active-distance slopes.

Binary Extended Perfect Codes of Length $16$ by the Generalized Concatenated Construction
V. A. Zinoviev and D. V. Zinoviev
pp. 296–322

Abstract—We enumerate binary extended nonlinear perfect codes of length $16$ obtained by the generalized concatenated construction (GC-construction). There are $15$ different types of such codes. They are defined by pairs of MDS codes $A_i\colon(4,2,64)_4$. For every pair, we give the number of nonequivalent codes of this type. In total, there are $285$ nonequivalent binary extended nonlinear perfect codes of length $16$ obtained by the GC-construction, including the Hamming (i.e., linear) code. Thus, we obtain all binary extended perfect codes of length $16$ and rank $13$. Their total number is equal to $272$.

On Density Estimation under Relative Entropy Loss Criterion
M. V. Burnashev and S. Amari
pp. 323–346

Abstract—A density estimation problem under relative entropy loss criterion is considered. When the densities estimated constitute a $d$-dimensional smooth parameter family, an exact asymptotics of the minimax risk is established.

Size of the Largest Antichain in a Partition Poset
V. M. Blinovsky and L. H. Harper
pp. 347–353

Abstract—Partitions $\{(k_1,\ldots,k_\ell )\}$ of a given set are considered as a partially ordered set (poset) with a natural partial ordering with respect to inclusion. Asymptotics for the size of the largest antichain in this poset is found for $\ell$ fixed.

Entropy and Large Deviations for Discrete-Time Markov Chains
G. Fayolle and A. de La Fortelle
pp. 354–367

Abstract—Let $E$ be a denumerable state space and $X$ be a homogeneous Markov chain on $E$ with kernel $P$. Then the chain $X$ verifies a weak Sanov's theorem, i.e., a weak large deviation principle holds for the law of the pair empirical measure. This LDP holds for any discrete state space Markov chain, not necessarily ergodic or irreducible. It is also known that a strong LDP cannot hold in the present framework. The result is obtained by a new method, which allows us to extend the LDP from a finite state space setting to a denumerable one, somehow like the projective limit approach. The analysis presented here offers some by-products, among which there are a contraction principle for the weak LDP, leading directly to a weak Sanov's theorem for the one-dimensional empirical measure. A refined analysis of the ubiquitous entropy function $H$ proves to be useful in other frameworks, e.g., continuous time or stochastic networks, and allows us to improve the sharpness of asymptotics.

On the Invariance of Stationary State Probabilities of a Non-Product-Form Single-Line Queueing System
V. A. Ivnitskii
pp. 368–376

Abstract—We consider a single-line queueing system (QS) with Poisson input flow of varying intensity, which depends on the number of demands in the system. The job size (length) distribution for a demand depends on the number of demands in the system at the arrival moment. The service rate also depends on the number of calls in the QS. If the job size for a new arrival is larger than the remaining job size for the currently processed demand, then the arrival is put at the beginning of the queue with a certain probability, which depends on the total number of demands in the system. Otherwise, it occupies the server and displaces the currently processed demand, which is put at the beginning of the queue. The probability distribution of stationary states of the QS is found and necessary and sufficient conditions for this distribution to be invariant with respect to the job size distribution with a fixed mean are obtained.

On the 100th Anniversary since the Birth of Andrei Nikolaevich Kolmogorov
pp. 377–385

INDEX
pp. 386–389