LFSR：线性反馈移位寄存器及其应用

时间  2020-07-24 标签 lfsr 线性 反馈 移位 寄存器 及其 应用

LFSR简介

LFSR(Linear-feedback shift register)是一种特殊的的移位寄存器，他的输入取决于其先前状态。
LFSR的使用异常普遍，能够说涉及到方方面面，如下是Wikipedia列举的一些应用html

  • INTELSAT business service (IBS)
  • Intermediate data rate (IDR)
  • SDI (Serial Digital Interface transmission)
  • Data transfer over PSTN (according to the ITU-T V-series recommendations)
  • CDMA (Code Division Multiple Access 码分多址) cellular telephony
  • 100BASE-T2 “fast” Ethernet scrambles bits using an LFSR
  • 1000BASE-T Ethernet, the most common form of Gigabit Ethernet, scrambles - bits using an LFSR
  • PCI Express 3.0
  • SATA
  • Serial attached SCSI (SAS/SPL)
  • USB 3.0
  • IEEE 802.11a scrambles bits using an LFSR
  • Bluetooth Low Energy Link Layer is making use of LFSR (referred to as whitening)
  • Satellite navigation systems such as GPS and GLONASS

事实上LFSR在上述系统中更广为人知的应用是伪随机数的生成与CRC计算。
如下来自Wikipedia的动图展现了LFSR的一个有趣的应用。
在这里插入图片描述
这是一个使用LSFR构建的31位伪随机数发生器，LED充当了其输出。原做者使用了4块74HC565（这个IC查不到，应该是做者看错了）和一块74HC86（异或门）。
对于一个LFSR，其能够看做一个FSM。这个LFSR最多状态数为
2 n − 1 2^n -1 git

那么对于上面那个31位的LFSR，有多达2,147,483,6487个状态，假如一个状态持续0.2秒，那么须要长达13.61925年这个状态机才能从新回到初始状态！web

LFSR的实现

LFSR可使用若干个寄存器和异或门组成，其结构也不一样，这里列举其中两个。算法

Galois型

在这里插入图片描述

Fibonacci型

在这里插入图片描述
固然这两种不管哪种都是比较方便用HDL语言或者其余语言实现的。网络

咱们以一个简单的3位Galois型LFSR为例。
在这里插入图片描述
注意这里 g 0 = 1 g_0 = 1 ， g 1 = 0 g_1 = 0 ， g 2 = 1 g_2 = 1 ， g 3 = 1 g_3 = 1 。app

请注意，不管是何种LFSR， g 0 g_0 与 g n g_n 都是不可能为0的。ide

咱们能够写出这样一段C语言代码描述这个3位的LFSRsvg

void lfsr3()
{
	unsigned int temp0, temp1, temp2;
	temp0 = ff0; //拷贝ff0
	temp1 = ff1; //拷贝ff1
	temp2 = ff2; //拷贝ff2
	ff0 = temp2;
	ff1 = temp0 ^ (0 * temp2);
	ff2 = temp1 ^ (1 * temp2);
}

如今咱们令三个ff的初值为 f f 0 = 1 ff_0 = 1 、 f f 1 = 0 ff_1 = 0 、 f f 2 = 0 ff_2 = 0 ，运行这段代码20次能够获得以下结果：编码

// ff2 ff1 ff0
[1]:    0  0  1
[2]:    0  1  0
[3]:    1  0  0
[4]:    1  0  1
[5]:    1  1  1
[6]:    0  1  1
[7]:    1  1  0
[8]:    0  0  1
[9]:    0  1  0
[10]:   1  0  0
[11]:   1  0  1
[12]:   1  1  1
[13]:   0  1  1
[14]:   1  1  0
[15]:   0  0  1
[16]:   0  1  0
[17]:   1  0  0
[18]:   1  0  1
[19]:   1  1  1
[20]:   0  1  1

很明显能够看到每7次一个循环，咱们看到这个LFSR刚好达到了最多的状态数。至于为何且看下面的分析。spa

LFSR的行为

LFSR的行为是比较难于分析的。事实上这是一个伽罗华域（Galois Field）上的除法运算。这里一样以上面的那个3位的LFSR为例。

图中的3位数按照从高到低的顺序，即( f f 2 , f f 1 , f f 0 ff_2 ,ff_1 ,ff_0 )的顺序。

在这里插入图片描述

咱们将每个ff的值看做一个多项式中某一项，例如

100 = ( 1 × x 0 ) + ( 0 × x 1 ) + ( 0 × x 2 ) = x 0 100 = (1\times x^0)+(0\times x^1)+(0\times x^2)=x^0

因而这个状态转移图能够描述为一个多项式结果的转换，特别地，这里x=2

在这里插入图片描述
这样作有什么意义呢？
前面说到，这样一个LFSR的行为能够视做一个伽罗华域的除法。对于伽罗华域而言，其四则运算封闭，则结果必然是这个域中的一个元素。这个域咱们记做 G F ( 2 3 ) GF(2^3) 。
在这里插入图片描述
这里 R ( x ) R(x) 是ff的值， M ( x ) M(x) 是输入多项式， G ( x ) G(x) 是抽头多项式。

注意这个是在伽罗华域中的除法运算，本质上是一个模二除法。

这里给出 M ( x ) M(x) 的值，列出下表(当 G ( x ) = x 3 + x 2 + x 0 G(x)=x^3+x^2+x^0 时)

