# 几道有趣的HDL题目（from HDLBits）

## 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:

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:

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 自己的解

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

#### 坑点：

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