离散时间PRBS源

前言

在进行链路仿真中会经常遇到各种 PRBS7、PRBS13、SSPRQ 等码型。这些码型在仿真中通常用算法来生成，而非直接存储调用。针对 ADS 中的 PRBS 码型生成器 VtLFSR_DT，我们大致了解一下码型的生成原理与设置指标。

信源生成器

VtLFSR_DT 是一个信源生成器组件，全名是 Vt(Voltage source in time domain)、LFSR(Linear Feedback Shift Register)、DT(Discrete Time)。这是一个离散时间数字源，需要输入的主要参数为 Vlow、Vhigh、Rate、Delay、Taps 和 Seed。

Vlow、Vhigh、Rate、Delay 不需要多说，无非就是高低电平，符号率与时延，决定了输出序列的大小、速率和相位。

问题主要集中在 Taps 和 Seed，这俩是啥？

为了彻底搞清楚这俩到底是什么，我们得从一个最基本的数学概念开始讲起，伽罗瓦域

群论与伽罗瓦域

伽罗瓦域的概念源自于群论，想必大家都听说过法国数学家伽罗瓦的故事，在他还只有十几岁的时候，他就发现了 n 次多项式可以用根式解的充要条件，解决了长期困扰数学界的问题。可惜他二十岁决斗送死，天才陨落。

整个知识体系的逻辑链如下：

群论
 → 环
   → 域
     → 有限域 GF(2)
       → GF(2^n)
         → LFSR
           → PRBS
             → BCH/RS编码
               → CRC
                 → AES

PRBS 码生成器所在的逻辑区域是

1
2
3

GF(2^n)
 → LFSR
   → PRBS

本质就是在伽罗瓦域（Galois Field）进行的一系列数学操作。

群、环、域

普通实数世界能做加减乘除等操作，类比计算机里的类，除了包含所有的实数（类属性），还包含实数之间的运算规则（类方法）。元素本身不重要，元素之间允许的操作才重要。我们将数字先放一边，仅提取一套封闭运算规则加以研究，于是诞生了抽象代数。

群（Group）是最基础的结构（集合+规则），只要求一种运算，例如整数加法群：

$(\mathbb{Z},+)$

群需要满足：

封闭性
结合律
单位元
逆元

所谓封闭性，指的是该群元素之间进行内部运算规则之后生成的元素，依旧包含在该群之中。结合律代表运算规则的先后作用不影响生成结果，即路径无关。单位元则是集合中的一个特殊元素，它和其他元素运算时，对方保持不变，类似单位矩阵，例如加法群里的 $0\,(5+0=5)$ ，乘法群里的 $1\,(5\times 1=5)$ 。逆元和单位元有关，指的是集合中的每一个元素，都能找到另一个元素通过作用将它抵消回单位元，例如加法群里 5 的逆元是 -5，因为 $5+(-5)=0$ 。

进一步的，讨论环（Ring），它包含两种运算，例如整数加法乘法群（不一定能除）：

$(\mathbb{Z},+,\times)$

再进一步，则是包含四则运算的域，即所有非零元素都能使用除法，例如实数域、复数域。我们在这种数学框架中才能完成

解方程
线性代数变换
求解特征值

等操作

伽罗瓦域

数学家伽罗瓦发现：有限元素集合也能形成域。例如二进制元素 0、1，虽然只有两个元素，但完全满足域的概念及运算规则，这也就是 GF(2)，二阶伽罗瓦域（Galois Field of order 2）。

这还不是最神奇的，最神奇的是 GF(2) 的运算规则加法和乘法，可以通过异或 XOR 和逻辑与 AND 来完美实现。于是数学逻辑的硬件实现可以依靠一堆并级联的异或门、与门和触发器来完成，这便是数字电路的理论基础。

LFSR

LFSR 本质是 GF(2) 上的线性递推系统，原理图如下

所谓的 Taps，指的是 $a(r)$ 一系列权重，考虑到 GF(2) 的限制，这里应该是一串二进制数，也就是说仅有部分位移寄存器的数据参与了反馈循环。

所谓的 Seed，指的是位移寄存器的初始 $D(n)$ ，同样也是一串二进制数，例如

$D(0)=Seed_2(0)=1\\ D(-1)=Seed_2(1)=0\\ \cdots\\ D(1-r)=Seed_2(r-1)=1$

这里的 Taps = bin(“10000000001”) 表示右往左数，第 1 位和第 11 位 $a(r)$ 为 1，所以是：

$D(n)=D(n-11)\oplus D(n-1)$

问题来了，为什么这里图中操作是

