Adaptive data compression system
First Claim
1. A data compression system for use in a data transmission system for transmitting data over a data communication channel between first and second data processing systems, comprising:
- a first data compression unit coupling said first data processing system to said channel and a second data compression unit coupling said second data processing system to said channel, both data compression units including;
host receiving means for receiving host input data comprising sequences of binary data from the data processing system coupled to said data compression unit;
data encoding means for encoding said input data, includinga plurality of encoding tables, each said table defining a method of encoding data using codes whose length varies inversely with the frequency of units of data in a predefined set of data;
means for encoding said input data using a selected one of said encoding tables and thereby producing encoded data;
encoding table building means for building a new encoding table to be including in said plurality of encoding tables using a preselected portion of the previously encoded input data, includingmeans for determining when to perform said table building; and
encoding table change means for selecting from among said encoding tables the one which minimizes the bit length of the encoded data for a preselected sample of said input data, includingmeans for determining when to perform said table selection; and
means for adding to said encoded data a table change code which corresponds to said selected table, including means for indicating when said selected table is a new encoding table built by said table building means;
channel transmitting means for transmitting said encoded data over said channel;
channel receiving means for receiving encoded data;
data decoding means for decoding said encoded data, includinga plurality of decoding tables, each said decoding table defining a method of decoding data which was encoded using codes whose length varies inversely with the frequency of units of data in a predefined set of data;
means for decoding said encoded data using a selected one of said decoding tables and thereby producing decoded data;
decoding table building means for building a new decoding table to be including in said plurality of decoding tables using a preselected portion of previously decoded data, includingmeans for initiating the performance of said table building when said encoded data includes a table change code which indicates that the encoded data following said table change code was encoded using a new encoding table; and
decoding table change means for selecting a new decoding table from among said plurality of decoding tables when said encoded data includes a table change code;
host transmitting means for transmitting said decoded data to the data processing system coupled to said data compressing unit.
1 Assignment
0 Petitions
Accused Products
Abstract
A data compression system for increasing the speed of data transmission system over a communication channel with a predefined data transmission rate. The system has two data compression units--one on each end of the channel, coupled to first and second data processing systems. Input data from either data processing system is encoded using a selected one of a plurality of encoding tables, each of which defines a method of encoding data using codes whose length varies inversely with the frequency of units of data in a predefined set of data. Whenever an analysis of the encoded data indicates that the data is not being efficiently compressed, the system invokes a table changer for selecting from among the encoding tables the one which minimizes the bit length of the encoded data for a preselected sample of the input data. If a new table is selected, a table change code which corresponds to the selected table is added to the encoded data. Also, a dynamic table builder builds a new encoding table to be including in the set of available encoding tables using a preselected portion of the previously encoded input data which an analysis of the encoded data indicates that a new encoding table will enhance compression. Each data compression unit includes a data decoder for decoding encoded data sent over the channel by the other unit. Thus the data decoder uses a set of decoding tables corresponding to the encoding tables, means for selecting a new table when a table change code is received, and means for building a new decoding table when it receives a table change code which indicates that the encoded data following the table change code was encoded using a new encoding table.
-
Citations
17 Claims
-
1. A data compression system for use in a data transmission system for transmitting data over a data communication channel between first and second data processing systems, comprising:
-
a first data compression unit coupling said first data processing system to said channel and a second data compression unit coupling said second data processing system to said channel, both data compression units including; host receiving means for receiving host input data comprising sequences of binary data from the data processing system coupled to said data compression unit; data encoding means for encoding said input data, including a plurality of encoding tables, each said table defining a method of encoding data using codes whose length varies inversely with the frequency of units of data in a predefined set of data; means for encoding said input data using a selected one of said encoding tables and thereby producing encoded data; encoding table building means for building a new encoding table to be including in said plurality of encoding tables using a preselected portion of the previously encoded input data, including means for determining when to perform said table building; and encoding table change means for selecting from among said encoding tables the one which minimizes the bit length of the encoded data for a preselected sample of said input data, including means for determining when to perform said table selection; and means for adding to said encoded data a table change code which corresponds to said selected table, including means for indicating when said selected table is a new encoding table built by said table building means; channel transmitting means for transmitting said encoded data over said channel; channel receiving means for receiving encoded data; data decoding means for decoding said encoded data, including a plurality of decoding tables, each said decoding table defining a method of decoding data which was encoded using codes whose length varies inversely with the frequency of units of data in a predefined set of data; means for decoding said encoded data using a selected one of said decoding tables and thereby producing decoded data; decoding table building means for building a new decoding table to be including in said plurality of decoding tables using a preselected portion of previously decoded data, including means for initiating the performance of said table building when said encoded data includes a table change code which indicates that the encoded data following said table change code was encoded using a new encoding table; and decoding table change means for selecting a new decoding table from among said plurality of decoding tables when said encoded data includes a table change code; host transmitting means for transmitting said decoded data to the data processing system coupled to said data compressing unit. - View Dependent Claims (2)
-
-
3. A data compression system, comprising:
-
encoding means for encoding input data received from a first data processing system in accordance with a predefined data compression encoding scheme;
wherein said first data processing system requires acknowledgement of receipt of predefined quantities of said input data before it will send more of said input data to said encoding means;modem transmission means for transmitting the encoded representation of said input data generated by said encoding means over a communication channel to a second data processing system;
said modem transmission means being able to transmit one set of encoded data at the same time that said encoding means is receiving and encoding a different set of input data;hold buffer means for storing said transmitted data; buffer purging means for purging data from said hold buffer means when an acknowledgement of the receipt of said transmitted data is received from said communication channel; retransmitting means for retransmitting over said communication channel said data in said hold buffer means if receipt of said transmitted data is not acknowledged; and protocol emulation means for sending to said first data processing system an acknowledgement of the receipt of said input data before said encoded data is transmitted over said communication channel; whereby the transmission of data from said first data processing system to said second data processing system is not delayed by said first data processing system waiting for an acknowledgement of receipt of said data to be sent by said second data processing system.
-
-
4. A data compression system, comprising:
-
input buffer means for storing input data received from a first data processing system; encoding means for encoding said input data received from said first data processing system in accordance with a predefined data compression encoding scheme; packet means for accumulating encoded data from said encoding means and generating packets, including packet sizing means for stopping the accumulation of encoded data for a packet (a) when the quantity of encoded data exceeds a defined packet limit, and (b) when all of said input data has been encoded by said encoding means, and no input data is received by said encoding means for a predefined length of time, said packet means including means for adding a transmission error detection code to each said packet; modem transmission means for transmitting said data packets of encoded data over a communication channel to a second data processing system at a predefined transmission rate, including means for transmitting a packet of encoded data at the same time that said encoding means is receiving and encoding input data; wherein said second data processing system can accept decoded data at a predefined data reading rate; and said packet sizing means includes means for stopping the accumulation of encoded data for a packet, when said modem transmission means is not transmitting a packet of data, and the lenght of time it will take for said second data processing system to accept the input data already encoded and accumulated by said encoding means and packet means, at said predefined data reading rate, is greater than the length of time it will take to transmit over said channel, at said predefined transmission rate, the input data stored in said input buffer but not yet encoded by said encoding means. - View Dependent Claims (5, 6, 7)
-
-
8. A data compression system, comprising:
-
encoding means for encoding input data received from a first data processing system in accordance with a selected character by character data compression encoding scheme; modem transmission means for transmitting an encoded representation of said input data over a communication channel; history buffer means for storing at least a portion of said input data which has been encoded by said encoding means; character substitution encoding means for finding the longest string of data in said history buffer which matches said input data, and, if said longest string meets a predefined length requirement, representing said input data with a string substitution code including a pointer to the portion of said history buffer with said matching string, and a length indicator of the length of said matching string; whereby some of said transmitted data is encoded on a character by character basis and some of said transmitted data is encoded with a string substitution code; and a receiver of said transmitted data can decode said transmitted data by maintaining a history buffer identical in content to said history buffer means in said data compression system, and by separately decoding said transmitted data in accordance with whether said data is encoded on a character by character basis or by a character substitution code. - View Dependent Claims (9, 10)
-
-
11. A data compression system for encoding and transmitting data to a data decoding system that can simultaneously receive encoded data and decode previously received encoded data, comprising:
-
input buffer means for storing input data received from a data processing system; encoding means for encoding said input data received from said data processing system in accordance with a predefined data compression encoding scheme; packet means for accumulating encoded data from said encoding means and generating packets, including packet sizing means for stopping the accumulation of encoded data for a packet (a) when the quantity of encoded data exceeds a defined packet limit, and (b) when all of said input data has been encoded by said encoding means, and no input data is received by said encoding means for a predefined length of time; modem transmission means for transmitting said data packets of encoded data over a communication channel to said data decoding system at a predefined transmission rate, including means for transmitting a packet of encoded data at the same time that said input buffer means and said encoding means are receiving and encoding input data; wherein said packet sizing means further includes downsizing means for detecting the end of a data transmission and then decreasing the size of said packets generated by said packet means so that the data decoding system receiving said packets will simultaneously receive encoded packets of data from said end of said data transmission while decoding previously received data packets; whereby the last datum at the end of said data transmission will be decoded sooner than if the size of said packets were not decreased. - View Dependent Claims (12, 13)
-
-
14. A data compression system for encoding and transmitting data to a data decoding system that can simultaneously receive encoded data and decode previously received encoded data, comprising:
-
input buffer means for storing input data received from a data processing system; encoding means for encoding said input data received from said data processing system in accordance with a predefined data compression encoding scheme; packet means for accumulating encoded data from said encoding means and generating packets, including packet sizing means for stopping the accumulation of encoded data for a packet (a) when the quantity of encoded data exceeds a defined packet limit, and (b) when all of said input data has been encoded by said encoding means, and no input data is received by said encoding means for a predefined length of time; modem transmission means for transmittng said data packets of encoded data over a communication channel to said data decoding system at a predefined transmission rate, including means for transmitting a packet of encoded data at the same time that said input buffer means and said encoding means are receiving and encoding input data; wherein said defined packet limit has a predefined initial value and is increased by a predefined growth ratio each time the accumulation of data for a packet of data is ended by said packet means, until said defined packet limit reaches a predefined maximum packet size limit. - View Dependent Claims (15, 16, 17)
-
Specification