PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 55, Number 3, July–September, 2019
Back to contents page

CONTENTS                   Powered by MathJax

 

Upper Bounds for the Holevo Information Quantity and Their Use
M. E. Shirokov
pp. 201–217

Abstract—We present a family of easily computable upper bounds for the Holevo (information) quantity of an ensemble of quantum states depending on a reference state (as a free parameter). These upper bounds are obtained by combining probabilistic and metric characteristics of the ensemble. We show that an appropriate choice of the reference state gives tight upper bounds for the Holevo quantity which in many cases improve the estimates existing in the literature. We also present an upper bound for the Holevo quantity of a generalized ensemble of quantum states with finite average energy depending on the metric divergence of an ensemble. In the case of a multi-mode quantum oscillator, this upper bound is tight for large energy. Upper bounds for the Holevo capacity of finite-dimensional quantum channels depending on metric characteristics of the channel output are obtained.

 

Optimal Upper Bounds for the Divergence of Finite-Dimensional Distributions under a Given Variational Distance
V. V. Prelov
pp. 218–225

Abstract—We consider the problem of finding the maximum values of divergences $D(P\,||\,Q)$ and $D(Q\,||\,P)$ for probability distributions $P$ and $Q$ ranging in the finite set $\mathcal{N}=\{1,2,\ldots,n\}$ provided that both the variation distance $V(P,Q)$ between them and either the probability distribution $Q$ or (in the case of $D(P\,||\,Q)$) only the value of the minimal component $q_{\min}$ of the probability distribution $Q$ are given. Precise expressions for the maximum values of these divergences are obtained. In several cases these expressions allow us to write out some explicit formulas and simple upper and lower bounds for them. Moreover, explicit formulas for the maximum of $D(P\,||\,Q)$ for given $V(P,Q)$ and $q_{\min}$ and also for the maximum of $D(Q\,||\,P)$ for given $Q$ and $V(P,Q)$ are obtained for all possible values of these parameters.

 

Divisible Arcs, Divisible Codes, and the Extension Problem for Arcs and Codes
I. Landjev and A. Rousseva
pp. 226–240

Abstract—In an earlier paper we developed a unified approach to the extendability problem for arcs in $\operatorname{PG}(k-1,q)$ and, equivalently, for linear codes over finite fields. We defined a special class of arcs called $(t\bmod{q})$-arcs and proved that the extendabilty of a given arc depends on the structure of a special dual arc, which turns out to be a $(t\bmod{q})$-arc. In this paper, we investigate the general structure of $(t\bmod{q})$-arcs. We prove that every such arc is a sum of complements of hyperplanes. Furthermore, we characterize such arcs for small values of $t$, which in the case $t=2$ gives us an alternative proof of the theorem by Maruta on the extendability of codes. This result is geometrically equivalent to the statement that every $2$-quasidivisible arc in $\operatorname{PG}(k-1,q)$, $q\ge5$, $q$ odd, is extendable. Finally, we present an application of our approach to the extendability problem for caps in $\operatorname{PG}(3,q)$.

 

Generalization of IPP Codes and IPP Set Systems
E. E. Egorova
pp. 241–253

Abstract—A quarter century ago Chor, Fiat, and Naor proposed mathematical models for revealing a source of illegal redistribution of digital content (tracing traitors) in the broadcast encryption framework, including the following two combinatorial models: nonbinary IPP codes, based on an $(n,n)$-threshold secret sharing scheme, and IPP set systems, based on the general $(w,n)$-threshold secret sharing scheme. We propose a new scheme combining the main ideas of nonbinary IPP codes and IPP set systems, which can also be considered as a generalization of nonbinary IPP codes to the case of constant-weight codes. In the simplest case of a coalition of size two, we compare the new scheme with previously known ones.

 

Some $q$-ary Cyclic Codes from Explicit Monomials over $\mathbb{F}_{q^m}$
L. Li, S. Zhu, L. Liu, and X. Kai
pp. 254–274

Abstract—Cyclic codes as a subclass of linear codes have practical applications in communication systems, consumer electronics, and data storage systems due to their efficient encoding and decoding algorithms. The objective of this paper is to construct some cyclic codes by the sequence approach. More precisely, we determine the dimension and the generator polynomials of three classes of $q$-ary cyclic codes defined by some sequences with explicit polynomials over $\mathbb{F}_{q^m}$. The minimum distance of such cyclic codes is also discussed. Some of these codes are optimal according to code tables. Moreover, the third class of cyclic codes provides some answers for Open Problem 3 proposed by Ding and Zhou in [1].

 

On Alphabetic Coding for Superwords
S. S. Marchenkov
pp. 275–282

Abstract—We consider alphabetic coding of superwords. We establish an unambiguity coding criterion for the cases of finite and infinite codes. We prove that in the case of an infinite code the ambiguity detection problem is $m$-complete in the $\exists^1\forall^{\,0}$ class of Kleene's analytical hierarchy.

 

Traceability Codes and Their Generalizations
G. A. Kabatiansky
pp. 283–294

Abstract—Codes with the identifiable “parent” property appeared as one of solutions for the broadcast encryption problem. We propose a new, more general model of such codes, give an overview of known results, and formulate some unsolved problems.

 

Note on “Smaller Explicit Superconcentrators” by N. Alon and M. Capalbo
L. A. Bassalygo
pp. 295–297

Abstract—We slightly improve the superconcentrator construction by Alon and Capalbo.

 

Erratum to: On Completely Regular Codes
J. Borges, J. Rifà, and V. A. Zinoviev
p. 298

Abstract—We correct mistakes in the formulations of Theorem 19 and Proposition 17 of the original article, published in vol. 55, no. 1, 1–45.