Byte-based prefix encoding

Abstract

Two software-only prefix encoding techniques employ encoding look-up tables to produce contributions to the encoded bit stream that are incremented in integral numbers of bytes to facilitate accelerated encoding rates at the expense of an acceptable trade-off in increased memory size requirements. The first technique, referred to as offset-based encoding, employs encoding tables which eliminate most of the bit-based operations that need to be performed by a prefix encoder without inordinately expanding memory requirements. In offset-based encoding, a Huffman table is employed which contains information for each number of bits by which the length of a Huffman word is offset from an integral number of bytes. The encoding method generates bytes of encoded data, even though the Huffman code has variable length code words for each symbol to be encoded. The second technique, referred to as byte-based encoding, employs a byte-based Huffman encoding table which operates even faster than the offset-based encoding scheme because it does not employ any bit-based operations at all; however, this is achieved at the expense of a considerable expansion in memory requirements.