Variable-Length Decoder for Static Huffman Code (Version 1.0)

Tom Wada, Prof of the University of the Ryukyus, Information Engineering Dept.

[0] Introduction

This year's design target is the Variable-Length Decoder for Huffman codes, with which the amount of the digital data is compressed. Using the decoder we can obtain the original data from the compressed data.

There are bunch of multi-media data compression algorithms such as MP3, AAC (Advanced Audio Coding) for sound and voice compression, and JPEG, MPEG for digital still / motion image compression. In those algorithms, DCT (Discrete Cosine Transform) is used with the combination of Quantizations. 

In those algorithms, the Huffman code is also used in order to further decrease the amount of the data. Since the sound, voice, image compressions are frequently used in a real time application such as the broadcasting, you have to design the Variable-Length Decoder for a real time application.

Since this contest is mainly for University students, the code size in the task is relatively small to let student to design easily. In addition, some task level is prepared for several students levels. The requirements of the design is to write HDL (VHDL or Verilog HDL) and to synthesize digital circuits using Synopsys design analyzer or any other EDA tools. Making FPGA is also optional but our judges love to see your FPGA designs.

Figure1 System Diagram

The figure 1 shows the system diagram. The system is divided into two large blocks such as Sender and Decoder. The sender transmits the compressed data using Huffman codes, and the decoder uncompresses the data and recover the original data.

Since the Huffman code length is not fixed, the decoder has to find out the length of each code while processing. In the following sections, the basics of the Huffman codes are explained in order the students who has the digital design knowledge to challenge the design task.

[1] The introduction to Huffman codes

Suppose the following example. There is a sentence in which only 5 characters A to E are used.

CEACDABABCEABADACADABABADEACBADABCADAEE

In total there are 39 characters. The table 1 show the each character's appearance frequency.

Table1. Each Character's Appearance Frequency

From the table 1, you will notice the appearance frequency of 'A' is maximum. If you want to express the sentence as a digital data, you can assign fixed length bit pattern to each alphabets. Please see the table 2.

Table 2. Fixed Length Code

In order to express the 5 alphabets, 3 bits-length code is used. Since there are totally 39 alphabets, 39*3=117 bits are needed to express the sentence in digital data.

In the table 2 example used the 3 bits fixed length code. Since the appearance frequency of 'A' is high, if we use shorter length code for 'A', the amount of digital data to express the sentence can be decreased. One method to do this is to use the Huffman code. The table 3 shows the the example using the Huffman code. The total number of bits are reduced from 117 to 87 bits.

Table 3. Huffman Code

Using the Huffman code in tha table 3, the word 'BAD' can be expressed '1000110', which is 7 bits length. Instead, the bit stream '01100111' can be analyzed from the beginning then the word 'ADAE' can be recovered. Using the figure 2, the decoding method will be explained.

Figure 2. Huffman Code Decoding

The bit stream '01100111' has to be analyzed from the beginning, then find out a matching Huffman Code. Since the code length is not fixed, once the matched Huffman code is detected, the first bit of the next code can be found. In the example of the figure 2, at first the code '0' is found. Then you can know the alphabet 'A' and the code length of 1. Then you can restart the analysis from the second bit. After 3 more bits are analyzed, the code '110' will be found. Then you can know the alphabet 'D' and the code length of 3. 

The Huffman code satisfies the condition of " any code of the group does not match the any prefix of other code of the group". Then the decoding method explained above can only generate the original data.

[2] Huffman Coding of the Image Data

Suppose you are designing the part of the image data uncompression system. Figure 3 shows a one example of the black and White image data. Each pixel (picture element) is organized by 3 bits. Then there are 8 levels of the pixel intensity.

Figure 3. Black and White Image

The left figure in the figure 3 is 8 kinds of pixel intensities. The center number is the level. The most bright pixel is 0. The larger the number increases, the darker the pixel gets. Since there are 8 levels, 3 bits can express the levels. Since the right image (cross mark) is organized by 8x8=64 pixels, simply the image needs 64x3=192 bits. 

The table 4 shows a example to apply the Huffman code to this image. Most frequently appeared pixel number of 0 corresponds to the code '1'. In total, the cross mark image can be expressed in 168 bits. Then the compression ration is 168/192=87.5%. 

Table 4. Huffman Coded Cross Image

The table 5 shows more details of the pixel number and it's Huffman code of the cross mark.

Table 5. Pixel Number and Huffman Code of Crossmark.

You can get the huffman coded cross mark in the following link. Please check it by yourself.

Huffman Coded Crossmark：　crossdata.txt

[3] Variable Length Decoder's Algorithm Example

In this section, one example of the variable length decoder will be explained. Since the maximum length of the Huffman code is 4 bits, at least one data can be decoded from the 4 bits code. See the example in the table 6. 

Table 6. Decoding example

Figure 4. Algorithm Example of Variable-Length Decoder

The explanation of the algorithm in the figure 4.

STEP1：

