alex9ufo 聰明人求知心切

2021年6月26日星期六

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[i16+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[i16+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[i16+j] < 2)
q_2d[i][j] <= 1'b0;
else if (nghbr_num[i16+j] > 3)
q_2d[i][j] <= 1'b0;
else if (nghbr_num[i16+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[i16+j] = q_2d[i][j];
end
end
end
endmodule

HDLBits Rule110

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

Left	Center	Right	Center's next state
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	0

(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).

根據卡諾圖可以得到:OUT = Center ^ Right + (Center · ~Left )

另一說法

HDL語言的描述方式是，當left為1時，center ^ right；left為0時，center | right。用代碼描述即為

center <= left ？ center ^ right ：center | right ；

使用條件語句可以很輕易的描述rule 110，但是在Verilog代碼實際編寫過程中，我們無法一位一位的進行判斷然後進行異或操作或者與操作，於是可以把思路從行為級描述轉變到結構級描述，通過使用最基礎的and gate、or gate 和 xor gate 來實現上述電路

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

HDLBits Rule90

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

Left	Center	Right	Center's next state
1	1	1	0
1	1	0	1
1	0	1	0
1	0	0	1
0	1	1	1
0	1	0	0
0	0	1	1
0	0	0	0

(The name "Rule 90" comes from reading the "next state" column: 01011010 is decimal 90.)

首先，我們通過觀察上表可以很容易的发現一個規律，center的下一個狀態由center的左鄰和右鄰 XOR 而成。

center的下一個狀態列：01011010，轉換為十進制即為90，所以我們將其命名為rule 90.

知道了下一狀態產生的規則後，我們就根據其規則實現下面這個電路：

在這個電路中，我們創造512個細胞系統（q[511:0]），在每個時鐘周期前進一個步長。load輸入將輸出q加載為data[511:0]，假設邊界q[-1]和q[522]都為0.

我們將每一位用左鄰和右鄰的 XOR 表示出來，发現512位太長無法一一枚舉，所以觀察規律後直接使用按位 XOR ^。左鄰居可以不用在最前面添0，按位異或會默認從最低位對齊，高位多出來的用0補齊然後進行計算。

module top_module(
input clk,
input load,
input [511:0] data,
output [511:0] q );
always@(posedge clk)
if (load)
q <= data;
else
//q <= {q[510],q[511]^q[509],q[510]^q[508],……,q[2]^q[0],q[1]}
// left right
// neighbour neighbour
q <= {1'b0,q[511:1]}^{q[510:0],1'b0};
endmodule

2021年6月25日星期五

HDLBits Shift Register(Exams/m2014 q4k) LUT

HDLBits Shift Register(Exams/m2014 q4k) LUT

In this question, you will design a circuit for an 8x1 memory, where writing to the memory is accomplished by shifting-in bits, and reading is "random access", as in a typical RAM. You will then use the circuit to realize a 3-input logic function.

First, create an 8-bit shift register with 8 D-type flip-flops. Label the flip-flop outputs from Q[0]...Q[7]. The shift register input should be called S, which feeds the input of Q[0] (MSB is shifted in first). The enable input controls whether to shift. Then, extend the circuit to have 3 additional inputs A,B,C and an output Z. The circuit's behaviour should be as follows: when ABC is 000, Z=Q[0], when ABC is 001, Z=Q[1], and so on. Your circuit should contain ONLY the 8-bit shift register, and multiplexers. (Aside: this circuit is called a 3-input look-up-table (LUT)).

實現的是一個和 8x1 結構的存儲體相關的電路。存儲的輸入通過移入比特進行，存儲的讀取類似於傳統 RAM 中的隨機讀取，即可以指定讀出比特的位置，通過 3 個輸入端口指定讀取位置。

首先通過 8 個觸发器實現一個 8bit 深的移位寄存器。8個寄存器的輸出依次為 Q[0]...Q[7]。移位寄存器的輸入為 S，輸入首先會填充到 MSB（最高位），Q[0]。當 enable 信號控制移位，當其有效時輸入數據並移位。此外，該電路有三個輸入端口 A,B,C 以及輸出端口 Z。工作的功能如下：當 ABC = 000 時，Z = Q[0],當 ABC = 001 時，Z = Q[1],以此類推。你的電路中只能包括一個 8bit 移位寄存器以及一個多路選擇器。（這就是個三輸入查找表 LUT 電路）

module top_module (
input clk,
input enable,
input S,
input A, B, C,
output Z );

reg [7:0] Q;
always@(posedge clk)begin
if(enable)begin
Q <= {Q[6:0], S};
end
else begin
Q <= Q;
end
end
always@(*)begin
case({A, B, C})
3'b000: Z = Q[0];
3'b001: Z = Q[1];
3'b010: Z = Q[2];
3'b011: Z = Q[3];
3'b100: Z = Q[4];
3'b101: Z = Q[5];
3'b110: Z = Q[6];
3'b111: Z = Q[7];
endcase
end
endmodule

DE2-115 Shift Register(Exams/m2014 q4b)

DE2-115 Shift Register(Exams/m2014 q4b)

Consider the n-bit shift register circuit shown below:

實現下圖中的 n bit 移位暫存器電路

Write a top-level Verilog module (named top_module) for the shift register, assuming that n = 16. Instantiate four copies of your MUXDFF subcircuit in your top-level module. Assume that you are going to implement the circuit on the DE2-115 board.

Connect the R inputs to the SW [15:0] switches,
clk to KEY[0],
E to KEY[1],
L to KEY[2], and
w to KEY[3].
Connect the outputs to the red lights LEDR[15:0].

(Reuse your MUXDFF from exams/2014_q4a.)

module m2014q4b (
input [17:0] SW,
input [3:0] KEY,
output [15:0] LEDR
); //
wire [15:0] w_input = {KEY[3],LEDR[15],LEDR[14],LEDR[13],
LEDR[12],LEDR[11],LEDR[10],LEDR[9],LEDR[8],LEDR[7],
LEDR[6],LEDR[5],LEDR[4],LEDR[3],LEDR[2],LEDR[1]};
generate
genvar i;
for(i=0;i<16;i=i+1) begin:muxdff
MUXDFF (
.clk(KEY[0]),
.w(w_input[i]),
.R(SW[i]), //load sw[15:0] data
.E(SW[17]),
.L(SW[16]),
.Q(LEDR[i]) );
end
endgenerate
endmodule

module MUXDFF (
input clk,
input w, R, E, L,
output reg Q
);
always@(posedge clk)begin
case({E,L})
2'b00: Q <= Q;
2'b01: Q <= R; //load sw[15:0] data
2'b10: Q <= w; //load KEY[3] data
2'b11: Q <= R; //load sw[15:0] data
endcase
end
endmodule

HDLBits Shift Register(Exams/m2014 q4b)

HDLBits Shift Register(Exams/m2014 q4b)

Consider the n-bit shift register circuit shown below:

實現下圖中的 n bit 移位暫存器電路

Write a top-level Verilog module (named top_module) for the shift register, assuming that n = 4. Instantiate four copies of your MUXDFF subcircuit in your top-level module. Assume that you are going to implement the circuit on the DE2 board.

Connect the R inputs to the SW [3:0] switches,
clk to KEY[0],
E to KEY[1],
L to KEY[2], and
w to KEY[3].
Connect the outputs to the red lights LEDR[3:0].

(Reuse your MUXDFF from exams/2014_q4a.)

module top_module (
input [3:0] SW,
input [3:0] KEY,
output [3:0] LEDR
); //
wire [3:0] w_input = {KEY[3],LEDR[3],LEDR[2],LEDR[1]};
generate
genvar i;
for(i=0;i<4;i=i+1) begin:muxdff
MUXDFF (
.clk(KEY[0]),
.w(w_input[i]),
.R(SW[i]),
.E(KEY[1]),
.L(KEY[2]),
.Q(LEDR[i]) );
end
endgenerate
endmodule
//module MUXDFF (...);
module MUXDFF (
input clk,
input w, R, E, L,
output Q
);
always@(posedge clk)begin
case({E,L})
2'b00: Q <= Q;
2'b01: Q <= R;
2'b10: Q <= w;
2'b11: Q <= R;
endcase
end
endmodule

HDLBits Shift Register(Exams/m2014 q4k)

HDLBits Shift Register(Exams/m2014 q4k)

Implement the following circuit:

module top_module (
    input clk,
    input resetn,   // synchronous reset
    input in,
    output reg out);
	reg q0,q1,q2;
    
    always@(posedge clk)begin
        if(~resetn)begin
            q0	<=	1'b0;
            q1	<=	1'b0;
            q2	<=	1'b0;
            out	<=	1'b0;
        end else begin
            q0	<=	in;
            q1	<=	q0;
            q2	<=	q1;
            out	<=	q2;
        end
    end
endmodule

//=========原網站解法=================

module top_module (
input clk,
input resetn,
input in,
output out
);
reg [3:0] sr;

// Create a shift register named sr. It shifts in "in".
always @(posedge clk) begin
if (~resetn) // Synchronous active-low reset
sr <= 0;
else
sr <= {sr[2:0], in};
end

assign out = sr[3]; // Output the final bit (sr[3])
endmodule

訂閱：文章 (Atom)

2021年6月26日 星期六

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

module top_module( input clk, input load, input [511:0] data, output [511:0] q ); always@(posedge clk) if (load) q <= data; else //q <= {q[510],q[511]^q[509],q[510]^q[508],……,q[2]^q[0],q[1]} // left right // neighbour neighbour q <= {1'b0,q[511:1]}^{q[510:0],1'b0};endmodule

2021年6月25日 星期五

module MUXDFF ( input clk, input w, R, E, L, output reg Q); always@(posedge clk)begin case({E,L}) 2'b00: Q <= Q; 2'b01: Q <= R; //load sw[15:0] data 2'b10: Q <= w; //load KEY[3] data 2'b11: Q <= R; //load sw[15:0] data endcase endendmodule

2021年6月26日星期六

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

module top_module(
input clk,
input load,
input [511:0] data,
output [511:0] q );
always@(posedge clk)
if (load)
q <= data;
else
//q <= {q[510],q[511]^q[509],q[510]^q[508],……,q[2]^q[0],q[1]}
// left right
// neighbour neighbour
q <= {1'b0,q[511:1]}^{q[510:0],1'b0};
endmodule

2021年6月25日星期五

module MUXDFF (
input clk,
input w, R, E, L,
output reg Q
);
always@(posedge clk)begin
case({E,L})
2'b00: Q <= Q;
2'b01: Q <= R; //load sw[15:0] data
2'b10: Q <= w; //load KEY[3] data
2'b11: Q <= R; //load sw[15:0] data
endcase
end
endmodule