$D(n)=(D(n-11)+D(n-1))\bmod2 \tag{1}$

这就不得不提 GF(2) 又一个神奇的地方： $a\oplus b=(a+b)\bmod2$

因为对于 GF(2)（只有 0 和 1，没有 10，101这些），mod 2 本质就是算序列中 1 的个数的奇偶性，奇数个 1 结果为 1，偶数个 1 结果为 0，这就是奇偶校验。当多比特异或时（a xor b xor c xor d），由于 XOR 的物理特性：每遇到一个 1 就翻转一次状态（从 0 变 1，或从 1 变 0），与 GF(2) 中的加法完全等同。于是问题就变成了，所有的二进制数（只有 0 和 1）加起来的序列里有多少个 1。

考虑到 mod 2 作用是自动舍弃进位，而我们的 $D(n)$ 本就只有 1 位，在 GF(2) 里减法等于加法，式（1）就是

$D(n)+D(n-1)+D(n-11)=0$

做 Z 变换，利用：

$D(n-k)\ \longleftrightarrow\ z^{-k}D(z)$

所以：

$D(z)+z^{-1}D(z)+z^{-11}D(z)=0$

提出 $D(z)$ ：

$D(z)\left(1+z^{-1}+z^{-11}\right)=0$

所以递推关系对应的 延迟多项式 是：

$1+z^{-1}+z^{-11}$

用延迟算子 $x=z^{-1}$ 得到普通正幂形式：

$x^{11}+x+1$

这就是该 LFSR 的多项式。

需要注意的是，该式子可能不是本原多项式（primitive polynomial），即非 maximal-length LFSR。标准里的 PRBS taps 往往是固定的，例如

PRBS7： $x^7+x^6+1$

PRBS15: $x^{15}+x^{14}+1$

PRBS31: $x^{31}+x^{28}+1$

考虑到互反多项式把 $x^i$ 的系数变成 $x^{n-i}$ 的系数，例如 $p(x)=x^7+x^6+1$ 的互反多项式为 $p^*(x)=1\cdot x^7+1\cdot x^{7-6}+x^0=x^7+x^1+1$ 。根据本原性一致：如果一个多项式是本原多项式（能生成最长序列），那么它的互反多项式也一定是本原多项式。因此即便多项式与标准中的 PRBS 不一致，也可能属于本原多项式。除了本原性一致，互反多项式还会导致序列反转：如果你用原多项式生成一个序列 $S$ ，用互反多项式生成的序列，恰好是 $S$ 在时间上的倒序。硬件实现 LFSR 中，这对应了"从左往右移位"和"从右往左移位"的区别。

这是因为只有极少数 polynomial 是 primitive polynomial，能够遍历全部非零状态即：

$2^n-1$

个状态。而 Seed 基本可以随便取，因为所有非零 Seed，都在同一个 maximal-length cycle 上。

LFSR 的本质是 $GF(2^n)$ 中的线性变换，primitive polynomial 对应一个本原元，它能生成整个乘法循环群。如果不是 primitive，就只能生成某个子群。于是，如果 n=7，生成的序列周期会变成 128 的因子减一，例如 63，31。

之所以 LFSR 能产生伪随机数，是因为它的本质不是生成随机数，而是一个有限状态机，它任意时刻寄存器内容就是当前的系统状态。只要能遍历所有的系统状态达到最大不确定性 $2^n-1$ （减去全 0 的情况），得到的伪随机数可以在一定程度上认为是随机的。

PRBS

PRBS 全称是伪随机比特序列，由于它是通过 LFSR 产生的，因此 PRBS 序列不是一个线性序列，而是一个循环轨道。

Seed 只是这个轨道上的起点，它不能改变循环轨道的周期，只能改变码型起始位置在这个循环轨道周期里的相位。也可以认为 Seed 是 LFSR 有限状态机的初始状态。

PRBS 能作为伪随机比特序列，是因为 primitive polynomial 驱动的 maximal-length LFSR 能遍历除全零外的全部状态，使得序列在有限窗口统计上近似均匀分布，从而具有接近白噪声的统计特性。

如果从群论的角度出发，PRBS 的本质是一个循环群。LFSR 每 shift 一次，等价于群作用一次。这里的群作用，指的是本原元（primitive element，通常是 $x$ 或 $x^{-1}$ ）乘到当前状态上，然后对 primitive polynomial 取模。即：

$s_{n+1}=x\,s_n\quad \text{or} \quad x^{-1}s_n \pmod{p(x)}$

