PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Sphere-Packing Bound, Capacity, and Similar Results for Poisson Channels
M. V. Burnashev and Yu. A. Kutoyants
pp. 95–111

Abstract—A new approach to obtaining upper bounds on the capacity and reliability function of a Poisson channel is suggested. It is based on a new sphere-packing bound for the error probability. A strong conversion of the coding theorem is also proved.

Efficient Conversion of Random Sequences into Equiprobable and Independent Sequences
B. Ya. Ryabko and E. P. Machikina
pp. 112–116

Abstract—We consider the problem of efficient conversion of sequences generated by an arbitrary Bernoulli source into sequences of independent and equiprobable symbols. This problem was previously considered by J. von Neumann, P. Elias, etc. For the proposed method based on the Elias algorithm, the memory used and the time required for processing one symbol is exponentially smaller than for previously known algorithms.

On the Hamming Bound for Nonbinary Localized-Error-Correcting Codes
R. Ahlswede, L. A. Bassalygo, and M. S. Pinsker
pp. 117–124

Abstract—For nonbinary codes it is proved that the Hamming bound is asymptotically sharp in some range of the code rate.

The Berlekamp–Massey Algorithm over a Finite Commutative Ring
V. L. Kurakin
pp. 125–135

Abstract—An algorithm for finding a monic polynomial of the least degree that generates a given sequence of length $\ell$ over a finite commutative ring $R$ with identity is presented. The complexity of the algorithm is $O(\ell^2)$ operations in $R$ as $\ell\to\infty$.

A Statistical Approach to Some Inverse Problems for Partial Differential Equations
G. K. Golubev and R. Z. Khas'minskii
pp. 136–149

Abstract—Some inverse problems for the Laplace equation and heat-conduction equation are considered. The solutions of these equations are assumed to be observed under the Gaussian white noise of low intensity. The problem consists of the renewal of the unknown smooth boundary conditions or initial conditions from the solution observed against a noise background. It is shown that the minimax estimates of the second order are linear for low spectral density of the noise.

Nonparametric Estimation of Linear Functionals of the Regression Function for a Known Conditional Distribution of the Observation Noise
Yu. I. Pastukhova
pp. 150–157

Abstract—For the case where an observation plan is given and the distribution function of the additive noise of observations is known, we obtain a nonparametric estimate of linear functionals of the regression function. This estimate asymptotically attains the minimax bound of risks for the quadratic loss function.

Nonstationary Time Series with a Close Alternative Hypothesis: Locally Asymptotic Distribution of the Likelihood Ratio
P. Boulongne, K. A. Ol'shanskii, and V. I. Piterbarg
pp. 158–165

Abstract—Within the framework of the autoregressive model, we solve the problem of testing the hypothesis of the existence of the unit root of the characteristic polynomial against a close alternative hypothesis of this root to come infinitesimally close to unity. The asymptotic distribution of the likelihood ratio is calculated. This distribution is found to be substantially dependent on the information amount of the innovation noise distribution.

Large-Deviation Principle for Conditional Distributions of Diffusion Processes
M. L. Kleptsyna and A. P. Serebrovski
pp. 166–171

Abstract—The large-deviation principle for measures corresponding to marginal conditional distributions of diffusion processes is considered.

Universal Graph Model of Cyclic Networks and Their Reliability
A. A. Chernyak
pp. 172–179

Abstract—In the present paper, we extend the domination theory to cyclic monotone graphs, which are a universal graph model for the analysis of complex-structured system reliability. In particular, we derive a formula for calculating the reliability of arbitrary monotone graphs, which reduces the system level of reliability analysis to the element level. As a corollary, we prove that for any fixed integer $k$ the problem of calculating the reliability of monotone graphs of degree $k$ can be solved in a time that polynomially depends on the dimension of graphs and the number of their acyclic monotone subgraphs. At the same time, we show that the reliability determination problem is NP-hard even in the class of acyclic $dc$-trivial monotone graphs of degree $2$ with the number of minimal acyclic subgraphs being proportional to the graph vertex number.

Variance of the Number of Departed Messages in a Simple Queueing System
A. I. Ovseevich
pp. 180–185

Abstract—We study a simple queueing facility consisting of two servers in tandem, separated by a finite buffer. The servers are independent and their sequences of up/down modes are Bernoullian. The input flow is deterministic (one new message per time unit). We compute explicitly the coefficient $A$ in the asymptotics ${\bf D}(T)\sim AT$ of the covariance of the number of departed messages per interval $[0,T]$.

Computer Logic in Information Processes
N. A. Kuznetsov and V. A. Lyubetsky
pp. 186–189