Encoder using Huffman codes

• US 6,484,142 B1
• Filed: 04/18/2000
• Issued: 11/19/2002
• Est. Priority Date: 04/20/1999
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Ishikawa, Tomokazu, Norimatsu, Takeshi, Tsushima, Mineo, Miyasaka, Shuji, Sawada, Yoshiaki
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Nolan, Daniel A
• Application Number:
  US09/551,796
• Time in Patent Office: 945 Days
• Field of Search: 704/229, 704/230, 704/201, 704/219, 704/200, 704/500, 341/341, 341/65, 358/426.13
• US Class Current: 704/500
• 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 encoder of the present invention includes: G storage sections for storing G groups of data; a selection section for selecting one of H Huffman codebooks having codebook numbers for each of the groups of data; G encoding sections Huffman-encoding the G groups of data by using the selected Huffman codebook; and an encoding section for encoding the codebook number of each Huffman codebook selected. The selection section includes a calculation section for calculating a code length and a control section for selecting one of the Huffman codebooks. When the Huffman codebook selected is an unsigned codebook, a number of bits required for sign information has previously been added to the calculated code length.

Claims

1. An encoder, comprising:

a number G of storage sections (G is an integer equal to or greater than

     1) for storing a number G of groups of data;

a Huffman codebook selection section for selecting one of a number H of Huffman codebooks (H is an integer equal to or greater than

     1) for each of the groups of data stored in the respective storage sections, each of the Huffman codebooks having a codebook number;

a number G of Huffman encoding sections, each of the Huffman encoding sections Huffman-encoding a corresponding one of the G groups of data by using one of the Huffman codebooks which is selected by the Huffman codebook selection section for the one group of data; and

a codebook number encoding section for encoding the codebook number of each Huffman codebook selected by the Huffman codebook selection section, wherein;

the Huffman codebook selection section includes a code length calculation section for calculating a code length which would result from a Huffman encoding operation of each of the G groups of data using each Huffman codebook, and a control section for selecting one of the Huffman codebooks which is suitable for the group of data based on the code length calculated by the code length calculation section; and

when the Huffman codebook selected is an unsigned codebook, a number of bits required for sign information has previously been added to the code length calculated by the code length calculation section.

2. An encoder according to claim 1, wherein the code length calculation section has a table of data including a code length previously calculated for each Huffman codebook.

3. An encoder, comprising:

a number G of storage sections (G is an integer equal to or greater than

     1) storing a number G of groups of data;

a Huffman codebook selection section for selecting one of a number H of Huffman codebooks (His an integer equal to or greater than

     1) for each of the groups of data stored in the respective storage sections, each of the Huffman codebooks having a codebook number;

a number G of Huffman encoding sections, each of the Huffman encoding sections Huffman-encoding a corresponding one of the G groups of data by using one of the Huffman codebooks which is selected by the Huffman codebook selection section for the one group of data; and

a codebook number encoding section for encoding the codebook number of each Huffman codebook selected by the Huffman codebook selection section, wherein;

the Huffman codebook selection section includes a code length calculation section for calculating a code length which would result from a Huffman encoding operation of each of the G groups of data using each Huffman codebook, and a control section for selecting one of the Huffman codebooks which is suitable for the group of data based on the code length calculated by the code length calculation section; and

the code length calculation section is capable of simultaneously obtaining code lengths for a plurality of Huffman codebooks.

4. An encoder according to claim 3, wherein:

the code length calculation section is adapted to output respective code lengths which would result from Huffman encoding operations of the one group of data, for a plurality of Huffman codebooks; and

the control section selects one of the Huffman codebooks for which a smallest code length is output from the code length calculation section.

5. An encoder according to claim 3, wherein:

the code length calculation section is adapted to output respective code lengths which would result from Huffman encoding operations of the one group of data, for a plurality of Huffman codebooks; and

the control section selects one of the Huffman codebooks based on the code length of the Huffman codebook output from the code length calculation section and in view of the codebook number of the Huffman codebook.

6. An encoder according to claim 5, wherein the control section selects one of the Huffman codebooks for a (g+1)^th group of data (g is an integer such that 1≦

g≦

G−

1) by first obtaining a code length Bmin and another code length Bg, the code length Bmin being a code length which would result from a Huffman encoding operation of the (g+1)^th group of data using a Huffman codebook Hmin for which a smallest code length is output from the code length calculation section, and the code length Bg being a code length which would result from a Huffman encoding operation of a g^th group of data using a Huffman codebook Hg which has been selected for the g^th group of data, and then selecting the Huffman codebook Hmin if Bmin<

