📖 第8课：高寿命规则

HighLife B36/S23 规则变体自复制

🔬 超越Conway——规则变体的世界

Conway生命游戏使用B3/S23规则，但Moore邻域的2状态CA有极其丰富的规则空间。通过修改"出生"和"存活"条件，我们可以产生截然不同的行为——从自复制器到爆炸性增长到黑白对称的奇异世界。

规则记法：B_born/S_survive

B后面列出"出生"所需的邻居数，S后面列出"存活"所需的邻居数

总规则数 = 2^9 × 2^9 = 2^18 = 262,144（9位born + 9位survive，每位对应0-8个邻居）

但实际上很多规则是等价的（通过反射和取反变换），独立规则约 ~88,000 种

HighLife: B36/S23

HighLife与Conway生命游戏的唯一区别：死元胞在6个活邻居时也会"出生"。这个微小改变产生了巨大的行为差异——HighLife中存在自复制器！

HighLife的复制器：

一个简单的初始模式可以产生自身的多个副本！初始：特定的5元胞排列 → 自发复制成2个、4个、8个...

复制器的工作原理：当6个邻居可以"出生"时，某些结构会向两侧延伸，形成镜像副本

这在B3/S23中不可能——3个邻居的出生条件太严格

Day & Night: B3678/S34678

这个规则具有奇妙的黑白互换对称性——将所有活/死元胞互换，演化模式等价。

对称性证明：

如果 born = {3,6,7,8}，survive = {3,4,6,7,8}

那么 NOT-born = {0,1,2,4,5}，NOT-survive = {0,1,2,5,9}

在一个9-邻居的系统中，如果某元胞有k个活邻居，就有9-k个死邻居

当活变死、死变活时，新的邻居计数变为9-k

新的born条件：k' = 9-k ∈ {3,6,7,8} ⟺ k ∈ {1,2,3,6}

只有当 born 和 survive 的取补集恰好对应 swap 条件时，对称性成立

规则	名称	特征	应用
B3/S23	Conway Life	经典，复杂涌现	通用计算
B36/S23	HighLife	自复制器	人工生命研究
B3678/S34678	Day & Night	黑白对称	对称性研究
B1357/S1357	Replicator	一切模式自复制	自复制理论
B2/S	Seeds	爆炸性增长	图案生成
B3/S012345678	Life w/o Death	只生不死	分形生长
B368/S245	Morley/Move	菱形图案	图案设计
B378/S235678	Stains	墨迹效应	模式识别
B45678/S2345	Walled Cities	形成"城墙"	结构生成
B378/S235678	Anneal	退火行为	优化算法

⚡ 参数化生命游戏引擎

支持任意B/S规则的生命游戏引擎

