1. 伪随机比特序列到底是什么先别被“Pseudorandom Bit Sequences”这个英文名字唬住它拆开其实就两件事一串只有 0 和 1 的序列以及“看起来随机、实际上由确定规则产生”这个特性。伪随机比特序列说白了就是用一个确定性的算法生成一串统计性质上近似真随机的比特流。它广泛应用于通信、密码学、仿真测试、扩频系统、蒙特卡洛模拟等领域几乎所有需要“随机”但又不方便依赖物理随机源的场景都会用到它。我最早接触这个概念是在做通信基带仿真的时候。当时需要生成几百万个随机比特去模拟信道噪声和误码率系统自带的随机数函数在长周期统计上总是有点偏后来换成伪随机比特序列生成器问题一下就解决了。这里的关键不是“随机”本身而是“可复现、可调节、统计均匀”这三个特性。为什么需要伪随机而不是真随机原因很实际真随机源比如硬件噪声、量子过程速度慢、成本高而且不可复现。你在测试一个系统时如果每次输入的真随机序列都不一样那出了问题根本没办法定位是代码逻辑错了还是这次随机序列运气不好。伪随机序列则不同同一个种子Seed永远产生同一个序列这意味着测试可复现、错误可追踪这是工程上极其宝贵的性质。适合学习这篇文章的人主要是做通信算法验证、FPGA逻辑开发、嵌入式系统、密码学基础研究或者单纯对随机数生成原理感兴趣的开发者。不需要太深的数学基础但最好有一个“序列长度足够大时统计特性会趋近理论值”的直觉。接下来我会从设计思路、核心生成方法、具体实操、常见问题四个维度把这个话题讲透。2. 内容整体设计与思路拆解2.1 从需求到方案为什么不是“随便写个 rand()”很多人的第一反应是生成随机比特还不简单调一下标准库的随机函数取模二不就行了吗这个思路在应用层偶尔能凑合但在需要严格统计特性的场合完全不可靠。标准库的线性同余生成器LCG虽然速度快但低比特位的随机性很差而且周期很短有些实现只有 2^31 甚至更短。如果你把它当成伪随机比特序列来用频谱上会有明显的周期性尖峰在扩频通信或测试场景中会直接导致结果失真。另外标准库随机函数在不同平台上的实现差异很大你在一台机器上跑出的序列换台机器就完全不一样。这对可复现性要求高的工程场景是灾难。所以业界更倾向于使用有明确数学结构、周期可计算、统计特性经过充分检验的生成器比如 m 序列、Gold 序列、Kasami 序列或者是现代通用的 PRNG 算法如 xorshift、MT19937、PCG。我个人的习惯是如果只是做蒙特卡洛仿真PCG 或 xorshift 就够用了如果是做通信系统的同步、扩频、加扰那一定要用有理论保证的 m 序列或 Gold 序列。原因在于通信系统不仅要求“统计上随机”还要求“相关特性可控”——也就是自相关函数尖锐、互相关函数小。这个需求是普通 PRNG 无法满足的必须从序列设计层面去解决。2.2 核心指标周期、线性复杂度、相关性评价一个伪随机比特序列好不好不能只看“看起来乱不乱”。工程上有几个硬指标周期长度是最基本的。周期太短意味着序列很快开始重复在通信里会导致扩频增益失效在测试里会导致隐藏的相关性。m 序列的周期是 2^n - 1其中 n 是移位寄存器级数n31 时周期大约是 21 亿已经足够覆盖绝大多数场景。线性复杂度衡量的是“用线性反馈移位寄存器LFSR去复现这个序列最少需要多少级”。复杂度越高说明序列越难被预测密码学上越安全。普通 m 序列的线性复杂度就是它的级数 n这个值其实不高所以 m 序列不适合直接作为密钥流使用但在加扰和扩频场景下完全够用。自相关和互相关特性决定了序列在同步和分址方面的性能。m 序列的自相关函数是二值的在同步点上有一个尖锐的峰值其他位置全部是“-1/周期”的小值这让接收端能非常准确地对齐时间。Gold 序列则由两个优选 m 序列组合而成互相关特性受控适合 CDMA 系统里区分不同用户。还有一个很容易被忽略的指标游程分布。理想随机序列里长度为 1 的游程应占 1/2长度为 2 的占 1/4长度为 3 的占 1/8依此类推。m 序列精确满足这个分布这也是它被称为“伪随机”而非“纯随机”的原因——它在所有可测的统计维度上都逼近理想值但生成规则又是完全确定的。2.3 方案选型对比LFSR、Gold 序列与现代 PRNG既然要选型我们就做个清楚对比。这里我把三类常用方案放在一起看方便你根据场景直接挑。方案类型典型算法周期线性复杂度典型应用场景实现成本m 序列LFSR反馈多项式 x^n ... 12^n - 1n加扰、同步、扩频极低仅需移位寄存器Gold 序列两个优选 m 序列模二加2^n - 1约 2nCDMA 分址、多用户系统低需两组 LFSR现代 PRNGxorshift128, PCG2^128 或更高不固定仿真、测试、通用随机数低仅需位运算m 序列的优势是简单、可解析你可以精确知道它的周期和相关特性缺点是单个 m 序列的互相关特性不可控而且同一周期内的序列数量有限只有 φ(2^n - 1)/n 个本原多项式。Gold 序列的作用就是解决互相关问题它把两个结构互异的 m 序列异或起来得到的序列族数量更多且任意两个序列之间的互相关值有严格上限。这在多用户通信里特别关键因为用户之间的干扰直接取决于互相关值的大小。如果你做的不是通信系统只是想在软件里生成大量随机比特做测试那 LFSR 的方案就有点“杀鸡用牛刀”了。直接用 xorshift 或 PCG周期更长速度更快代码量还更少。但要记住通用 PRNG 生成的是 64 位或 32 位整数你可以取其中的某一位作为比特流也可以把整个整数直接当比特块用。取低位比特的话要特别小心——某些老式 LCG 的低位周期很短随机性极差这也是我不推荐用 LCG 做比特序列的原因。3. 核心细节解析与实操要点3.1 LFSR 的工作原理与本原多项式LFSR 是伪随机比特序列最经典的生成结构。它的核心是一个移位寄存器每个时钟周期把寄存器里的某些位做异或运算反馈回最低位同时最高位输出。这个“某些位”的选择由反馈多项式决定。比如生成 m 序列时反馈多项式必须是一个 n 次本原多项式这样周期才能达到最大值 2^n - 1。举个例子n4 时本原多项式可以取 x^4 x 1对应的反馈抽头是第 4 位和第 1 位从 1 开始计数传统上反馈抽头包括常数项。在 FPGA 里写起来就是reg [3:0] lfsr; wire feedback lfsr[3] ^ lfsr[0]; always (posedge clk or posedge rst) begin if (rst) lfsr 4h1; // 初始值不能为全 0 else lfsr {lfsr[2:0], feedback}; end这里有个关键陷阱初始值不能为全 0。因为 LFSR 是线性结构如果寄存器全部为 0异或结果恒为 0序列就卡死在全 0 状态再也出不去了。所以任何 LFSR 实现都必须保证初值非零。另外反馈抽头选错了序列周期就会变短甚至可能出现退化。你可以查表获得各阶次的本原多项式也可以写一个穷举程序去验证多项式是否为本原。C 语言实现 m 序列也很简单用移位和掩码即可uint32_t lfsr 0xACE1u; // 初值非零 uint32_t bit; int i; for (i 0; i 1000; i) { bit ((lfsr 0) ^ (lfsr 2) ^ (lfsr 3) ^ (lfsr 5)) 1u; lfsr (lfsr 1) | (bit 15); printf(%u, bit); }注意这里反馈多项式的映射方式和 FPGA 版本不同因为寄存器方向和位序定义不同但原理完全一致。你在实现前先确定好“哪个位是输出位、哪个位是反馈位”避免后面调试时越绕越晕。3.2 Gold 序列的构造方法与优选对选择Gold 序列不是简单随便拿两个 m 序列就能凑出来的。它要求这两个 m 序列构成“优选对”也就是它们的互相关函数值必须满足特定条件通常要求互相关三值分别为 -1、-t(n)、t(n)-2其中 t(n)2^((n1)/2)1n 为奇数。只有满足这个条件生成的 Gold 序列族才具备可控的互相关上界。具体构造方法是选定一个 n 级本原多项式生成第一个 m 序列 a然后找到另一个本原多项式生成 m 序列 b并且保证 b 是对 a 的采样序列采样间隔与 n 互质且满足优选对条件。将 a 和 b 逐位异或得到一个新的序列再把 b 循环移位 0 到 2^n - 2 位逐个与 a 异或就能得到一组包含 2^n 1 个序列的 Gold 序列族。实现时我建议先做一个 MATLAB 或 Python 脚本验证优选对关系确认互相关值符合理论值再移植到硬件上。盲选两个本原多项式然后直接异或大概率生成的序列族互相关特性很差在多用户环境里会带来明显的互干扰。Python 里有一个现成思路用 numpy 生成 LFSR 序列再异或验证互相关峰值代码不复杂import numpy as np def lfsr_sequence(taps, init, length): state init ((1 max(taps)) - 1) seq [] for _ in range(length): seq.append(state 1) fb 0 for t in taps: fb ^ (state (t - 1)) 1 state (state 1) | (fb (max(taps) - 1)) return np.array(seq)这里 taps 列表要按你选定的本原多项式来填。验证互相关时直接把两个序列做循环互相关取峰值看是否等于理论值。这个过程我每次做新序列族都会跑一遍耗时极短但能拦下很多低级错误。3.3 在 FPGA 与嵌入式平台中的实现要点FPGA 实现伪随机比特序列时第一优先级是时序约束。LFSR 本质上是一个简单的移位寄存器链没有乘法、除法这种复杂逻辑所以跑高频很容易但要注意反馈路径上异或门的级联延迟。抽头数量过多时异或链会变长可能导致时序违例。解决办法是给异或链插入流水线寄存器但插入寄存器会改变反馈时序你需要把“一步计算”改成“多拍流水”并保证输出序列的比特顺序不变。嵌入式平台上的实现则要关注两个问题一是随机数生成是否在中断上下文里执行二是是否需要抗故障注入。如果生成序列涉及安全相关功能比如密钥派生建议用芯片自带的硬件随机数生成器TRNG产出的种子去初始化软件 PRNG这样既有真随机熵源又有确定性的生成过程。另一个实操细节在软件中逐位生成太慢。如果你需要大量比特流应该一次生成一个 32 位或 64 位整数然后直接按位取用。以 xorshift 为例生成一个 64 位随机数只需要三次异或和三次移位比逐位调用 LFSR 快几十倍。但如果你必须用 LFSR 的比特输出去对接硬件接口那就没办法只能逐位生成此时可以先把 LFSR 输出缓存到一个 FIFO再由接口按位读取这样能减少 CPU 的中断频率。我做过一个 20 MHz 码率的扩频系统最开始用软件逐位生成 Gold 序列CPU 占用率高达 40%。后来改成 FPGA 硬件生成CPU 占用率直接归零。这个案例说明方案选型要结合系统整体架构不要一味追求纯软件或纯硬件该用硬件的场景就果断用硬件。4. 实操过程与核心环节实现4.1 从零生成一组可复验的 m 序列我们以 n7 为例完整走一遍生成流程。n7 时 m 序列周期为 127非常适合做实验验证。选一个常用的本原多项式 x^7 x^6 1对应反馈抽头是第 7 位和第 6 位。在 Python 里写一个通用函数输入多项式系数和初值输出序列。def lfsr_mseq(taps, init_state, length): taps sorted(taps, reverseTrue) n max(taps) state init_state ((1 n) - 1) if state 0: raise ValueError(init_state must be non-zero) output [] for _ in range(length): output.append((state (n - 1)) 1) fb 0 for t in taps: fb ^ (state (t - 1)) 1 state ((state 1) | fb) ((1 n) - 1) return output seq lfsr_mseq([7, 6], 0b1010101, 127) # 验证周期检查前 127 位与后 127 位是否一致 print(seq seq[:127])这段代码里去掉了初值全 0 的隐患并做了长度校验。生成后要做三个验证第一周期是否为 127第二1 的个数是否为 64因为 m 序列中 1 比 0 多一个第三游程分布是否符合 1/2、1/4 的理论比例。这三个检查都过关基本可以确认多项式选对了。周期验证还有一种更工程化的方式把序列重复循环与自身做相关运算观察峰值是否出现在偏移量为 0 的位置。用 Python 的 numpy 做循环互相关峰值应当极为显著。如果你的序列周期不对互相关图里会出现多个等高峰值一眼就能看出来。4.2 生成 Gold 序列族并验证互相关在 m 序列基础上进一步生成 Gold 序列。n7 时先找到与 x^7 x^6 1 构成优选对的另一个本原多项式。查表可知 x^7 x^3 1 是一个常用优选对伙伴。用上面的 lfsr_mseq 函数生成两个基础 m 序列然后逐位异或seq_a lfsr_mseq([7, 6], 0b1010101, 127) seq_b lfsr_mseq([7, 3], 0b1010101, 127) def xor_sequences(a, b): return [x ^ y for x, y in zip(a, b)] gold_base xor_sequences(seq_a, seq_b) print(len(gold_base), gold_base[:20])要生成完整的 Gold 序列族需要对 seq_b 做循环移位每次移位后与 seq_a 异或共获得 2^7 1 129 条序列包括两条基础 m 序列本身。每一条序列的周期都是 127任意两条之间的互相关值都限制在某个理论上界之内。验证互相关时自己写循环互相关函数即可注意避免直接用 O(n^2) 的暴力算法n127 无所谓但如果你做到 n31周期 21 亿就必须用 FFT 计算互相关。这里给出适用于中小周期的实现def cyclic_correlation(a, b): n len(a) a_arr np.array(a, dtypefloat) b_arr np.array(b, dtypefloat) # 用 FFT 加速循环互相关 a_fft np.fft.fft(a_arr) b_fft np.fft.fft(b_arr) corr np.fft.ifft(a_fft * np.conj(b_fft)).real return np.rint(corr).astype(int)跑完之后把互相关峰值打印出来对比理论值。如果互相关峰值超过理论值说明你的优选对选错了需要换一个本原多项式重新测试。我当年做这个实验时一开始随手选了两个多项式生成 Gold 序列互相关峰值比理论值高出 5 倍后来换成优选对才正常。这个过程千万别跳过。4.3 用 FPGA 实现高速 LFSR 并实测波形软件验证通过后我们再把它落到 FPGA 上。以 Xilinx FPGA 为例用 Verilog 写一个带使能信号的 LFSR 模块并将输出接到测试引脚通过示波器或逻辑分析仪观察序列波形。module lfsr7 #(parameter N 7) ( input wire clk, input wire rst, input wire en, output wire data_out ); reg [N-1:0] shift_reg; wire feedback; assign feedback shift_reg[6] ^ shift_reg[5]; // x^7 x^6 1 always (posedge clk or posedge rst) begin if (rst) shift_reg 7b1010101; // 非零初值 else if (en) shift_reg {shift_reg[N-2:0], feedback}; end assign data_out shift_reg[N-1]; endmodule这段代码有几个细节要注意。rst 采用同步复位还是异步复位需要根据项目规范决定但初值必须非零。en 信号用于控制序列推进如果不需要节流可以一直拉高。data_out 取最高位作为输出这是输出序列的标准方式当然你也可以取任意一位但不同位的输出时刻有相位差这在某些场景下会影响时序。上板调试时建议先把时钟分频到 1 Hz用 LED 显示 data_out肉眼可以直接看到 0101 序列的节奏验证初值和反馈是否正确。然后逐步提高时钟频率到 100 MHz 以上再观察。如果出现波形毛刺用示波器检查时序余量和信号完整性多半是 PCB 走线或逻辑分析仪探头的问题而不是 LFSR 逻辑本身的问题。4.4 统计测试工具NIST SP 800-22 跑一遍才算数生成出来的序列到底能不能用不能凭感觉要用统计测试工具去验证。NIST SP 800-22 是一套国际上广泛使用的随机数检验标准包含频数检验、游程检验、块内频数检验、二元矩阵秩检验、离散傅里叶变换检验等 15 个测试项。虽然不是每个场景都需要全套跑完但这是证明序列质量最有力的工具。最简化的使用方式是准备一个只含 0 和 1 的文本文件或二进制文件安装 nist-sts 工具后配置测试参数指定比特流文件运行即可。测试结束后会生成 report.txt每个测试项都会给出 P-value。一般规则是 P-value 大于 0.01 就算通过但如果多个测试项同时接近 0.01 甚至低于 0.01就要警惕序列的结构性问题。我实测过 m 序列和 xorshift 序列结论是m 序列在频数检验和游程检验上表现极好但在离散傅里叶变换检验上有时会显示轻微的非随机性这是因为 LFSR 结构本质上是线性的频谱上会留下一些可检测的痕迹。如果你做的是安全相关用途建议不要直接用裸 m 序列而是用现代 PRNG 或加密算法如 AES-CTR 模式来消除线性结构。5. 常见问题与排查技巧实录5.1 序列周期不对卡在某个短循环里这是个高频问题十次里有八次是因为反馈多项式选错还有两次是因为初值非零但反馈抽头接错。排查方法很简单生成足够长的序列比对开头与末尾是否重复。比如 n7 的 m 序列周期是 127那你生成 1000 位检查第 1 到第 127 位是否与第 128 到第 254 位完全相同。如果完全相同说明周期正常如果提前出现重复说明周期为某个更小的值多项式不是本原的。还有一种情况是初值恰好落入了某个退化状态。LFSR 理论上只有一个陷阱状态——全 0但在某些反馈配置下还会出现多个短周期环。解决方法是避免选取明显对称为 0 或接近全 0 的初值或者在初始化时检查状态是否为 0 并强制赋一个非零值。我在代码里加了初值校验一劳永逸。5.2 硬件上输出的序列和软件模拟对不上这个问题往往出在字节序和位序上。软件里你可能是从低位到高位输出而硬件里数据线是高位移出两边拼出来的序列完全相反。另外FPGA 代码里如果用了不同位序的寄存器初始化也会导致同样的多项式产生不同序列。排查思路是先固定一个已知序列让软件和硬件都输出前 32 位逐 bit 比对定位从哪一位开始不一致然后调整输出顺序。还有一种情况是时钟沿采样问题。当你用逻辑分析仪抓 data_out 时每次时钟上升沿后数据才更新如果你的采样时刻刚好落在数据跳变沿上会抓到毛刺。解决办法是把 data_out 打一拍再输出reg data_out_reg; always (posedge clk or posedge rst) begin if (rst) data_out_reg 1b0; else data_out_reg shift_reg[N-1]; end assign data_out data_out_reg;这个打拍操作会让输出延迟一个时钟周期但对序列本身的周期和统计特性没有任何影响却能让下游逻辑的时序裕量大很多。这是 FPGA 工程里非常实用的小技巧。5.3 统计测试不过P-value 大面积偏低如果 NIST 测试结果显示多项 P-value 都小于 0.01先别急着怀疑算法检查三个地方。第一测试文件的比特数是否足够。NIST 每个测试项都要求至少 100 万比特如果你只给几千个比特测试结果没有统计意义。第二序列是否发生了截断对齐问题。如果你生成 127 位 m 序列后直接拼接 100 万次中间没有清空状态那拼接处会产生一个不自然的大跳变。正确的做法是把循环模式理解清楚而不是简单拼接。第三是否把 0 和 1 颠倒了。NIST 工具要求 0 和 1 的表示与文件内容一致如果你的文件里存的是 ASCII 字符 ‘0’ 和 ‘1’而工具按二进制模式解析就会全乱。我之前踩过一个大坑用 Python 把序列存成字符串每行 64 位结果 NIST 工具按二进制读入把换行符也当成了比特整体统计全部偏掉。后来改用 struct.pack 直接写入二进制比特问题解决。记住格式问题是统计测试里最常见的坑。5.4 多路序列互相干扰自相关峰不明显这种情况主要出现在直接用多个独立 LFSR 生成不同用户的码序列时。虽然每个单独的 m 序列自相关没问题但任意两个独立 m 序列之间的互相关可能是不可控的某些偏移下可能出现较大的互相关峰值这在多用户系统里就表现为干扰。解决办法就是使用 Gold 序列族因为 Gold 序列的互相关值是受控的。生成时必须使用优选对且每个用户的序列应当是同一个 Gold 族里的不同成员而不是随意用两个独立 LFSR。我曾经参与过一个多用户系统的仿真最初用户 1 用 m 序列 A用户 2 用 m 序列 B两者互相关峰值最高达到周期值的 20%换成 Gold 序列后降到了理论下界以内系统误码率立刻改善。5.5 快速排查速查表现象可能原因快速验证方法解决方案序列提前重复反馈多项式非本原检查前 2 个周期是否一致换成查表得到的本原多项式输出全是 0LFSR 初值为全 0检查初始化代码强制初值非零软件与硬件序列不一致位序或字节序不匹配比对前 32 位输出统一输出位序硬件波形有毛刺数据跳变沿与采样沿对齐示波器观察时序data_out 打拍输出统计测试 P-value 偏低输入格式错误或比特数不足检查文件大小和解析方式用二进制格式存储保证 100 万比特以上多路序列互干扰未使用优选对计算互相关峰值改用 Gold 序列族6. 后续扩展方向与个人实操体会写完这套伪随机比特序列的完整流程我最大的感受是这东西入门简单做深了全是细节。很多人觉得 LFSR 就是一个移位加异或没什么技术含量可真到工程里多项式选择、初值设置、位序定义、统计验证每个环节都能埋雷。尤其当你从软件仿真往 FPGA 移植的时候同一个算法在两边的表现差异往往不是算法本身的问题而是你对“位”的理解还不够精确。我没有用标准库的随机函数直接生成比特流原因是反复讲过的可复现性和统计特性都不够。如果你只是做个临时脚本那没问题但只要你需要在多台设备上复现同一个测试序列或者需要向别人证明你的序列具备良好的随机性就必须走正规的伪随机序列生成路线。真正把这个技术用到极致的人不会只停留在生成阶段。他们会在生成之后加上完整的统计验证流程甚至进一步做差分攻击分析、相关性分析、频谱分析。伪随机比特序列这个领域的魅力就在于它既是数学问题又是工程问题还是系统设计问题。你在通信系统里优化的每一个自相关峰值放到密码学场景里就是抗攻击能力的体现你在 FPGA 里节省的每一个时钟周期放在大规模仿真里就是整体算力的提升。我个人建议想深入这块的朋友按这个顺序进阶先手写 LFSR 并验证周期和游程分布再做 Gold 序列并验证互相关然后用 NIST 工具标准化验证自己的序列最后找一个真实场景比如自适应均衡器、扩频收发机、加扰解扰器把序列用进去。整个过程走一遍你对“伪随机”这三个字的理解会远超那些只会调库的人。最后分享一个实操小技巧在生成任何伪随机比特序列前先写一个 20 行的验证脚本把周期、游程、相关性三件事测一遍。这个脚本会陪伴你很久每次换多项式、换初值、换参数都先跑它确认没问题再往下做。我自己的这个脚本已经用了快三年帮我在各种项目里拦截了无数低级错误比事后调试省时间多了。伪随机比特序列未必是系统里最亮眼的部分但它往往是决定系统能不能稳定工作的基石。把这块做扎实了你的信号处理、通信、密码学相关项目都会稳一大截。