HDLBits Conwaylift/conway's game of life 16x16

HDLBits  Conwaylift/conway's game of life 16x16 

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 16x16 grid. To make things more interesting, we will use a 16x16 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 16x16 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 16x16 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.

作為前兩題的升級版，本題的變換工作在一個二維矩陣上，是一個二維序列生成器。

遊戲規則如下：元素的下一個狀態取決於當前狀態九宮格中的 8 個鄰居元素中 1 的個數，當鄰居有 n 個 1 時：

0-1 ，元素變為 0

2 ，元素保持不變

3 ，元素變為 1

4+ ，元素變為 0

方便做題起見，本題中的這個二維矩陣設定為 16x16，廣義上可以是無限的。

為了讓事情變得更加有趣，這個16x16 矩陣的邊界進行循環處理，回卷到對邊，打個比方，上邊界的上一行為下邊界，左邊界的左一列為右邊界。

上下邊界回卷示意，左右邊界同理

所以對元素 (0,0) 來說，共有 8 個鄰居 : (15,1), (15,0), (15,15), (0,1), (0,15), (1,1), (1,0) 以及 (1,15)。

這個 16x16 矩陣表示為 256bit 長度的向量 q，其中 q[15:0] 代表第一行，q[31:16] 代表第二行，以此類推。

你也可以使用二維向量表示這個矩陣。load 信號有效時，更新 q 信號值為初始值 data, q 每個周期變換一次。

統計矩陣中每個元素的 8 -相鄰元素中 1 的個數

根據相鄰元素中的 1 的個數，決定元素下一狀態的值

使用組合邏輯，采用相加的方式計算相鄰元素中 1 的個數，使用一個 256 長的序列來記錄每個元素相鄰元素中 1 的個數，最大為 8 個，所以每個元素使用 3 bit 來記錄。

wire [2:0] nghbr_num [255:0];

在統計時，需要處理邊界繞回的的特殊情況。對於邊界上的元素，根據繞回的規則確立邊界。需要特殊處理的是第一/最後一行/列。在編寫 Verilog 代碼時，可以對這幾種情況分別確立邊界。

因為不想代表顯得太冗長，這里引入了 4 個整形變量 idx_i_d, idx_i_u, idx_j_r, idx_j_l ，在不同的情況下，來確立四條邊界。

idx_i_u = (i == 0) ? i-1+16 :i-1; //up idx

idx_i_d = (i == 15)? i+1-16 :i+1; //down idx

idx_j_l = (j == 0) ? j-1+16 :j-1; //left idx

idx_j_r = (j == 15)? j+1-16 :j+1; //right idx

使用時序邏輯，根據統計的結果，決定下一周期元素的值。

輸出最終結果時，將二維信號重新轉換為一維信號，Verilog 不支持直接在一維/二維信號之間賦值。

module top_module(
    input clk,
    input load,
    input [255:0] data,
    output [255:0] q ); 
    
    reg [15:0] q_2d [15:0]; //2-d q
    wire [2:0] nghbr_num [255:0];
    int idx_i_d,idx_i_u,idx_j_r,idx_j_l,i,j;
    //count num of neighbours
    always@(*) begin
        for(i = 0 ; i < 16 ; i = i + 1) begin
            for(j = 0 ; j < 16 ; j = j + 1) begin
                idx_i_u = (i == 0) ? i-1+16 :i-1; //up idx
                idx_i_d = (i == 15)? i+1-16 :i+1; //down idx
                idx_j_l = (j == 0) ? j-1+16 :j-1; //left idx
                idx_j_r = (j == 15)? j+1-16 :j+1; //right idx
                nghbr_num[i*16+j] = q_2d[idx_i_u][idx_j_l] + q_2d[idx_i_u][j  ] + q_2d[idx_i_u][idx_j_r]
                                +   q_2d[i      ][idx_j_l]                      + q_2d[i      ][idx_j_r]
                                +   q_2d[idx_i_d][idx_j_l] + q_2d[idx_i_d][j  ] + q_2d[idx_i_d][idx_j_r];
            end
        end
    end
    //next state transform base on num of neighbours
    always @(posedge clk) begin
        if(load) begin:init
            for(i = 0 ; i < 16 ; i = i + 1) begin
                for(j = 0 ; j < 16 ; j = j + 1) begin
                    q_2d[i][j]    <=  data[i*16+j];
                end
            end
        end
        else begin:set_val
            for(i = 0 ; i < 16 ; i = i + 1) begin
                for(j = 0 ; j < 16 ; j = j + 1) begin
                    if(nghbr_num[i*16+j] < 2)
                        q_2d[i][j]      <=  1'b0;
                    else if (nghbr_num[i*16+j] > 3)
                        q_2d[i][j]      <=  1'b0;
                    else if (nghbr_num[i*16+j] == 3)
                        q_2d[i][j]      <=  1'b1;
                    else
                        q_2d[i][j]      <=  q_2d[i][j];
                end
            end
        end
    end
    //output
    always@(*) begin
        for(i = 0 ; i < 16 ; i = i + 1) begin
            for(j = 0 ; j < 16 ; j = j + 1) begin
                q[i*16+j] = q_2d[i][j];
            end
        end
    end
endmodule