(Bg−

A) (A is a predetermined integer) or the Huffman codebook Hg if Bmin≧

(Bg−

A).

7. An encoder according to claim 6, wherein the control section selects one of the Huffman codebooks for which a smallest code length is output from the code length calculation section as a Huffman codebook for a first group of data.

8. An encoder according to claim 5, wherein the control section selects one of the Huffman codebooks for a (g−

1)^th group of data (g is an integer such that 2≦

g≦

G) by first obtaining a code length Bmin and another code length Bg, the code length Bmin being a code length which would result from a Huffman encoding operation of the (g−

1)^th group of data using a Huffman codebook Hmin for which a smallest code length is output from the code length calculation section, and the code length Bg being a code length which would result from a Huffman encoding operation of a g^th group of data using a Huffman codebook Hg which has been selected for the g^th group of data, and then selecting the Huffman codebook Hmin if Bmin<

(Bg−

A) (A is a predetermined integer) or the Huffman codebook Hg if Bmin≧

(Bg−

A).

9. An encoder according to claim 8, wherein the control section selects one of the Huffman codebooks for which a smallest code length is output from the code length calculation section as a Huffman codebook for a G^th group of data.

10. An encoder according to claim 6, wherein when a same Huffman codebook is selected for two or more contiguous groups of data, the codebook number encoding section encodes the codebook number of the Huffman codebook and the number of the contiguous groups of data with a number of bits equal to the predetermined integer A.

11. An encoder according to claim 3, wherein the H Huffman codebooks are eleven Huffman codebooks used for Huffman-encoding of spectral data as defined in the MPEG2-AAC standard.

12. An encoder according to claim 11, wherein:

the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 1-4 defined in the MPEG2-AAC standard; and

the code length calculation section has a first table including respective code lengths which would result when encoding data by using Huffman codebooks 1 and 2 for a common index value and a second table including respective code lengths which would result when encoding data by using Huffman codebooks 3 and 4 for the common index value.

13. An encoder according to claim 12, wherein a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 3 and 4 which are included in the second table.

14. An encoder according to claim 13, wherein the first table includes respective values of T1(F1(a, b, c, d)) and T2(F1(a, b, c, d)) for i1, and the second table includes respective values of T3(F2(a, b, c, d))+nonz(a, b, c, d) and T4(F2(a, b, c, d))+nonz(a, b, c, d) for i2, where:

nonz(w, x, y, z) is a function which gives the number of non-zero values among w, x, y and z;

F1(w, x, y, z) is a function defined as follows;

F1(w, x, y, z)=27*(w+1)+9*(x+1)+3*(y+1)+(z+1) (where an absolute value of each of w, x, y and z is 1 or less);

F2(w, x, y, z) is a function defined as follows;

F2(w, x, y, z)=27*abs(w)+9*abs(x)+3*abs(y)+abs(z) (where an absolute value of each of w, x, y and z is 2 or less);

abs(x) is a function which gives an absolute value of x;

