Adaptive data compression system

• US 5,319,682 A
• Filed: 12/09/1991
• Issued: 06/07/1994
• Est. Priority Date: 12/08/1990
• Status: Expired due to Fees

• Current Assignee: CRAY Communications Limited
• Original Assignee: CRAY Communications Limited
• Inventors: Clark, Alan D.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Bocure, Tesfaldet
• Application Number:
  US07/802,255
• Time in Patent Office: 911 Days
• Field of Search: 375/121, 375/122, 375/25, 375/27, 381/34, 381/35, 381/29, 358/133, 341/143, 341/51, 307/269, 328/153
• US Class Current: 375/240
• 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

Abstract

An adaptive data compression system comprises an encoder 2 which responds to input characters by producing output codewords according to a stored encoding map or table of characters and codewords, and an adapter 4, 5 which adapts the encoding map or table in accordance with the input characters so as to increase the compression ratio between the input characters and output codewords. An optimizer 5 monitors the performance of the system and accordingly varies adaptation of the encoding map or table by the adapter 4 so as to optimize performance of the system. Performance of the system is preferably monitored in terms of the computational loading of the processor and the compression ratio it achieves. A decoder 7 subsequently decodes the codewords by reference to a corresponding decoding map or table which is adapted 9, 10 in accordance with the output data from the decoder and in accordance with variations in the adaptation process in the encoder.

Claims

1. An adaptive data compression system comprising an encoder which converts input characters into output codewords according to a stored encoding map or table of characters and codewords stored in the encoder, adapting means which adapts the encoding map or table in accordance with the input characters so as to increase the compression ratio between the input characters and output codewords, and optimization means which monitors the computational loading of the system when converting input characters into output codewords and varies the rate at which the adapting means adapts the encoding map or table in accordance with said computational loading.

2. A system as claimed in claim 1 in which the optimisation means varies the rate at which the adapting means adapts the encoding map or table, either to reduce said rate to reduce computational loading of the system, or to increase said rate to improve the compression ratio of the system.

3. A system as claimed in claim 2 in which the optimisation means increases the rate at which the adapting means adapts the encoding map or table if the compression ratio falls below a predetermined maximum compression ratio.

4. A system as claimed in claim 1 in which the optimisation means monitors the computational loading by comparing the character processing rate of the encoder with a predetermined maximum rate.

5. A system as claimed in claim 1 in which the optimisation means monitors the computational loading by monitoring the time spent by the system when not processing input characters to compress them.

6. A system as claimed in claim 1 in which the optimisation means monitors the computational loading by monitoring the compression ratio of the encoder.

7. A system as claimed in claim 6, in which the optimization means monitors the computational loading by monitoring the ratio of the rate of input data to the encoder to the rate of output data from the encoder and comparing this ratio with said compression ratio.

8. A system as claimed in claim 1 which includes a decoder which converts to input codewords as received from the encoder into output characters according to a stored decoding map or table of codewords and characters, and adapting means which adapts the decoding map or table in accordance with the output characters and in accordance with variations in the adaptation process in the encoder so that its mapping corresponds to that of the encoding map or table.

9. A system as claimed in claim 8 in which the optimisation means causes the adapting means to adapt the decoding map or table in accordance with the variation in the adaptation process in the encoder.

10. A system as claimed in claim 9 in which an encoder and decoder are provided at each end of a two-way communications link, and each encoder is provided with corresponding adapting means which adapts the encoding map or table and optimisation means which varies the adaptation of the encoding map or table, and each decoder is provided with corresponding adapting means which adapts the decoding map or table and optimisation means which varies adaptation of the decoding map or table under the control of the optimisation means at the other end of the link so that the corresponding encoding and decoding maps or tables are adapted in step with one another, the optimisation means which varies adaptation of the decoding map or table also serving to control the optimisation means at the same end of the link which varies adaptation of the encoding map or table so that the encoding maps or tables of the adapting means at both ends of the link are adapted in step with one another.

11. A decoder for use with an adaptive data compression system as claimed in claim 1, the decoder being such as to convert to input codewords as received from the encoder into output characters according to a stored decoding map or table of codewords and characters, and comprising adapting means which adapts the decoding map or table in accordance with the output characters and in accordance with variations in the adaptation process in the encoder so that its mapping corresponds to that of the encoding map or table therein.