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

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...