Computer Science – Information Theory
Scientific paper
2007-12-06
Computer Science
Information Theory
25 pages, 17 figures. Submitted to the IEEE Transactions on Information Theory
Scientific paper
Inspired by the context of compressing encrypted sources, this paper considers the general tradeoff between rate, end-to-end delay, and probability of error for lossless source coding with side-information. The notion of end-to-end delay is made precise by considering a sequential setting in which source symbols are revealed in real time and need to be reconstructed at the decoder within a certain fixed latency requirement. Upper bounds are derived on the reliability functions with delay when side-information is known only to the decoder as well as when it is also known at the encoder. When the encoder is not ignorant of the side-information (including the trivial case when there is no side-information), it is possible to have substantially better tradeoffs between delay and probability of error at all rates. This shows that there is a fundamental price of ignorance in terms of end-to-end delay when the encoder is not aware of the side information. This effect is not visible if only fixed-block-length codes are considered. In this way, side-information in source-coding plays a role analogous to that of feedback in channel coding. While the theorems in this paper are asymptotic in terms of long delays and low probabilities of error, an example is used to show that the qualitative effects described here are significant even at short and moderate delays.
Chang Cheng
Sahai Anant
No associations
LandOfFree
The price of ignorance: The impact of side-information on delay for lossless source-coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The price of ignorance: The impact of side-information on delay for lossless source-coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The price of ignorance: The impact of side-information on delay for lossless source-coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-91415