使用 Verilog 实现排序

系统管理员 2022-10-05 04:42 256阅读 0赞

## 实现目标 ##

输入  N = 4 N=4 N=4 个数，通过简单选择排序，对这个四个数进行简单选择排序：每次选择最小的，将最小的数移到起始位置，之后输出。这是同步时序电路和状态机的高级应用。

## 伪代码 ##

设输入  N N N 个数，将其存在寄存器数组  R R R 中；两个循环变量  i , j i,j i,j；将每次遍历到的数分别赋值给  A , B A,B A,B。  
简单选择排序的伪代码可以描述如下：

for i = 0 to N-2 do
    	A = R[i];
    	for j = i to N-1 do
    		B = R[j];
    		if B < A then
    			R[i] = B;
    			R[j] = A;
    			A = R[i];
    		end if;
    	end for;
    end for;

## 数据通路设计 ##

主要牵涉到两大块结构：

*  状态机（控制逻辑）的设计
 *  数据存储的设计

## 状态机的设计 ##

总共设置9个状态，来执行完成该设计。状态图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center]

### 数据存储 ###

设置4个  n n n bit 的寄存器，用来存储输入数据，至于存储的地址（寄存器编号）则作为输入端口，由用户给出。存储器的设计不光要照顾到对输入数据的存储，还需要对每次循环迭代到的  A , B A,B A,B 进行存储，并且  A , B A,B A,B 还需要写回，尤其当  B < A B<A B<A 成立的时候，需要交换写回。所以还需要设置两个  n n n bit 寄存器用来存储  A , B A,B A,B。

至于写回的地址设置，则需要根据判断条件给出。设计的存储模块如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center 1]  
其中有很多信号量，将会在代码里给出注释。

## 代码编写 ##

编写的 Verilog 代码如下：

module sort (
    	input			clk		,
    	input			rst_n	,
    	input			s		,
    	input			WrInit	,
    	input	[1:0]	RAdd	,
    	input	[15:0]	DataIn	,
    	input			Rd		,
    
    	output	[15:0]	DataOut	,
    	output	reg		Done
    );
    
    	localparam	[3:0]	S1 = 4'b0000,
    						S2 = 4'b0001,
    						S3 = 4'b0010,
    						S4 = 4'b0011,
    						S5 = 4'b0100,
    						S6 = 4'b0101,
    						S7 = 4'b0110,
    						S8 = 4'b0111,
    						S9 = 4'b1000;
    	// 表示两个循环变量
    	wire [1:0] Ci, Cj;
    	wire [1:0] CMux, IMux;
    	// CMus is Ci or Cj 
    	// IMux is the read adder
    	wire [15:0] R0, R1, R2, R3, A, B, RData, ABMux;
    
    	// A B 的大小判断和循环变量是否达到上界
    	wire BltA, zi, zj;
    
    	reg Int, Csel, Wr, Ain, Bin, Bout; 
    	reg LI, LJ, EI, EJ; // ports for count
    	reg Rin0, Rin1, Rin2, Rin3; // enable for regs
    
    	reg [15:0] ABData;
    	
    	reg [3:0] curr_state;
    	reg [3:0] next_state;
    	always@(posedge clk or negedge rst_n) begin:state_ff
    		if (!rst_n) curr_state <= S1;
    		else		curr_state <= next_state;
    	end
    	
    	always@(*) begin: state_table
    		Int = 1; Done = 0; Csel = 0; Wr = 0; Ain = 0; Bin = 0; Bout = 0;
    		LI = 0; LJ = 0; EI = 0; EJ = 0; 
    		case(curr_state) 
    			S1: begin
    				LI = 1;  // make Ci be 0 
    				Int = 0; // indicate the initial process
    				if (s == 0) next_state = S1;
    				else next_state = S2;
    			end
    			S2: begin
    				//Int = 1;
    				//Csel = 0; // 
    				Ain = 1; // make A be R[Ci]
    				LJ = 1;  // make Cj be 0
    				next_state = S3;
    			end
    			S3: begin
    				EJ = 1; // make Cj = Cj + 1
    				next_state = S4;
    			end
    			S4: begin
    				Bin  = 1; // make B be R[Cj]
    				Csel = 1; // 
    				//Wr = 1; // write enable
    				next_state = S5;
    			end
    			S5: begin
    				if (BltA) next_state = S6;
    				else next_state = S8;
    			end
    			S6: begin
    				Csel = 1;
    				Wr = 1;
    				next_state = S7;
    			end
    			S7: begin
    				Wr = 1;
    				Bout = 1;
    				next_state = S8;
    			end
    			S8: begin
    				Ain = 1;
    				if (!zj) begin     // Cj < 3
    					EJ = 1;
    					EI = 0;
    					next_state = S4;
    				end
    				else if (!zi) begin // Ci < 2
    					EJ = 0;
    					EI = 1;
    					next_state = S2;
    				end
    				else 
    					next_state = S9;
    			end
    			S9: begin
    				Done = 1;
    				if (s) next_state = S9;
    				else next_state = S1;
    			end
    		endcase
    
    	end
    	
    	// Instance Modules
    	
    	reg16 Reg0 (clk, rst_n, RData, Rin0, R0);
    	reg16 Reg1 (clk, rst_n, RData, Rin1, R1);
    	reg16 Reg2 (clk, rst_n, RData, Rin2, R2);
    	reg16 Reg3 (clk, rst_n, RData, Rin3, R3);
    	
    	reg16 RegA (clk, rst_n, ABData, Ain, A);
    	reg16 RegB (clk, rst_n, ABData, Bin, B);
    
    	upcount OuterLoop (clk, EI, 2'b0, LI, Ci);
    	upcount InnerLoop (clk, EJ,   Ci, LJ, Cj);
    	
    	assign BltA = (B < A) ? 1 : 0;
    	
    	// when BltA == 1 then Bout will be 1
    	assign ABMux = (Bout   == 0) ? A      : B;
    	assign RData = (WrInit == 1) ? DataIn : ABMux;
    
    	// CMux decides the writing order of A and B
    	assign CMux = (Csel == 0) ? Ci   : Cj;
    	assign IMux = (Int  == 1) ? CMux : RAdd;
    	
    	assign zi = (Ci == 2);
    	assign zj = (Cj == 3);
    
    	// the regs' reading and writing
    	always@(*) begin
    		// choose the regs out
    		case(IMux)
    			0: ABData = R0;
    			1: ABData = R1;
    			2: ABData = R2;
    			3: ABData = R3;
    		endcase
    
    		// the write enable is valid
    		// WrInit for initial and Wr for the write back of A or B 
    		if (WrInit || Wr) begin
    			case (IMux)
    				0: { Rin3, Rin2, Rin1, Rin0} = 4'b0001;
    				1: { Rin3, Rin2, Rin1, Rin0} = 4'b0010;
    				2: { Rin3, Rin2, Rin1, Rin0} = 4'b0100;
    				3: { Rin3, Rin2, Rin1, Rin0} = 4'b1000;
    			endcase
    		end
    		else { Rin3, Rin2, Rin1, Rin0} = 4'b0000;
    
    	end
    	// rd read data 信号有效时，将四个寄存器的数据依次读出（需要仿真给予激励信号）
    	assign DataOut = (Rd == 0) ? 'bz : ABData;
    
    
    endmodule
    // 定义的 16 bit 寄存器
    module reg16 (
    	input				clk		,
    	input				rst_n	,
    	input		[15:0]	D		,
    	input 				en		,
    	output	reg	[15:0]	Q
    );
    
    	always@(posedge clk or negedge rst_n) begin
    		if (!rst_n) 
    			Q <= 16'b0;
    		else if (en)
    			Q <= D;
    		else
    			Q <= Q;
    	end
    
    endmodule
    // 定义的计数器，带使能、清零、起始值
    module upcount (
    	input 				clk		,
    	input				en		,
    	input		[1:0]	init	,
    	input				clear	,
    	output	reg	[1:0]	Q
    );
    
    	always@(posedge clk) begin
    		if (clear)
    			Q <= init;
    		else if (en) 
    			Q <= Q + 1;
    		else
    			Q <= Q;
    	end
    
    endmodule

仿真结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center 3]

