2007 Data Compression Conference (DCC'07) Bounds on Redundancy in Constrained Delay Arithmetic Coding Snowbird, Utah March 27-March 29 ISBN: 0-7695-2791-4
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2007.19
We address the problem of a ?nite delay constraint in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. Therefore, to meet a ?nite delay constraint, it is necessary to intervene with the normal ?ow of the coding process, e.g., to insert ?ctitious symbols. This results in an in- evitable coding rate redundancy. In this paper, we derive an upper bound on the achievable redundancy for a memoryless source. We show that this redun- dancy decays exponentially as a function of the delay constraint, and thus it is clearly superior to block to variable methods in that aspect. The redundancy- delay exponent is shown to be lower bounded by log (1=?), where ? is the probability of the most likely source symbol. Our results are easily applied to practical problems such as the compression of English text.
Citation:
Ofer Shayevitz, Eado Meron, Meir Feder, Ram Zamir, "Bounds on Redundancy in Constrained Delay Arithmetic Coding," dcc, pp.133-142, 2007 Data Compression Conference (DCC'07), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||