📖 第2课：一维初等CA——Wolfram规则

Wolfram规则 规则编码 硬件映射

🎯 本课目标

深入理解Wolfram的256种一维初等CA的编码体系，掌握规则号与状态转移表的数学关系，并用Verilog实现一个支持运行时规则切换的CA引擎。

🔢 Wolfram规则的数学结构

邻域与规则空间

一维初等CA的定义：

• 状态数：k = 2（0或1）
• 邻域半径：r = 1（左右各1个邻居）
• 邻域大小：2r + 1 = 3个元胞
• 可能的邻域模式：k^(2r+1) = 2³ = 8种

规则的完整解码表

规则等价类

256种规则中，许多是等价的。等价变换有两种：

⚡ 运行时可配置的CA引擎

上一课的ca_core_1d使用编译时参数RULE，现在我们实现运行时可切换规则的版本。

// ============================================================================
// ca_configurable_1d.v - 运行时可配置规则的一维CA引擎
// 支持动态规则切换、多种边界条件、步数计数
// ============================================================================
module ca_configurable_1d #(
    parameter WIDTH = 64               // 网格宽度
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire             enable,     // 步进使能
    input  wire             init,       // 初始化脉冲
    input  wire [WIDTH-1:0] seed,       // 初始种子
    input  wire [7:0]       rule,       // Wolfram规则号(运行时可变)
    input  wire             wrap_en,    // 1=环形边界, 0=固定边界
    input  wire             fixed_val,  // 固定边界值(当wrap_en=0时)
    output wire [WIDTH-1:0] state,      // 当前状态
    output wire [31:0]      step_count  // 已运行步数
);

    // ---- 状态寄存器 ----
    reg [WIDTH-1:0] curr_state;
    reg [WIDTH-1:0] next_state;
    reg [31:0]      step_reg;

    // ---- 边界处理 ----
    wire left_boundary, right_boundary;

    // 左边界：环形 or 固定
    assign left_boundary  = wrap_en ? curr_state[WIDTH-1] : fixed_val;
    assign right_boundary = wrap_en ? curr_state[0]       : fixed_val;

    // ---- 邻域提取与规则应用 ----
    genvar i;
    generate
        for (i = 0; i < WIDTH; i = i + 1) begin : gen_cell
            wire left, self, right;

            // 提取左邻居
            assign left  = (i == 0)        ? left_boundary  : curr_state[i-1];
            // 自身
            assign self  = curr_state[i];
            // 提取右邻居
            assign right = (i == WIDTH-1)  ? right_boundary : curr_state[i+1];

            // 邻域编码
            wire [2:0] neighborhood = {left, self, right};

            // 规则查找：从8位规则中选取对应位
            assign next_state[i] = rule[neighborhood];
        end
    endgenerate

    // ---- 状态更新 ----
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            curr_state <= {WIDTH{1'b0}};
            step_reg    <= 32'd0;
        end else if (init) begin
            curr_state <= seed;
            step_reg    <= 32'd0;
        end else if (enable) begin
            curr_state <= next_state;
            step_reg    <= step_reg + 32'd1;
        end
    end

    assign state      = curr_state;
    assign step_count = step_reg;

endmodule

🔬 特殊规则的硬件优化

某些规则的结构允许大幅简化硬件。让我们分析几个关键规则：

规则90 — Sierpinski三角形生成器

// ============================================================================
// ca_rule90_opt.v - 规则90的优化硬件实现
// 规则90等价于 XOR(left, right)，无需查找表
// ============================================================================
module ca_rule90_opt #(
    parameter WIDTH = 128              // 支持更大宽度，因为逻辑极简
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire             enable,
    input  wire             init,
    input  wire [WIDTH-1:0] seed,
    output wire [WIDTH-1:0] state
);

    reg [WIDTH-1:0] curr_state;
    wire [WIDTH-1:0] next_state;

    // 规则90: next[i] = curr[i-1] XOR curr[i+1]
    // 环形边界
    assign next_state[0]        = curr_state[WIDTH-1] ^ curr_state[1];
    assign next_state[WIDTH-1]  = curr_state[WIDTH-2] ^ curr_state[0];

    genvar i;
    generate
        for (i = 1; i < WIDTH-1; i = i + 1) begin : gen_xor
            assign next_state[i] = curr_state[i-1] ^ curr_state[i+1];
        end
    endgenerate

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            curr_state <= {WIDTH{1'b0}};
        else if (init)
            curr_state <= seed;
        else if (enable)
            curr_state <= next_state;
    end

    assign state = curr_state;

endmodule

规则150 — 另一个XOR规则

规则关系的代数结构

🧪 完整仿真验证

我们编写一个综合testbench，同时验证多个规则：

// ============================================================================
// ca_multi_rule_tb.v - 多规则验证
// ============================================================================
\`timescale 1ns/1ps

module ca_multi_rule_tb;

    parameter WIDTH = 16;
    reg clk, rst_n, enable, init;
    reg  [WIDTH-1:0] seed;
    reg  [7:0]       rule;
    wire [WIDTH-1:0] state;
    wire [31:0]      step_count;

    ca_configurable_1d #(.WIDTH(WIDTH)) dut (
        .clk(clk), .rst_n(rst_n), .enable(enable),
        .init(init), .seed(seed), .rule(rule),
        .wrap_en(1'b1), .fixed_val(1'b0),
        .state(state), .step_count(step_count)
    );

    // 时钟生成
    initial clk = 0;
    always #5 clk = ~clk;

    // 规则测试序列
    reg [7:0] rules_to_test [0:3];
    integer   r, step;

    initial begin
        rules_to_test[0] = 8'd30;    // 混沌
        rules_to_test[1] = 8'd90;    // Sierpinski
        rules_to_test[2] = 8'd110;   // 通用计算
        rules_to_test[3] = 8'd150;   // XOR

        $dumpfile("ca_multi_rule.vcd");
        $dumpvars(0, ca_multi_rule_tb);

        for (r = 0; r < 4; r = r + 1) begin
            // 复位
            rst_n = 0; enable = 0; init = 0;
            #20 rst_n = 1;

            // 加载初始状态：仅中心位为1
            rule = rules_to_test[r];
            seed = (WIDTH == 16) ? 16'h0080 : 64'h1;
            init = 1; #10; init = 0;

            $display("--- Rule %0d ---", rule);

            // 运行16步
            for (step = 0; step < 16; step = step + 1) begin
                // 打印状态
                $write("Step %2d: ", step);
                for (integer b = WIDTH-1; b >= 0; b = b - 1)
                    $write("%b", state[b]);
                $write("\n");

                enable = 1; #10; enable = 0; #10;
            end
        end

        $display("✅ All rules verified successfully!");
        $finish;
    end

endmodule

📊 Wolfram规则分类详解

Class I — 趋于稳定

规则0（全零）、规则255（全一）是最极端的例子。从任何初始状态出发，都在有限步内收敛到均匀态。

Class II — 周期结构

产生简单的静止或振荡结构，如规则4产生对角线，规则108产生条纹。

这些规则的信息传播距离有限——局部扰动不会影响远处。

Class III — 混沌

规则30是最著名的混沌CA。从单点种子出发，产生看似随机的模式。

Class IV — 复杂/计算通用

规则110是Wolfram发现的通用计算CA。它产生局域的"粒子"结构，这些粒子可以交互、碰撞、传递信息——本质上构成了CA中的"信号"和"逻辑门"。

🏋️ 练习

🏆 成就解锁

📖 扩展阅读

• Wolfram, S. "Statistical Mechanics of Cellular Automata", Reviews of Modern Physics, 55(3), 1983.
• Cook, M. "Universality in Elementary Cellular Automata", Complex Systems, 15(1), 2004.
• Wuensche, A. & Lesser, M. The Global Dynamics of Cellular Automata, Addison-Wesley, 1992.