线性反馈移位寄存器(LFSR)的 Galois 多项式与 Fibonacci 多项式之间的转换

简介

本页内容可以用一句话概括:如果想把 LFSR 的多项式从 Galois 形式转换为 Fibonacci 形式,只要把系数的顺序颠倒过来即可。

例如,下面就是常用于加扰器(scrambler)的 LFSR 的结构图:

图中每一个标有 D 的方块都表示延迟一个时钟周期。这个 LFSR 用 Galois 多项式表示如下:

G(x) = x¹⁶ + x⁵ + x⁴ + x³ + 1

注意,多项式中的指数(3、4、5)反映的是每个 XOR(异或)左侧的延迟单元数量。

同一个 LFSR 也可以用 Fibonacci 形式来实现,如下图所示:

尽管这两幅图看起来很相似,但箭头的方向是相反的。两种 LFSR 的实现方式完全不同。

Fibonacci 多项式(也叫反馈多项式,feedback polynomial)如下:

F(x) = x¹⁶ + x¹³ + x¹² + x¹¹ + 1

该多项式的次数为 n=16,因此 G(x) 中的每个 xⁱ 在 F(x) 中都以 x^n-i 的形式出现。本页的剩余部分会说明这并非巧合。

关于 LFSR 的一般性介绍,请参见维基百科相关条目。

LFSR 与数字滤波器

数字滤波器背后的理论(例如 FIR 和 IIR)通常是在复数域上讨论的。不过,这套理论也可以应用于 GF(2),也就是由 0 和 1 两个数构成的有限域(finite field,即 Galois Field)。有几点需要注意:

• 在这个域中,加法运算符等价于 XOR。
• 所有乘法都只涉及整数。实际上,乘以偶数等价于乘以 0;类似地,乘以奇数等价于乘以 1。这个数是正还是负并不重要。
• 由于这条乘法规则,加法和减法的含义相同,都可以用 ⊕(也就是 XOR)代替。

数字滤波器的基础理论只要求系统是 线性时不变(linear time-invariant,LTI)的。LFSR 满足这些要求,因为 XOR 是线性的,而且 LFSR 的行为是时不变的。

最有趣的结论是,可以使用 z 变换(z-transform)来分析 LFSR。例如,请看下面这个结构:

它可以用下面的方程来描述:

y(t) = x(t) ⊕ x(t-1)

其中 t 是一个表示时间的整数。

我们可以把它看成一个 FIR,然后写出这个方程的 z 变换:

Y(z) = X(z) + X(z)z^-1 = X(z) (1 + z^-1)

相应地,可以像通常那样定义“冲激响应”:H(z) = Y(z)/X(z),或者更简单地说:

H(z) = 1 + z^-1

如果把两个这样的滤波器级联起来会怎样?这个滤波器的“冲激响应”又是什么呢?

数字滤波器理论给了一个很直接的答案:

H₂(z) = H(z)H(z) = (1 + z^-1)(1 + z^-1) = 1 + 2z^-1 + z^-2

还记得在 GF(2) 中,乘以一个偶数相当于乘以 0。因此:

H₂(z) = 1 + 2z^-1 + z^-2 = 1 + 0z^-1 + z^-2 = 1 + z^-2

它对应的是下面这个结构:

要看出最后两幅图中的滤波器是等价的并不容易。但只要给它们输入相同的 x(t),两个滤波器的输出 y(t) 就是相同的。所以这两个滤波器是相同的,尽管第二个延迟单元中存储的值并不相同。

这个例子说明了用 z 变换(以及类似的多项式方法)来分析逻辑滤波器的好处。

这里顺便提一下:人们经常用 D 或 D^-1 来代替 z^-1。事实上,Galois 多项式与 Fibonacci 多项式中的 x 和 z^-1 的意思相同。这些符号都表示延迟。

Galois 型 LFSR

为了找到 Fibonacci 形式的表示,我从 Galois 型 LFSR 开始看起。

请看上文中的 Galois LFSR 示意图。那一排延迟线与抽头(tap)可以看作一个 FIR 滤波器,我把它记作 A(z)。因此,Galois LFSR 等价于下面这个结构:

因为有反馈,Y(z) 满足:

Y(z) = Y(z)A(z)

那么这个 FIR 的参数与 Galois 多项式之间是什么关系?让我们写出 Galois 多项式的一般形式:

G(x) = xⁿ + g_n-1x^n-1+ g_n-2x^n-2+…+ g₀

