Data compression for use with a communications channel

• US 6,489,902 B2
• Filed: 09/17/2001
• Issued: 12/03/2002
• Est. Priority Date: 12/02/1997
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Original Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Inventors: Heath, Robert Jeff
• Primary Examiner(s): YOUNG, BRIAN K
• Application Number:
  US09/953,783
• Publication Number:
  US 20020057213A1
• Time in Patent Office: 442 Days
• Field of Search: 341/87, 341/51, 341/106, 341/67, 341/95, 341/50
• US Class Current: 341/87
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A method, and apparatus for accomplishing the method, of compressing data for transmission over a communications channel by receiving one or more data symbols comprising a current data string and at least one subsequent symbol, matching a longest previous data string with the current data string, the previous data string being defined by a code word, placing the code word into a compressed data stream, attempting to extend the current data string by a plurality of symbols, placing, in the event the current data string is extended, a string-extension length indicative of the plurality of symbols into the compressed data stream, and transmitting the compressed data stream though the communications channel.

Claims

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

receiving one or more data symbols comprising a current data string;

matching a longest previous data string with the current data string;

placing, in the event the longest previous data string having been matched is a single symbol, the single symbol into a compressed data stream;

placing, in the event the longest previous data string having been matched is a multiple symbol data string, a code word into the compressed data stream, wherein the code word is indicative of the longest previous data string;

attempting, in the event the longest previous data string having been matched is a multiple symbol data string, to extend the current data string by one or more symbols;

placing, in the event the current data string is extended by one or more symbols, a string-extension length into the compressed data stream, wherein the string-extension length is indicative of the number of symbols by which the current data string is extended;

placing a one or two bit code prefix into the compressed data stream, the one or two bit code prefix indicating whether the following bits are said single symbol, said code word, or said string-extension length; and

transmitting the compressed data stream through the communications channel.

2. The method of claim 1 wherein said single symbol is represented by an ordinal.

3. The method of claim 1 wherein said string-extension length is comprised of one or more sub-fields, each consisting of one or more bits, that specify the length of said plurality of symbols.

4. The method of claim 1 further comprising placing a code prefix, consisting of two bits, into the compressed data stream prior to the placing step, the code prefix indicating that the following bits are said string-extension length.

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

receiving a plurality of bits;

determining whether the plurality of represents a single symbol, code word, or string-extension length;

placing, in the event the plurality of bits represents a single symbol, the single symbol into an output data stream; and

placing, in the event the plurality of bits represents a code word, a data string defined by the code word into the output data stream; and

placing, in the event the plurality of bits represents a string-extension length, an extension string being copied from said output data stream, at a symbol following a last symbol of the previous code word processed, to the output data stream.

6. The method of claim 5 wherein said receiving comprises receiving a code prefix consisting of one or two bits and a plurality of subsequent bits.

7. The method of claim 5 wherein said determining comprises determining, using said code prefix, whether said plurality of subsequent bits represents said single symbol, said code word, or said string-extension length.

8. A data decompression system for decompressing a compressed data stream received though a communications channel comprising:

an input device for receiving a plurality of bits; and

a programmable device operable to determine whether the plurality of bits represents a single symbol, code word, or string-extension length, and to place, in the event the plurality of bits represents a single symbol, the single symbol into an output data stream, to place, in the event the plurality of bits represents a code word, a data string defined by the code word into the output data stream, and to place in the event the plurality of bits represents a string-extension length, an extension string being copied from said output data stream at a symbol following a last symbol of the previous code word processed to the output data stream.