几道有趣的HDL题目(from HDLBits)

前言

最近发现了一个Verilog刷题的好网站 HDLBits,如果本科学习数字逻辑或者复杂数字系统时,能够知道这个网站就好了。久疏Verilog,从头开始恢复一下coding的能力,目前刷到了这几道有趣的题目。
题目路径: HDLBits →Circutis→More Circutis

  1. Rule90
  2. Rule110
  3. Conwaylife

1. Rule90

Rule 90 is a one-dimensional cellular automaton with interesting properties.

The rules are simple. There is a one-dimensional array of cells (on or off). At each time step, the next state of each cell is the XOR of the cell’s two current neighbours. A more verbose way of expressing this rule is the following table, where a cell’s next state is a function of itself and its two neighbours:

LeftCenterRightCenter’s next state
1110
1101
1010
1001
0111
0100
0011
0000
(The name “Rule 90” comes from reading the “next state” column: 01011010 is decimal 90.)


In this circuit, create a 512-cell system (q[511:0]), and advance by one time step each clock cycle. The load input indicates the state of the system should be loaded with data[511:0]. Assume the boundaries (q[-1] and q[512]) are both zero (off).

Solution 1.1 自己的解

把左移和右移先用组合逻辑分配好,再做异或操作。

module top_module(
    input clk,
    input load,
    input [511:0] data,
    output [511:0] q ); 
	
    wire [511:0] L,R;
    assign L = {1'b0,q[511:1]};
    assign R = {q[510:0],1'b0};
    
    always @(posedge clk) begin
        if (load)
            q<=data;
        else begin
            q<=L^R;
        end
    end
    
endmodule

Solution 1.2 作者的解

用向量切片的方法直接写在时序逻辑里,做异或操作。

module top_module(
	input clk,
	input load,
	input [511:0] data,
	output reg [511:0] q);
	
	always @(posedge clk) begin
		if (load)
			q <= data;	// Load the DFFs with a value.
		else begin
			// At each clock, the DFF storing each bit position becomes the XOR of its left neighbour
			// and its right neighbour. Since the operation is the same for every
			// bit position, it can be written as a single operation on vectors.
			// The shifts are accomplished using part select and concatenation operators.
			
			//     left           right
			//  neighbour       neighbour
			q <= q[511:1] ^ {q[510:0], 1'b0} ;
		end
	end
endmodule

2 Rule110

Rule 110 is a one-dimensional cellular automaton with interesting properties (such as being Turing-complete).

There is a one-dimensional array of cells (on or off). At each time step, the state of each cell changes. In Rule 110, the next state of each cell depends only on itself and its two neighbours, according to the following table:

LeftCenterRightCenter’s next state
1110
1101
1011
1000
0111
0101
0011
0000
(The name “Rule 110” comes from reading the “next state” column: 01101110 is decimal 110.)

In this circuit, create a 512-cell system (q[511:0]), and advance by one time step each clock cycle. The load input indicates the state of the system should be loaded with data[511:0]. Assume the boundaries (q[-1] and q[512]) are both zero (off).

Solution 2.1 自己的解

还是先用组合逻辑分配左移和右移操作完的向量,然后当作三输入的组合逻辑,根据真值表化简卡诺图,在时序逻辑里给输出赋值。

module top_module(
    input clk,
    input load,
    input [511:0] data,
    output [511:0] q ); 
	
    wire [511:0] L,R;
    assign L = {1'b0,q[511:1]};
    assign R = {q[510:0],1'b0};
    
    always @(posedge clk) begin
        if (load)
            q<=data;
        else 
            q<=L&(q^R) | (~L)&(q|R);

    end
    
endmodule

3 Conwaylife

Conway’s Game of Life is a two-dimensional cellular automaton.

The “game” is played on a two-dimensional grid of cells, where each cell is either 1 (alive) or 0 (dead). At each time step, each cell changes state depending on how many neighbours it has:

  • 0-1 neighbour: Cell becomes 0.
  • 2 neighbours: Cell state does not change.
  • 3 neighbours: Cell becomes 1.
  • 4+ neighbours: Cell becomes 0.

The game is formulated for an infinite grid. In this circuit, we will use a 16×16 grid. To make things more interesting, we will use a 16×16 toroid, where the sides wrap around to the other side of the grid. For example, the corner cell (0,0) has 8 neighbours: (15,1), (15,0), (15,15), (0,1), (0,15), (1,1), (1,0), and (1,15). The 16×16 grid is represented by a length 256 vector, where each row of 16 cells is represented by a sub-vector: q[15:0] is row 0, q[31:16] is row 1, etc. (This tool accepts SystemVerilog, so you may use 2D vectors if you wish.)

  • load: Loads data into q at the next clock edge, for loading initial state.
  • q: The 16×16 current state of the game, updated every clock cycle.

The game state should advance by one timestep every clock cycle.

John Conway, mathematician and creator of the Game of Life cellular automaton, passed away from COVID-19 on April 11, 2020.

solution 3.1 自己的解

题意容易理解,根据当前所在位置周围8个元胞的数量决定下一时刻的状态,也就是下一个状态(update)只和当前的状态(q)有关。

但是与前面一维的情况不同(左移、右移),二维的邻居包括八种:左、右、上、下、左上、左下、右上、右下。但是输入变量由一维的 [255:0] 向量表示,上下操作比较容易,通过一次切片操作,将首部或尾部16位数据移动到另一端;左右操作则需要先切分16个[15:0]的数据再进行循环左移或右移1位,该部分使用for循环实现。

然后将这八个位置的数据分别相加、判断,对update进行赋值。由于这八个位置完全中心对称,实际上下左右的状态只需要完全列举即可,可以不加以区分。

最后使用时序逻辑,当时钟上升沿到来时进行判断,更新输出。

module top_module(
	input clk,
	input load,
	input [255:0] data,
	output reg[255:0] q );
    
    reg [255:0] update; // updated q
    reg [255:0] L,R,U,D,UL,UR,DL,DR; // neighbour
	integer i;
	
    // generate 8 neighbours in [255:0], combinational logic circuit
    always@(*)begin
    	for(i=0;i<16;i=i+1)begin
		L[16*i +:16] = {q[16*i],q[16*i+1 +:15]};
        R[16*i +:16] = {q[16*i +:15],q[16*i+15]};
	end

        D = {q[15:0],q[255:16]};
        U = {q[239:0],q[255:240]}; 
        DL = {L[15:0],L[255:16]};
        UL = {L[239:0],L[255:240]};
        DR = {R[15:0],R[255:16]};
        UR = {R[239:0],R[255:240]};
    end
    
    // calculate update, combinational logic circuit
    always@(*) begin
 		for(i=0;i<256;i=i+1)begin
			if(R[i]+L[i]+D[i]+U[i]+DL[i]+DR[i]+UL[i]+UR[i] <= 1)
				update[i] = 1'b0;
			else if(R[i]+L[i]+D[i]+U[i]+DL[i]+DR[i]+UL[i]+UR[i] == 2)
				update[i] = q[i];
			else if(R[i]+L[i]+D[i]+U[i]+DL[i]+DR[i]+UL[i]+UR[i] == 3)
				update[i] = 1'b1;
			else
				update[i] = 1'b0;
        end
    end
    
    // load or update, sequential logic circuit
	always@(posedge clk)begin
        if(load)
            q <= data;
        else
            q <= update;
    end
    
endmodule

坑点:

最初上下操作由于只要assign一次,但把左移和右移的操作写在了时序逻辑里always@(posedge clk),这样造成了错误 ,应该写在always@(*)中作为组合逻辑。

强化了一个知识点,向量的切片

reg [31:0] dword;
reg [7:0] byte0;
reg [7:0] byte1;
reg [7:0] byte2;
reg [7:0] byte3;

assign byte0 = dword[0 +: 8];    // Same as dword[7:0]
assign byte1 = dword[8 +: 8];    // Same as dword[15:8]
assign byte2 = dword[16 +: 8];   // Same as dword[23:16]
assign byte3 = dword[24 +: 8];   // Same as dword[31:24]


dword[8*sel +: 8] // variable part-select with fixed width

几道有趣的HDL题目(from HDLBits)》有1个想法

  1. Pingback引用通告: HDLBits 刷题总结 | My ignorance

发表评论

邮箱地址不会被公开。 必填项已用*标注