Browse Prior Art Database

Prefix Run-Length Coded Huffman-Shannon-Fano Code for Table Size Reduction

IP.com Disclosure Number: IPCOM000112768D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 41K

Publishing Venue

IBM

Related People

Kimoto, H: AUTHOR [+2]

Abstract

Disclosed is a method to convert variable-length Huffman-Shannon-Fano (HSF) Code to fixed-length code for easy and fast table searching. Also, this method makes it possible to reduce a code conversion table size.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 64% of the total text.

Prefix Run-Length Coded Huffman-Shannon-Fano Code for Table Size
Reduction

      Disclosed is a method to convert variable-length
Huffman-Shannon-Fano (HSF) Code to fixed-length code for easy and
fast table searching.  Also, this method makes it possible to reduce
a code conversion table size.

A structure of Prefix Run-Length (PRL) Coded HSF Code

 - When the number of components is N and the Maximum code length is
    Lmax, the maximum number of consecutive symbols of the same
    value(run length) of this HSF code header is Lmax.  If only the
    Lmax value will be handled as an exception, this run-length value
    can be expressed as log2(Lmax) bit code.

                  exp) Lmax = 16  Log2(16) = 4(bit)

-And the maximum number of bits of the remaining bit data without run
   length can be expressed as CEIL(log2(FLOOR((N - 1) / 2))).

         note: CEIL(N) means the minimum integral number more than or
               equal to N.
               FLOOR(N) means the maximum integral number less than
or
               equal to N.

               exp) N = 256  CEIL(log2(FLOOR((N - 1) / 2))) = 7(bit)

      Therefore, the Prefix Run-Length Coded HSF Code maximum length
can be expressed as
               log2(Lmax) + CEIL(log2(FLOOR((N - 1) / 2)))

      This Code maximum length is less than the original HSF Code
maximum length.  The following is a Prefix...