// ============================================================================
// life_variable_rule.v - 支持任意Born/Survive规则的生命游戏
// 规则通过9位寄存器配置：born[0:8] + survive[0:8]
// ============================================================================
module life_variable_rule #(
    parameter WIDTH  = 64,
    parameter HEIGHT = 64
)(
    input  wire                     clk,
    input  wire                     rst_n,
    input  wire                     enable,
    input  wire                     init,
    input  wire [WIDTH*HEIGHT-1:0]  seed,
    input  wire [8:0]               born,       // born[i]=1: i个邻居时出生
    input  wire [8:0]               survive,    // survive[i]=1: i个邻居时存活
    output wire [WIDTH*HEIGHT-1:0]  state,
    output wire [31:0]              generation,
    output wire [31:0]              population
);

    reg [WIDTH*HEIGHT-1:0] curr;
    wire [WIDTH*HEIGHT-1:0] nxt;

    genvar gx, gy;
    generate
        for (gy = 0; gy < HEIGHT; gy = gy + 1) begin : gen_row
            for (gx = 0; gx < WIDTH; gx = gx + 1) begin : gen_col
                localparam integer idx = gy * WIDTH + gx;
                localparam integer xm = (gx == 0) ? WIDTH-1 : gx-1;
                localparam integer xp = (gx == WIDTH-1) ? 0 : gx+1;
                localparam integer ym = (gy == 0) ? HEIGHT-1 : gy-1;
                localparam integer yp = (gy == HEIGHT-1) ? 0 : gy+1;

                wire [7:0] nb;
                assign nb[0] = curr[ym*WIDTH+xm];
                assign nb[1] = curr[ym*WIDTH+gx];
                assign nb[2] = curr[ym*WIDTH+xp];
                assign nb[3] = curr[gy*WIDTH+xm];
                assign nb[4] = curr[gy*WIDTH+xp];
                assign nb[5] = curr[yp*WIDTH+xm];
                assign nb[6] = curr[yp*WIDTH+gx];
                assign nb[7] = curr[yp*WIDTH+xp];

                wire [3:0] ncount = nb[0]+nb[1]+nb[2]+nb[3]+
                                    nb[4]+nb[5]+nb[6]+nb[7];
                wire self = curr[idx];
                assign nxt[idx] = self ? survive[ncount] : born[ncount];
            end
        end
    endgenerate

    reg [31:0] gen_reg;
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            curr    <= {WIDTH*HEIGHT{1'b0}};
            gen_reg <= 32'd0;
        end else if (init) begin
            curr    <= seed;
            gen_reg <= 32'd0;
        end else if (enable) begin
            curr    <= nxt;
            gen_reg <= gen_reg + 32'd1;
        end
    end

    assign state = curr;
    assign generation = gen_reg;

    integer p;
    reg [31:0] pop_reg;
    always @(*) begin
        pop_reg = 32'd0;
        for (p = 0; p < WIDTH*HEIGHT; p = p + 1)
            pop_reg = pop_reg + curr[p];
    end
    assign population = pop_reg;

endmodule

规则自动分类器

262,144种规则太多，无法逐一手动分析。我们可以设计一个硬件规则分类器：

规则行为分类器

// ============================================================================
// rule_classifier.v - 自动分类B/S规则的行为
// 运行N步后统计：种群变化、空间分布、周期检测
// ============================================================================
module rule_classifier #(
    parameter WIDTH  = 32,
    parameter HEIGHT = 32,
    parameter STEPS  = 256
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire [8:0]       born,
    input  wire [8:0]       survive,
    input  wire             start,
    output wire [2:0]       category,    // 0=稳定 1=振荡 2=混沌 3=复杂 4=消亡
    output wire [31:0]      period,      // 检测到的周期
    output wire             done
);

    // 实例化可变规则CA
    wire [WIDTH*HEIGHT-1:0] ca_state;
    wire [31:0] ca_gen;
    wire [31:0] ca_pop;
    wire ca_init, ca_en;

    life_variable_rule #(.WIDTH(WIDTH), .HEIGHT(HEIGHT)) ca (
        .clk(clk), .rst_n(rst_n), .enable(ca_en),
        .init(ca_init), .seed({(WIDTH*HEIGHT){1'b0}} | (1 << (WIDTH*HEIGHT/2))),
        .born(born), .survive(survive),
        .state(ca_state), .generation(ca_gen), .population(ca_pop)
    );

    // 种群历史缓冲（用于周期检测）
    reg [31:0] pop_history [0:STEPS-1];
    reg [31:0] step_cnt;
    reg        running;
    reg [2:0]  cat_reg;
    reg [31:0] per_reg;
    reg        done_reg;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            step_cnt <= 32'd0;
            running  <= 1'b0;
            cat_reg  <= 3'd0;
            per_reg  <= 32'd0;
            done_reg <= 1'b0;
        end else if (start && !running) begin
            step_cnt <= 32'd0;
            running  <= 1'b1;
            done_reg <= 1'b0;
        end else if (running) begin
            pop_history[step_cnt] <= ca_pop;

            if (step_cnt == STEPS - 1) begin
                running  <= 1'b0;
                done_reg <= 1'b1;

                // 简单分类逻辑
                if (ca_pop == 0)
                    cat_reg <= 3'd4;  // 消亡
                else if (ca_pop == pop_history[STEPS/2])
                    cat_reg <= 3'd0;  // 稳定
                else
                    cat_reg <= 3'd2;  // 其他（简化）
            end else begin
                step_cnt <= step_cnt + 32'd1;
            end
        end
    end

    assign category = cat_reg;
    assign period   = per_reg;
    assign done     = done_reg;

endmodule

🏋️ 练习

练习8.1：用life_variable_rule测试HighLife规则。初始配置设为已知的复制器种子，观察自复制过程。

练习8.2：编写规则扫描脚本，遍历所有2^18种B/S规则，对每种运行100步，按行为分类。哪些规则最"有趣"？

练习8.3：证明Day & Night规则的黑白互换对称性。提示：born和survive集合的取补是否满足对称条件？

练习8.4：实现B2/S(Seeds)规则的优化版本。分析其爆炸性增长给硬件设计带来的挑战（种群暴增→组合延迟增加）。

练习8.5（挑战）：在HighLife中构造一个"计算器"——利用自复制器传递信息，实现简单的算术运算。

🏆 成就解锁

🏅 规则探索者

你已超越Conway生命游戏，进入规则变体的广阔世界。参数化引擎让你可以探索任意B/S规则的行为。

✅ 实现参数化B/S规则引擎
✅ 了解HighLife的自复制器
✅ 掌握Day & Night的对称性
✅ 理解规则空间的规模和分类
✅ 实现规则行为自动分类器

🔧 工程实践指南

将CA从理论变为可运行的硬件系统需要解决许多工程细节。以下是基于实践经验的详细指南：

时钟域设计

CA系统通常需要多个时钟域：

clk_ca：CA计算时钟，100-200MHz
clk_vga：VGA像素时钟，25-165MHz
clk_uart：UART波特率时钟，115200Hz
clk_ddr：DDR内存接口时钟，200-400MHz

跨时钟域同步使用双触发器或异步FIFO

资源优化清单

优化项	方法	节省量
邻居计数器	增量更新替代全加法	~40% LUT
状态存储	BRAM替代分布式RAM	~60% FF
规则查找	硬编码XOR替代MUX	~75% LUT（XOR规则）
显示输出	行缓冲替代全帧缓冲	~50% BRAM
边界处理	环形替代固定（零开销）	0

调试技巧

CA系统的调试有其特殊性：

守恒律验证：粒子数守恒、动量守恒、能量守恒——每步检查
已知模式测试：用已知的经典图案（滑翔机、Sierpinski等）验证规则正确性
对偶验证：软件模拟和硬件实现对比，用相同输入产生相同输出
边界测试：特别注意边界条件——环形边界最容易出错
初始条件敏感：不同的初始种子可能暴露不同的bug

⚠️ 常见陷阱：

忘记双缓冲——读写同一状态导致部分元胞使用t+1值
环形边界索引错误——首尾元胞的邻居指向错误位置
定点数溢出——大网格的种群计数器可能溢出
跨时钟域未同步——导致亚稳态和随机错误
VGA时序违反——消隐期内输出数据导致显示异常

性能基准测试

为CA引擎建立性能基准：

关键性能指标：

SPS（Steps Per Second）：每秒完成的CA步数
PPS（Pixel Updates Per Second）：每秒更新的元胞数 = SPS × W × H
延迟：从输入变化到输出响应的时间
功耗：每百万元胞更新所需的能量

理论峰值PPS = f_clk × W × H（全并行）

实际PPS取决于架构——行缓冲约为理论值的1/H

◀ 第7课 📜 目录第9课 ▶

元胞自动机课程 · 从Conway到Langton到Lattice Gas