Representing Variable-Length Codes in Fixed-Length T-Depletion Format in Encoders and Decoders

Abstract

T-Codes are a class of variable-length codes. Their self-synchronisation properties are useful in compression and communication applications where error recovery rather than error correction is at issue, for example, in digital telephony. T-Codes may be used without error correction or additional synchronisation mechanisms. Typically, the representation of variable-length codes is a problem in computers based on a fixed-length word architecture. This presents a problem in encoder and decoder applications. The present paper introduces a fixed-length format for storing and handling variable-length T-Code codewords, the T-depletion codewords, which are derived from the recursive construction of the T-Code code- words. The paper further proposes an algorithm for the conversion of T-Code codewords into T-depletion codewords that may be used as a decoder for generalized T-Codes. As well as representing all codewords of a T-Code set (the leaf nodes in the set's decoding tree), the T-depletion code format also permits the representation of “pseudo-T codewords” - strings that are not in the T-Code set. These strings are shown to correspond uniquely to all proper prefixes of T-Code codewords, thus permitting the representation of both intermediate and final decoder states in a single format. We show that this property may be used to store arbitrary finite and prefix-free variable-length codes in a compact fixed-length format.