PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Remark on “On the Capacity of a Multiple-Access Vector Adder Channel” by A.A. Frolov and V.V. Zyablov
E. A. Bakin and G. S. Evseev
pp. 1–5

Abstract—For vector adder channel, we present an upper bound on the capacity, which coincides with the lower bound given in [1]. Thus, we prove optimality of the uniform probability distribution of symbols for $\gamma\in(0,\gamma^*]$ and of the twisted distribution for $\gamma\in(\gamma^*,\infty)$, where $\gamma$ is the ratio of the number of users to the number of subchannels and $\gamma^*=1.3382$.

Upper Bound on the Minimum Distance of LDPC Codes over $\mathop{\it GF}(q)$ Based on Counting the Number of Syndromes
A. A. Frolov
pp. 6–13

Abstract—In [1] a syndrome counting based upper bound on the minimum distance of regular binary LDPC codes is given. In this paper we extend the bound to the case of irregular and generalized LDPC codes over $\mathop{\it GF}(q)$. A comparison with the lower bound for LDPC codes over $\mathop{\it GF}(q)$, upper bound for the codes over $\mathop{\it GF}(q)$, and the shortening upper bound for LDPC codes is made. The new bound is shown to lie under the Gilbert–Varshamov bound at high rates.

Analysis of Queues with Hyperexponential Arrival Distributions
V. N. Tarasov
pp. 14–23

Abstract—We study H$_2$/H$_2$/1, H$_2$/M/1, and M/H$_2$/1 queueing systems with hyperexponential arrival distributions for the purpose of finding a solution for the mean waiting time in the queue. To this end we use the spectral decomposition method for solving the Lindley integral equation. For practical application of the obtained results, we use the method of moments. Since the hyperexponential distribution law has three unknown parameters, it allows to approximate arbitrary distributions with respect to the first three moments. The choice of this distribution law is due to its simplicity and the fact that in the class of distributions with coefficients of variation greater than 1, such as log-normal, Weibull, etc., only the hyperexponential distribution makes it possible to obtain an analytical solution.

Lattice Flows in Networks
V. D. Shmatkov
pp. 24–38

Abstract—We consider flows in networks analogous to numerical flows but such that values of arc capacities are elements of a lattice. We present an analog of the max-flow min-cut theorem. However, finding the value of the maximum flow for lattice flows is based on not this theorem but computations in the algebra of matrices over the lattice; in particular, the maximum flow value is found with the help of transitive closure of flow capacity functions. We show that there exists a correspondence between flows and solutions of special-form systems of linear equations over distributive lattices.

Simple One-Shot Bounds for Various Source Coding Problems Using Smooth Rényi Quantities
N. A. Warsi
pp. 39–65

Abstract—We consider the problem of source compression under three different scenarios in the one-shot (nonasymptotic) regime. To be specific, we prove one-shot achievability and converse bounds on the coding rates for distributed source coding, source coding with coded side information available at the decoder, and source coding under maximum distortion criterion. The one-shot bounds obtained are in terms of smooth max Rényi entropy and smooth max Rényi divergence. Our results are powerful enough to yield the results that are known for these problems in the asymptotic regime both in the i.i.d. (independent and identically distributed) and non-i.i.d. settings.

Interactive Function Computation via Polar Coding
T. C. Gülcü and A. M. Barg
pp. 66–91

Abstract—In a series of papers (2011–2013) N. Ma and P. Ishwar considered a range of distributed source coding problems that arise in the context of interactive computation of functions, characterizing the region of achievable communication rates. We consider the problems of interactive computation of functions by two terminals and interactive computation in a collocated network, showing that the rate regions for both these problems can be achieved using several rounds of polar-coded transmissions.

Time Series Prediction Based on Data Compression Methods
A. S. Lysyak and B. Ya. Ryabko
pp. 92–99

Abstract—We propose efficient (“fast” and low memory consuming) algorithms for universal-coding-based prediction methods for real-valued time series. Previously, for such methods it was only proved that the prediction error is asymptotically minimal, and implementation complexity issues have not been considered at all. The provided experimental results demonstrate high precision of the proposed methods.

Erratum to: “On One Method for Constructing a Family of Approximations of Zeta Constants by Rational Fractions” [Problems of Information Transmission 51, 378 (2015)]
E. A. Karatsuba
pp. 100–101