M ( x ) M(x) R ( x ) R(x)
x 0 x^0 x 0 x^0
x 1 x^1 x 1 x^1
x 2 x^2 x 2 x^2
x 3 x^3 x 2 + x 0 x^2+x^0
x 4 x^4 x 2 + x 1 + x 0 x^2+x^1+x^0
x 5 x^5 x 1 + x 0 x^1+x^0
x 6 x^6 x 2 + x 1 x^2+x^1

对照上面的状态转移图，咱们能够看到实际上这个LFSR的行为就是一个模二除法的输出，除法表达式受抽头表达式的控制。

对于一个 n n 位的LFSR，可用的抽头至少有 n n 个（第0个抽头是必须的，不算数）
虽然一个 n n 位的LFSR能够有不少种不一样的抽头配置，但不是全部抽头都能使其达到最长输出序列。下表给出一些可以使LFSR达到最长反馈的抽头配置

LFSR位数 状态周期 抽头配置 LFSR位数 状态周期 抽头配置
2 3 2，1 17 131,071 17, 14
3 7 3, 2 18 262,143 18, 11
4 15 4, 3 19 524, 287 19, 6, 2, 1,
5 31 5, 3 20 1,048,575 20, 17
6 63 6, 5 21 2,097,151 21, 19
7 127 7, 6 22 4,194,303 22, 21
8 255 8, 6, 5, 4, 23 8,388,607 23, 18
9 511 9, 5 24 16,777,215 24, 23, 22, 17,
10 1,023 10, 7 25 33,554,431 25, 22
11 2,047 11, 9 26 67,108,963 26, 6, 2, 1,
12 4,095 12, 6, 4, 1, 27 134,217,727 27, 5, 2, 1,
13 8,191 13, 4, 3, 1, 28 268,435,455 28, 25
14 16,383 14, 5, 3, 1, 29 536,870,911 29, 27
15 32,767 15, 14 30 1,073,741,823 30, 6, 4, 1,
16 65,535 16, 15, 13, 4, 31 2,147,483,646 31, 28
32 4,294,967,294 32, 22, 2, 1,

这里抽头对应的多项式 G ( x ) G(x) 均为 G F ( 2 n ) GF(2^n) 域上的本原多项式。

须要注意的是一个肯定域上的本原多项式可能不止一个，例如 G F ( 2 3 ) GF(2^3) 上的本原多项式除了 x 3 + x + 1 x^3+x+1 还有 x 3 + x 2 + 1 x^3+x^2+1 ，这个你们能够验证如下，这俩多项式构造的LFSR序列长度都是7。

本原多项式能够经过查表得到，也能够经过特定算法生成，这些生成算法在某些领域很是有用。

LFSR应用

PRBS（随机序列）发生器

在通讯系统常常会用到一些PRBS，这些发生器可使用必定长度的LFSR构建。由上面的结论可知，当抽头表达式刚好为本原多项式时，LFSR由最长PRBS输出。即便抽头表达式不为本原多项式，足够位数的LFSR产生的PRBS长度依然很是可观！

咱们可使用一些经典的分立器件构造LFSR，例如D触发器74HC574。

须要注意的是，若是使用移位寄存器构造LFSR，则要使用斐波那契型的LFSR。

值得关注的是Fibonacci型提升工做频率的时候容易出现误码（能够观察反馈抽头和移位寄存器），所以Galois型设计能够有更高的码率。

利用HDL在CPLD或FPGA上实现LFSR也是很是方便的。

在这里插入图片描述
这个就是一个32位的LFSR，抽头表达式为 x 32 + x 22 + x 2 + x + 1 x^{32 }+ x^ {22} + x^ 2 + x + 1 ，是一个本原多项式。

白噪声发生器

白噪声是在其频率范围内频谱平坦的噪声，功率谱密度和每单位带宽的功率在噪声带宽上是恒定的。

倘若将PRBS发生器输出接入一个权电阻网络，就能够构成一个速度还不错的DAC，DAC的输出通过低通滤波，能够在必定带宽内获得不错的白噪声。

在这里插入图片描述
图片来源：Digi-Key

补充：另外几种低成本的白噪声产生方法

1.利用电阻的约翰逊噪声产生白噪声
这个方法比较简单，噪声电压密度为
V N O I S E = 4 k B T R V_{NOISE} = \sqrt{4k_{B}TR}
其中 k B k_B 为玻尔兹曼常数。
2.利用PN结的齐纳击穿
可使用二极管或者BJT或者JFET有PN结的东西产生白噪声，这个容易在版图上实现。目前intel CPU内部的真随机数发生器是这个原理。

PRBS设计白噪声发生器的缺点
滤波器难以设计
带宽受限

**传说白噪声煲耳机不错，博主改天得弄个玩玩😀 传说白噪声能安神助眠，放松身体（尚无更多科学依据支撑）**

CRC计算

CRC计算实际是一个 G F ( 2 n ) GF(2^n) 上的除法，又叫作模二除法。加入可以注意到这幅图，CRC的计算就迎刃而解。
在这里插入图片描述
CRC多项式对应了 G ( x ) G(x) ，如今只须要依次输入 M ( x ) M(x) 便可，微调如下LFSR的结构，加一个异或门，变成这个亚子

在这里插入图片描述
关于CRC与LFSR，在另外一篇文章中介绍。

RS编码

这个目前博主没有研究，留一个坑等之后填。

联系我们 沪ICP备2021010478号-7