T1(index) to T4(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 1 to 4, respectively;

a, b, c and d are integers representing a group of data; and

i1 and i2 are index values calculated as a function of the integers a, b, c and d.

15. An encoder according to claim 14, wherein:

i1=(X{circumflex over ( )}3)*(a+1)+(X{circumflex over ( )}2)*(b+1)+X*(c+1)+(d+1), where X is a positive number equal to or greater than 3;

i2=(Y{circumflex over ( )}3)*abs(a)+(Y{circumflex over ( )}2)*abs(b)+Y*abs(c)+abs(d), where Y is a positive number equal to or greater than 3; and

the symbol “

{circumflex over ( )}”

denotes an exponentiation.

16. An encoder according to claim 14, wherein:

the index value i1 is obtained through a bit connecting operation of a, b, c and d each of which is represented with X bits or more, where X is a positive number equal to or greater than 2; and

the index value i2 is obtained through a bit connecting operation of abs(a), abs(b), abs(c) and abs(d) each of which is represented with Y bits or more, where Y is a positive number equal to or greater than 2.

17. An encoder according to claim 11, wherein:

the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 1-4 defined in the MPEG2-AAC standard; and

the code length calculation section has a table of data including respective code lengths which would result when encoding data by using Huffman codebooks 1 to 4 for a common index value.

18. An encoder according to claim 17, wherein a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 3 and 4 which are included in the table.

19. An encoder according to claim 18, wherein the table includes respective values of T1(F1(a, b, c, d)), T2(F1(a, b, c, d)), T3(F2(a, b, c, d))+nonz(a, b, c, d) and T4(F2(a, b, c, d))+nonz(a, b, c, d) for j, where:

nonz(w, x, y, z) is a function which gives the number of non-zero values among w, x, y and z;

F1(w, x, y, z) is a function defined as follows;

F1(w, x, y, z)=27*(w+1)+9*(x+1)+3*(y+1)+(z+1) (where an absolute value of each of w, x, y and z is 1 or less);

F2(w, x, y, z) is a function defined as follows;

F2(w, x, y, z)=27*abs(w)+9*abs(x)+3*abs(y)+abs(z) (where an absolute value of each of w, x, y and z is 2 or less);

abs(x) is a function which gives an absolute value of x;

T1(index) to T4(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 1 to 4, respectively;

a, b, c and d are integers representing a group of data; and

j is an index value calculated as a function of the integers a, b, c and d.

20. An encoder according to claim 19, wherein the index value j is obtained through a bit connecting operation of a, b, c and d each of which is represented with Y bits or more, where Y is a positive number equal to or greater than 2.

21. An encoder according to claim 11, wherein:

the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 5-10 defined in the MPEG2-AAC standard; and

the code length calculation section has a first table including respective code lengths which would result when encoding data by using Huffman codebooks 5 and 6 for a common index value, a second table including respective code lengths which would result when encoding data by using Huffman codebooks 7 and 8 for a common index value, and a third table including respective code lengths which would result when encoding data by using Huffman codebooks 9 and 10 for a common index value.

22. An encoder according to claim 21, wherein:

a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 7 and 8 which are included in the second table; and

a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 9 and 10 which are included in the third table.

23. An encoder according to claim 22, wherein the first table includes respective values of T5(F3(a, b)) and T6(F3(a, b))for i3, the second table includes respective values of T7(F4(a, b))+nonz(a, b) and T8(F4(a, b))+nonz(a, b) for i4, and the third table includes respective values of T9(F5(a, b))+nonz(a, b) and T10(F5(a, b))+nonz(a, b) for i5, where:

nonz(x, y) is a function which gives the number of non-zero values among x and y;

F3(x, y) is a function defined as follows;

F3(x, y)=9*(x+4)+(y+4) (where an absolute value of each of x and y is 4 or less);

F4(x, y) is a function defined as follows;

F4(x, y)=8*abs(x)+abs(y) (where an absolute value of each of x and y is 7 or less);

F5(x, y) is a function defined as follows;

F5(x, y)=13*abs(x)+abs(y) (where an absolute value of each of x and y is 12 or less);

abs(x) is a function which gives an absolute value of x;

T5(index) to T10(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 5 to 10 defined in the MPEG2-AAC standard, respectively;

a and b are integers representing a group of data; and

i3, i4 and i5 are index values calculated as a function of the integers a and b.

24. An encoder according to claim 23, wherein:

i3=X*(a+4)+(b+4), where X is a positive number equal to or greater than 9;

i4=Y*abs(a)+abs(b), where Y is a positive number equal to or greater than 8; and

i5=Z*abs(a)+abs(b), where Z is a positive number equal to or greater than 13.

25. An encoder according to claim 24, wherein:

the index value i3 is obtained through a bit connecting operation of a and b each of which is represented with X bits or more, where X is a positive number equal to or greater than 4;

the index value i4 is obtained through a bit connecting operation of a and b each of which is represented with Y bits or more, where Y is a positive number equal to or greater than 4; and

the index value i5 is obtained through a bit connecting operation of a and b each of which is represented with Z bits or more, where Z is a positive number equal to or greater than 5.

26. An encoder according to claim 11, wherein:

the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 5-10 defined in the MPEG2-AAC standard; and

the code length calculation section has a table including respective code lengths which would result when encoding data by using Huffman codebooks 5 to 10 for a common index value.

27. An encoder according to claim 26, wherein a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 7 to 10 which are included in the table.

28. An encoder according to claim 27, wherein the table includes respective values of T5(F3(a, b)), T6(F3(a, b)), T7(F4(a, b))+nonz(a, b), T8(F4(a, b))+nonz(a, b), T9(F5(a, b))+nonz(a, b) and T10(F5(a, b))+nonz(a, b) for k, where:

nonz(x, y) is a function which gives the number of non-zero values among x and y;

F3(x, y) is a function defined as follows;

F3(x, y)=9*(x+4)+(y+4) (where an absolute value of each of x and y is 4 or less);

F4(x, y) is a function defined as follows;

F4(x, y)=8*abs(x)+abs(y) (where an absolute value of each of x and y is 7 or less);

F5(x, y) is a function defined as follows;

F5(x, y)=13*abs(x)+abs(y) (where an absolute value of each of x and y is 12 or less);

abs(x) is a function which gives an absolute value of x;

T5(index) to T10(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 5 to 10 defined in the MPEG2-AAC standard, respectively;

a and b are integers representing a group of data; and

k is an index value calculated as a function of the integers a and b.

29. An encoder according to claim 28, wherein the index value k is obtained through a bit connecting operation of a and b each of which is represented with Z bits or more, where Z is a positive number equal to or greater than 5.

30. An encoder according to claim 3, wherein:

the code length calculation section is adapted to output an invalid signal which indicates that a Huffman codebook is invalid when an input data value is outside a variable range within which a code length can be calculated using the Huffman codebook; and

the control section is adapted not to select a Huffman codebook when the control section receives an invalid signal for the Huffman codebook.

31. An encoder according to claim 14, wherein:

the value of the function T1(F1(a, b, c, d)) and the value of the function T2(F1(a, b, c, d)) are stored respectively on a MSB side and on a LSB side with respect to the index value i1, with at least m1 bits of “

0”

(m1 is a positive integer) being inserted between the value of the function T1 and the value of the function T2; and

the value of the function T3(F2(a, b, c, d))+nonz(a, b, c, d) and the value of the function T4(F2(a, b, c, d))+nonz(a, b, c, d) are stored respectively on a MSB side and on a LSB side with respect to the index value i2, with at least m1 bits of “

0”

being inserted between the value of the function T3 and the value of the function T4.

32. An encoder according to claim 19, wherein:

the value of the function T1(F1(a, b, c, d)), the value of the function T2(F1(a, b, c, d)), the value of the function T3(F2(a, b, c, d))+nonz(a, b, c, d) and the value of the function T4(F2(a, b, c, d))+nonz(a, b, c, d) are stored in this order from a MSB side to a LSB side with respect to the index value j, with at least m1 bits of “

0”

(m1 is a positive integer) being inserted between the value of T1 and the value of T2, between the value of T2 and the value of T3, and between the value of T3 and the value of T4.

33. An encoder according to claim 31, wherein the value of m1 is an integer value obtained by rounding up a value of the logarithm of 2 to the base of n1 (log₂(n1)), where n1 is a value obtained by dividing a maximum number of data included in each group among the G groups of data by 4.

34. An encoder according to claim 23, wherein:

the value of the function T5 (F3(a, b)) and the value of the function T6(F3(a, b)) are stored respectively on a MSB side and on a LSB side with respect to the index value i3, with at least m2 bits of “

0”

(m2 is a positive integer) being inserted between the value of the function T5 and the value of the function T6;

the value of the function T7(F4(a, b))+nonz(a, b) and the value of the function T8(F4(a, b))+nonz(a, b) are stored respectively on a MSB side and on a LSB side with respect to the index value i4, with at least m2 bits of “

0”

being inserted between the value of the function T7 and the value of the function T8; and

the value of the function T9(F5(a, b))+nonz(a, b) and the value of the function T10(F5(a, b))+nonz(a, b) are stored respectively on a MSB side and on a LSB side with respect to the index value i5, with at least m2 bits of “

0”

being inserted between the value of the function T9 and the value of the function T10.

35. An encoder according to claim 28, wherein the value of the function T5(F3(a, b)), the value of the function T6(F3(a, b)), the value of the function T7(F4(a, b))+nonz(a, b), the value of the function T8(F4(a, b))+nonz(a, b), the value of the function T9(F5(a, b))+nonz(a, b) and the value of the function T10(F5(a, b))+nonz(a, b) are stored in this order from a MSB side to a LSB side with respect to the index value k, with at least m2 bits of “

0”

(m2 is a positive integer) being inserted between the value of T5 and the value of T6, between the value of T6 and the value of T7, between the value of T7 and the value of T8, between the value of T8 and the value of T9, and between the value of T9 and the value of T10.

36. An encoder according to claim 34, wherein the value of m2 is an integer value obtained by rounding up a value of the logarithm of 2 to the base of n2 (log₂(n2)), where n2 is a value obtained by dividing a maximum number of data included in each group among the G groups of data by 2.