注意,为了简化后面的数学推导,这个表达式中没有出现 g_n。此外,g_n 总是等于 1。

G(x) 与 A(z) 的关系如下:

A(z) = g_n-1z^-1+g_n-2z^-2+…+g₁z^1-n+g₀z^-n

为什么会有这个关系呢?我们以上面的 Galois LFSR 为例,看看这个表达式是如何成立的。

先看与 g₅ 相对应的 XOR。数字 5 表示这个 XOR 的左侧有 5 个延迟单元。不过 z 的指数取决于这个 XOR 与 FIR 输出端之间的延迟单元数量,也就是该 XOR 右侧的延迟单元数。延迟单元总共有 16 个。因此,g₅ 在 A(z) 中以 g₅z^-11 的形式出现。这与 g_n-iz^-i 的规律相符。

另一种解释方式是从时域的角度把 A(z) 看成 FIR。这个 FIR 的输入是 x(t),输出是 y(t):

y(t) = x(t–16) ⊕ x(t–13) ⊕ x(t–12) ⊕ x(t–11)

同样,t 是表示时间的整数。这个表达式描述的是去掉反馈之后的 Galois LFSR。该 FIR 的传递函数为:

A(z) = Y(z)/X(z) = z^-16 + z^-13 + z^-12 + z^-11

这与 G(x) = x¹⁶ + x⁵ + x⁴ + x³ + 1 时 A(z) 的一般表达式是一致的。

Fibonacci 等价形式

Fibonacci 形式的 LFSR 用下面的多项式表示:

F(x) = f_nxⁿ+f_n-1x^n-1+…+f₁x + 1

注意,这个多项式里没有 f₀,因为它总是等于 1。这和 G(x) 中不出现 g_n 是类似的。

该多项式的实现可以写成:

y(t) = f₁y(t-1) + f₂y(t-2) +…+ f_ny(t-n)

相应的 z 变换为:

Y(z) = f₁Y(z)z^-1+f₂Y(z)z^-2+…+f_nY(z)z^-n

把 B(z) 定义如下:

B(z) = f₁z^-1+f₂z^-2+…+f_nz^-n

于是 Y(z) 可以写成:

Y(z) = Y(z)B(z)

回顾前文,Y(z) = Y(z)A(z)。因此,如果 Fibonacci 形式的 LFSR 和由 Galois 多项式给出的 LFSR 具有相同的行为,那么就可以得到 A(z)=B(z)。也就是说:

f_i=g_n-i (i=1,2, … , n)

所以,正如我在开头所说:要把 LFSR 的多项式从 Galois 形式转换为 Fibonacci 形式,只要颠倒系数的顺序即可。

LFSR 的逆滤波器

再来看一次 Fibonacci 形式的 LFSR 实现:

y(t) = f₁y(t-1) + f₂y(t-2) +…+ f_ny(t-n)

但这个表达式也可以改写成:

y(t) + f₁y(t-1) + f₂y(t-2) +…+ f_ny(t-n) = 0

(回想一下,在 GF(2) 中,+ 和 - 是相同的。)

所以,Fibonacci 多项式的系数还告诉我们如何对 y(t-i) 的值进行 XOR,使得结果始终为 0。换句话说,这描述了一个很有意思的 FIR。

对最后一个表达式做 z 变换,得到:

Y(z) + f₁Y(z)z^-1+f₂Y(z)z^-2+…+f_nY(z)z^-n = 0

或者等价地写成:

Y(z)(1+ f₁z^-1+f₂z^-2+…+f_nz^-n) = Y(z)H(z) = 0

Y(z)H(z) 就是把滤波器 H(z) 作用于 Y(z) 后得到的输出,而这个输出为零。

因此,H(z) 是一个 FIR 滤波器的传递函数。如果把由 F(x) 定义的 LFSR 的输出接入这个 FIR,这个 FIR 的输出将始终为零。根据上文对 B(z) 的定义,这个 FIR 的传递函数为:

H(z) = 1 + f₁z^-1+f₂z^-2+…+f_nz^-n

或者用时域表示:如果输入为 x(t),输出为 y(t),则:

y(t) = x(t) ⊕ f₁x(t-1) ⊕ f₂x(t-2) ⊕ … ⊕ f_nx(t-n)

如果 x(t) 是由 F(x) 定义的 LFSR 的输出,那么对所有 t,y(t) 都为 0。