PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 42, Number 4, October–December, 2006

Back to contents page

** Code Spectrum and the Reliability
Function: Binary Symmetric Channel
**

M. V. Burnashev

pp. 263–281

**Abstract**—A new approach for upper bounding the channel
reliability function using the code spectrum is described. It allows to treat
both the low and high rate cases in a unified way. In particular, previously
known upper bounds are improved, and a new derivation of the sphere-packing
bound is presented.

** On the Structure of Optimal Sets for a
Quantum Channel
**

M. E. Shirokov

pp. 282–297

**Abstract**—Special sets of states, called optimal, which are
related to the Holevo capacity and to the minimal output entropy of a quantum
channel, are considered. By methods of convex analysis and operator theory,
structural properties of optimal sets and conditions of their coincidence are
explored for an arbitrary channel. It is shown that strong additivity of the
Holevo capacity for two given channels provides projective relations between
optimal sets for the tensor product of these channels and optimal sets for
the individual channels.

** On the Reliability Exponent of the
Additive Exponential Noise Channel
**

Y. Ovadia and S. I. Bross

pp. 298–318

**Abstract**—We study the reliability exponent of the additive
exponential noise channel (AENC) in the absence as well as in the presence of
noiseless feedback. For rates above the critical rate, the
fixed-transmission-time reliability exponent of the AENC is completely
determined, while below the critical rate an expurgated exponent is obtained.
Using a fixed-block-length code ensemble (with block length denoting the
number of recorded departures), we obtain a lower bound on the
random-transmission-time reliability exponent of the AENC. Finally, with a
variable-block-length code ensemble, a lower bound on the
random-transmission-time *zero-error capacity* of the AENC with
noiseless feedback is obtained.

** An Extension Theorem for Arcs and
Linear Codes
**

I. Landjev and A. Rousseva

pp. 319–329

**Abstract**—We prove the following generalization to the extension
theorem of Hill and Lizak: For every nonextendable linear $[n,k,d]_q$ code, $q=p^s$,
$(d,q)=1$, we have
$$
\sum_{i\not\equiv 0,d\: \pmod{q}} A_i\gt q^{k-3} r(q),
$$
where $q+r(q)+1$ is the smallest size of a nontrivial blocking set in
$\operatorname{PG}(2,q)$. This result is applied further to rule out the existence of
some linear codes over $\mathbb{F}_4$ meeting the Griesmer bound.

** On-line Estimation of Smooth Signals
with Partial Observation
**

P. L. Chow and R. Z. Khasminskii

pp. 330–339

**Abstract**—The paper concerns the estimation of a smooth signal $S(t)$
and its derivatives in the presence of a noise depending on a small parameter
$\varepsilon$ based on a partial observation. A nonlinear Kalman-type filter is proposed
to perform on-line estimation. For the signal $S$ in a given class of smooth
functions, the convergence rate for the estimation risks, as $\varepsilon\to 0$, is
obtained. It is proved that such rates are optimal in a minimax sense. In contrast to
the complete observation case, the rates are reduced, due to incomplete
information.

** Construction of Virus-Free Switching
Circuits
**

V. V. Tarasov

pp. 340–343

**Abstract**—We consider relay switching circuits constructed from
switches whose operation is described by Boolean functions with external parameters
${z_1},\dots,{z_m}$ and a Boolean variable $x$ that controls the relay coil. We
construct switching circuits that are free from the influence of external factors
whose indicators are ${z_1},\dots,{z_m}$.

** Self-averaging Property of Queuing
Systems
**

A. A. Vladimirov, A. N. Rybko, and S. B. Shlosman

pp. 344–355

**Abstract**—We establish an averaging property for a one-server queuing
process, $M(t)/G/1$. It is a new relation between the output flow rate and the input
flow rate, crucial in the study of the Poisson hypothesis. Its implications include
the statement that the output flow always possesses more regularity than the input
flow.

** On Flows in Simple Bidirected and
Skew-Symmetric Networks
**

M. A. Babenko

pp. 356–370

**Abstract**—We consider a simple directed network. Results of Karzanov,
Even, and Tarjan show that the blocking flow method constructs a maximum integer flow
in this network in $O(m \min(m^{1/2}, n^{2/3}))$ time (hereinafter, $n$ denotes the
number of nodes, and $m$ the number of arcs or edges). For the bidirected case, Gabow
proposed a reduction to solve the maximum integer flow problem in $O(m^{3/2})$ time.
We show that, with a variant of the blocking flow method, this problem can also be
solved in $O(mn^{2/3})$ time. Hence, the gap between the complexities of directed and
bidirected cases is eliminated. Our results are described in the equivalent terms of
skew-symmetric networks. To obtain the time bound of $O(mn^{2/3})$, we prove that the
value of an integer $s$–$s'$ flow in a skew-symmetric network without parallel
arcs does not exceed $O(U n^2/d^2)$, where $d$ is the length of the shortest regular
$s$–$s'$ path in the split network and $U$ is the maximum arc capacity. We also
show that any acyclic integer flow of value $v$ in a skew-symmetric network without
parallel arcs can be positive on at most $O(n \sqrt{v})$ arcs.

** Invariance of the Stationary
Distribution of States of Multimode Service Policy Networks
**

A. N. Starovoitov

pp. 371–378

**Abstract**—We consider open and closed preemptive-resume
queueing systems with absolute priority of incoming customers. Single-server
nodes have several service modes (regimes); the time of switching between the
modes is exponential. Switching can be made to adjacent modes only. The
amount of work required for servicing an incoming customer (workload) is a
random variable with an arbitrary distribution function. For an open network,
the input flow is Poissonian. We prove that the stationary distribution of
the network states is invariant with respect to a functional form of workload
distributions if the first moments are fixed.

** Contemporary Debates on the Nature of
Mathematics
**

A. N. Kolmogorov (*Comments by V.A. Uspenskiy*)

pp. 379–389

**Abstract**—Kolmogorov’s article “Contemporary Debates on the
Nature of Mathematics” was published in 1929 in *Nauchnoe slovo* journal
(no. 6, pp. 41–54) and has not been republished since then. At the
end of the 19th and at the beginning of the 20th century, abstractions of a very
high order appeared and were rooted in mathematics, so that their correlation with
reality became a crucial question. A number of great mathematicians of the time were
interested in this question, and Kolmogorov’s article was quite up to date. The
goal of the republication of this article, which is currently difficult to access,
is not only to acquaint the reader with a scarcely known article of the great
scientist but to invite him to observe the process of scientific progress. It should
be noted that, only a year after the publication of the article, some astonishing
results of Gödel appeared that gave answers to a number of questions in
Kolmogorov’s article and brought mathematical strictness in the very
formulation of these questions. Therefore, the article is accompanied by external
comments in order to give an insight into the current state of the art. In the text
the comments are indicated by numbers in brackets, from [1] to [21]. As for the
rest, Kolmogorov’s text is published in the same way as it was published in
*Nauchnoe slovo*, without any alterations of the sense. Accompanying comments
given to the article by the editors of *Nauchnoe slovo* (footnotes and
introduction to the article) are omitted.

** INDEX
**

pp. 390–393