📖 第3课：规则30与随机性

规则30 伪随机数 密码学 PRNG硬件

🎯 本课目标

深入分析规则30的混沌行为，理解确定性系统如何产生伪随机序列，并实现一个基于规则30的硬件伪随机数生成器（PRNG）。

🌀 规则30的神奇特性

规则30（LUT = 00011110）是Wolfram在1984年发现的"最简单的混沌系统"。它的行为令人震惊：

• 规则完全确定——给定相同输入，输出永远相同
• 但从单点种子出发，产生的中心列序列通过了所有标准随机性统计测试
• 左半部分呈现明显的三角形规律，右半部分却完全混沌

规则30的左右不对称性

观察规则30的演化图案，你会发现：

• 左侧：呈现规则的三角形结构（信息从右向左传播受限）
• 右侧：完全混沌，无法预测

🎲 规则30作为PRNG

Wolfram在1985年提出用规则30的中心列作为伪随机数序列。具体方法：

⚡ 规则30 PRNG的Verilog实现

// ============================================================================
// prng_rule30.v - 基于规则30的硬件伪随机数生成器
// 从中心列提取随机位，支持多位并行输出
// ============================================================================
module prng_rule30 #(
    parameter WIDTH     = 64,      // CA网格宽度（建议≥32）
    parameter OUT_WIDTH = 32       // 随机数输出位宽
)(
    input  wire                  clk,
    input  wire                  rst_n,
    input  wire                  enable,      // 使能
    input  wire                  init,        // 初始化
    input  wire [WIDTH-1:0]      seed,        // 初始种子
    output wire [OUT_WIDTH-1:0]  random_out,  // 随机数输出
    output wire                  valid,       // 输出有效
    output wire [WIDTH-1:0]      state_debug  // 调试：当前CA状态
);

    // ---- CA状态寄存器 ----
    reg [WIDTH-1:0] curr;
    reg [WIDTH-1:0] nxt;

    // ---- 规则30: f(L,C,R) = L XOR (C OR R) ----
    // 优化实现：无需8:1 MUX，直接用布尔逻辑
    wire left_ext  = curr[WIDTH-1]; // 环形：左边界的左邻居
    wire right_ext = curr[0];       // 环形：右边界的右邻居

    genvar i;
    generate
        for (i = 0; i < WIDTH; i = i + 1) begin : gen_rule30
            wire L = (i == 0)        ? left_ext  : curr[i-1];
            wire C = curr[i];
            wire R = (i == WIDTH-1)  ? right_ext : curr[i+1];
            assign nxt[i] = L ^ (C | R);
        end
    endgenerate

    // ---- 状态更新 ----
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            curr <= {WIDTH{1'b0}};
        else if (init)
            curr <= seed;
        else if (enable)
            curr <= nxt;
    end

    // ---- 随机位提取 ----
    // 方法1：取中心列连续OUT_WIDTH步的值（需要OUT_WIDTH步才能输出一个数）
    // 方法2：从当前状态的多列并行提取（1步即可输出）

    // 这里采用方法2：从网格中均匀采样OUT_WIDTH个位
    // 采样间隔 = WIDTH / OUT_WIDTH
    localparam SAMPLE_GAP = WIDTH / OUT_WIDTH;

    genvar j;
    generate
        for (j = 0; j < OUT_WIDTH; j = j + 1) begin : gen_sample
            // 从右半部分采样（右半部分更混沌）
            localparam IDX = WIDTH/2 + (j * SAMPLE_GAP);
            // 确保索引在范围内
            if (IDX < WIDTH)
                assign random_out[j] = curr[IDX];
            else
                assign random_out[j] = curr[WIDTH-1];
        end
    endgenerate

    assign valid       = enable;
    assign state_debug = curr;

endmodule

多位并行输出PRNG

对于需要高速随机数的应用（如蒙特卡洛仿真），我们可以利用规则30的列独立性，从不同列同时提取随机位：

// ============================================================================
// prng_rule30_parallel.v - 高速并行规则30 PRNG
// 每时钟周期输出一个完整的随机数
// 使用多个CA列同时提取，通过列间延迟保证独立性
// ============================================================================
module prng_rule30_parallel #(
    parameter WIDTH = 128,           // 加宽CA以提供更多独立列
    parameter OUT_W = 32             // 输出位宽
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              reseed,        // 重新播种
    input  wire [WIDTH-1:0]  new_seed,
    output wire [OUT_W-1:0]  rand_data,     // 随机数据
    output wire              rand_valid     // 数据有效
);

    // ---- CA阵列 ----
    reg [WIDTH-1:0] ca_state;
    wire [WIDTH-1:0] ca_next;

    // 规则30组合逻辑
    genvar i;
    generate
        for (i = 0; i < WIDTH; i = i + 1) begin : gen_ca
            wire L = (i == 0)        ? ca_state[WIDTH-1] : ca_state[i-1];
            wire C = ca_state[i];
            wire R = (i == WIDTH-1)  ? ca_state[0]       : ca_state[i+1];
            assign ca_next[i] = L ^ (C | R);
        end
    endgenerate

    // ---- 采样逻辑 ----
    // 从CA状态的右半部分均匀采样OUT_W个位
    // 右半部分混沌度更高，随机性更好
    localparam HALF = WIDTH / 2;
    localparam GAP  = HALF / OUT_W;

    genvar k;
    generate
        for (k = 0; k < OUT_W; k = k + 1) begin : gen_out
            assign rand_data[k] = ca_state[HALF + k * GAP];
        end
    endgenerate

    // ---- 状态更新 ----
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            ca_state <= {WIDTH{1'b0}};
        else if (reseed)
            ca_state <= new_seed;
        else
            ca_state <= ca_next;  // 每周期自动步进
    end

    assign rand_valid = ~reseed;  // 非重新播种时输出有效

endmodule

📐 规则30的数学分析

李雅普诺夫指数与敏感性

周期长度分析

与LFSR的比较

🧪 统计验证Testbench

// ============================================================================
// prng_rule30_stat_tb.v - 规则30 PRNG统计测试
// 验证输出序列的频率分布和自相关性
// ============================================================================
\`timescale 1ns/1ps

module prng_rule30_stat_tb;

    parameter WIDTH = 64;
    parameter OUT_W = 8;
    parameter SAMPLES = 10000;  // 采样数

    reg  clk, rst_n, enable, init;
    reg  [WIDTH-1:0] seed;
    wire [OUT_W-1:0] rand_out;
    wire valid;
    wire [WIDTH-1:0] debug;

    prng_rule30 #(.WIDTH(WIDTH), .OUT_WIDTH(OUT_W)) dut (
        .clk(clk), .rst_n(rst_n), .enable(enable),
        .init(init), .seed(seed),
        .random_out(rand_out), .valid(valid), .state_debug(debug)
    );

    initial clk = 0;
    always #5 clk = ~clk;

    // 统计计数器
    integer counts [0:255];  // 对8位输出的256种值计数
    integer total;
    real    chi_square;
    real    expected;

    integer n;

    initial begin
        // 初始化计数器
        for (n = 0; n < 256; n = n + 1) counts[n] = 0;
        total = 0;

        $dumpfile("prng_rule30.vcd");
        $dumpvars(0, prng_rule30_stat_tb);

        // 复位
        rst_n = 0; enable = 0; init = 0;
        #50 rst_n = 1;

        // 初始化：中心位为1
        seed = 64'h1 << 31;
        init = 1; #10; init = 0;

        // 采集样本
        enable = 1;
        for (n = 0; n < SAMPLES; n = n + 1) begin
            @(posedge clk);
            counts[rand_out] = counts[rand_out] + 1;
            total = total + 1;
        end

        // 计算卡方统计量
        expected = real'(total) / 256.0;
        chi_square = 0.0;
        for (n = 0; n < 256; n = n + 1) begin
            chi_square = chi_square +
                ((real'(counts[n]) - expected) *
                 (real'(counts[n]) - expected)) / expected;
        end

        $display("=== Rule 30 PRNG Statistics ===");
        $display("Samples: %0d", total);
        $display("Expected per bin: %0.1f", expected);
        $display("Chi-square: %0.2f", chi_square);
        $display("Chi-square critical (df=255, p=0.05): 293.25");
        if (chi_square < 293.25)
            $display("✅ PASSED: Distribution appears uniform");
        else
            $display("❌ FAILED: Distribution may be non-uniform");

        $finish;
    end

endmodule

🏋️ 练习

🏆 成就解锁

📖 扩展阅读

• Wolfram, S. "Random Sequence Generation by Cellular Automata", Advances in Applied Mathematics, 7(2), 1986.
• Martin, O., Odlyzko, A. & Wolfram, S. "Algebraic Properties of Cellular Automata", Communications in Mathematical Physics, 93, 1984.
• Meier, W. & Staffelbach, O. "Analysis of Pseudo Random Sequences Generated by Cellular Automata", Advances in Cryptology - EUROCRYPT'91, 1991.