US4376933A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Circuit for compacting data
Assignee: Xerox Corp
•
Filing: 1980-05-23
•
Granted: 1983-03-15
•
Expires: 2000-05-23
Abstract
Abstract A circuit for compacting variable length data words into a fixed word length format is disclosed. Each variable length data word and its associated leading 0's are separated by a delimiter bit and stored in memory. When the memory is accessed, the output word is loaded in parallel into a first shift register and shifted to strip the leading 0's and delimiter bit. The remaining data bits are then shifted serially into a second shift register. When the second shift register is full, the resultant fixed length data word is latched out. When the first shift register is empty, the next word is loaded in from memory. In this way, a series of variable length words may be compacted into a series of fixed length words. This circuit is useful for compacting variable length Huffman codes since the boundaries between codes are self evident. This circuit can also be used as a character generator, where the variable length data output comprises the bits required to generate a character image on a raster scanned display.
Inventors
- 👤 Amitabh Saran
- 👤 Guillermo F. Luzio
- 👤 Frank A. Betron
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 18:46
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
195 words
A circuit for compacting variable length data into a fixed word length format comprising: an m bit per word memory for storing and outputting variable length data words, said m bits comprising a variable length data word, unused bits and a delimiter bit to mark the boundary between said data word and said unused bits, an m bit shift register for serially receiving the contents of said m bit shift register, an n bit shift register for serially receiving the contents of said m bit shift register, means for preventing the loading of said unused bits and said delimiter bit into said n bit shift register as said bits are shifted out of said m bit register, a counter responsive to the count of bits remaining in said m bit shift register for enabling said memory to load an m bit next word into said m bit shift register after the previous m bit register contents have been completely shifted out, and a counter responsive to the count of bits loaded into said n bit register for enabling said n bit register to output its contents in parallel after serially receiving n bits of data.
Claim 2
Dependent Claim
195 words
A circuit for compacting variable length data into a fixed word length format comprising: an m bit per word memory for storing and outputting variable length data words, said m bits comprising a variable length data word, unused bits and a delimiter bit to mark the boundary between said data word and said unused bits, an m bit shift register for serially receiving the contents of said m bit shift register, an n bit shift register for serially receiving the contents of said m bit shift register, means for preventing the loading of said unused bits and said delimiter bit into said n bit shift register as said bits are shifted out of said m bit register, a counter responsive to the count of bits remaining in said m bit shift register for enabling said memory to load an m bit next word into said m bit shift register after the previous m bit register contents have been completely shifted out, and a counter responsive to the count of bits loaded into said n bit register for enabling said n bit register to output its contents in parallel after serially receiving n bits of data.
Claim 3
Dependent Claim
16 words
The apparatus of claim 1 wherein said m bit per word memory is read only memory.
Claim 4
Dependent Claim
41 words
The apparatus of claim 1 further comprising an n bit processor and associated memory into which said n bit words are to be loaded, and a DMA channel for storing the n bit shift register output into said n bit memory.
Claim 5
Dependent Claim
41 words
The apparatus of claim 1 further comprising, an n bit processor and associated memory into which said n bit words are to be loaded and an I/O port for storing the n bit shift register output into said n bit memory.
Claim 6
Dependent Claim
24 words
The apparatus of claim 1 further comprising a buffer memory for temporarily storing said n bit word output from said n bit shift register.
Claim 7
Dependent Claim
15 words
The apparatus of claim 1 wherein said m bit per word memory is volatile RAM.
Claim 8
Dependent Claim
59 words
The apparatus of claim 1 wherein said variable length data are codes corresponding to input run length data and further comprising means for generating an address of the location in said m bit per word memory in which is located the code corresponding to said run length, and for addressing said m bit per word memory with said address.
Claim 9
Dependent Claim
65 words
The apparatus of claim 1 wherein said variable length data are data bit runs of variable lengths and further comprising means for generating an address of the location in said m bit per word memory in which is located the data bit run corresponding to a run length code received by said apparatus, and for addressing said m bit per word memory with said address.
Claim 10
Dependent Claim
52 words
The apparatus of claim 8 further comprising: a processor and associated memory and a subroutine in said memory adapted to be executed by said processor for iteratively accessing one or a plurality of m bits per word memory locations so that an output data bit run exceeding m bits may be output.
Claim 11
Dependent Claim
40 words
The apparatus of claim 8 wherein the address generated is a function of a raster scan line number and a character code and wherein said data bit runs of variable length are the corresponding video required to generate the character.
Claim 12
Dependent Claim
152 words
In a facsimile transmitter, a circuit for converting run length code into variable length code and for compacting said variable length code into n bit fixed length words, comprising: a memory in which variable length codes, unused bits and delimiter bits are stored, said memory arranged so that when an address which is a function of a run length is received, the associated variable length code will be produced, a first shift register adapted to receive the output bits from said memory in parallel, means for stripping said unused bits and delimiter bit from said first register, a second shift register adapted to receive the variable length code bits serially from said first shift register, means for enabling said second shift register to output its contents in parallel when said second shift register is full, and means for generating a next address for said memory when said first shift register becomes empty.
Claim 13
Dependent Claim
152 words
In a facsimile transmitter, a circuit for converting run length code into variable length code and for compacting said variable length code into n bit fixed length words, comprising: a memory in which variable length codes, unused bits and delimiter bits are stored, said memory arranged so that when an address which is a function of a run length is received, the associated variable length code will be produced, a first shift register adapted to receive the output bits from said memory in parallel, means for stripping said unused bits and delimiter bit from said first register, a second shift register adapted to receive the variable length code bits serially from said first shift register, means for enabling said second shift register to output its contents in parallel when said second shift register is full, and means for generating a next address for said memory when said first shift register becomes empty.
Claim 14
Dependent Claim
20 words
The apparatus of claim 11 wherein said memory is a read-only memory and said means for generating is a processor.
Claim 15
Dependent Claim
19 words
The apparatus of claim 12 further comprising a buffer register for storing the output of said second shift register.
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) | 1986-03-14 | 1986-09-13 | 1987-03-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-03-14 | 1990-09-13 | 1991-03-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-03-14 | 1994-09-13 | 1995-03-15 | $7700.00 | Window Closed / Lapsed |