PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii
On One Extreme Value Problem for Entropy and
Error Probability
V. V. Prelov
pp. 203216
AbstractThe problem of determining both the maximum and minimum entropy of a random variable $Y$ as well as the maximum absolute value of the difference between entropies of $Y$ and another random variable $X$ is considered under the condition that the probability distribution of $X$ is fixed and the error probability (i.e., the probability of noncoincidence of random values of $X$ and $Y$) is given. A precise expression for the minimum entropy of $Y$ is found. Some conditions under which the entropy of $Y$ takes its maximum value are pointed out. In other cases, some lower and upper bounds are obtained for the maximum entropy of $Y$ as well as for the maximum absolute value of the difference between entropies of $Y$ and $X$.
On Using Noisy Feedback in a Gaussian Channel
M. V. Burnashev and H. Yamamoto
pp. 217231
AbstractFor information transmission, a discrete-time channel with independent additive Gaussian noise is used. There is also another channel with independent additive Gaussian noise (the feedback channel), and the transmitter observes all outputs of the forward channel without delay via that channel. Transmission of nonexponentially many messages is considered (i.e., the transmission rate is zero), and the achievable decoding error exponent for such a combination of channels is investigated. The transmission method strengthens the method previously used by the authors for the BSC and Gaussian channels. In particular, for small feedback noise, this yields a gain of 33.3$\%$ (instead of 23.6$\%$ earlier in the similar case of a Gaussian channel).
On Superactivation of One-Shot Quantum
Zero-Error Capacity and the Related Property of Quantum Measurements
M. E. Shirokov and T. V. Shulman
pp. 232246
AbstractWe give a detailed description of a low-dimensional quantum channel (input dimension 4, Choi rank 3) demonstrating the symmetric form of superactivation of one-shot quantum zero-error capacity. This property means appearance of a noiseless (perfectly reversible) subchannel in the tensor square of a channel having no noiseless subchannels. Then we describe a quantum channel with an arbitrary given level of symmetric superactivation (including the infinite value). We also show that superactivation of one-shot quantum zero-error capacity of a channel can be reformulated in terms of quantum measurement theory as appearance of an indistinguishable subspace for the tensor product of two observables having no indistinguishable subspaces.
DNA Codes for Nonadditive Stem Similarity
A. G. D'yachkov, A. N. Kuzina, N. A. Polyansky, A. Macula, and V. V. Rykov
pp. 247269
AbstractDNA sequences are sequences with elements from the quaternary DNA alphabet $\{A,C,G,T\}$. An important property of them is their directedness and ability to form duplexes as a result of hybridization process, i.e., coalescing two oppositely directed sequences. In biological experiments exploiting this property it is necessary to generate an ensemble of such sequences (DNA codes) consisting of pairs of DNA sequences referred to as WatsonCrick duplexes. Furthermore, for any two words of the DNA code that do not form a WatsonCrick duplex, hybridization energystability measure of a potential DNA duplexis upper bounded by a constant specified by conditions of an experiment. This problem can naturally be interpreted in terms of coding theory. Continuing our previous works, we consider a nonadditive similarity function for two DNA sequences, which most adequately models their hybridization energy. For the maximum cardinality of DNA codes based on this similarity, we establish a Singleton upper bound and present an example of an optimal construction. Using ensembles of DNA codes with special constraints on codewords, which we call Fibonacci ensembles, we obtain a random-coding lower bound on the maximum cardinality of DNA codes under this similarity function.
Non-Full-Rank Steiner Quadruple Systems
$S(v,4,3)$
V. A. Zinoviev and D. V. Zinoviev
pp. 270279
AbstractAll different Steiner systems $S(2^m,4,3)$ of order $2^m$ and rank $2^m-m-1+s$ over $\mathbb{F}_2$, where $0\le s\le m-1$, are constructed. The number of different systems $S(2^m,4,3)$ whose incident matrices are orthogonal to a fixed code is obtained. A connection between the number of different Steiner systems and of different Latin cubes is described.
Proof of Two Conjectures on Correlation
Inequalities for One Class of Monotone Functions
V. M. Blinovsky
pp. 280284
AbstractWe prove two correlation inequalities conjectured in [1], for functions that are linear combinations of unimodal Boolean monotone nondecreasing functions.
Universal Coding Algorithm for a Family of
Context Markov Sources
Yu. M. Shtarkov
pp. 285291
AbstractOften, for a source to be encoded it is only known (or assumed) that its model belongs to some known family; parameters of models are unknown. The number of context Markov models in a family can be enormous, and methods for finding the best of them to describe a current block (message fragment of length $n$) have not been discussed previously. We propose a way to solve this problem and describe a coding algorithm.
Remark on Tooms Partial Order Is
Transitive Published in Probl. Peredachi Inf., 2012, no. 2
M. A. Raskin
pp. 292301
AbstractIn my paper Tooms Partial Order Is Transitive (Probl. Peredachi Inf., 2012, vol. 48, no. 2, pp. 7999) there is a mistake in the proof of Theorem 3. In the construction given in the paper for the proof of additivity of the constructed measures $\alpha'$ and $\beta'$, we assume that the distributions of zeros inserted into a given word $y$ with respect to the measures $\alpha$ and $\beta$ can be taken to be independent. This assumption does not take into account the fact that the distribution of the number of zeros and the distribution of the succeeding nonzero symbol may be dependent. For example, $Y$-projection of the measure $\alpha$ may consist of independently chosen equiprobable blocks ${\oplus}{\odot}{\oplus}{\ominus}$ and ${\oplus}{\oplus}{\oplus}{\odot}$. This mistake can be corrected by using averaging and considering the accumulation point of the sequence of the averaged measures.