PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Asymptotic Bounds on the Decoding Error Probability for Two Ensembles of LDPC Codes
P. S. Rybin and V. V. Zyablov
pp. 205–216

Abstract—Two ensembles of low-density parity-check (LDPC) codes with low-complexity decoding algorithms are considered. The first ensemble consists of generalized LDPC codes, and the second consists of concatenated codes with an outer LDPC code. Error exponent lower bounds for these ensembles under the corresponding low-complexity decoding algorithms are compared. A modification of the decoding algorithm of a generalized LDPC code with a special construction is proposed. The error exponent lower bound for the modified decoding algorithm is obtained. Finally, numerical results for the considered error exponent lower bounds are presented and analyzed.

Decoding of Repeated-Root Cyclic Codes up to New Bounds on Their Minimum Distance
A. Zeh and M. Ulmschneider
pp. 217–230

Abstract—The well-known approach of Bose, Ray-Chaudhuri, and Hocquenghem and its generalization by Hartmann and Tzeng are lower bounds on the minimum Hamming distance of simple-root cyclic codes. We generalize these two bounds to the case of repeated-root cyclic codes and present a syndrome-based burst error decoding algorithm with guaranteed decoding radius based on an associated folded cyclic code. Furthermore, we present a third technique for bounding the minimum Hamming distance based on the embedding of a given repeated-root cyclic code into a repeated-root cyclic product code. A second quadratic-time probabilistic burst error decoding procedure based on the third bound is outlined.

Reconstruction of Eigenfunctions of a $q$-ary $n$-Dimensional Hypercube
A. Yu. Vasil'eva
pp. 231–239

Abstract—We prove that values of an arbitrary eigenfunction of a $q$-ary $n$-dimensional hypercube can be uniquely reconstructed at all vertices inside a ball if its values on the corresponding sphere are known; we give sufficient conditions for such reconstruction in terms of the eigenvalue and the ball radius. We show that in the case where values of an eigenfunction are given on a sphere of radius equal to the corresponding eigenvalue, all values of the eigenfunction can be reconstructed; similarly to the previous case, sufficient numerical conditions are presented.

Strong Divergence for System Approximations
H. Boche and U. J. Mönich
pp. 240–266

Abstract—In this paper we analyze approximation of stable linear time-invariant systems, like the Hilbert transform, by sampling series for bandlimited functions in the Paley–Wiener space $\mathcal{PW}_\pi^1$. It is known that there exist systems and functions such that the approximation process is weakly divergent, i.e., divergent for certain subsequences. Here we strengthen this result by proving strong divergence, i.e., divergence for all subsequences. Further, in case of divergence, we give the divergence speed. We consider sampling at Nyquist rate as well as oversampling with adaptive choice of the kernel. Finally, connections between strong divergence and the Banach–Steinhaus theorem, which is not powerful enough to prove strong divergence, are discussed.

Algorithmic Aspects of Decomposition and Equivalence of Finite-Valued Transducers
An. A. Muchnik^† and K. Yu. Gorbunov
pp. 267–288

Abstract—We study algorithmic issues of the problems of decomposing a finite-valued transducer into a union of single-valued ones and inclusion of an arbitrary transducer in a finite-valued one. We propose algorithms that partially improve efficiency estimates for known analogous algorithms.

The $MMAP/M/R/0$ Queueing System with Reservation of Servers Operating in a Random Environment
A. N. Dudin and A. A. Nazarov
pp. 289–298

Abstract—We consider a multiserver queueing system without buffer, with customers of two types, operating in a random environment. The system is fed by a marked Markovian arrival process which depends on the environment state. Customers of the first type have absolute priority over customers of the second type. Instantaneous service rates are piecewise constant with parameters depending on the customer type and the current environment state. The system behavior is described by a continuous-time multivariate Markov chain. We present a generator of this chain in a block-tridiagonal form. We briefly describe the procedure for finding a stationary probability distribution of system states and obtain formulas for the main probabilistic characteristics of the system in terms of the stationary distribution. An algorithm for computing the Laplace–Stieltjes transform of the sojourn time for an arbitrary customer of the first type is obtained.

A Mathematical Method for Packet Loss Ratio Estimation for a Multipath Route in the Presence of Correlated Errors
I. S. Kargin, E. M. Khorov, and A. I. Lyakhov
pp. 299–305

Abstract—We consider two-hop multipath routing in wireless networks. Errors occurring in transmission through different paths can be correlated. We explicitly find eigenvectors and eigenvalues of the transition probability matrix describing the system. We obtain an expression for the delivery probability of a packet to a final destination.