Data compression for use with a communications channel

• US 5,955,976 A
• Filed: 12/02/1997
• Issued: 09/21/1999
• Est. Priority Date: 12/02/1997
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (Rtx Corporation)
• Original Assignee: Hughes Electronics Corporation (Rtx Corporation)
• Inventors: Heath, Robert Jeff
• Primary Examiner(s): Williams, Howard L.
• Assistant Examiner(s): TRAN, ANH Q
• Application Number:
  US08/982,864
• Time in Patent Office: 658 Days
• Field of Search: 341/51, 341/87
• US Class Current: 341/87
• CPC Class Codes: H03M 7/00 Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of information is represented by a different sequence or number of digits
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• 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 method of compressing data involves receiving a symbol, and a subsequent symbol; determining in a compression dictionary whether the symbol has a valid extension pointer; using, in the event the symbol does have a valid extension pointer, the valid extension pointer to access string extension symbols; determining, in the event the symbol does have a valid extension pointer, whether the string extension symbols equal the at least one subsequent symbol; determining in the compression dictionary, in the event the string extension symbols do not equal the at least one subsequent symbol, whether the symbol has a valid parallel extension; repeating, in the event the symbol has a valid parallel extension, the using step; repeating, in the event the string extension symbols do not equal the at least one subsequent symbol, the determining of whether the symbol has a valid extension pointer; inserting, in the event the symbol does not have a valid extension pointer or in the event the symbol does not have a valid parallel extension, a code word indicative of a longest string found into a compressed data stream; determining whether the longest string was a single symbol; extending, in the event the longest string was a single symbol, the longest string by one symbol; extending, in the event the longest string was not a single symbol, the longest string by a plurality of symbols; inserting a string extension signalling code word if the string is extended by multiple symbols and transmitting the compressed data stream through the communications channel.

Claims

1. A method of compressing data for transmission over a communications channel comprising:

receiving a symbol, and at least one subsequent symbol;

determining in a compression dictionary whether the symbol has a valid extension pointer;

using, in the event the symbol does have a valid extension pointer, the valid extension pointer to access string extension symbols;

determining, in the event the symbol does have a valid extension pointer, whether the string extension symbols equal the at least one subsequent symbol;

determining in the compression dictionary, in the event the string extension symbols do not equal the at least one subsequent symbol, whether the symbol has a valid parallel extension;

repeating, in the event the symbol has a valid parallel extension, the using step;

repeating, in the event the string extension symbols equal the at least one subsequent symbol, the determining of whether the symbol has a valid extension pointer;

inserting, in the event the symbol does not have a valid extension pointer or in the event the symbol does not have a valid parallel extension, a code word indicative of a longest string found into a compressed data stream;

determining whether the longest string was a single symbol;

extending, in the event the longest string was a single symbol, the longest string by one symbol;

extending, in the event the longest string was not a single symbol, the longest string by a plurality of symbols;

placing, in the event the longest string was not a single symbol, and in the event the longest string is extended by more than one symbol, a multi-character extension string signaling code word into the compressed data stream; and

transmitting the compressed data stream through the communications channel.

2. The method of claim 1 further comprising:

determining whether said longest string is longer than a maximum string length;

placing, in the event the longest string is longer than a maximum string length of a repeated symbol, a run length encoding signaling code word into said compressed data stream.

3. The method of claim 1 further comprising:

linking a new extension string to the longest string by;

placing a code word associated with the new extension string in an extension pointer of the dictionary entry associated with the longest string;

placing a count indicative of a number of symbols in the new extension string into a new dictionary entry for the new extension string; and

placing a location pointer to a first symbol of the new extension string into the new dictionary entry for the new extension string.

4. A method for decompressing data received over a communications channel comprising:

receiving a code word;

determining whether the code word represents a single character;

placing, in the event the code word represents a single character, the code word into an output data stream;

determining, in the event the code word represents more than a single character, whether the code word is in a dictionary;

placing, in the event the code word is in the dictionary, a string defined by the code word into the output data stream;

determining, in the event the code word is not in the dictionary, whether the code word is a next code word to be built;

placing, in the event the code word is a next code word to be built, a string into the output data stream, the string being copied from a dictionary entry indicated by a previous code word processed;

placing, in the event the code word is the next code word to be built, a first symbol of the string into the output data stream; and

placing, in the event the code word is not in the dictionary and is not the next code word to be built, an extension string into the output data stream, the extension string being copied from the output data stream at a symbol following a last symbol of a dictionary entry indicated by a previous code word processed.

5. The method of claim 4 further comprising:

determining whether the previous code word processed is of a maximum string length;

placing, in the event the code word is not in the dictionary and the previous code word processed is of the maximum string length, a run length string into the output data stream, the run length string comprising a first symbol of the previous code word processed repeated a number of times indicated by a next code word to be processed.