Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 54, № 3 (2018)
- Год: 2018
- Статей: 8
- URL: https://journal-vniispk.ru/0032-9460/issue/view/10148
Information Theory
Analytical Properties of Shannon’s Capacity of Arbitrarily Varying Channels under List Decoding: Super-Additivity and Discontinuity Behavior
Аннотация
The common wisdom is that the capacity of parallel channels is usually additive. This was also conjectured by Shannon for the zero-error capacity function, which was later disproved by constructing explicit counterexamples demonstrating the zero-error capacity to be super-additive. Despite these explicit examples for the zero-error capacity, there is surprisingly little known for nontrivial channels. This paper addresses this question for the arbitrarily varying channel (AVC) under list decoding by developing a complete theory. The list capacity function is studied and shown to be discontinuous, and the corresponding discontinuity points are characterized for all possible list sizes. For parallel AVCs it is then shown that the list capacity is super-additive, implying that joint encoding and decoding for two parallel AVCs can yield a larger list capacity than independent processing of both channels. This discrepancy is shown to be arbitrarily large. Furthermore, the developed theory is applied to the arbitrarily varying wiretap channel to address the scenario of secure communication over AVCs.
199-228
On Some Optimization Problems for the Rényi Divergence
Аннотация
We consider the problem of determining the maximum and minimum of the Rényi divergence Dλ(P||Q) and Dλ(Q||P) for two probability distribution P and Q of discrete random variables X and Y provided that the probability distribution P and the parameter α of α-coupling between X and Y are fixed, i.e., provided that Pr{X = Y } = α.
229-244
Coding Theory
On m-Near-Resolvable Block Designs and q-ary Constant-Weight Codes
Аннотация
We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs.
245-252
Methods of Signal Processing
New Good’s Type Kronecker Power Expansions
Аннотация
We propose a new version of the proof of Good’s theorem stating that the Kronecker power of an arbitrary square matrix can be represented as a matrix power of a sparse matrix Z. We propose new variants of sparse matrices Z. We observe that for another version of the tensor power of a matrix, the b-power, there exists an analog of another Good’s expansion but no analog of this theorem.
253-257
Automata Theory
On the Complexity of Polynomial Recurrence Sequences
Аннотация
We consider recurrence sequences over the set of integers with generating functions being arbitrary superpositions of polynomial functions and the sg function, called polynomial recurrence sequences. We define polynomial-register (PR) machines, close to random-access machines. We prove that computations on PR machines can be modeled by polynomial recurrence sequences. On the other hand, computation of elements of a polynomial recurrence sequence can be implemented using a suitable PR machine.
258-262
Large Systems
A Local Large Deviation Principle for Inhomogeneous Birth–Death Processes
Аннотация
The paper considers a continuous-time birth–death process where the jump rate has an asymptotically polynomial dependence on the process position. We obtain a rough exponential asymptotic for the probability of trajectories of a re-scaled process contained within a neighborhood of a given continuous nonnegative function.
263-280
Infinite Spectra of First-Order Properties for Random Hypergraphs
Аннотация
We study the asymptotic behavior of probabilities of first-order properties for random uniform hypergraphs. In 1990, J. Spencer introduced the notion of a spectrum for graph properties and proved the existence of a first-order property with an infinite spectrum. In this paper we give a definition of a spectrum for properties of uniform hypergraphs and establish an almost tight bound for the minimum quantifier depth of a first-order formula with infinite spectrum.
281-289
Communication Network Theory
290-299