Title :
On random-access data compaction
Author :
Willems, Frans M J ; Tjalkens, Tjalling J. ; Volf, Paul A J
Author_Institution :
Dept. of Electr. Eng., Eindhoven Univ. of Technol., Netherlands
Abstract :
Consider a binary i.i.d. sequence that consists of K=2J blocks of length T. We are looking for a universal compaction method that allows us to decode a certain block by looking only at certain segments in the code sequence. We have investigated a hierarchical method that encodes the source sequence into a code sequence that consists of 2J+1 variable-length segments. For decoding a certain block only J+2 segments need to be accessed. During decoding it is always clear where the next segment that needs to be accessed appears in the code sequence. The cumulative individual redundancy that is achieved by this method, is optimal in the sense that ½ log2 N behavior is obtained where N=2JT. An additional increase of at most one bit per code-segment is possible however
Keywords :
binary sequences; decoding; source coding; variable length codes; binary i.i.d. sequence; code sequence; decoding; hierarchical method; optimal cumulative individual redundancy; prefix codes; random-access data compaction; source sequence encoding; universal compaction method; variable-length code segments; Binary sequences; Compaction; Decoding;
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.781428