PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Abstract—

Constructions and Invariants of Optimal Codes in the Lee Metric
I. Yu. Mogilnykh and F. I. Solov'eva^†
pp. 71–85

Abstract—We propose concatenation and switching methods for the construction of single-error-correcting perfect and diameter codes in the Lee metric. We analyze ranks and kernels of diameter perfect codes obtained by the switching construction.

Covering Codes for the Fixed Length Levenshtein Metric
I. V. Vorobyev
pp. 86–98

Abstract—A covering code, or a covering, is a set of codewords such that the union of balls centered at these codewords covers the entire space. As a rule, the problem consists in finding the minimum cardinality of a covering code. For the classical Hamming metric, the size of the smallest covering code of a fixed radius $R$ is known up to a constant factor. A similar result has recently been obtained for codes with $R$ insertions and for codes with $R$ deletions. In the present paper we study coverings of a space for the fixed length Levenshtein metric, i.e., for $R$ insertions and $R$ deletions. For $R=1$ and $2$, we prove new lower and upper bounds on the minimum cardinality of a covering code, which differ by a constant factor only.

Near-Ideal Predictors and Causal Filters for Discrete-Time Signals
N. G. Dokuchaev
pp. 99–114

Abstract—The paper presents linear predictors and causal filters for discrete-time signals featuring some different kinds of spectrum degeneracy. These predictors and filters are based on approximation of ideal noncausal transfer functions by causal transfer functions represented by polynomials of the Z-transform of the unit step signal.

Geometric Interpretation of the Entropy of Sofic Systems
G. D. Dvorkin
pp. 115–127

Abstract—We consider a geometric approach to the notion of metric entropy. We justify the possibility of this approach for the class of Borel invariant ergodic probability measures on sofic systems, which is the first result of such generality for non-Markovian systems.

Invariant Measures for Contact Processes with State-Dependent Birth and Death Rates
E. A. Zhizhina and S. A. Pirogov
pp. 128–145

Abstract—We consider contact processes on locally compact separable metric spaces with birth and death rates that are heterogeneous in space. We formulate conditions on the rates that ensure the existence of invariant measures of contact processes. One of the crucial conditions is the so-called critical regime condition. To prove the existence of invariant measures, we use the approach proposed in our preceding paper. We discuss in detail the multi-species contact model with a compact space of marks (species) in which both birth and death rates depend on the marks.

Feasibility of Data Transmission under Attack: From Isolated Toughness Variant Perspective
W. Gao, H. M. Başkonuş, and C. Cattani
pp. 146–162

Abstract—The graph model is an appreciable tool for data transmission network, where the feasibility of data transmission in site attack circumstances can be described by fractional critical graphs, and the vulnerability of networks can be measured by isolation toughness variant. This paper considers both the stability of the network and the feasibility of data transmission when the sites are destroyed, and determines the isolated toughness variant bound for fractional $(a,b,n)$-critical graphs, where the parameter $n$ represents the number of damaged sites at a certain moment. A counterexample proves the sharpness of the given isolated toughness variant bound. The main theoretical conclusion provides an equilibrium between performance and cost in network topology designing.

Existence of Sequences Satisfying Bilinear Type Recurrence Relations
A. A. Illarionov
pp. 163–180

Abstract—We study sequences $\left\{A_n\right\}_{n=-\infty}^{+\infty}$ of elements of an arbitrary field $\mathbb{F}$ that satisfy decompositions of the form $$ \begin{aligned} A_{m+n} A_{m-n}&=a_1(m) b_1(n)+a_2(m) b_2(n),\\ A_{m+n+1} A_{m-n}&=\tilde a_1(m) \tilde b_1(n)+\tilde a_2(m) \tilde b_2(n), \end{aligned} $$ where $a_1,a_2,b_1,b_2\colon \mathbb{Z}\to\mathbb{F}$. We prove some results concerning the existence and uniqueness of such sequences. The results are used to construct analogs of the Diffie–Hellman and ElGamal cryptographic algorithms. The discrete logarithm problem is considered in the group $(S,+)$, where the set $S$ consists of quadruples $S(n)=(A_{n-1},A_n, A_{n+1}, A_{n+2})$, $n\in\mathbb{Z}$, and $S(n)+S(m)=S(n+m)$.