Browse Prior Art Database

An Adaptive Run-Length Coding Algorithm

IP.com Disclosure Number: IPCOM000047922D
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Feb-08
Document File: 3 page(s) / 50K

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR

Abstract

This invention relates to the combining of Golomb's non-adaptive run-length code and a binary adaptive technique. The counter used for adaptation is also used for the coder. The result is simple because the adaptive part is synchronized with the coding part to avoid the carry-over problem. In the prior art of run-length codes, for a predetermined probability of the more probable symbol, Golomb provides a procedure for deriving a table of code words which encode the runs. Langdon and Rissanen describe an adaptive algorithm for compressing black/white (B/W) images. Treating the image as a memoryless source, the algorithm becomes an adaptive run-length code. With the conditioning state as the value of the previous symbol (0 or 1), the algorithm reduces to an adaptive run-length code for white runs and another for black runs.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

An Adaptive Run-Length Coding Algorithm

This invention relates to the combining of Golomb's non-adaptive run-length code and a binary adaptive technique. The counter used for adaptation is also used for the coder. The result is simple because the adaptive part is synchronized with the coding part to avoid the carry-over problem. In the prior art of run-length codes, for a predetermined probability of the more probable symbol, Golomb provides a procedure for deriving a table of code words which encode the runs. Langdon and Rissanen describe an adaptive algorithm for compressing black/white (B/W) images. Treating the image as a memoryless source, the algorithm becomes an adaptive run-length code. With the conditioning state as the value of the previous symbol (0 or 1), the algorithm reduces to an adaptive run-length code for white runs and another for black runs. Ordinary codes for binary events exist which accept a coding parameter, independent of where it came from. These coders are more complex because they are designed to accept any coding parameter at any bit position. Also, adaptive techniques for binary events exist, The adaptive run-length coding algorithm method of this invention utilizes repeat event preselection. In this regard, the Golomb algorithm preselects the run event: the more probable symbol is known. For the application of run-length codes to repeated characters in data files, the event on which runs are counted is preselected (i.e., the repeat event). Moreover, for B/W images with separate codes for runs of black and white, the run event is also preselected (white for white runs, black for black runs). Preliminaries: Adapt on the value K = log2 (log base 2) of m. For example for m = 1, number K is 0. At the start of encoding, the value K of 0 could be used; this is a choice made by the designer. The algorithm uses two variables: Count and K. Count stores a binary integer. Variable K is a coding parameter, and gives the code its adaptive property. When the code is used in conjunction with contexts, a unique variable K(z) is used for each context z. For example, in B/W image compression the two contexts are black and white, and we would need two coding variables, K(white) and K(black). Observe that once we are in a context, we remain in it until a "nonrepeat" event is received. Variable Count is part of the code and not the model, so there is only one such variable. The Encoding Method: The algorithm for the preselected repeat event is given in the figure. At the start of encoding, C...