In the algorithm, 4 bit-wide sliding window is used. The 4 bit data corresponding the sliding window is compared with the righthand side table. The top of the table is '1'.  The MSB of the input 4 bits is '1' then match the top of the table in spite of the other 3 bits and outputs the pixel number of '0' and the code length of 1. 

STEP2：

In the STEP1, the code length is 1. Then shift the sliding window by 1 bit then get the 4 bit inputs corresponding the new sliding window and proceed the same procedure as STEP1. In the example, the new 4 bits is '0110' then the MSB 3bits will match '011'. As a result, pixel number of 1 and the code length of 3 will be obtained.

STEP3：

In the STEP2, the code length was 3. Then shift the sliding window by 3 bits then get the next 4 bits inputs. And repeat the same operation.

[4] Variable Length Decoder's Architecture Example

In this section, the hardware organization of the algorithm described in the section 3 will be shown.

Figure 5. Architecture Example of Variable-Length Decoder

In this architecture, two sets of 4 bit registers are included. The 4 bit width sliding window will be inside of this 8 bit width. Then the 4 bit inputs corresponding the sliding window has to be compared with the Look-up table. 

The look-up table outputs both the pixel number and the code length. According to the code length, sliding window has to be shifted. This shift operation is realized by the accumulator and Barrel Shifter.

The timing critical path will be Barrel Shifter -> Look-up Table -> Accumulator -> Barrel Shifter. In order to achieve the higher clock rate, circuit optimization such as pipelining will be necessary. 

[5] System Oraganization

Figure 6 shows the total of the system including the sender and VLD (Variable-Length Decoder).

Figure 6. System Diagram

SENDER:

The SENDER outputs the Huffman coded cross image data from the CODE output. The data can be found in the following link. LOAD signal is 1 bit width and is asserted when CODE is valid.

Huffman Coded Crossmark: crossdata.txt

VLD:

VLD received the CODE signal and uncompress operation inside then outputs the decoded pixel number on PIXEL terminal. The PIXEL signal indicated the integer from 0 to 7, then 3 bit wdth signal. VALID will be asserted when the PIXEL signal is valid.

[6] Operational Timing

Figure 7. System Timing Diagram

Figure 7 shows the operational timing. After the dis-assertion of RESET signal, SENDER outputs CODE signal such as 1111011001010100....

In this timing diagram, the bit width of CODE signal is 4 bits. Then every 4 cycle, LOAD signal is asserted and the 4 bit width CODE is captured into the Lower register. When the following LOAD signal is asserted, the contents of the Lower register is transferred into the Upper register and the next 4 bit CODE is captured into the Lower register.

The total 8 bits of Upper and Lower register contents are analyzed from the top. Then the decoding is performed. PIXEL signal is output and VALID is asserted when the PIXEL is valid.

The decoding process will continue until all bits in the Upper register are processed. If the upper bit is found in the Upper register and some Lower register bit will  be used if necessary. After all bits in the Upper register is processed, the decoding is posed and VALID signal gets '0'.

Since there will be maximum 4 PIXEL outputs from the Upper 4 bits register, CODE data is input every 4 cycles in this design.

[7] LEVEL1 Task for beginners

The beginners' task has the following pin lists.

Table 7. Pin list for LEVEL1

SENDER and TESTBENCH VHDL file is linked as follow. Please use as it is or modified.

• SENDER:  sender.vhd

• TESTBENCH:　test_vld.vhd

[8] LEVEL2 Task for experienced designners

In the Level 2 task, you do NOT need to follow the detail design spec.

Mandatory rule is 

1) Please design decoder which can decode the crossdata.txt.

2) Any Architecture, any timing, any pin list are acceptable. I believe you can enjoy your originality.

[9] Speed unit

Since it is impossible to use the same synthesis library for various participants, use the 1 exor gate delay as a unit for speed comparison.

How to measure 1 exor gate delay

1. Synthesize the 50 inputs exor gate
2. Measure the total delay time
3. Unit delay is obtained by total delay divided by the number of stages

• VHDL code for 50 inputs exor : parity.vhd
• example of synthesized circuit :　PDF, PS
• example of critical path delay measurement : report_timing
• example of circuit area measurement : report_area

In the previous example, total delay = 7.17 ns and 6 circuit stages, then the 7.17/6= 1.195 ns is the unit of the speed. Please normalize your circuit speed by this unit.

[10] Report

The report has to include the following contents. Be concise!

Report has to be emailed to the following address. Please use PDF file format.

If you want to send the report data other than PDF, please consult me.

wada@ie.u-ryukyu.ac.jp

THE DEAD LINE IS 2003/FEBRUARY/14TH!

[11] Suggestion from judges

• We try to evaluate not only the speed and the area, but also your idea ,originality, uniqueness. But be sure to remember that we are not perfect, please make a good presentation to appeal us.
• We definitely take your school grade into account.
• We like fun ideas. Please do something different from others.

ENJOY HDL! We want to see you at OKINAWA!