Open Access
Access granted
Subscription Access
Vol 59, No 2 (2023)
Articles
3-17
Covering codes for the fixed length Levenshtein metric
Abstract
A covering code, or a covering, is a set of codewords such that the union of balls centered at these codewords covers the whole space. As a rule, the problem consists in nding the minimum of a covering code. For the classical Hamming metric, the size of the smallest covering code of a xed radius R is known up to a constant factor. A similar result has recently been obtained for codes with R insertions and codes with R deletions. In the present paper we study coverings of a space for the xed length Levenshtein metric, i.e., for R insertions and R deletions. For R = 1, 2 we prove new lower and upper bounds on the minimum cardinality of a covering code, which di er by a constant factor only.
Problemy peredači informacii. 2023;59(2):18-31
18-31
Near-ideal predictors and causal filters for discrete-time signals
Abstract
The paper presents linear predictors and causal lters for discrete-time signals featuring some di erent kinds of spectrum degeneracy. These predictors and lters 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.
Problemy peredači informacii. 2023;59(2):32-48
32-48
Geometric interpretation of the entropy of so c systems
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 so c systems, which is the rst result of such generality for non-Markovian systems.
Problemy peredači informacii. 2023;59(2):49-62
49-62
Invariant measures for contact processes with state-dependent birth and death rates
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.
Problemy peredači informacii. 2023;59(2):63-82
63-82
Feasibility of data transmission under attack: from isolated toughness variant perspective
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.
Problemy peredači informacii. 2023;59(2):83-101
83-101
Existence of sequences satisfying bilinear type recurrence relations
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 $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)$, 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)$.
Problemy peredači informacii. 2023;59(2):102-119
102-119