PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 58, Number 2, April–June, 2022
Back to contents page

CONTENTS                   Powered by MathJax

 

Entropy in Thermodynamics and in Information Theory
V. A. Zorich
pp. 103–110

Abstract—We discuss the relation between the concepts of entropy in thermodynamics and in information theory.

 

On the Maximum Number of Non-Confusable Strings Evolving under Short Tandem Duplications
M. Kovačević
pp. 111–121

Abstract—The set of all $q$-ary strings that do not contain repeated substrings of length $\le\! 3$ (i.e., that do not contain substrings of the form $a a$, $a b a b$, and $a b c a b c$) constitutes a code correcting an arbitrary number of tandem-duplication mutations of length $\le\! 3$. In other words, any two such strings are non-confusable in the sense that they cannot produce the same string while evolving under tandem duplications of length $\le\! 3$. We demonstrate that this code is asymptotically optimal in terms of rate, meaning that it represents the largest set of non-confusable strings up to subexponential factors. This result settles the zero-error capacity problem for the last remaining case of tandem-duplication channels satisfying the “root-uniqueness” property.

 

Theoretical and Experimental Upper and Lower Bounds on the Efficiency of Convolutional Codes in a Binary Symmetric Channel
A. A. Kurmukova, F. I. Ivanov, and V. V. Zyablov
pp. 122–136

Abstract—We propose a new approach to the analytical estimation of the error burst probability, the probability of erroneous decoding, and the probability of error per bit for convolutional codes with Viterbi decoding in a binary symmetric channel (BSC). Upper and lower estimates of the probability of error per bit and of the erroneous decoding probability are based on active distances and the distance spectrum of active distances for a convolutional code. The estimates are derived for rate $1/2$ convolutional codes, but they can also be generalized to any convolutional code with rate $1/n$. Calculation of the estimates described here has linear time complexity in the error burst minimal length if code distance properties are known. The computational complexity does not depend on the crossover probability of a BSC. Simulation results show that the considered estimates are rather tight, especially for small crossover probabilities.

 

Geometric Interpretation of Entropy for Dyck Systems
G. D. Dvorkin
pp. 137–143

Abstract—We consider a relation between the metric entropy and the local boundary deformation rate (LBDR) in the symbolic case. We show the equality between the LBDR understood as a limit almost everywhere and the entropy for a vast class of measures on Dyck systems.

 

Large Deviation Principle for Terminating Multidimensional Compound Renewal Processes with Application to Polymer Pinning Models
A. V. Logachov, A. A. Mogulskii, and E. I. Prokopenko
pp. 144–159

Abstract—We obtain a large deviations principle for terminating multidimensional compound renewal processes. We also obtain the asymptotics of large deviations for the case where a Gibbs change of the original probability measure takes place. The random processes mentioned in the paper are widely used in polymer pinning models.

 

Poissonian Two-Armed Bandit: A New Approach
A. V. Kolnogorov
pp. 160–183

Abstract—We consider a new approach to the continuous-time two-armed bandit problem in which incomes are described by Poisson processes. For this purpose, first, the control horizon is divided into equal consecutive half-intervals in which the strategy remains constant, and the incomes arrive in batches corresponding to these half-intervals. For finding the optimal piecewise constant Bayesian strategy and its corresponding Bayesian risk, a recursive difference equation is derived. The existence of a limiting value of the Bayesian risk when the number of half-intervals grows infinitely is established, and a partial differential equation for finding it is derived. Second, unlike previously considered settings of this problem, we analyze the strategy as a function of the current history of the controlled process rather than of the evolution of the posterior distribution. This removes the requirement of finiteness of the set of admissible parameters, which was imposed in previous settings. Simulation shows that in order to find the Bayesian and minimax strategies and risks in practice, it is sufficient to partition the arriving incomes into 30 batches. In the case of the minimax setting, it is shown that optimal processing of arriving incomes one by one is not more efficient than optimal batch processing if the control horizon grows infinitely.

 

On New Problems in Asymmetric Cryptography Based on Error-Resistant Coding
V. V. Zyablov, F. I. Ivanov, E. A. Krouk, and V. R. Sidorenko
pp. 184–201

Abstract—We consider the problem of constructing a cryptosystem with a public key based on error-resistant coding. At present, this type of cryptosystems is believed to be able to resist the advent of quantum computers and can be considered as a method of post-quantum cryptography. The main drawback of a code-based cryptosystem is a great length of the public key. Most papers devoted to reducing the cryptosystem key length consisted in replacing the Goppa codes used in the original cryptosystem with some other codes with a requirement that the system remains secure against attacks by a quantum computer. Here we propose another approach to the key length reduction that is stated as a task of a simple description of an error set which has either errors of weights greater than half the minimum distance or errors that cannot be corrected without an additional secret knowledge. If a code structure allows to give such a description of an error set, then the complexity of most attacks (for instance, information-set decoding) significantly increases.