US5930790A
Expired / Lapsed
US
⏱️ 0.0 years remaining
String-match array for substitutional compression
Assignee: Xerox Corp
•
Filing: 1997-09-25
•
Granted: 1999-07-27
•
Expires: 2017-09-25
Abstract
Abstract A circuit for implementing a substitutional compressor. Comparators compare a current input pixel against a large number of previous pixels, the "history", stored in a series of shift registers. Each register and associated comparator constitutes a cell. If one or more matches are found the history data is shifted one pixel, the non-matching cells are disabled, and the next input pixel is compared against the contents of the same cells that had the previous matches. The matching is terminated when the longest series of matching pixels is found. The output code is then the length of the matching series of pixels, and the displacement of the first input pixel from the first matching pixel. An encoder generates an initialize signal that resets all of the disabled cells on the same clock cycle on which the output code word is generated. To make the circuit more compact, the cells can be arranged into a square format with one output line for each row and column from the cells to the encoder.
Inventors
- 👤 Simon M. Law
- 👤 Daniel H. Greene
- 👤 Li-Fung Cheung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 07:38
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
301 words
A circuit for compressing a string of words having one or more bits per word comprising: a first cell and a remaining number of cells, each comprising a means for storing a word, and a comparator, wherein all of said cells are coupled together so that all of the means for storing form a continuous register and are adapted to shift the words one word when a word is shifted into the means for storing of the first cell, each comparator coupled to the current word and the word stored in the means for storing in the same cell and adapted to compare the current word and the word stored in the means for storing, and to generate a match signal if there is a match, and to disable itself for detecting a match during the next clock cycle if there is no match, and an encoder coupled to every comparator and responsive to said match signals for generating an output code comprising the largest number of consecutive matches in a single cell and the displacement between the input and matching word, and wherein the cells are arranged into rows and columns, with an output line for each row and each column of cells for coupling all of the cells in each row and each column on an output line to the encoder, and wherein, after the detection of a non-match after two or more consecutive matches, if there are cells in more than one row with the same largest number of matches, the match generated by a cell in a previous row will be selected to output the code, and if there is more than one cell in a row with the same number of matches, the match generated by a previous cell will be selected to output the code.
Claim 2
Dependent Claim
301 words
A circuit for compressing a string of words having one or more bits per word comprising: a first cell and a remaining number of cells, each comprising a means for storing a word, and a comparator, wherein all of said cells are coupled together so that all of the means for storing form a continuous register and are adapted to shift the words one word when a word is shifted into the means for storing of the first cell, each comparator coupled to the current word and the word stored in the means for storing in the same cell and adapted to compare the current word and the word stored in the means for storing, and to generate a match signal if there is a match, and to disable itself for detecting a match during the next clock cycle if there is no match, and an encoder coupled to every comparator and responsive to said match signals for generating an output code comprising the largest number of consecutive matches in a single cell and the displacement between the input and matching word, and wherein the cells are arranged into rows and columns, with an output line for each row and each column of cells for coupling all of the cells in each row and each column on an output line to the encoder, and wherein, after the detection of a non-match after two or more consecutive matches, if there are cells in more than one row with the same largest number of matches, the match generated by a cell in a previous row will be selected to output the code, and if there is more than one cell in a row with the same number of matches, the match generated by a previous cell will be selected to output the code.
Claim 3
Dependent Claim
54 words
The circuit of claim 1 wherein the encoder will output the code after the detection of a non-match in the cell that generated the longest number of matches on the previous clock, and initialize the circuit to compare the current word with the contents of every means for storing on the same clock cycle.
Claim 4
Dependent Claim
244 words
A circuit for compressing a string of words comprising: a first cell and a remaining number of cells, each cell comprising a means for storing a word and a comparator, wherein all of said cells are coupled together so that all of the means for storing form a continuous register and are adapted to shift the words one word when a current word is shifted into said first means for storing on each clock cycle, each comparator coupled to the current input pixel and the means for storing in the same cell, and adapted to compare the current pixel and the pixel stored in the means for storing on each clock cycle, and to generate a match signal when there is a match, and to disable itself when there is no match, and an encoder responsive to the first clock after the end of a continuous number of match signals for generating an output code comprising the largest number of consecutive matches in a single cell and the displacement of the cell that detected the matches or the lowest numbered cell that detected the matches if there were more than one, and for generating an initializing signal to enable all of the comparators that were disabled, and wherein the cells are arranged in rows and columns and wherein the encoder is coupled to all of the cells in each row by one line and all of the cells in each column by one line.
Claim 5
Dependent Claim
244 words
A circuit for compressing a string of words comprising: a first cell and a remaining number of cells, each cell comprising a means for storing a word and a comparator, wherein all of said cells are coupled together so that all of the means for storing form a continuous register and are adapted to shift the words one word when a current word is shifted into said first means for storing on each clock cycle, each comparator coupled to the current input pixel and the means for storing in the same cell, and adapted to compare the current pixel and the pixel stored in the means for storing on each clock cycle, and to generate a match signal when there is a match, and to disable itself when there is no match, and an encoder responsive to the first clock after the end of a continuous number of match signals for generating an output code comprising the largest number of consecutive matches in a single cell and the displacement of the cell that detected the matches or the lowest numbered cell that detected the matches if there were more than one, and for generating an initializing signal to enable all of the comparators that were disabled, and wherein the cells are arranged in rows and columns and wherein the encoder is coupled to all of the cells in each row by one line and all of the cells in each column by one line.
References Cited (Backward Citations)
US3648254A
Cited
US5003307A
Cited
US5179378A
Cited
US5373290A
Cited
US5467319A
Cited
US5499382A
Cited
US5532693A
Cited
US5828593A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-26 | 2003-01-25 | 2003-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-26 | 2007-01-25 | 2007-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-26 | 2011-01-25 | 2011-07-27 | $7700.00 | Window Closed / Lapsed |