 |
|
|
|
|
|
 Title: |
US5450562:
Cache-based data compression/decompressionCACHE-BASED DATA COMPRESSION/DECOMPRESSION
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Rosenberg, Charles; Mt. View, CA
Berge, Thomas G.; Boise, ID
|
| Assignee: |
Hewlett-Packard Company, Palo Alto, CA
other patents from HEWLETT-PACKARD COMPANY (250060) (approx. 10,220)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1995-09-12
/ 1992-10-19
|
| Application Number: |
US1992000963201
|
| IPC Code: |
Advanced:
G06F 5/00;
G06F 12/08;
G06F 12/12;
H03M 7/30;
H03M 7/46;
H04N 1/417;
Core:
more...
IPC-7:
G06F 12/02;
|
| ECLA Code: |
G06F12/08B; G06F12/12B4B; H04N1/417;
|
| U.S. Class: |
Current:
711/119;
341/055;
341/056;
341/099;
711/E12.017;
711/E12.073;
Original:
395/446;
364/DIG.1;
364/229.1;
364/243.4;
341/055;
341/056;
341/099;
|
| Field of Search: |
364/200 MS,900 MS
395/400,425
341/26 MS,29 MS,56 MS,55 MS,99 MS
|
| Priority Number: |
| 1992-10-19 |
US1992000963201 |
|
| Abstract: |
A system for compressing bilevel data includes a first cache memory having a plurality of assigned levels of usage, a first usage level assigned to a most recently used data segments and a second level assigned to a plurality of less recently used data segments. A processor determines if a received data segment is found in the cache memory and, if not, it assigns the received data segment to the cache memory's first level in place of a previous data segment stored therein. The previous data segment is assigned to a position in the second level in place of a less recently used data segment. The less recently used data segment that is displaced is chosen by a pseudo-random method. A not-found indication is then transmitted to a receiving station along with the identity of the received data segment. The receiving station contains identical cache structures and updates its caches in response to received code words and data segments. A further version of the invention emplaces data segments into cache memories in accordance with the context in which the data segments are found, the cache memories being assigned in accordance with context derived addresses.
|
| Primary / Asst. Examiners: |
Rudolph, Rebecca L.; Nguyen, Hiep T.
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
DE FR GB IT
|
| Family: |
Show 10 known family members
|
First Claim:
Show all 22 claims |
What is claimed is:
1. A system for data compression/decompression, including transmission means and receiving means, said transmission means comprising:
- first cache memory means having a plurality of levels, a first said level assigned to a most recently used data segment, a second said level assigned to a plurality of less recently used data segments;
- means for determining if a first data segment is found in said first cache memory means and, if not, assigning said first data segment to said first level in said first cache memory means in place of a second data segment assigned to said first level, and assigning said second data segment to a position in said second level in place of a less recently used data segment, said less recently used data segment chosen without regard to prior usage by a predetermined selection method from among less recently used data segments assigned to said second level;
- means for transmitting to said receiving means a not found indication and said first data segment in uncompressed form; and
- means responsive to a determination that said first data segment is found in said first cache memory means for causing said transmitting means to transmit to said receiving means a position code indicating where in said first cache memory means said first data segment is assigned, said position code manifesting a smaller data size than said data segment.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 24 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
|
| Other Abstract Info: |
DERABS G1994-137260
DERABS G1998-597050
|
| Other References: |
Roy Hunter and A. Harry Robinson, "International Digital Facsimile Coding Standards", Proceedings of the IEEE, vol. 68, No. 7, Jul. 1980, pp. 854-371.
(14 pages)
Cited by 20 patents
Ross N. Williams. "An Extremely fast ZIV-Lempel Data Compression Algorithm," Proceedings of the IEEE Data Compression Conf., Apr. 1991, pp. 362-371.
Thomas S. Huang. "Coding of Two-Tone Images", IEEE Transactions on Communications, vol. COM-25, No. 11, Nov. 1977, pp. 1406-1424.
(19 pages)
Cited by 5 patents
J. C. Stoffel. "Halftone Pictorial Encoding", SPIE Applications of Digital Image Processing, vol. 19, 1977, pp. 56-63.
Glen G. Langdon, Jr. and Jorma Rissanen. "Compression of Black-White Images with Arithmetic Coding", IEEE Transactions on Communications, vol. COM-29, No. 6, Jun. 1981, pp. 858-867.
(10 pages)
Cited by 26 patents
Jon Louis Bentley, Andiel D. Sleator, Robert E. Tarjan and Victor K. Wei. "A Locally Adaptive Data Compression Scheme", Communications of the ACM, vol.29, No. 4, Apr. 1986, pp. 320-330.
(11 pages)
Cited by 12 patents
R. Nigel Horspool. "Technical Correspondence on A Locally Adaptive Data Compression Scheme", Communications of the ACM, vol. 30, No. 9, Sep. 1987, pp. 792-793.
(3 pages)
T. Usubuchi, T. Omachi, and K. Ilnuma "Adaptive Predictive Coding for Newspaper Facsimile", Proceedings of the IEEE, vol. 68, No. 7, 1980, pp. 807-813.
(7 pages)
Cited by 7 patents
Horst Hampel, et al. "Technical Features of the JBIG Standard for Progressive B-level Image Compression", Image Communication Journal vol. 4, No. 2 (1992).
Jon Louis Bentley, Andiel D. Sleator, Robert E. Tarjan and Victor K. Wei. "A Locally Adaptive Data Compression Scheme", Communications of the ACM, vol. 29, No. 4, Apr. 1986, pp. 320-330.
(11 pages)
Cited by 12 patents
Takahiro Saito, Ryuji Abe, Takashi Komatsu, Hiroshi Harashima "Multi-Dimensional Lossy Coding via Copying With Its Practical Application to Interframe Low-Rate Video Compression", IEICE Transactions, vol. E-74, No. 9, Sep. 1991, pp. 2513-2521.
(10 pages)
[ISI abstract]
|
|
 Nominate this for the Gallery...
|
|
