MIT Department of Electrical Engineering & Computer Science

SPECIAL EECS SEMINAR

Thursday, April 27, 1995
RLE Conference Room, 36-428

Refreshments at 1:45 PM
Talk at 2:00 PM

Variable-to-Fixed Length Codes for Sources with Memory

Serap A. Savari
Massachusetts Institute of Technology

The construction of good variable-to-fixed length codes is an important problem in data compression that is not well-understood for sources with memory. A variable-to-fixed length encoding procedure is a mapping from a dictionary of variable length strings of source outputs to the set of codewords of a given length. Variable-to-fixed length codes are noteworthy because of their great potential for exploiting the statistical dependencies of the source output. Tunstall codes are variable-to-fixed length codes that maximize the expected number of source letters per dictionary string for discrete, memoryless sources. We analyze a generalization of Tunstall coding to Markov sources and demonstrate that this code becomes asymptotically optimal as the dictionary size increases.