这里建立的是一个基于 伽罗瓦（Galois）型 LFSR 的数学模型。

在 ADS 中，VtLFSR_DT建立的是 斐波那契（Fibonacci）型 LFSR。下面以 Fibonacci LFSR 为例

以 PRBS7 为例，taps 为 1100000，初始 seed 为 0000011，对应寄存器状态

$1\cdot x^6+1\cdot x^5+0\cdot x^4+0\cdot x^3+0\cdot x^2+0\cdot x+0\cdot x^0$

结合图

$a(6)=a(7)=1,\,a(1)=a(2)=\cdots=a(5)=0$

$D(n-6)=D(n-7)=1,\,D(n-1)=\cdots=D(n-5)=0$

$a(r)$ 从左到右排序 0000011， $D(n)$ 从左到右排序 0000011

排序，taps 是按照时延排序，而 seed 是按照存储顺序排序，taps 这里刚好与前面给的值是反着的。

先反馈， $D(n-6)\oplus D(n-7)=0=D(n)$ ，整体右移一位，将反馈 $D(n)$ 塞进 $D(n-1)$

因此，斐波那契 LFSR 的下一个状态为 0000001

再下一个状态为 1000000

如果我们用基于 伽罗瓦（Galois）型 LFSR 的数学模型，作用延迟算子 $x$ 在初始 seed 上，状态为

$1\cdot x^7+1\cdot x^6+0\cdot x^5+0\cdot x^4+0\cdot x^3+0\cdot x^2+0\cdot x$

根据本原多项式 $x^7+x^6+1$ ，在 GF(2) 中，减法等于加法，因此

$x^7=x^6+1$

时延算子使得状态变为

$0\cdot x^6+0\cdot x^5+0\cdot x^4+0\cdot x^3+0\cdot x^2+0\cdot x+1\cdot x^0$

因此这个模型下，下一个状态为 1000000，与斐波那契型 LFSR 不一致

Fibonacci 与 Galois 型 LFSR

两种模型的详细对比表

维度	斐波那契型 (Fibonacci)	伽罗瓦型 (Galois)
电路逻辑	反馈只影响第一位。中间位只负责右移。	反馈影响多个位。溢出位同时异或多个位置。
数学操作	无法直接用简单的 $x \cdot S(x) \pmod{G(x)}$ 。	严格对应 $S_{next}(x) = [x \cdot S(x)] \pmod{G(x)}$ 。
移位本质	物理平移。像传送带。	代数状态转换。像矩阵运算。

上面提到在二阶伽罗瓦域中，斐波那契型 LFSR 与伽罗瓦型 LFSR 本质是线性同构的

所谓线性同构，指的是这两组坐标基都能完全构建同一个线性空间

以 PRBS7 为例

对于 Galois-field LFSR，采用标准多项式基 basis

$\{1,x,x^2,x^3,x^4,x^5,x^6\}$

状态向量为

$s_n=a_0+a_1x+\cdots+a_6x^6$

对应列向量：

$\mathbf s_n= \begin{bmatrix} a_0\\ a_1\\ a_2\\ a_3\\ a_4\\ a_5\\ a_6 \end{bmatrix}$

basis 元素乘以本原元 $x$ 并带入特征多项式 $x^7=x^6+1$

$s_{n+1}=a_6+a_0x+\cdots +a^4x^5+(a_5+a_6)x^6$

对应列向量：

$\mathbf s_{n+1}= \begin{bmatrix} a_6\\ a_0\\ a_1\\ a_2\\ a_3\\ a_4\\ a_5+a_6 \end{bmatrix}$

推导出状态更新方程：

$\mathbf{s}_{n+1}=M\mathbf{s}_n$

其中 $M$ 为

$M= \begin{bmatrix} 0&0&0&0&0&0&1\\ 1&0&0&0&0&0&0\\ 0&1&0&0&0&0&0\\ 0&0&1&0&0&0&0\\ 0&0&0&1&0&0&0\\ 0&0&0&0&1&0&0\\ 0&0&0&0&0&1&1 \end{bmatrix}$

对于 Fibonacci LFSR，存在反馈 $c_{\text{new}}=c_5\oplus c_6$ ，右移后

$\mathbf c_{n}= \begin{bmatrix} c_0\\ c_1\\ c_2\\ c_3\\ c_4\\ c_5\\ c_6 \end{bmatrix} \quad\Rightarrow\quad \mathbf c_{n+1}= \begin{bmatrix} c_5\oplus c_6\\ c_0\\ c_1\\ c_2\\ c_3\\ c_4\\ c_5 \end{bmatrix}$