2022 Digital IC Design Homework 3: LZ77 Encoder and Decoder
1. Introduction
LZ77 is a lossless data compression algorithm. In this homework, you need to design a LZ77 image compression encoder and a LZ77 decompression decoder. The following section will describe the details of this homework. Three different image test data are provided to verify the correctness of your design. The cycle in the testbench is set as 30 ns, which can’t be modified. You have to pass all three test data to get the score of each part.
2. DesignSpecifications 2.1 Block overview
Copyright By PowCoder代写 加微信 powcoder
Fig.1 Encoder block overview
Fig.2 Decoder block overview
2.2 I/O Interface
Encoder signal table
Signal Name I/O
reset I 1 chardata I 8
encode O 1 O
match_len O 3 char_nxt O 8
This circuit is a synchronous design triggered at the positive edge of clk. Active-high asynchronous reset signal. Character to be encoded.
When encoding, set encode signal to high.
The length of matched string.
The next character behind last matched character in look-ahead buffer.
When the encoding process finishes, set finish signal to high.
Description
When output encoding result, set valid signal to high. The testbench will check the output result when valid signal is high.
The offset between the position of the first character in the matched string to the head of the search buffer.
finish O 1
Table1. Encoder I/O
Decoder signal table
Signal Name I/O clk I
reset I code_pos I
code_len I chardata I
encode O char_nxt O finish O
1 This circuit is a synchronous design triggered at the positive edge of clk.
1 Active-high asynchronous reset signal.
4 The begining position of the matched string
in the search buffer.
3 The length of matched string.
8 The next character behind matched string.
1 When decoding, set encode signal to low.
8 Decoded character.
1 When the decoding process finishes, set
finish signal to high. Table2. Decoder I/O
Description
2.3 File Description
Description
LZ77_Encoder.v LZ77_Decoder.v tb_Encoder.sv tb_Decoder.sv
The module of LZ77_Encoder, which is the top module in this design The module of LZ77_Decoder, which is the top module in this design Encoder testbench. The content is not allowed to be modified. Decoder testbench. The content is not allowed to be modified.
Table3. file description
2.4 LZ77 Algorithm
LZ77 is a lossless data compression algorithm. It is a dictionary coder. LZ77 has two main characteristics:
1. It makes use of encoded input sequence as dictionary.
2. Using a sliding window to encode data. Sliding window is composed of
search buffer and look-ahead buffer. Search buffer saved encoded input sequence, and look-ahead buffer store sequence to be encoded.
The following are the steps of LZ77 encoding algorithm:
Moving the pointer to data in search buffer until equal to the first character in look-ahead buffer. Then check the next character both in search buffer and look-ahead buffer. If they are equal, check the next character again until they are not equal. The total number of equal characters is called length of match.
Repeating step 1 until determining the longest one in all matched sequences.
Output the encoding result [offset, match_len, char_nxt].
i. offset : The offset between the position of the first character in the
matched string to the head of the search buffer.
ii. match_len: The length of the longest matched sequence.
iii. char_nxt: The character behind the longest matched sequence in look-ahead buffer.
The decoding algorithm is the opposite of encoding algorithm.
Move match_len + 1 characters from look-ahead buffer to search buffer. Repeating step 1 to step 4 until all of the data are encoded.
We provide a simple example of LZ77 algorithm : There is a sequence, “ 112a112a2112112112a21$ ”, assumed that the size of search buffer is 9 characters long, look-ahead buffer is 8 characters long. “$” is the end of
input sequence. The following are encoding process :
search look-ahead
buffer buffer
input sequence
2112112112a21$
112112112a21$
2112112a21$
112112a21$
Table4. encoding steps
The result of encoding:
{[0,0,1] [0,1,2] [0,0,a] [3,4,2] [8,3,1] [2,5,a] [7,2,$]}
Notice that, in step6, because the sliding window of LZ77 algorithm is
composed of search buffer and look-ahead buffer, the character to be encoded can be searched not only in the search buffer but also in the look-ahead buffer.
The decoding method is the opposite of the encoding process :
search buffer
1 112 112a
look-ahead
2.5 Function Description
Table5. decoding steps
In this homework, you need to design LZ77 encoder and decoder. The size of search buffer is 9 characters long, look-ahead buffer is 8 characters long. The input sequence to be encoded is a grayscale image, which length is 32x32x2+1 (each pixel value will be sent in two continuously cycle, e.g. pixel value=8’h1a, then tb will send 8’h01 and 8’h0a in continuously cycle). And there will be a symbol “$” in the end of input sequence.
In the encoder module, tb will send chardata immediately in every cycle when reset finished. Each chardata is 8 bits, you need to save all input characters
before finishing encoding them. When chardata is “$” (8’h24), it is the end of input sequence.
The encode, valid signal should be set to high before outputting the encode result (offset, match_len, char_nxt). Otherwise, verification might fail. After finishing encoding, set finish signal to high, tb will terminate the verification.
Fig3. Input image data
Fig4. Encoding output
In the decode module, tb will send decoding data (code_pos, code_len, chardata) immediately when reset finished, and you should output the decoded result(char_nxt). The output timing is as below. The encode signal should be low and set finish signal to high after finishing decoding.
Fig5. Decoding output
3. Scoring
In this homework, we provide three different image data to verify the
correctness of your design. You have to change the pattern path in the testbench (tb_Encoder.sv/ tb_Decoder.sv) to simulate with different image data. The cycle
in the testbench is set as 30 ns, which can’t be modified. In each part, you have to pass all these three test data. Otherwise, you won’t get any score.
3.1Functional Part [60%, each of encoder/decoder is 30%]
All of the result should be generated correctly, and you will get the following
message in ModelSim simulation.
Gate Level Part [20%, each of encoder/decoder is 10%]
3.2.1 Synthesis
Your code should be synthesizable. After synthesizing in Quartus, the
file named LZ77_Encoder.vo(LZ77_Decoder.vo) and LZ77_Encoder_v.sdo (LZ77_Decoder_v.sdo) will be obtained.
Device : Cyclone II EP2C70F896C8
3.2.2 Simulation
All of the result should be generated correctly using LZ77_Encoder.vo
(LZ77_Decoder.vo) and LZ77_Encoder_v.sdo(LZ77_Decoder_v.sdo), and you will get the following message in ModleSim simulation. (There should be no setup or hold time violations.)
3.3 PerformancePart[20%]
The performance is scored by the number of logic elements, memory bits,
and embedded multiplier 9-bit elements your design used in gate-level simulation. The score will be decided by your ranking in all received homework.
The scoring standard: (The smaller, the better)
Total score = encoder score + decoder score Score = Total logic elements + total memory bits + 9*embedded multiplier 9-bit elements
4. Submission
You should classify your files into three directories and compress them to .zip format. The naming rule is HW3_studentID_name.zip. If your file is not named according to the naming rule, you will lose five points.
*.v All of your Verilog RTL code
*.vo Gate-Level netlist generated by Quartus
*.sdo SDF timing information generated by Quartus
4.1 Report file
Please follow the spec of report. If your report does not meet the spec, you
may lose up to ten points. You are asked to describe how the circuit is designed as detailed as possible, and the flow summary results are necessary. Note that, you need to record all of the three pattern of gate-level simulation time in report, we will test your design with them.
RTL category
Gate-Level category
Documentary category
The report file of your design (in pdf).
This homework required your circuit to operate in given clock frequency,
which is 30ns clock width. You could not modify the defined CYCLE in testbench file. The only part you can modify is End_CYCLE, which decide the maximum cycles your circuit took to complete simulation.
Please submit your .zip file to folder HW3 in the moodle.
Deadline: 2022/04/18 23:55
If you have any problem, please contact by the TA by email
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com