Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimum Redundancy Coding for Uncertain Sources
116
0
0.0
(
0
)
Added by
Michael Baer
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Consider the set of source distributions within a fixed maximum relative entropy with respect to a given nominal distribution. Lossless source coding over this relative entropy ball can be approached in more than one way. A problem previously considered is finding a minimax average length source code. The minimizing players are the codeword lengths --- real numbers for arithmetic codes, integers for prefix codes --- while the maximizing players are the uncertain source distributions. Another traditional minimizing objective is the first one considered here, maximum (average) redundancy. This problem reduces to an extension of an exponential Huffman objective treated in the literature but heretofore without direct practical application. In addition to these, this paper examines the related problem of maximal minimax pointwise redundancy and the problem considered by Gawrychowski and Gagie, which, for a sufficiently small relative entropy ball, is equivalent to minimax redundancy. One can consider both Shannon-like coding based on optimal real number (ideal) codeword lengths and a Huffman-like optimal prefix coding.
rate research
Read More
Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The $ell$-th stopping redundancy is the minimum number of rows in the parity-check matrix of a code, which contains no stopping sets of size up to $ell$. In this work, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative decoding over the BEC, the parity-check matrix should contain no coverable stopping sets of size $ell$, for $1 le ell le n-k$, where $n$ is the code length, $k$ is the code dimension. By estimating the number of coverable stopping sets, we obtain upper bounds on the $ell$-th stopping redundancy, $1 le ell le n-k$. The bounds are derived for both specific codes and code ensembles. In the range $1 le ell le d-1$, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented.
We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a prior distribution that is known to be close to the source distribution, a problem first considered by Juba et al. We consider the question of how much longer the messages need to be in order to cope with the uncertainty about the receivers prior and the source distribution, respectively, as compared to the standard source coding problem. We consider two variants of this uncertain priors problem: the original setting of Juba et al. in which the receiver is required to correctly recover the message with probability 1, and a setting introduced by Haramaty and Sudan, in which the receiver is permitted to fail with some probability $epsilon$. In both settings, we obtain lower bounds that are tight up to logarithmically smaller terms. In the latter setting, we furthermore present a variant of the coding scheme of Juba et al. with an overhead of $logalpha+log 1/epsilon+1$ bits, thus also establishing the nearly tight upper bound.
Distributed arithmetic coding (DAC) has been shown to be effective for Slepian-Wolf coding, especially for short data blocks. In this letter, we propose to use the DAC to compress momery-correlated sources. More specifically, the correlation between sources is modeled as a hidden Markov process. Experimental results show that the performance is close to the theoretical Slepian-Wolf limit.
A transmitter without channel state information (CSI) wishes to send a delay-limited Gaussian source over a slowly fading channel. The source is coded in superimposed layers, with each layer successively refining the description in the previous one. The receiver decodes the layers that are supported by the channel realization and reconstructs the source up to a distortion. In the limit of a continuum of infinite layers, the optimal power distribution that minimizes the expected distortion is given by the solution to a set of linear differential equations in terms of the density of the fading distribution. In the optimal power distribution, as SNR increases, the allocation over the higher layers remains unchanged; rather the extra power is allocated towards the lower layers. On the other hand, as the bandwidth ratio b (channel uses per source symbol) tends to zero, the power distribution that minimizes expected distortion converges to the power distribution that maximizes expected capacity. While expected distortion can be improved by acquiring CSI at the transmitter (CSIT) or by increasing diversity from the realization of independent fading paths, at high SNR the performance benefit from diversity exceeds that from CSIT, especially when b is large.
An encoder, subject to a rate constraint, wishes to describe a Gaussian source under squared error distortion. The decoder, besides receiving the encoders description, also observes side information consisting of uncompressed source symbol subject to slow fading and noise. The decoder knows the fading realization but the encoder knows only its distribution. The rate-distortion function that simultaneously satisfies the distortion constraints for all fading states was derived by Heegard and Berger. A layered encoding strategy is considered in which each codeword layer targets a given fading state. When the side-information channel has two discrete fading states, the expected distortion is minimized by optimally allocating the encoding rate between the two codeword layers. For multiple fading states, the minimum expected distortion is formulated as the solution of a convex optimization problem with linearly many variables and constraints. Through a limiting process on the primal and dual solutions, it is shown that single-layer rate allocation is optimal when the fading probability density function is continuous and quasiconcave (e.g., Rayleigh, Rician, Nakagami, and log-normal). In particular, under Rayleigh fading, the optimal single codeword layer targets the least favorable state as if the side information was absent.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
