Browse Prior Art Database

LIFO Arithmetic Compression Coding Method for Conditional Sources

IP.com Disclosure Number: IPCOM000052055D
Original Publication Date: 1981-Apr-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 4 page(s) / 90K

Publishing Venue

IBM

Related People

Arps, RB: AUTHOR [+2]

Abstract

This article relates to a method for LIFO (last in, first out) compression coding of bit streams from conditional binary sources, such as Boolean-coded image arrays. The method and its implementing apparatus is believed cost effective for high-speed compression applications where the power of conditional encoding is desired, along with less complexity and greater speed than the most powerful known algorithm [1]. It is also cheaper and much more flexible than other algorithms in the same class [2], in that the necessary compressed data buffering is reduced, simplified, and can be located at either the encoder, the decoder, or in centralized store-and-forward hardware.

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 45% of the total text.

Page 1 of 4

LIFO Arithmetic Compression Coding Method for Conditional Sources

This article relates to a method for LIFO (last in, first out) compression coding of bit streams from conditional binary sources, such as Boolean-coded image arrays. The method and its implementing apparatus is believed cost effective for high-speed compression applications where the power of conditional encoding is desired, along with less complexity and greater speed than the most powerful known algorithm [1]. It is also cheaper and much more flexible than other algorithms in the same class [2], in that the necessary compressed data buffering is reduced, simplified, and can be located at either the encoder, the decoder, or in centralized store-and-forward hardware. For example, with the buffering in the encode step, this algorithm is believed cost effective in a single encode/multiple high-speed decode environment, such as may be found in font generation in all-points-addressable output devices.

ENCODING: The encoding method steps comprise (1) scanning a matrix in reverse raster scan order; (2) for each source bit, ascertaining the integer value of its conditioning class K, derived from a "template" on N nearby bits; (3) incrementing the corresponding kth run counter; (4) if the symbol to be encoded is a least probable symbol (LPS) for class K, pushing the corresponding codeword c(s) on a LIFO stack and resetting the kth run counter to p. These coding steps are iterated within a scan line, with the K counters originally initialized at a count of 1. Upon completion of a scan line, the remaining K counts are translated into codewords and transmitted as a header in the order c(1), c(2),...,c(k). The accumulated codewords are then transmitted in LIFO order by popping the stack.

If the encoder scans the B/W (black/white) document in reverse order, it can encode, making one pass of the image. Then, by buffering the compressed code string in a LIFO stack, it can be transmitted in the exact order required by the decoder by simply popping the stack. The process generates the multiplexed run lengths in the exact order they are required by the decoder if it is to generate the source sequence of 0's and 1's in the desired raster scan order.

The encoder makes a pass of the document in reverse order. Details of this LIFO encoding process are as follows: Whenever an LPS (least probable symbol) is encountered, a code word is generated, based on the appropriate kth state emitted and placed on the code string, growing the code string to the left. The composition of the code string is shown in Fig. 1.

Fig. 2 illustrates a major concept. The string of 0's shown in this figure has the same run length, independent of whether the run is approached from the FIFO (left to right) or LIFO (right to left) direction. See Original.

When the encoder finally reached the "last" pel (in the reverse sense), all current counter contents hold the initialization run-lengths to the first LPS symbol for...