Data compression using run length encoding and statistical encoding

• US 4,626,829 A
• Filed: 08/19/1985
• Issued: 12/02/1986
• Est. Priority Date: 08/19/1985
• Status: Expired due to Fees

• Current Assignee: Intellistor Incorporated
• Original Assignee: Intelligent Storage Incorporated
• Inventors: Hauck, Edward L.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): Logan, Sharon D.
• Application Number:
  US06/767,186
• Time in Patent Office: 470 Days
• Field of Search: 340/347 DD, 358/260, 358/261, 364/200, 364/900, 382/56, 375/19
• US Class Current: 341/63
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

A compression device which uses both run length encoding and statistical encoding. The run length encoding scheme uses a flag byte symbol which is disposed between a character signal and a run length symbol. The statistical encoding process uses multiple statistical encoding tables which are selected based upon previously occurring data.

Claims

1. A system for compressing data comprised of information symbols encoded from binary data comprising:

run length encoding means for encoding said information symbols to produce run length encoded data having a character symbol indicating a repeated information symbols, a flag symbol indicating the existence of a run, and a run length symbol indicating the number of said repeated information symbols;

statistical encoding means for statistically encoding said run length encoded data in accordance with one of several statistical encoding tables selected by a pointer signal produced during statistical encoding of previous run length encoded data, and for generating a pointer signal to select a statistical encoding table for subsequent run length encoded data;

means for detecting the occurrence of said information symbols in said data corresponding to said flag symbol; and

,

means for encoding said information symbols in said data corresponding to said flag symbol as a double flag symbol to distinguish said flag symbol from said information symbols in said data.

2. The system of claim 1 further comprising:

means for statistically encoding said flag symbol to have a predetermined number of bits equal to half of the number of bits in a byte of said flag symbol.

3. The system of claim 2 wherein said several statistical encoding tables comprise:

null table means for generating an output which is independent of statistical probabilities of occurrence of said information symbols in said data;

generic table means for statistically encoding said data to maximize compression of letter character text;

numeric table means for statistically encoding said data to maximize compression of numerical character text.

4. The system of claim 3 wherein said null table means, said generic table means and said numeric table means comprise lookup tables which store statistical translations of said run length encoded data at address locations corresponding to said run length encoded data and said pointer signals for selecting a statistical encoding table for said subsequent run length encoded data.

5. The system of claim 4 wherein said pointer signals provide a predetermined amount of hysteresis to said system to prevent thrashing between said statistical encoding tables by allowing a predetermined amount of expansion of predetermined information symbols prior to indicating a change between said statistical encoding tables.

6. A system for compressing byte formatted data to produce compressed data and decompressing said compressed data to produce decompressed byte formatted data comprising:

run length encoding means for producing run length encoded data having a character byte, a flag byte and a run length byte;

lookup table means for statistically encoding said run length encoded data to produce said compressed data in accordance with a predetermined statistical encoding lookup table selected from several statistical encoding lookup tables by a pointer signal generated from said predetermined statistical encoding lookup table during a previous statistical encoding process and stored in said predetermined statistical encoding lookup table at address locations corresponding to said run length encoded data being statistically encoded;

lookup table means for statistically decoding said compressed data to produced statistically decoded data in accordance with a predetermined statistical decoding lookup table selected from several statistical decoding lookup tables by a pointer signal generated from said predetermined statistical decoding lookup table during a previous statistical decoding process and stored at address locations corresponding to said compressed data received from said storage device;

run length decoding means for run length decoding said statistically decoded data comprising a character byte, a flag byte and a run length byte to produce said decompressed byte formatted data.

7. The system of claim 6 further comprising:

means for detecting the occurrence of byte formatted data corresponding to said flag byte;

means for encoding said byte formatted data corresponding to said flag byte as a double flag byte to distinguish said flag byte from said byte formatted data corresponding to said flag byte.

8. The system of claim 7 wherein said previous statistical encoding process comprises a statistical encoding process occurring immediately prior to said statistical encoding of said run length encoded data, and said previous statistical decoding process comprises a statistical decoding process occurring immediately prior to said statistical decoding of said compressed data. PG,39

9. The system of claim 8 wherein said several statistical encoding tables comprise:

null table means for generating said compressed data having a statistical probability which is independent of the occurrence of said run length encoded data;

generic table means for statistically encoding said run length encoded data to maximize compression of letter character text;

numeric table means for statistically encoding said run length encoded data to maximize compression of numerical character text.

10. A system for statistically encoding information symbols in a data stream comprising:

multiple statistical encoding table means for compression of a current information symbol in said data stream of said information symbols in accordance with a specified statistical encoding table which is one of a plurality of statistical encoding tables having statistical encoding data stored therein corresponding to a plurality of classifications of said information symbols;

