PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Some “Goodness” Properties of LDA Lattices
S. Vatedka and N. Kashyap
pp. 1–29

Abstract—We study some structural properties of Construction-A lattices obtained from low density parity check codes over prime fields. Such lattices are called low density Construction-A (LDA) lattices, and permit low-complexity belief propagation decoding for transmission over Gaussian channels. It has been shown that LDA lattices achieve the capacity of the power constrained additive white Gaussian noise (AWGN) channel with closest lattice-point decoding, and simulations suggested that they perform well under belief propagation decoding. We continue this line of work and prove that these lattices are good for packing and mean squared error quantization and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacity of the power constrained AWGN channel, the capacity of the dirty paper channel, the rates guaranteed by the compute-and-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.

Bounds on the Rate of Separating Codes
I. V. Vorob'ev
pp. 30–41

Abstract—A code with words in a finite alphabet is said to be an $(s,\ell)$ separating code if for any two disjoint collections of its words of size at most $s$ and $\ell$, respectively, there exists a coordinate in which the set of symbols of the first collection do not intersect the set of symbols of the second. The main goal of the paper is obtaining new bounds on the rate of $(s,\ell)$ separating codes. Bounds on the rate of binary $(s,\ell)$ separating codes, the most important for applications, are studied in more detail. We give tables of numerical values of the best presently known bounds on the rate.

Optimal Conflict-Avoiding Codes for $3$, $4$ and $5$ Active Users
T. Baicheva and S. Topalova
pp. 42–50

Abstract—Conflict-avoiding codes are used in multiple-access collision channels without feedback. The number of codewords in a conflict-avoiding code is the number of potential users of the channel. That is why codes with maximum cardinality (optimal codes) for given parameters are of interest. In this paper we classify, up to multiplier equivalence, all optimal conflict-avoiding codes of weights $3$, $4$, and $5$ and given small lengths. We also determine some previously unknown values of the maximum cardinality of conflict-avoiding codes of weights $4$ and $5$.

Remark on Balanced Incomplete Block Designs, Near-Resolvable Block Designs, and $q$-ary Constant-Weight Codes
L. A. Bassalygo and V. A. Zinoviev
pp. 51–54

Abstract—We prove that any balanced incomplete block design $B(v,k,1)$ generates a near-resolvable balanced incomplete block design $\operatorname{\it NRB}(v,k-1,k-2)$. We establish a one-to-one correspondence between near-resolvable block designs $\operatorname{\it NRB}(v,k-1,k-2)$ and the subclass of nonbinary (optimal, equidistant) constant-weight codes meeting the generalized Johnson bound.

Linear Algorithm for Minimal Rearrangement of Structures
K. Yu. Gorbunov and V. A. Lyubetsky
pp. 55–72

Abstract—We propose a linear time and linear space algorithm which constructs a minimal sequence of operations rearranging one structure (directed graph of cycles and paths) into another. Structures in such a sequence may have a varying number of edges; a list of operations is fixed and includes deletion and insertion of a fragment of a structure. We give a complete proof that the algorithm is correct, i.e., finds the corresponding minimum.

Model of a Random Geometric Graph with Attachment to the Coverage Area
S. N. Khoroshenkikh and A. B. Dainiak
pp. 73–83

Abstract—We propose a model of random geometric graph with vertices in $\mathbb{R}^n$ and $\mathbb{Z}^n$ as an alternative to existing models of ad-hoc wireless networks. We provide estimates for some graph invariants in our model in $\mathbb{R}^1$ and $\mathbb{Z}^n$.

Occurrence Numbers for Vectors in Cycles of Output Sequences of Binary Combining Generators
O. V. Kamlovskii
pp. 84–91

Abstract—We give formulas for computing the occurrence frequencies of $r$-tuples in cycles of output sequences of combining generators over the two-element field. From these formulas we derive some estimates for these frequencies.

Number of Curves in the Generalized Edwards Form with Minimal Even Cofactor of the Curve Order
A. V. Bessalov and O. V. Tsygankova
pp. 92–101

Abstract—We analyze properties of points of orders $2$, $4$, and $8$ of a curve in the generalized Edwards form. Arithmetic for group operations with singular points of these curves is introduced. We propose a classification of curves in the Edwards form into three disjoint classes. Formulas for the number of curves of order $4n$ of different classes are obtained. Works of other authors are critically analyzed.