|
Representing Variable-Length Codes in Fixed-Length T-Depletion Format in Encoders and Decoders
Ulrich Günther (Department of Computer Science, The University of Auckland, New Zealand)
Peter Hertling (Department of Computer Science, The University of Auckland, New Zealand)
Radu Nicolescu (Department of Computer Science, The University of Auckland, New Zealand)
Mark Titchener (Department of Computer Science, The University of Auckland, New Zealand)
Abstract: T-Codes are a class of variable-length codes. Their self-synchronization properties are useful in compression and communication applications where error recovery rather than error correction is at issue, for example, in digital telephony. T-Code s may be used without error correction or additional synchronization 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 codewords. 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.
1.) The authors' research is supported by the Department of Computer Science, the Division of Science and Technology (Tamaki Campus), and the Graduate Research Fund, all of The University of Auckland, the Centre for Discrete Mathematics and Theoretical Computer Science (CDMTCS) of the University of Auckland and the University of Waikato, and by the Deutsche Forschungsgemeinschaft (DFG). 2.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.
Keywords: T-Codes, decoders, encoders, representation, variable-length codes
Categories: H.3.3
|
