Browse Prior Art Database

An Efficient Method for Run Length Encoding

IP.com Disclosure Number: IPCOM000108189D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 1 page(s) / 47K

Publishing Venue

IBM

Related People

Feig, E: AUTHOR [+2]

Abstract

Novel methods for run-length encoding are disclosed. The methods lead to simpler decoding algorithms than standard run-length encoding methods.

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

An Efficient Method for Run Length Encoding

      Novel methods for run-length encoding are disclosed.  The
methods lead to simpler decoding algorithms than standard run-length
encoding methods.

      For simplicity, assume that the data stream is made up of
integers and run-lengths of zeros are coded.  The methods given are
easily generalized to other types run-length encoders.

      Let the data block have n run-lengths.  At the begining of a
block, the encoder sends a codeword indicating that the block has n
run-lengths.  This codeword is followed by n codewords containing the
run-length data.  No end of block codeword is sent.  On the decoding
side, the decoder first decodes the codeword that indicates the
number of run-lengths.  The decoder then enters a simple loop to
decode the n run-length codewords.

      The method just described will lead to some redundancy in the
coded data stream.  Consider the case when the last two data elements
are non-zero.  The information contained in the codeword indicating
the number of run-lengths and the first n-1 run-length codewords
indicate that the last run length must have length 0.  Nonetheless,
when the method we have just described is used, the encoder will send
a codeword indicating the the last run-length is 0.  The following
variation on the method just described eliminates this redundancy.

      When the last two data elements are non-zero, the encoder does
not send a codeword indicating...