PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 48, Number 1, January–March, 2012
Back to contents page

CONTENTS                   Powered by MathJax

 

Information Capacity of a Quantum Observable
A. S. Holevo
pp. 1–10

Abstract—In this paper we consider the classical capacities of quantum-classical channels corresponding to measurement of observables. Special attention is paid to the case of continuous observables. We give formulas for unassisted and entanglement-assisted classical capacities $C$ and $C_{\mathrm{ea}}$ and consider some explicitly solvable cases, which give simple examples of entanglement-breaking channels with $C\lt C_{\mathrm{ea}}$. We also elaborate on the ensemble-observable duality to show that $C_{\mathrm{ea}}$ for the measurement channel is related to the $\chi$-quantity for the dual ensemble in the same way as $C$ is related to the accessible information. This provides both accessible information and the $\chi$-quantity for quantum ensembles dual to our examples.

 

Boundary Distortion Rate in Synchronized Systems: Geometrical Meaning of Entropy
S. A. Komech
pp. 11–20

Abstract—The geometrical meaning of the Kolmogorov entropy is studied. The relation between the entropy and boundary distortion rate in the phase space is obtained for a wide class of symbolic dynamical systems, namely synchronized systems.

 

Dual Convolutional Codes and the MacWilliams Identities
I. E. Bocharova, F. Hug, R. Johannesson, and B. D. Kudryashov
pp. 21–30

Abstract—A recursion for sequences of spectra of truncated as well as tailbitten convolutional codes and their duals is derived. The order of this recursion is shown to be less than or equal to the rank of the weight adjacency matrix (WAM) for the minimal encoder of the convolutional code. It is sufficient to know finitely many spectra of these terminated convolutional codes in order to obtain an infinitely long sequence of spectra of their duals.

 

Shadows under the Word-Subword Relation
R. Ahlswede and V. S. Lebedev
pp. 31–47

Abstract—We introduce a minimal shadow problem for a word-subword relation. We obtain upper and lower bounds for the minimal shadow cardinality.

 

Cardinality Spectra of Components of Correlation Immune Functions, Bent Functions, Perfect Colorings, and Codes
V. N. Potapov
pp. 48–56

Abstract—We study cardinalities of components of perfect codes and colorings, correlation immune functions, and bent function (sets of ones of these functions). Based on results of Kasami and Tokura, we show that for any of these combinatorial objects the component cardinality in the interval from $2^k$ to $2^{k+1}$ can only take values of the form $2^{k+1}- 2^p$, where $p\in\{0,\ldots,k\}$ and $2^k$ is the minimum component cardinality for a combinatorial object with the same parameters. For bent functions, we prove existence of components of any cardinality in this spectrum. For perfect colorings with certain parameters and for correlation immune functions, we find components of some of the above-given cardinalities.

 

On Large Deviations for Poisson Stochastic Integrals
M. V. Burnashev and Yu. A. Kutoyants
pp. 57–70

Abstract—We obtain asymptotically exact estimates for large deviations of Poisson stochastic integrals. We also find a region where such an integral can be approximated by the corresponding Gaussian random variable. In all of these results, we obtain nonasymptotic estimates for remainder terms.

 

Remark on One Problem in Extremal Combinatorics
V. M. Blinovsky
pp. 71–72

Abstract—We reduce the problem of determining the maximum number of permutations of a finite set such that any pair of permutations has at least $t$ common transpositions to the problem of determining the maximum number of permutations of finite set such that any pair has at least $t$ common fixed points. The latter problem was solved by the author in [1].

 

Two-Armed Bandit Problem for Parallel Data Processing Systems
A. V. Kolnogorov
pp. 73–84

Abstract—We consider application of the two-armed bandit problem to processing a large number $N$ of data where two alternative processing methods can be used. We propose a strategy which at the first stages, whose number is at most $r-1$, compares the methods, and at the final stage applies only the best one obtained from the comparison. We find asymptotically optimal parameters of the strategy and observe that the minimax risk is of the order of $N^\alpha$, where $\alpha=2^{r-1}/(2^r-1)$. Under parallel processing, the total operation time is determined by the number $r$ of stages but not by the number $N$ of data.