Technique for decoding variable length data codes

Details Technique for decoding variable length data codes Technique for decoding variable length data codes

1997-04-17

2002-05-07

Patel, Jayanti K. (Department: 2621)

Image analysis

Image compression or coding

Including details of decompression

C382S166000, C382S233000, C382S245000, C382S246000, C358S296000, C358S296000, C358S539000

Reexamination Certificate

active

06385341

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to variable length data codes, and more particularly, to a technique for efficient decoding of bit streams encoded with variable length codes.
BACKGROUND OF THE INVENTION
Variable length codes are known in the art, and are commonly used in applications, such as facsimile transmission, where a horizontal scan line comprises black and white pixels. Facsimile machines use variable length codes to represent the number of adjacent black or white pixels in a horizontal scan line. The number of adjacent pixels, sometimes called a “run,” is represented as a separate set of variable length codes for black pixels and white pixels. Variable length codes are efficient for representing the number of pixels in a black run or a white run because the most frequently occurring runs of black and white pixels are represented by only a few data bits in the variable length code, while less frequently occurring runs of black and white pixels are represented by longer length codes. Therefore, on average, a message is represented by the fewest number of data bits since the most commonly occurring runs of black and white pixels are represented by the shortest variable length codes.
Decoding bit streams encoded with variable length codes is a tedious process. Because the code length is unknown, the conventional decoder uses a binary tree to search for valid outputs, which are sometimes called tokens. The data tokens are typically stored in a look-up table that require one data look-up operation for each bit in the variable length code. Thus, decoding bit streams encoded with variable length codes is an inefficient process. This is particularly troublesome when attempting to perform real time operations, such as converting from one facsimile encoding standard to a second facsimile encoding standard. Therefore, it can be appreciated that there is a significant need for a system and method for efficient decoding of bit streams encoded with variable length codes. The present invention provides this and other advantages as will be apparent from the following detailed description and accompanying figures.
SUMMARY OF THE INVENTION
The present invention is embodied in a system and method for the decoding of bit streams encoded with variable length codes. The system includes a buffer to store a predetermined number of data bits extracted from the encoded bit stream and a data structure containing decoded tokens corresponding to a decoded version of the extracted bits. The predetermined number of data bits in the buffer are indicative of a location in the data structure containing at least a portion of a decoded token corresponding to a portion of the predetermined number of extracted data bits. The portion of the decoded token may not use all of the predetermined number of extracted data bits. Therefore, the system may further include count means to determine a number corresponding to the portion of the predetermined number of extracted data bits to permit the extraction of additional encoded data so as to reform the predetermined number of data bits in the buffer for a subsequent look-up operation. The system may also include a data pointer to indicate a data location where the data encoded with variable length codes is stored such that the buffer stores the predetermined number of data bits extracted from the encoded data starting at the data location indicated by the pointer. The count means may adjust to the pointer by adding the number corresponding to the portion of predetermined number of data bits used in the previous data look-up operation. This permits the subsequent extraction of the predetermined number of data bits from the encoded bit stream starting at the data location indicated by the pointer.
In one embodiment, the structure itself may contain additional data indicative of the number corresponding to the portion of the predetermined number of data bits such that the count means can use the additional data to permit the extraction of additional encoded data to reform the predetermined number of data bits in the buffer. The variable length codes have a maximum code length. In one embodiment, the predetermined number is at least as large as the maximum code length to guarantee the decoding of at least one token for each look-up operation, typically resulting, however, in retrieving multiple data tokens at once. In one embodiment, the decoding system may utilize a plurality of data structures each of which includes additional data indicative of which of the plurality of data structures will be used to decode next portion of encoded data.
The system may be readily employed in a computer where data is stored using a predetermined memory model. Under such a memory model, the data structures are constructed to use the predetermined memory model, thus minimizing data processing steps. The system may also be used with facsimile technology where the data encoded with variable length codes are facsimile data and the decoded tokens correspond to pixel data in a facsimile image. In this embodiment, the decoded tokens correspond to black pixel data and white pixel data and the data look-up table may comprise a black look-up table for use when the last decoded token was a white terminating token and a white look-up table for use when the last decoded token was a black terminating token. In one embodiment for facsimile operation, the facsimile look-up tables may include additional data to permit rapid decoding of two dimensional facsimile codes.


REFERENCES:
patent: 3717851 (1973-02-01), Cocke et al.
patent: 4097903 (1978-06-01), Nakagome et al.
patent: 4168513 (1979-09-01), Hains et al.
patent: 4185302 (1980-01-01), Mounts et al.
patent: 4558302 (1985-12-01), Welch
patent: 4606069 (1986-08-01), Johnsen
patent: 4809081 (1989-02-01), Linehan
patent: 4899149 (1990-02-01), Kahan
patent: 5032838 (1991-07-01), Murayama et al.
patent: 5317428 (1994-05-01), Osawa et al.
patent: 5414526 (1995-05-01), Friedman
patent: 5675332 (1997-10-01), Limberg
Dwu-Shian Ma et al., “programmable and parallel variable-length decoder for video systems”, IEEE, pp. 448-454, Aug. 1993.

Affiliated with

Also associated with

Rating

Technique for decoding variable length data codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Technique for decoding variable length data codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for decoding variable length data codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2903604