PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Woven Convolutional Graph Codes with Large Free Distances
I. E. Bocharova, F. Hug, R. Johannesson, and B. D. Kudryashov
pp. 1–14

Abstract—Constructions of woven graph codes based on constituent convolutional codes are studied, and examples of woven convolutional graph codes are presented. Existence of codes satisfying the Costello lower bound on the free distance within a random ensemble of woven graph codes based on $s$-partite, $s$-uniform hypergraphs is shown, where $s$ depends only on the code rate. Simulation results for Viterbi decoding of woven graph codes are presented and discussed.

On Metric Rigidity for Some Classes of Codes
D. I. Kovalevskaya
pp. 15–27

Abstract—A code $C$ in the $n$-dimensional metric space $\mathbb{F}^n_q$ over the Galois field $\operatorname{\it GF}(q)$ is said to be metrically rigid if any isometry $I\colon C\to \mathbb{F}^n_q$ can be extended to an isometry (automorphism) of $\mathbb{F}^n_q$. We prove metric rigidity for some classes of codes, including certain classes of equidistant codes and codes corresponding to one class of affine resolvable designs.

Computing the Longest Common Substring with One Mismatch
M. A. Babenko and T. A. Starikovskaya
pp. 28–33

Abstract—The paper describes an algorithm for computing longest common substrings of two strings $\alpha_1$ and $\alpha_2$ with one mismatch in $O(|\alpha_1\rvert \lvert\alpha_2|)$ time and $O(|\alpha_1|)$ additional space. The algorithm always scans symbols of $\alpha_2$ sequentially, starting from the first symbol. The RAM model of computation is used.

Intersection Theorem for Finite Permutations
V. M. Blinovsky
pp. 34–45

Abstract—We find the maximal number of permutations on a set of $n$ elements such that any pair of permutations has at least $t$ common cycles.

On Conditions for a Product-Form Stationary Probability Distribution of States of a Multimode Service Network
A. N. Starovoitov
pp. 46–56

Abstract—We consider open and closed queueing networks with Markovian routing and symmetric service policies. Single-server nodes may operate in several modes. In each node, the amount of work required for servicing an arrival or for switching the mode is distributed arbitrarily. The performance rate for each of these operations depends on the residual amount of work. For open networks, the arrival flow is Poissonian. We establish conditions for a product-form stationary distribution of states of the piecewise continuous process that describes the network behavior.

A Zero-or-One Law in Aggregated Closed Queueing Networks
G. Sh. Tsitsiashvili and M. A. Osipova
pp. 57–63

Abstract—For a closed queueing network with single-server nodes, we prove that if the total number of requests, the number of servers in one of the nodes, and service rates in all other nodes are made $n$ times as large, then the stationary number of requests in the multiserver node divided by $n$ converges in probability as $n\to\infty$ to a positive constant, determined by parameters of the original network, with geometric convergence rate. Single-server nodes in the constructed network can be interpreted as repair nodes, the multiserver node as a set of workplaces, and requests as elements in a redundancy-with-repair model.

Enumeration of Constant-Weight Run-Length Limited Binary Sequences
O. F. Kurmaev
pp. 64–80

Abstract—Constant-weight binary sequences with constrained run lengths of zeros and ones are introduced. These run-length constraints are separate and independent. Using the Babkin–Cover enumerative scheme, the number of these sequences is found. Then enumeration-based encoding and decoding procedures are constructed.

Iosif Abramovich Ovseevich: In Memoriam
pp. 81–84