附上仿真代码：

module sort_tb;
    
    reg clk;
    reg rst_n;
    reg s;
    reg WrInit;
    reg [1:0] RAdd;
    reg [15:0] DataIn;
    reg Rd;
    
    wire [15:0] DataOut;
    wire Done;
    
    
    initial begin
    	clk = 0;
    	forever begin
    		#5 clk = ~clk;
    	end
    end
    
    initial begin
    	rst_n = 0;
    	#20 rst_n = 1;
    	WrInit = 1;
    	DataIn = 3;
    	s = 0;
    	RAdd = 0;
    	Rd = 0;
    	#10 DataIn = 2;
    	RAdd = 1;
    	#10 DataIn = 4;
    	RAdd = 2;
    	#10 DataIn = 1;
    	RAdd = 3;
    	#10 WrInit = 0;
    	DataIn = 0;
    	RAdd = 0;
    	s = 1;
    	#1200 Rd = 1;
    	s = 0;
    	RAdd = 0;
    	#10 RAdd = 1;
    	#10 RAdd = 2;
    	#10 RAdd = 3;
    	#10 RAdd = 0;
    	#100 $finish;
    end
    
    initial begin
    	$vcdpluson;
    end
    
    sort ssort (
    	.clk(clk),
    	.rst_n(rst_n),
    	.s(s),
    	.WrInit(WrInit),
    	.RAdd(RAdd),
    	.DataIn(DataIn),
    	.Rd(Rd),
    
    	.DataOut(DataOut),
    	.Done(Done)
    
    );
    endmodule

有错误欢迎指出。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/08491c9458824eaba79535187cdc354a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/6da150030c014b449bc5b6421ec9308a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/7149ae0d234f4745ad64a450622e746b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/bd7d370d95284835a54cc5b875449f46.png