Design of Huffman Decoder and Its Application in MP3 Decoding

2 Huffman coding algorithm
--- Entropy coding stipulates that for any given series of data, if the probability of occurrence of each data symbol is known, it can be encoded in a more efficient manner. The basic idea of ​​Huffman coding is to encode shorter data words into data symbols with higher probability of occurrence, and to encode code symbols with lower probability of occurrence.
--- A specific example is given to illustrate how Huffman coding can eliminate data redundancy under the premise of lossless compression. For details, see the data samples and codes displayed in Table 1. It can be seen from the table that for the same information source, Huffman coding effectively reduces data redundancy, minimizes the average code length of the output codeword, and is closest to the source entropy value, and the coding method is optimal.
--- In the case of applying Huffman coding, a Huffman decoder is required at the information receiving end to reply to the initial codeword. The main problem in designing a Huffman decoder is the variable length characteristic of the Huffman code.

3 Huffman decoder hardware structure research
Huffman decoder with 3.1 bit string structure
--- The simplest Huffman decoder structure is to decode the input data stream bit by bit, that is, the bit string mode decoder. With the Moore state machine, the bit string mode decoder can be easily designed. Assuming any given set of Huffman codes, the finite state machine of the decoder can be established by treating each node (0 or 1) as a different state and treating the input at the next moment as the next The condition of the state jump. In this way, the state machine of the decoder of the Huffman code in "Table 1" can be constructed as shown in FIG.
--- Although the bit string mode decoder has its advantages, the design difficulty is small, and the hardware resources consumed are small. As shown in Fig. 1, only three triggers are needed in this example. But its shortcomings are also obvious: due to the different lengths of the input codewords, the number of clock cycles required for decoding is also different, which will cause bit rate discontinuity in the decoding process, which requires additional hardware to solve this problem. problem. In addition, the bit-line mode Huffman decoder is not suitable for use in systems requiring real-time decoding conditions due to the long decoding time.
--- Another problem with this structure is that when the Huffman code tree had to change the entire design modifications. A better option is to use a parallel structure Huffman decoder to speed up the decoding time.

3.2 Huffman decoder with parallel structure
--- The advantage of the decoder designed by parallel technology is that the decoding can be performed in each clock cycle, regardless of the code length, and the hardware complexity is improved in order to speed up the decoding speed. The basic idea of ​​the decoder designed with parallel technology as shown in Fig. 2 is to use the lookup table (LUT) to save the Huffman codewords, and achieve the purpose of decoding by matching the words to be decoded with the codewords in the lookup table. . The length of this structured bit stream input to the decoder is fixed, say 8 bits. An 8-bit data input length may contain more than one codeword data, which requires a buffer to hold the input data stream. The buffer can be implemented with a bucket shift register. Another purpose of the application buffer is to ensure that after a codeword is solved, it can be shifted to the correct position. After the codeword in the buffer is resolved, it begins to receive the new codeword from the bitstream, repeating the above process, so it takes more than one clock cycle to resolve the possible codewords in the buffer. Also, in order to make the data in the lookup table
--- Matching the input codeword, you also need to save the value of each corresponding code length, so that after a codeword is solved, the lookup table simultaneously inputs the value of the code length into an accumulator. The accumulator has two functions: one is to indicate the position of the next word to be decoded in the buffer, this step is calculated by accumulating the lengths of the previous code words; the second is to notify the buffer when all the code words are solved. The bitstream receives a new codeword. The structure of the lookup table is composed of a data pointer and a memory in which a Huffman code table to be used for decoding is stored in advance.
--- Take the code table of "Table 1" as an example, assuming that the first input data stream consists of eight bits: "00100110". The value of the first cycle accumulator to start decoding is "0", the decoded codeword is "00" (A), and the code length is "2". In the second cycle, the value of the accumulator is "2" for the code length decoded in the first cycle, and the accumulator controls the buffer to shift by 2 bits. Thus, the decoded codeword is "10" (D) and the code length is "2". ". In the third period, the value of the accumulator is the sum of the code lengths decoded in the first two periods, the accumulator controls the shift of the buffer by 4 bits, the decoded codeword is "011" (C), and the code length is " 3". In the fourth cycle, the value of the accumulator is "7" and one bit of data remains in the buffer. The accumulator control buffer shifts the first seven out and inputs a new bit stream. Count the remaining "0" of the last decoding, assuming that the second input of the 8-bit data is "10010101", so that the next solved codeword is "01001" (E). In the fifth clock cycle, the value of the accumulator is "12", which is already greater than the 8-bit capacity of the buffer, so the value obtained by subtracting "8" from the value of the accumulator is the location of the next undecoded data in the buffer. . The decoder repeats the above process until all the data in the bitstream has been solved.
--- From the above example, it can be seen that regardless of the length of the codeword, the clock cycles required for decoding each codeword are the same, and the decoding time is relatively short, which is more suitable for an environment requiring real-time decoding. Moreover, when Huffman's code table is changed, it is only necessary to modify the data in the lookup table, and it is also convenient in terms of versatility.

4 Huffman decoder application in MP3 decoder
--- As a compression algorithm for important audio data, the mp3 algorithm has achieved high evaluation with its excellent compression capability and high quality sound quality. In the mp3 compression algorithm, the initial data of the Huffman encoding is the quantized value of the audio frequency line output by the DCT transform. In the process of mp3 decoding, the function of the Huffman decoder is to accept the main data in the mp3 bit stream and output 576 initial frequency lines. The Huffman code of mp3 is divided into three areas: Big-values, Count1, and Rzero. The Big-values ​​area contains the DCT coefficients with the lowest frequency of occurrence and is encoded with the highest accuracy. To further enhance the accuracy of Huffman coding, the Big-values ​​area is subdivided into three areas, each with 32 areas. The code table is available for selection; the Count1 area contains DCT coefficients with medium frequency of occurrence. Each of the four values ​​in this area is coded as one codeword, and there are two code tables for this region to select; the Rzero region contains the highest frequency. The frequency values, all encoded as 0, do not need to be transmitted. When designing the Huffman decoder portion of the mp3 decoder, in addition to the parallel structure described above, the starting boundaries of the above three regions and the problem of zero padding are also considered. The start boundary information and the code table selection information of the three regions of the Huffman codeword can be found in the frame header and side information of the mp3 bitstream data; after the data in the two regions of Big-values ​​and Count1 are solved, The decoder should also automatically fill 0 until 576 frequency values ​​are resolved. The state machine design of the Huffman decoder in the MP3 decoder is shown in Figure 3.


5 Conclusion
--- We take "Huffman code table 6" in the "ISO/IEC 11172-3" standard as an example to verify the final simulation output waveform as shown in Figure 4, "data_in" is the data input, "code_x" And "code_y" is the final output codeword, "valid" is a valid signal, and the output codeword is valid when "valid" is high.
--- Through the actual operation, the decoder of the parallel structure meets the requirements of mp3 decoding well. It can also be easily modified to meet the decoding needs of various application environments. In addition, the design is verified to be synthesizable. The key path of the circuit is Shifter -> Look-up Table -> Accumulator -> Shifter. If you want to achieve higher clock frequency, you can further optimize this critical path by using pipelinelining and other structures.