Method and apparatus for performing data compression

• US 5,867,114 A
• Filed: 02/29/1996
• Issued: 02/02/1999
• Est. Priority Date: 02/29/1996
• Status: Expired due to Term

• Current Assignee: Mitel Networks Corporation
• Original Assignee: Zarlink Semiconductor Inc. (Microchip Technology Incorporated)
• Inventors: Barbir, Abbulkader Omar
• Primary Examiner(s): Young, Brian
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US08/609,129
• Time in Patent Office: 1,069 Days
• Field of Search: 341/51, 341/107, 341/50, 341/59, 341/65, 341/67
• US Class Current: 341/107
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

A method and apparatus are disclosed for performing data compression on raw uncompressed data. The method develops a semi-adaptive modeler that sub-divides the length of an input data file into blocks of fixed size. The blocks are then sub-divided into sub-blocks in which the frequencies of the symbols are mapped to occupy the whole frequency space. The modeler is then used to develop a reduced complexity implementation of arithmetic coding, whereby, the time consuming divide operation used in computing the symbols'"'"' true probabilities is replaced by a simple shift operation. The reduced complexity arithmetic coder is referred to as approximate arithmetic coder. The modeler and the approximate arithmetic coder are then used in a multi-step data compression system that employs a ZL coder. The multi-step method results in high efficiency data compression systems that are ideal for real time operations and are better suited for network communications or data storage systems. The method overcomes many of the difficulties found in the prior art and generally achieves better compression ratios.

Claims

1. A method for utilizing a processor to change the form of input data having symbols, comprising the steps of:

a) providing the input data to the processor;

b) implementing a modelling method in the processor, the modelling method comprising mapping the frequencies of the symbols in at least a portion of the input data such that the sum of the frequencies of the symbols in the at least a portion of the input data, after mapping, equals a pre-set value;

c) processing the input data in the processor using a first coder comprising a shift operation instead of a divide or multiply operation to compute the symbols'"'"' probabilities and to produce compressed data;

d) applying the compressed data to a medium.

2. A method as defined in claim 1, wherein the implementing of the modelling method step (b) includes the steps of:

i) partitioning the input data into at least one block; and

ii) mapping the frequencies of the symbols in each block such that the sum of the frequencies of the symbols in each block, after mapping, equals a pre-set value, each block being the at least a portion of the input data.

3. A method as defined in claim 1, wherein the implementing of the modelling method step (b) includes the steps of:

i) partitioning the input data into at least one block;

ii) partitioning each block into sub-blocks; and

iii) mapping the frequencies of the symbols in each sub-block such that the sum of the frequencies of the symbols in each sub-block, after mapping, equals a pre-set value, each sub-block being the at least a portion of the input data.

4. A method as defined in claim 1, further comprising between steps (a) and (b) the step of:

processing the data in the processor using a second coder.

5. A method as defined in claim 4, wherein the second coder is a ZL coder.

6. A method as defined in claim 4, wherein the second coder is a variant of a ZL coder.

7. A method as defined in claim 1, wherein the first coder is an arithmetic coder.

8. A method as defined in claim 1, wherein the pre-set value equals an integer power of an integer, and wherein processing the input data using the fist coder includes shifting probability data for each symbol by the integer power, instead of dividing or multiplying the probability data by the pre-set value.

9. A method as defined in claim 8, wherein the first coder is an arithmetic coder.

10. An apparatus for utilizing a processor to change the form of input data having symbols comprising:

a) means for obtaining the input data at the processor;

b) means at the processor for implementing a modelling method comprising means for mapping the frequencies of the symbols in at least a portion of the input data such that the sum of the frequencies of the symbols in the at least a portion of the input data, after mapping, equals a pre-set value;

c) means at the processor for processing the input data using a first coder comprising a shift operation instead of a divide or multiply operation to compute the symbols'"'"' probabilities and to produce compressed data; and

d) means for applying the compressed data to a medium.

11. An apparatus as defined in claim 10, wherein the means at the processor for implementing a modelling method comprises:

i) means for partitioning the data into at least one block; and

ii) means for mapping the frequencies of the symbols in each block such that the sum of the frequencies of the symbols in each block, after mapping, equals a pre-set value.

12. An apparatus as defined in claim 10, wherein the means at the processor for implementing a modelling method comprises:

i) means for partitioning the data in to at least one block;

ii) means for partitioning each block into sub-blocks; and

iii) means for mapping the frequencies of the symbols in each sub-block such that the sum of the frequencies of the symbols in each sub-block, after mapping, equals a pre-set value.

13. An apparatus as defined in claim 10, further comprising:

means at the processor for processing the data obtained at the processor using a second coder.

14. An apparatus as defined in claim 13, wherein the second coder is a ZL coder.

15. An apparatus as defined in claim 13, wherein the second coder is a variant of a ZL coder.

16. An apparatus as defined in claim 10, wherein the first coder is an arithmetic coder.

17. An apparatus as defined in claim 16, wherein the arithmetic coder is an approximate arithmetic coder.

18. An apparatus as defined in claim 17, wherein the approximate arithmetic coder is an arithmetic coder wherein the divide operation that computes the symbols'"'"' probabilities is substituted by a shift operation in accordance with the modelling method.

19. The apparatus as defined in claim 10, wherein the pre-set value equals an integer power of an integer, and wherein the first coder is operable to process the input data by shifting probability data for each symbol by the integer power, instead of dividing or multiplying the probability data by the pre-set value.

20. An apparatus as defined in claim 19, wherein the first coder is an arithmetic coder.