Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVariable Length Lossless Coding for Variational Distance Class: An Optimal Merging Algorithm
334
0
0.0
(
0
)
Added by
Themistoklis Charalambous
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we consider lossless source coding for a class of sources specified by the total variational distance ball centred at a fixed nominal probability distribution. The objective is to find a minimax average length source code, where the minimizers are the codeword lengths -- real numbers for arithmetic or Shannon codes -- while the maximizers are the source distributions from the total variational distance ball. Firstly, we examine the maximization of the average codeword length by converting it into an equivalent optimization problem, and we give the optimal codeword lenghts via a waterfilling solution. Secondly, we show that the equivalent optimization problem can be solved via an optimal partition of the source alphabet, and re-normalization and merging of the fixed nominal probabilities. For the computation of the optimal codeword lengths we also develop a fast algorithm with a computational complexity of order ${cal O}(n)$.
rate research
Read More
This paper presents lossless prefix codes optimized with respect to a pay-off criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorithm which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and a scalar parameter. The pay-off criterion considered encompasses a trade-off between maximum and average codeword length; it is related to a pay-off criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length pay-off criterion subject to a limited length constraint. A special case of the first related pay-off is connected to coding problems involving source probability uncertainty and codeword overflow probability, while the second related pay-off compliments limited length Huffman coding algorithms.
This paper describes a new set of block source codes well suited for data compression. These codes are defined by sets of productions rules of the form a.l->b, where a in A represents a value from the source alphabet A and l, b are -small- sequences of bits. These codes naturally encompass other Variable Length Codes (VLCs) such as Huffman codes. It is shown that these codes may have a similar or even a shorter mean description length than Huffman codes for the same encoding and decoding complexity. A first code design method allowing to preserve the lexicographic order in the bit domain is described. The corresponding codes have the same mean description length (mdl) as Huffman codes from which they are constructed. Therefore, they outperform from a compression point of view the Hu-Tucker codes designed to offer the lexicographic property in the bit domain. A second construction method allows to obtain codes such that the marginal bit probability converges to 0.5 as the sequence length increases and this is achieved even if the probability distribution function is not known by the encoder.
With the phenomenal growth of the Internet of Things (IoT), Ultra Reliable Low Latency Communications (URLLC) has potentially been the enabler to guarantee the stringent requirements on latency and reliability. However, how to achieve low latency and ultra-reliability with the random arrival remains open. In this paper, a queue-aware variable-length channel coding is presented over the single URLLC user link, in which the finite blocklength of channel coding is determined based on the random arrival. More particularly, a cross-layer approach is proposed for the URLLC user to establish the optimal tradeoff between the latency and power consumption. With a probabilistic coding framework presented, the cross-layer variable-length coding can be characterized based on a Markov chain. In this way, the optimal delay-power tradeoff is given by formulating an equivalent Linear Programming (LP). By solving this LP, the delay-optimal variable-length coding can be presented based on a threshold-structure on the queue length.
Soft compression is a lossless image compression method, which is committed to eliminating coding redundancy and spatial redundancy at the same time by adopting locations and shapes of codebook to encode an image from the perspective of information theory and statistical distribution. In this paper, we propose a new concept, compressible indicator function with regard to image, which gives a threshold about the average number of bits required to represent a location and can be used for revealing the performance of soft compression. We investigate and analyze soft compression for binary image, gray image and multi-component image by using specific algorithms and compressible indicator value. It is expected that the bandwidth and storage space needed when transmitting and storing the same kind of images can be greatly reduced by applying soft compression.
The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashevs classic result is extended and a single letter characterization for the reliability function of finite-state Markov channels is presented, under the assumption that the channel state is causally observed both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference. In particular the convex analytical approach to Markov decision processes is adopted to handle problems with stopping time horizons arising from variable-length coding schemes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
