JUCS - Journal of Universal Computer Science 3(11): 1207-1225, doi: 10.3217/jucs-003-11-1207
Representing Variable-Length Codes in Fixed-Length T-Depletion Format in Encoders and Decoders
expand article infoUlrich Günther, Peter Hertling, Radu Nicolescu, Mark Titchener
‡ Department of Computer Science, The University of Auckland, Auckland, New Zealand
Open Access
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
variable-length codes, T-Codes, encoders, decoders, representation