means for selecting said specified statistical encoding table based upon a predetermined classification of a previous information symbol chronologically immediately prior to said current information symbol, said predetermined classification of said previous information symbol corresponding to one of said plurality of classifications.

11. A system for statistically encoding information symbols in a data stream comprising:

multiple statistical encoding table means for compression of a current information symbol in said data stream of said information symbols in accordance with a specified statistical encoding table which is one of a plurality of statistical encoding tables having statistical encoding data stored therein corresponding to a plurality of classifications of said information symbols;

means for selecting said specified statistical encoding table based upon a predetermined classification of a previous information symbol corresponding to one of said plurality of classifications;

means for storing a pointer signal with said previous information symbol to select said specified statistical encoding table based upon said predetermined classification of said previous information symbol.

12. The system of claim 11 wherein said multiple statistical encoding table means comprises lookup tables which store said statistical encoding data at address locations corresponding to said information symbols.

13. A system for statistically encoding information symbols in a data stream comprising:

multiple statistical encoding table means for compression of a current information symbol in said data stream of said information symbols in accordance with a specified statistical encoding table which is one of a plurality of statistical encoding tables having statistical encoding data stored therein corresponding to a plurality of classifications of said information symbols, said multiple statistical encoding table means comprising;

null table means for storing said statistical encoding data having a statistical probability which is independent of the occurrence of said information symbols;

generic table means for storing said statistical encoding data having a statistical probability to increase compression of letter character text;

numeric table means for storing said statistical encoding data having a statistical probability to increase compression of number character text; and

,

means for selecting said specified statistical encoding table based upon a predetermined classification of a previous information symbol corresponding to one of said plurality of classifications.

14. A system for run length encoding byte formatted data comprising:

means for generating a character byte identifying a repeated byte of said byte formatted data;

means for generating a run length byte indicating a number of repeated bytes in a run of said byte formatted data;

means for generating a flag byte consisting of a nonfrequently occurring byte of said byte formatted data, said flag byte sequentially disposed between said character byte and said run length byte;

means for generating a double flag byte during run length encoding of said nonfrequently occurring byte selected as said flag byte to distinguish said flag byte from said nonfrequently occurring byte in said formatted data.

15. A method of compressing information symbols comprising the steps of:

run length encoding said information symbols to produce a data stream of run length encoded symbols having a character symbol indicating a repeated symbol of said information symbols, a flag symbol indicating the existence of said repeated symbol in said run length encoded data and a run length symbol indicating a number of said repeated symbols in a run of said run length encoded symbol;

statistically encoding said data stream of said run length encoded symbols by a plurality of statistical encoding tables having statistical encoding data stored therein for statistically encoding said run length encoded symbols in accordance with predetermined classifications of said run length encoded symbols;

selecting a specified statistical encoding table of said plurality of said statistical encoding tables for a current run length encoded symbol based upon a specified classification of a previous run length encoded symbol which is chronologically previous to said current run length encoded symbol in said data stream of said run length encoded symbols; and

,

storing a pointer signal with said statistical encoding table to select said specified statistical encoding table.

16. The method of claim 15 further comprising the step of:

providing lookup tables for storing said statistical encoding data at address locations corresponding to said run length encoded symbols.

17. A method of compressing and decompressing information symbols comprising the steps of:

run length encoding said information symbols to produce a data stream of run length encoded symbols having a character symbol identifying a repeated symbol of said information symbols, a flag symbol byte indicating the existence of a run, and a run length symbol indicating a number of repeated symbols of said run length encoded data;

statistically encoding a current run length encoded symbol in said data stream of said run length encoded symbols with a specified compression table which is one of a plurality of compression tables having statistical encoding data stored therein for statistically encoding said run length encoded symbols in accordance with a predetermined classification of said run length encoded symbols to produce compressed data comprising the steps of;

reading said current run length encoded data symbol as an address code in a lookup table having said statistical encoding data stored at an address location corresponding to said address code;

generating a statistical translation output from said statistical encoding data stored at said address location;

generating a pointer signal from pointer signal data stored at said address location;

determining if said current run length encoded data symbol is a first symbol of said data stream;

selecting a predetermined compression table for said first symbol;

selecting said specified compression table in accordance with said pointer signal generated for said previous run length encoded symbol for data other than said first symbol;

selecting said specified compression table based upon said predetermined classification of a previous run length encoded symbol which is chronologically previous to said current run length encoded symbol in said data stream of said run length encoded symbol;

statistically decoding said compressed data to produce statistically decoded data using one of a plurality of statistical decoding tables selected in accordance with a selection process dependent upon the order of said compressed data such that selection data of said selection process is inherent in said order of said compressed data; and

,

run length decoding said statistically decoded data to produce decompressed information symbols.