loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Ofer Shayevitz, Tel Aviv University, Tel Aviv 69978, Israel
Eado Meron, Tel Aviv University, Tel Aviv 69978, Israel
Meir Feder, Tel Aviv University, Tel Aviv 69978, Israel
Ram Zamir, Tel Aviv University, Tel Aviv 69978, Israel
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.