Apparatus for compression using reversible embedded wavelets

Claim 2

A coder for encoding a plurality of data symbols comprising: a wavelet transform; a formatting unit coupled to receive a plurality of coefficients from the wavelet transform and to format the plurality of coefficients into a set of formatted coefficients; a magnitude memory coupled to receive the set of formatted coefficients and configured to reorder coefficients in trees into an order based on significance, wherein the magnitude memory comprises a plurality of storage areas, wherein each of the plurality of storage areas stores data for a distinct significance level, a plurality of counters, wherein each of the plurality of counters is associated with one of the plurality of storage areas and counter values for each of the plurality of counters provide address locations in the plurality of storage areas for storage of the formatted coefficients and are incremented after storing an individual formatted coefficient; a significance unit coupled to the formatting unit to generate a plurality of decisions in response to each of the set of formatted coefficients; a memory mechanism coupled to receive the plurality of decisions from the significance unit; and a coder coupled to the memory mechanism and configured to encode data.

Claim 3

The coder defined in claim 1 wherein the coder comprises an entropy coder.

Claim 4

The coder defined in claim 1 wherein the formatting unit comprises a sign magnitude unit configured to convert the plurality of coefficients into sign magnitude format.

Claim 5

The coder defined in claim 3 wherein the sign magnitude unit comprises: a significance determination mechanism to output a significance indication for each coefficient; a sign and mantissa generator coupled to receive each of the plurality of coefficients and to generate a sign and mantissa for said each of the plurality of coefficients; and an index counter for generating an index for each of the plurality of coefficients.

Claim 6

The coder defined in claim 4 wherein the significance determination mechanism comprises a priority encoder.

Claim 7

The coder defined in claim 4 wherein the significance determination mechanism comprises a pair of priority encoders and a selection mechanism to select between outputs from each of the pair of priority encoders to output the significance indication.

Claim 8

The coder defined in claim 3 wherein the sign magnitude unit further comprises means for generating an index for each coefficient indicating a tree location.

Claim 9

The coder defined in claim 1 wherein the wavelet transform comprises a reversible wavelet transform.

Claim 10

The coder defined in claim 1 wherein each of the plurality of formatted coefficients is stored in the magnitude memory based on significance level.

Claim 11

The coder defined in claim 1 wherein the magnitude memory reorders coefficients based on their magnitude.

Claim 12

The coder defined in claim 1 wherein each of the plurality of storage areas comprises a location for each possible coefficient in a subtree.

Claim 13

The coder defined in claim 1 wherein coefficient information is read out of the magnitude memory in descending order of significance.

Claim 14

The coder defined in claim 12 wherein the coefficient information is output from the magnitude memory by, repeatedly, reading out coefficient information at an address indicated by the counter for the highest level of significance and decrementing the counter value until the counter value is zero and then repeating the output of coefficient information for the next highest level of significance, wherein the output of coefficient information continues until all of the plurality of counters have been decremented to zero and all of the plurality of storage areas have been emptied.

Claim 15

The coder defined in claim 1 wherein each counter addresses its individual storage area such that a last in, first out buffer (LIFO) is implemented.

Claim 16

The coder defined in claim 1 wherein each counter addresses its individual storage area such that a first in, first out buffer (FIFO) is implemented.

Claim 17

The coder defined in claim 1 wherein the plurality of counters comprise two banks of counters and the plurality of storage areas comprise two banks of storage areas, and further wherein the magnitude memory uses one of the two banks of counters and one of the two banks of storage areas to receive formatted coefficients from the formatting unit while the magnitude memory uses the other of the two banks of counters and the other of the two banks of storage areas to output formatted coefficients to the significance unit.

Claim 18

