Digital_IC-Homework 3: Point Sorting Engine Solved

Introduction: 
In this homework, you are requested to design a Point Sorting Engine (PSE). The PSE circuit will take coordinate of arbitrary number of input points, and output them clockwise with first point remaining unchanged. The specification and function of

PSE circuit will be described in detail in the following section.

 

Design Specifications: 1 Block Overview
 

 

Fig. 1. The block overview.

 

2.2 I/O Interface
 

Signal Name
I/O
width
Description
clk
I
1
This circuit is a synchronous design triggered at the positive edge of clk.
reset
I
1
Active-high asynchronous reset signal.
Xin
I
10
X coordinate of input point.
Yin
I
10
Y coordinate of input point.
point_num
I
3
The number of input points. The range of point_num is from 3 to 6.
valid
O
1
Output valid signal.
Xout
O
10
X coordinate of output point.
Yout
O
10
Y coordinate of output point.
 

2.3 File Description
File Name
Description
PSE.v
The top module of the design.
tb.sv
The testbench file. The content in this file is not allowed to be modified.
obj.data
Input data file.
golden.data
Golden data file.
 

2.4 System Description
2.4.1 Sorting method
Figure 2 shows an example of input points. The points are input from P1 to P6. The request of PSE circuit is to arrange the index of points in clockwise. P1 is taken as reference point, so its index will not be changed.

To sort the points clockwise, you may use cross product to compare the points pair by pair. First, connect reference point and other points to form vectors (fig.3). Then compute the cross product between vectors to judge their direction. Take the two vectors in figure 4 as example. Vector A = (Ax, Ay) = (x1 – x0, y1 – y0). Vector B = (Bx, By) = (x2 – x0, y2 – y0). The cross product of vector A and vector B is Ax*By – Bx*Ay. If the cross product is minus, B is in the clockwise direction of A and vice versa.

      

                 Fig. 3. Vectors.               Fig. 4. Cross product calculation

After the arrangement is completed, PSE circuit has to output the coordinate of each point according to their new index. The sorted points are showed in figure 5, and they will be output from P1 to P6.

 

Fig. 5. Example of sorted points.

2.4.2 Data input and result output

After the system reset, the number of points to sort will be input by point_num port. Meanwhile, the coordinate of points will also be input by Xin and Yin ports. Testbench side will then wait for PSE circuit to complete its sorting process. PSE circuit should pull up valid signal when it complete calculation, and output coordinate of sorted points by Xout and Yout ports at the same time. When all sorted points are output, PSE circuit should pull down valid signal. Then testbench side will input next set of data.

 

 

Fig. 6. Waveform of data input and result output.

           

Scoring: 
3.1 Functional Simulation [60%] 
All of the result should be generated correctly, and you will get the following message in ModelSim simulation.

 

Fig. 7. Functional simulation result.

3.2 Gate-Level Simulation [20%] 
3.2.1 Synthesis
Your code should be synthesizable. After it is synthesized in Quartus, a file named PSE.vo will be obtained.

3.2.2 Simulation
All of the result should be generated correctly using PSE.vo, and you will get the following message in ModelSim simulation.

 

Fig. 8. Gate-level simulation result.

             Device：Cyclone II EP2C70F896C8 

3.3 Performance [20%] 
The performance is scored by the total logic elements your design used in gatelevel simulation. The score will be decided by your ranking in all received homework. (The smaller, the better)