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

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

首先，我們通過觀察上表可以很容易的发現一個規律，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