PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 35, Number 2, April–June, 1999

Back to contents page

**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