Patent US4494151A successfully refreshed from Google Patents.
US4494151A
Expired / Lapsed
US
⏱️ 0.0 years remaining
4-Pixel run-length code for data compression
Assignee: Xerox Corp
•
Filing: 1982-02-09
•
Granted: 1985-01-15
•
Expires: 2002-02-09
Abstract
Abstract A circuit to encode image data. The circuit receives image data in four bit nibbles which are either all-zero nibbles or terminating nibbles containing at least one non-zero bit. The circuit output is a series of code words, each a multiple of four bits and up to twenty-four bits long, packed into eight bit output words. Each code word contains a first part containing a run length specifying the number of received all-zero nibbles and a second part specifying the bit pattern of the terminating nibble. The circuit uses PROMs for the look-up and control elements and a pipeline of registers to allow high speed operation.
Inventors
- 👤 Henry H. Liao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 10:30
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; G; G06; G06T; G06T9/00; G06T9/005; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/415
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
116 words
A method for the compression of serial binary data comprising the steps of: separating said serial data into bit nibbles, counting the run length of all-zero nibbles received prior to receiving a terminating nibble, converting the run length of all-zero nibbles into a first code word portion, converting the terminating nibble data pattern into a second code word portion, the more common terminating nibble data patterns being compressed into second code words of shorter length than the original data, generating a plurality of flag bits to identify the format of said code word, and combining the first and second code word portions and said flag bits into a code word a multiple of n bits long.
Claim 2
Independent Claim
116 words
A method for the compression of serial binary data comprising the steps of: separating said serial data into bit nibbles, counting the run length of all-zero nibbles received prior to receiving a terminating nibble, converting the run length of all-zero nibbles into a first code word portion, converting the terminating nibble data pattern into a second code word portion, the more common terminating nibble data patterns being compressed into second code words of shorter length than the original data, generating a plurality of flag bits to identify the format of said code word, and combining the first and second code word portions and said flag bits into a code word a multiple of n bits long.
Claim 3
Dependent Claim
9 words
The method of claim 1 where n=4 and x=4.
Claim 4
Dependent Claim
28 words
The method of claim 2 wherein said more common terminating nibble data patterns are 1000, 0100, 0010 and 0001, and are compressed into 2 bit second code words.
Claim 5
Dependent Claim
18 words
The method of claim 2 wherein the more frequently occurring run lengths are assigned to shorter code words.
Claim 6
Dependent Claim
78 words
The method of claim 4 wherein any all-zero count which is too large to be convertable into a first code word portion is separated into a first run length which is convertable, and a second run length which is the remainder, said first run length being converted into a code word which contains only run length information, and said second run length and the terminating nibble being converted into an additional code word as described in claim 4.
Claim 7
Dependent Claim
37 words
The method of claim 5 wherein the first run length is 64, all code words are 4, 8 or 12 bits, and code word prefixes of one, two or three bits identify the length of the word.
Claim 8
Dependent Claim
25 words
The method of claim 6 wherein code word prefixes of 10, 0 and 11 identify code word lengths of 4, 8 and 12 bits, respectively.
Claim 9
Dependent Claim
42 words
The method of claim 6 wherein the four more common terminating nibble bit patterns are coded into 2 bit code word portions, and the remaining eleven patterns are embedded directly into an 8 or 12 bit code word to enable simple decoding.
Claim 10
Dependent Claim
14 words
The method of claim 5 wherein otherwise unused codes are used as control codes.
Claim 11
Dependent Claim
16 words
The method of claim 9 wherein six control codes are converted into 8 bit code words.
Claim 12
Independent Claim
187 words
A method of run-length encoding and compression for converting input data into output code words, each a multiple of n bits in length, for use in an image processing system including means to raster scan a document to form raster scan lines of black and white pixels, each line represented as a series of n binary bit nibbles, the method of converting strings of said input data into a series of encoded words having a run-length and data pattern format, said conversion comprising the steps of: determining the run length of zero nibbles prior to receiving a terminating nibble, generating a first code word portion representative of said run length, generating a second code word portion representative of said terminating nibble, wherein said second code word portion may be a compressed representation of said terminating nibble, generating a plurality of flag bits to specify the format of said code word, and combining said first and second code word portions and said flag bits into composite code words, the bit lengths of which are multiple integers of n thereby permitting high data conversion rates of said input data.
Claim 13
Independent Claim
187 words
A method of run-length encoding and compression for converting input data into output code words, each a multiple of n bits in length, for use in an image processing system including means to raster scan a document to form raster scan lines of black and white pixels, each line represented as a series of n binary bit nibbles, the method of converting strings of said input data into a series of encoded words having a run-length and data pattern format, said conversion comprising the steps of: determining the run length of zero nibbles prior to receiving a terminating nibble, generating a first code word portion representative of said run length, generating a second code word portion representative of said terminating nibble, wherein said second code word portion may be a compressed representation of said terminating nibble, generating a plurality of flag bits to specify the format of said code word, and combining said first and second code word portions and said flag bits into composite code words, the bit lengths of which are multiple integers of n thereby permitting high data conversion rates of said input data.
Claim 14
Dependent Claim
42 words
The method of claim 11 including the step of compressing second code word portions comprising terminating nibbles of common occurrence by generating two bit second code word portions thereby producing shorter code words upon combining said first and second code word portions.
Claim 15
Dependent Claim
16 words
The method of claim 11 wherein n=4 and said multiple integers are 1, 2 and 3.
Claim 16
Dependent Claim
37 words
The method of claim 11 including the steps of separating out run lengths of said zero nibbles that are multiples of m, and generating a second type of code word indicative only of the run length thereof.
Claim 17
Dependent Claim
24 words
The method of claim 11 including the step of providing one, two or three bit code word prefixes indicative of the code word length.
Claim 18
Dependent Claim
50 words
The method of claim 14 including the step of providing code word prefixes indicative of the code word length, said code prefixes being 10, 0 and 11, identifying code word lengths of 4, 8 and 12 bits, respectively, where n is equal to 4 and m is equal to 64.
Claim 19
Independent Claim
166 words
A method of compressing serial binary data into code words comprising the steps of: separating said serial data into 4 bit nibbles, incrementing the count of all-zero nibbles if the current nibble is all zeros, transmitting a code word if the current nibble is not all zeros, said code word being one of three types, a first type 4 bits in length wherein the leading two bits are code word identifiers and the second two bits identify four of sixteen possible nibble bit patterns, a second type 8 bits in length wherein the leading two or three bits are code word identifiers, two bits identify said four nibble patterns and the remaining bits are the all-zero nibble count, and a third type 8 or 12 bits in length wherein the leading two or three bits are code word identifiers, four bits are an exact representation of the current nibble bit pattern and the remaining bits are the all-zero nibble count, and zeroing the all-zero nibble count.
Claim 20
Independent Claim
166 words
A method of compressing serial binary data into code words comprising the steps of: separating said serial data into 4 bit nibbles, incrementing the count of all-zero nibbles if the current nibble is all zeros, transmitting a code word if the current nibble is not all zeros, said code word being one of three types, a first type 4 bits in length wherein the leading two bits are code word identifiers and the second two bits identify four of sixteen possible nibble bit patterns, a second type 8 bits in length wherein the leading two or three bits are code word identifiers, two bits identify said four nibble patterns and the remaining bits are the all-zero nibble count, and a third type 8 or 12 bits in length wherein the leading two or three bits are code word identifiers, four bits are an exact representation of the current nibble bit pattern and the remaining bits are the all-zero nibble count, and zeroing the all-zero nibble count.
Claim 21
Dependent Claim
17 words
The method of claim 17 wherein said four identified bit patterns are 1000, 0100, 0010 and 0001.
Claim 22
Dependent Claim
61 words
The method of claim 17 further comprising a fourth type of code word 12 bits in length wherein the first one or several bits are code word identifiers and the remaining bits contain a representation of the all-zero nibble count, for use when the count is too large to be contained in any of the first three types of code words.
Claim 23
Dependent Claim
17 words
The method of claim 17 wherein a number of 8 bit codes are reserved as control codes.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-01-15 | 1988-07-16 | 1989-01-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-01-15 | 1992-07-16 | 1993-01-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-01-15 | 1996-07-16 | 1997-01-15 | $7700.00 | Window Closed / Lapsed |