A coder for encoding a plurality of data symbols comprising: a wavelet transform; a sign/magnitude unit coupled to receive a plurality of coefficients from the wavelet transform and to format each of the plurality of coefficients into sign magnitude format; a magnitude memory coupled to the sign magnitude unit to reorder coefficients in sign magnitude format into an order based on significance, wherein the magnitude memory comprises a plurality of counters; and a plurality of memories coupled to the plurality of counters, such that each of the plurality of counters is coupled to a distinct one of the plurality of memories, wherein each counter and memory pair is associated with a significance level, such that one of the memories stores each coefficient formatted in sign/magnitude format at a location in said one memory based on an address specified by a count in its associated counter and the count is incremented after an individual formatted coefficient is stored at the location specified by the count; a significance unit coupled to generate a plurality of decisions in response to each of the plurality of coefficients being in sign magnitude format; a tree memory coupled to receive the plurality of decisions from the significance unit; and a coder coupled to the memory mechanism and configured to encode data.

Claim 19

A coder for encoding a plurality of data symbols comprising: a wavelet transform; a sign/magnitude unit coupled to receive a plurality of coefficients from the wavelet transform and to format each of the plurality of coefficients into sign magnitude format; a magnitude memory coupled to the sign magnitude unit to reorder coefficients in sign magnitude format into an order based on significance, wherein the magnitude memory comprises a plurality of counters; and a plurality of memories coupled to the plurality of counters, such that each of the plurality of counters is coupled to a distinct one of the plurality of memories, wherein each counter and memory pair is associated with a significance level, such that one of the memories stores each coefficient formatted in sign/magnitude format at a location in said one memory based on an address specified by a count in its associated counter and the count is incremented after an individual formatted coefficient is stored at the location specified by the count; a significance unit coupled to generate a plurality of decisions in response to each of the plurality of coefficients being in sign magnitude format; a tree memory coupled to receive the plurality of decisions from the significance unit; and a coder coupled to the memory mechanism and configured to encode data.

Claim 20

The coder defined in claim 17 wherein the sign/magnitude unit comprises: a multiplexer (MUX) having a first input, a second input, a selection input, and an output, wherein the first input is coupled to receive a portion of each coefficient and the second input is coupled to receive an inverted version of said each coefficient, and further wherein the selection input is coupled to receive a sign bit indication for said each coefficient, the output being the mantissa; and a priority encoder coupled to receive the mantissa from the MUX to determine the first significant bit of each coefficient.

Claim 21

The coder defined in claim 18 wherein the sign/magnitude unit further comprises a counter to associate an index for each coefficient with a current tree element.

Claim 22

The coder defined in claim 17 wherein each of the plurality of storage areas comprises a location for each possible coefficient in a subtree.

Claim 23

The coder defined in claim 17 wherein each memory location is configured to store a mantissa, a sign bit indication and an index received from the sign/magnitude unit.

Claim 24

The coder defined in claim 17 wherein each counter is enabled to count based on a significance indication received from the sign/magnitude unit.

Claim 25

The coder defined in claim 17 wherein a mantissa, a sign bit indication and an index for each coefficients are read out of the plurality of memories based on descending order of significance.

Claim 26

The coder defined in claim 17 wherein the wavelet transform comprises a reversible wavelet transform.

Claim 27

The coder defined in claim 17 wherein coefficient information is read out of the magnitude memory in descending order of significance.

Claim 28

The coder defined in claim 25 wherein the coefficient information is output from the magnitude memory by, repeatedly, reading out coefficient information at an address indicated by the counter for the highest level of significance and decrementing the counter value until the counter value is zero and then repeating the output of coefficient information for the next highest level of significance, wherein the output of coefficient information continues until all of the plurality of counters have been decremented to zero and all of the plurality of storage areas have been emptied.

Claim 29

The coder defined in claim 17 wherein each counter addresses its individual storage area such that a last in, first out buffer (LIFO) is implemented.

Claim 30

The coder defined in claim 17 wherein each counter addresses its individual storage area such that a first in, first out buffer (FIFO) is implemented.

Claim 31

The coder defined in claim 17 wherein the plurality of counters comprise two banks of counters and the plurality of storage areas comprise two banks of storage areas, and further wherein the magnitude memory uses one of the two banks of counters and one of the two banks of storage areas to receive formatted coefficients from the formatting unit while the magnitude memory uses the other of the two banks of counters and the other of the two banks of storage areas to output formatted coefficients to the significance unit.