Encoder using Huffman codes

Details Encoder using Huffman codes Encoder using Huffman codes

2000-04-18

2002-11-19

Dorvil, Richemond (Department: 2654)

Data processing: speech signal processing, linguistics, language

Audio signal bandwidth compression or expansion

C704S201000, C341S065000, C358S426130

Reexamination Certificate

active

06484142

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an encoder using Huffman codes. More particularly, the present invention relates to an encoder capable of selecting the optimal Huffman codebook from among a plurality of Huffman codebooks so as to encode digital data by using the optimally selected Huffman codebook.
2. Description of the Related Art
In recent years, efficient audio signal compression methods encode spectral data of quantized audio signals by using a Huffman encoding scheme. A conventional data compression method, for example, a data compression method disclosed in the MPEG2-AAC standard will now be described (see ISO/IEC 13818-7).
First, an input PCM (Pulse Code Modulation) signal is converted through an MDCT (Modified Discrete Cosine Transform) operation into 1024 elements of frequency spectral data. This process is described in detail in “ISO/IEC 13818-7 ANNEX B 2.3 FilterBank and block switching” and will not be discussed below. “ISO/IEC 13818-7 ANNEX B 2.3 FilterBank and block switching is incorporated by reference in its entirety.
Then, the 1024 elements of frequency spectral data are quantized (converted into integers) by using a non-linear quantization method. This process is described in detail in “ISO/IEC 13818-7 ANNEX B 2.7 Quantizing” and will not be discussed below. “ISO/IEC 13818-7 ANNEX B 2.7 Quantizing” is incorporated by reference in its entirety.
Next, the 1024 elements of quantized frequency spectral data are grouped into a number of scale factor bands (in this specification, a scale factor band (SFB) may also be referred to as a “group of data”). Using a sampling frequency of 48 kHz, for example, the 1024 elements of quantized frequency spectral data would be grouped into 49 SFBs. Referring now to
FIG. 14
, the grouping of frequency spectral data is performed as shown in a table
450
. For example, the frequency spectral data is grouped into SFBs so that SFB
0
includes four elements
0
-
3
of the frequency spectral data (as shown in row
451
), SFB
1
includes four elements
4
-
7
of the frequency spectral data (as shown in row
452
), and SFB
2
includes four elements
8
-
11
of the frequency spectral data.(as shown in row
453
) (see “ISO/IEC 13818-7 3.8 Tables”).
Referring to
FIG. 15
, a table
500
illustrating frequency spectral data which has been quantized and grouped into a number of SFBs (SFB
0
to SFB(G−1)) in a process as described above is shown. In
FIG. 15
, left column
501
designated “SFB” shows a number of SFBs (SFB
0
to SFB(G−1)), center column
502
designated “spectrum” shows frequency spectral data numbers, and right column
503
designated “value” shows the absolute value of each frequency spectral data.
Then, the quantized and grouped frequency spectral data is Huffman-encoded for each SFB. The Huffman encoding operation is performed based on one Huffman codebook which is selected for each SFB from among a plurality of Huffman codebooks. According to the MPEG2-AAC standard, a Huffman codebook is selected from among eleven Huffman codebooks (Huffman codebooks
1
-
11
). In the following description, however, only four Huffman codebooks (Huffman codebooks
3
-
6
) are used for the sake of simplicity.
FIGS. 16
to
19
illustrate Huffman codebooks
3
-
6
, respectively. In the Huffman codebooks
3
-
6
illustrated in
FIGS. 16
to
19
, respectively, the leftmost column designated “index” shows the index number of each data to be encoded, the second column designated “length” shows the code length of each encoded data, and the third column designated “codeword (hexadecimal)” shows a hexadecimal representation of each encoded data (codeword). The Huffman codebooks
3
-
6
illustrated in
FIGS. 16
to
19
each contain the code length of each encoded data (length) and a hexadecimal representation of each encoded data (codeword) for index numbers
0
-
80
.
In SFB
0
shown in
FIG. 15
, the largest absolute spectral data value is
4
. According to the MPEG2-AAC standard, Huffman codebooks that can be selected for an input signal are limited by the largest absolute value of the input signal. This limitation is determined by LAV (largest absolute value) as shown in FIG.
20
. LAV of a Huffman codebook denotes the largest absolute value of input data that can be encoded by using a particular Huffman codebook. According to the table shown in
FIG. 20
, when the largest absolute spectral data value in SFB
0
is
4
, Huffman codebooks
5
and
6
are the candidate Huffman codebooks. The code length which would result when encoding data with the candidate Huffman codebook
5
is compared with the code length which would result when encoding data with the candidate Huffman codebook
6
. The candidate Huffman codebook that gives the smaller code length is selected. In this example, where the Huffman codebooks
5
and
6
are candidates, the code length which would result when Huffman-encoding data with the candidate Huffman codebooks is calculated as follows:
First, two index values “index
0
” and “index
1
” are calculated from Expressions (1) and (2) below:
index
0
=(D
0
+LAV)*(2*LAV+1)+(D
1
+LAV)  (1)
index
1
=(D
2
+LAV)*(2*LAV+1)+(D
3
+LAV)  (2)
where D
0
, D
1
, D
2
and D
3
respectively denote the four spectral data elements (values) of SFB
0
. The calculated values of “index
0
” and “index
1
” are used as the index values. The code length “length” for the candidate Huffman codebooks
5
and
6
is obtained based on the index values.
Referring to
FIG. 15
, substituting the following values into Expressions (1) and (2), D
0
=4, D
1
=-2, D
2
=0, D
3
=3 and LAV=4, result in index
0
=74 and index
1
=43. Referring to the Huffman codebook
5
shown in
FIG. 18
, a length=12 for index
0
=74 and a length=
8
for index
1
=43 can be determined, indicating that the code length would be 20 (12+8) bits when Huffman-encoding data with the Huffman codebook
5
. Referring to the Huffman codebook
6
shown in
FIG. 19
, a length=9 for index
0
=74 and a length=7 for index
1
=43 can be determined, indicating that the code length would be 16 (9+7) bits when Huffman-encoding data with the Huffman codebook
6
. Therefore, it is more advantageous to select the candidate Huffman codebook
6
for encoding each spectral data included in SFB
0
. Thus, the Huffman codebook
6
is selected.
Similarly, for SFB
1
, the code length would be 18 bits when encoding data with the Huffman codebook
5
, and 13 bits when encoding data with the Huffman codebook
6
. Therefore, it is more advantageous to also select the Huffman codebook
6
for encoding each spectral data included in SFB
1
. Thus, the Huffman codebook
6
is selected.
For SFB
2
shown in
FIG. 15
, whose largest absolute spectral data value is 1, the Huffman codebooks
3
-
6
are the candidate Huffman codebooks. For the Huffman codebooks
5
and
6
, the code length of Huffman-encoded data can be determined as described above; 9 bits for the Huffman codebook
5
and 8 bits for the Huffman codebook
6
.
For the Huffman codebooks
3
and
4
, the code length of Huffman-encoded data is calculated as follows. The Huffman codebooks
3
and
4
are so-called unsigned codebooks which are used for encoding data without a sign (unsigned data). When using an unsigned codebook, the absolute value of input data is Huffman-encoded, while the number of ignored signs are separately counted and added to the code amount of the Huffman encoding operation. The number of ignored signs corresponds to the number of non-zero elements (elements that require a sign) of the data to be encoded. The code length which would result when Huffman-encoding data with such an unsigned Huffman codebook can be obtained as follows.
First, an index value “index
0
” is calculated from Expression (3) below:
index
0
=
abs
(D
0
)*(k{circumflex over ( )}3)+
abs
(D
1
)*(k{circumflex over ( )

Affiliated with

Also associated with

Rating

Encoder using Huffman codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Encoder using Huffman codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoder using Huffman codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2978244