Title :
Universal source coding theory based on grammar transforms
Author :
Yang, En-Hui ; Kieffer, John C.
Author_Institution :
Dept. of Electr. & Comput. Eng., Waterloo Univ., Ont., Canada
Abstract :
A new universal lossless source coding theory is presented. Within this theory, a lossless source code called a grammar based code first transforms the original data sequence to be compressed into a context free grammar, from which the original data sequence can be fully reconstructed by performing parallel substitutions, and then uses an arithmetic coding algorithm to compress the context free grammar of the corresponding sequence of parsed phrases. It is shown that if a grammar-based code transforms each data sequence into an irreducible context free grammar, then the grammar-based code is universal for the class of stationary, ergodic sources. Specific redundancy bounds are also given
Keywords :
arithmetic codes; context-free grammars; sequences; source coding; transforms; arithmetic coding; context free grammar; data sequence; grammar based code; grammar transforms; grammar-based code; lossless source code; parallel substitution; parsed phrases; redundancy bounds; stationary ergodic sources; universal lossless source coding theory; universal source coding theory; Algorithm design and analysis; Arithmetic; Compression algorithms; Context modeling; Data compression; Encoding; Entropy; Heuristic algorithms; Predictive models; Source coding;
Conference_Titel :
Information Theory and Communications Workshop, 1999. Proceedings of the 1999 IEEE
Conference_Location :
Kruger National Park
Print_ISBN :
0-7803-5268-8
DOI :
10.1109/ITCOM.1999.781414
