PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

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.