PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Entropy of a Stationary Process and Entropy of a Shift Transformation in Its Sample Space
B. M. Gurevich
pp. 103–113

Abstract—We construct a class of non-Markov discrete-time stationary random processes with countably many states for which the entropy of the one-dimensional distribution is infinite, while the conditional entropy of the “present” given the “past” is finite and coincides with the metric entropy of a shift transformation in the sample space. Previously, such situation was observed in the case of Markov processes only.

Generalized Error-Locating Codes with Component Codes over the Same Alphabet
I. V. Zhilin and V. V. Zyablov
pp. 114–135

Abstract—We consider generalized error locating (GEL) codes over the same alphabet for both component codes. We propose an algorithm for computing an upper bound on the decoding error probability under known input symbol error rate and code parameters. Is is used to construct an algorithm for selecting code parameters to maximize the code rate for a given construction and given input and output error probabilities. A lower bound on the decoding error probability is given. Examples of plots of decoding error probability versus input symbol error rate are given, and their behavior is explained.

MDS Codes in Doob Graphs
E. A. Bespalov and D. S. Krotov
pp. 136–154

Abstract—The Doob graph $D(m,n)$, where $m>0$, is a Cartesian product of $m$ copies of the Shrikhande graph and $n$ copies of the complete graph $K_4$ on four vertices. The Doob graph $D(m,n)$ is a distance-regular graph with the same parameters as the Hamming graph $H(2m+n,4)$. We give a characterization of MDS codes in Doob graphs $D(m,n)$ with code distance at least $3$. Up to equivalence, there are $m^3/36+7m^2/24+11m/12+1-(m \bmod 2)/8-(m\bmod 3)/9$ MDS codes with code distance $2m+n$ in $D(m,n)$, two codes with distance $3$ in each of $D(2,0)$ and $D(2,1)$ and with distance $4$ in $D(2,1)$, and one code with distance $3$ in each of $D(1,2)$ and $D(1,3)$ and with distance $4$ in each of $D(1,3)$ and $D(2,2)$.

Fast Discrete Fourier Transform on Local Fields of Positive Characteristic
S. F. Lukomskii and A. M. Vodolazov
pp. 155–163

Abstract—For the discrete Fourier transform with respect to the system of characters of a local field with positive characteristic, we propose a fast algorithm. We find the complexity of the algorithm.

Spaceability for Sets of Bandlimited Input Functions and Stable Linear Time-Invariant Systems with Finite Time Blowup Behavior
H. Boche and U. J. Mönich
pp. 164–182

Abstract—The approximation of linear time-invariant systems by sampling series is studied for bandlimited input functions in the Paley–Wiener space $\mathcal{PW}_\pi^1$, i.e., bandlimited signals with absolutely integrable Fourier transform. It has been known that there exist functions and systems such that the approximation process diverges. In this paper we identify a signal set and a system set with divergence, i.e., a finite time blowup of the Shannon sampling expression. We analyze the structure of these sets and prove that they are jointly spaceable, i.e., each of them contains an infinite-dimensional closed subspace such that for any function and system pair from these subspaces, except for the zero elements, we have divergence.

Fast Protocols for Leader Election and Spanning Tree Construction in a Distributed Network
M. N. Vyalyi and I. M. Khuziev
pp. 183–201

Abstract—We consider leader election and spanning tree construction problems in a synchronous network. Protocols are designed under the assumption that nodes in the network have identifiers but the size of an identifier is unlimited. We present fast protocols with runtime $O(D\log L+L)$, where $L$ is the size of the minimal identifier and $D$ is the network diameter.