Average Coding Rate of a Multi-Shot Tunstall Code with an Arbitrary Parsing Tree Sequence

Mitsuharu ARIMURA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.12   pp.2281-2285
Publication Date: 2016/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.2281
Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)
Category: Source Coding and Data Compression
Keyword: 
lossless data compression,  source coding,  variable-to-fixed length code,  Tunstall code,  average coding rate,  

Full Text: PDF>>
Buy this Article




Summary: 
Average coding rate of a multi-shot Tunstall code, which is a variation of variable-to-fixed length (VF) lossless source codes, for stationary memoryless sources is investigated. A multi-shot VF code parses a given source sequence to variable-length blocks and encodes them to fixed-length codewords. If we consider the situation that the parsing count is fixed, overall multi-shot VF code can be treated as a one-shot VF code. For this setting of Tunstall code, the compression performance is evaluated using two criterions. The first one is the average coding rate which is defined as the codeword length divided by the average block length. The second one is the expectation of the pointwise coding rate. It is proved that both of the above average coding rate converge to the entropy of a stationary memoryless source under the assumption that the geometric mean of the leaf counts of the multi-shot Tunstall parsing trees goes to infinity.