PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 41, Number 2, April–June, 2005

Back to contents page

** On Estimation of Information via Variation
**

M. S. Pinsker^{†}

pp. 71–75

**Abstract**—New inequalities relating mutual information and
variational distance are derived.

** On a Sufficient Condition for
Additivity in Quantum Information Theory
**

N. Datta, A. S. Holevo, and Yu. M. Suhov

pp. 76–90

**Abstract**—In this paper we give a sufficient condition for
additivity of the minimum output entropy for a pair of given channels and an
analytic verification of this condition for specific quantum channels
breaking a closely related multiplicativity property [Amosov, G.G., and
Holevo, A.S., LANL e-print quant-ph/0103015; Werner, R.F., and Holevo, A.S.,
*J. Math. Phys.*, 2002, vol. 43, no. 9,
pp. 4353–4357]. This yields validity of the additivity conjecture
for these channels, a result obtained by a different method in [Matsumoto,
K., and Yura, F., LANL e-print quant-ph/0306009]. Our proof relies heavily
upon certain concavity properties of the output entropy, which are of
independent interest.

** Weight Functions and Generalized
Hamming Weights of Linear Codes
**

D. Yu. Nogin

pp. 91–104

**Abstract**—We prove that the weight function
$\operatorname{wt}\colon\mathbb{F}_q^k\to\mathbb{Z}$ on a set of messages uniquely
determines a linear code of dimension $k$ up to equivalence. We propose a natural way
to extend the $r$th generalized Hamming weight, that is, a function on $r$-subspaces
of a code $C$, to a function on $\mathbb{F}_q^{\binom{k}{r}}\cong\Lambda^r C$. Using
this, we show that, for each linear code $C$ and any integer $r\le k=\dim C$, a
linear code exists whose weight distribution corresponds to a part of the generalized
weight spectrum of $C$, from the $r$th weights to the $k$th. In particular, the
minimum distance of this code is proportional to the $r$th generalized weight of
$C$.

** On the Structure of Symmetry Groups of
Vasil'ev Codes
**

S. V. Avgustinovich, F. I. Solov'eva, and O. Heden

pp. 105–112

**Abstract**—The structure of symmetry groups of Vasil'ev codes is
studied. It is proved that the symmetry group of an arbitrary perfect binary
non-full-rank Vasil'ev code of length $n$ is always nontrivial; for codes of rank
$n-\log (n+1)+1$, an attainable upper bound on the order of the symmetry group is
obtained.

** Representation of
$\mathbb{Z}_4$-Linear Preparata Codes Using Vector Fields
**

N. N. Tokareva

pp. 113–124

**Abstract**—A binary code is called $\mathbb{Z}_4$-linear if its
quaternary Gray map preimage is linear. We show that the set of all quaternary linear
Preparata codes of length $n=2^m$, $m$ odd, $m\ge 3$, is nothing more than the set of
codes of the form $\mathcal{H_{\lambda,\psi}}+\mathcal{M}$ with
$$
\mathcal{H_{\lambda, \psi}}=\{y+T_{\lambda}(y)+S_{\psi}(y)\mid y\in H^n\},\quad
\mathcal{M}=2H^n,
$$
where $T_{\lambda}(\cdot)$ and $S_{\psi}(\cdot)$ are vector fields of a special form
defined over the binary extended linear Hamming code $H^n$ of length $n$. An upper
bound on the number of nonequivalent quaternary linear Preparata codes of length $n$
is obtained, namely, $2^{n\log_2 n}$. A representation for binary Preparata codes
contained in perfect Vasil'ev codes is suggested.

** Nonbinary Error-Correcting Codes with
One-Time Error-Free Feedback
**

L. A. Bassalygo

pp. 125–129

**Abstract**—We show that, using one-time error-free feedback, it
is possible to attain the asymptotic Hamming bound if the number of errors is
fixed.

** Interrelation of the Cyclic and Weight
Structure of Codes over $\operatorname{\it GF}(q)$ and Proportionality Classes
**

I. I. Mullayeva

pp. 130–133

**Abstract**—To determine the weight structure of cyclic codes, we
establish an interrelation of the cyclic structure of a code and classes of
proportional elements.

** Concentration Theorems for Entropy and
Free Energy
**

V. V. V'yugin and V. P. Maslov

pp. 134–149

**Abstract**—Jaynes's entropy concentration theorem states that, for most
words $\omega_1\ldots\omega_N$ of length $N$ such that $\sum\limits_{i=1}^N
f(\omega_i)\approx vN$, empirical frequencies of values of a function $f$ are close
to the probabilities that maximize the Shannon entropy given a value $v$ of the
mathematical expectation of $f$. Using the notion of algorithmic entropy, we define
the notions of entropy for the Bose and Fermi statistical models of unordered data.
New variants of Jaynes's concentration theorem for these models are proved. We also
present some concentration properties for free energy in the case of a nonisolated
isothermal system. Exact relations for the algorithmic entropy and free energy at
extreme points are obtained. These relations are used to obtain tight bounds on
fluctuations of energy levels at equilibrium points.

** Flow Control as a Stochastic Optimal
Control Problem with Incomplete Information
**

B. M. Miller, K. E. Avrachenkov, K. V. Stepanyan, and G. B. Miller

pp. 150–170

**Abstract**—A nonlinear stochastic control problem related to
flow control is considered. It is assumed that the state of a link is
described by a controlled hidden Markov process with a finite state set,
while the loss flow is described by a counting process with intensity
depending on a current transmission rate and an unobserved link state. The
control is the transmission rate, and it has to be chosen as a
nonanticipating process depending on the observation of the loss process. The
aim of the control is to achieve the maximum of some utility function that
takes into account losses of the transmitted information. Originally, the
problem belongs to the class of stochastic control problems with incomplete
information; however, optimal filtering equations that provide estimation of
the current link state based on observations of the loss process allow one to
reduce the problem to a standard stochastic control problem with full
observations. Then a necessary optimality condition is derived in the form of
a stochastic maximum principle, which allows us to obtain explicit analytic
expressions for the optimal control in some particular cases. Optimal and
suboptimal controls are investigated and compared with the flow control
schemes used in TCP/IP (Transmission Control Protocols/Internet Protocols)
networks. In particular, the optimal control demonstrates a much smoother
behavior than the TCP/IP congestion control currently used.

** New Product Theorems for Queueing Networks
**

G. Sh. Tsitsiashvili and M. A. Osipova

pp. 171–181

**Abstract**—New product theorems for open and closed queueing
networks are proved. The theorems give precise analytical formulas for the
computation of stationary distributions of queueing networks with a certain
structure and principle of operation. The subject touched upon in the paper
is developed in three directions, each of them being closely connected with
mobile phone network systems.

** Codes for Copyright Protection: The
Case of Two Pirates
**

G. A. Kabatiansky

pp. 182–186

**Abstract**—The problem of finding so-called pirates via the minimum
Hamming distance decoding is considered for the simplest case of two pirates. We
prove that for all $q\geq 3$ there exist “good” $q$-ary codes capable of
finding at least one pirate by the minimum distance decoding in the Hamming
metric.