In this paper we study universal coding problems for the integers, in particular, establish rather tight lower and upper bounds for the Elias omega code and other codes, In these bounds, the so-called log-star functio...
详细信息
In this paper we study universal coding problems for the integers, in particular, establish rather tight lower and upper bounds for the Elias omega code and other codes, In these bounds, the so-called log-star function plays a central role. Furthermore, we investigate unbounded search trees induced by these codes, including the Bentley-Yao search tree, We will reveal beautiful recursion structures latent in these search trees as well as in these codes. Finally, we introduce the modified log-star function to reveal the existance of better prefix codes than Elias omega code and other known codes.
universal coding for the Slepian-Wolf data compression system is considered. We shall demonstrate based on a simple observation that the error exponent given by Csiszar and Korner for the universal coding system can s...
详细信息
universal coding for the Slepian-Wolf data compression system is considered. We shall demonstrate based on a simple observation that the error exponent given by Csiszar and Korner for the universal coding system can strictly be sharpened in general for a region of relatively higher rates. This kind of observation can be carried over also to the case of lower rates outside the Slepian-Wolf region, which establishes the strong converse along with the optimal exponent.
On the coding for correlated sources we extend the Slepian-Wolf data compression system (called the SW system) to define a new system (called the SWL system), where two separate encoders of the SW system are mutually ...
详细信息
On the coding for correlated sources we extend the Slepian-Wolf data compression system (called the SW system) to define a new system (called the SWL system), where two separate encoders of the SW system are mutually linked, Determining the optimal error exponent for all rates inside the admissible rate region remains an open problem for the SW system, In this paper we shall completely solve this problem for the SWL system, and show that the optimal exponents can be achieved by universal codes, Furthermore, it is shown that the linkage of two encoders does not extend the admissible rate region and does not even improve the exponent of correct decoding outside this region, The zero error data transmission problem for the SWL system is also considered, We shall determine the zero error rate region, the admissible rate region under the condition that the error probability of decoding is strictly zero, and show that this region can be attained hy universal codes, Furthermore, we make it clear that the linkage of encoders enlarges the zero error rate region, It is interesting to note that the above results for the SWL system correspond in some sense to the previous results for the discrete memoryless channel with feedback.
This paper deals with the problem of universal lossless coding on a countable infinite alphabet. It focuses on some classes of sources defined by an envelope condition on the marginal distribution, namely exponentiall...
详细信息
This paper deals with the problem of universal lossless coding on a countable infinite alphabet. It focuses on some classes of sources defined by an envelope condition on the marginal distribution, namely exponentially decreasing envelope classes with exponent alpha. The minimax redundancy of exponentially decreasing envelope classes is proved to be equivalent to 1/1 alpha log e log(2) n. Then, an adaptive algorithm is proposed, whose maximum redundancy is equivalent to the minimax redundancy.
This paper's main objective is to clearly describe the construction of a universal code for minimizing Davisson's minimax redundancy in a range where the true model and stochastic parameters are unknown. Minim...
详细信息
This paper's main objective is to clearly describe the construction of a universal code for minimizing Davisson's minimax redundancy in a range where the true model and stochastic parameters are unknown. Minimax redundancy is defined as the maximum difference between the expected per-symbol code length and the per-symbol source entropy in the source range. A universal coding scheme is here formulated in terms of the weight function, i.e., a method is presented for determining a weight function which minimizes the minimax redundancy even when the true model is unknown. It is subsequently shown that the minimax redundancy achieved through the presented coding method is upper-bounded by the minimax redundancy of Rissanen's semi-predictive coding method.
We construct a universal code for a stationary and memoryless classical-quantum channel as a quantum version of the universal coding by Csiszar and Korner. Our code is constructed utilizing a combination of irreducibl...
详细信息
We construct a universal code for a stationary and memoryless classical-quantum channel as a quantum version of the universal coding by Csiszar and Korner. Our code is constructed utilizing a combination of irreducible representations, a decoder introduced through the quantum information spectrum, and the packing lemma.
Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is...
详细信息
Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e., we are particularly interested in prediction of Martin-Lof random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching (PPM) measure satisfies this requirement with a large reserve.
We address the problem of signal compression, basing on the mathematical model, in which a set of all possible signals is considered as a function space with a metric p. The main attention is focused on the minimizati...
详细信息
ISBN:
(纸本)0769520820
We address the problem of signal compression, basing on the mathematical model, in which a set of all possible signals is considered as a function space with a metric p. The main attention is focused on the minimization of the size of compressed representation, when function characteristics axe not known precisely.
This paper deals with a universal lossy coding problem for a certain kind of multiterminal source coding network called a complementary delivery system. A universal coding scheme based on Wyner-Ziv codes is proposed. ...
详细信息
ISBN:
(纸本)9781424422562
This paper deals with a universal lossy coding problem for a certain kind of multiterminal source coding network called a complementary delivery system. A universal coding scheme based on Wyner-Ziv codes is proposed. While the proposed scheme cannot attain the optimal rate-distortion trade-off in general, the rate-loss is upper bounded by a universal constant under some mild conditions. Moreover, the proposed scheme allows us to apply (non-universal) Wyner-Ziv codes to construct a universal lossy complementary delivery code.
暂无评论