Properties and Design of Variable-to-Variable Length Codes

摘要

For the entropy coding of independent and identically distributed (i.i.d.) binary sources, variable-to-variable length (V2V) codes are an interesting alternative to arithmetic coding. Such a V2V code translates variable length words of the source into variable length code words by employing two prefix-free codes. In this article, several properties of V2V codes are studied, and new concepts are developed. In particular, it is shown that the redundancy of a V2V code cannot be zero for a binary i.i.d. source {X) with 0 p(X)(1) 0.5. Furthermore, the concept of prime and composite V2V codes is proposed, and it is shown why composite V2V codes can be disregarded in the search for particular classes of minimum redundancy codes. Moreover, a canonical representation for V2V codes is proposed, which identifies V2V codes that have the same average code length function. It is shown how these concepts can be employed to greatly reduce the complexity of a search for minimum redundancy (size-limited) V2V codes.