IC的帆哥 - LFSR https://icfgblog.com/index.php/tag/LFSR/ PRBS并行输出 https://icfgblog.com/index.php/Digital/381.html 2024-01-28T23:24:00+08:00 PRBS(Pseudo-Random Binary Sequences)是通过LFSR和特征函数 伪随机数发生器产生的伪随机数序列,通常用于高速数字通信测试。 基本电路(单比特输出) prbs N表示用N比特lfsr尝试伪随机数序列,常用的有N=7,9,11,15,32等。伪随机序列的长度为$2^{N-1}$。 那么如何搭建电路产生这些伪随机数呢?以PRBS7,生成多项式为$G(x)=x^7 + x^6+1$,对应External Feedback LFSR电路如下图,其中1~7表示移位寄存器。 这样的电路一个周期只能产生一比特输出,如果需要每T产生伪序列中的两个,那么该如何实现?或者我想输出是6,7两个寄存器,下一拍更新时,希望是如图电路移位两拍的结果。 两比特输出 生成多项式还对应生成多项式还有对应的特征矩阵M。假设x1-7分别对应图中1~7个寄存器的输出,则下一拍x'1-7的值可以通过矩阵M,由当前拍x1-7的值得到。 $$ \left[ \begin{matrix} x_7' \\ x_6'\\x_5'\\x_4'\\x_3'\\x_2'\\x_1'\\ \end{matrix} \right] = \left[ \begin{matrix} 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& 0\\ 0 & 0 & 0& 0& 0& 0& 1\\ 1 & 1 & 0& 0& 0& 0& 0\\ \end{matrix} \right] \left[ \begin{matrix} x_7 \\ x_6 \\ x_5\\ x_4\\ x_3\\ x_2\\ x_1 \end{matrix} \right] $$ 如果一次更新要得到两拍后的结果,那么映射关系等于M^2,即 ![image.png](//www.icfgblog.com/usr/uploads/auto_save_image/334a493541a485194e9696535d422858.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 通过该映射关系,可以很容易写出x'1-7的更新逻辑。 $$ \begin{align} x'_7 &= x_5 \\ x'_6 &= x_4 \\ x'_5 &= x_3 \\ x'_4 &= x_2 \\ x'_3 &= x_1 \\ x'_2 &= x_7 \oplus x_6 \\ x'_1 &= x_6 \oplus x_5\\ \end{align} $$ 十比特输出 如果需要一次产生10比特的伪随机序列,又该如何实现呢?初值固定后,这些伪随机序列也是固定的,因此每T产生此序列的10个数也是固定的,那么该如何做到呢? 基本电路只有7个寄存器,该如何一次性输出十个数呢?如果这样想,就容易落入死胡同。换个思路,通过生成矩阵,只要确定初值,我们可以得到移位任意拍的输出逻辑。所以下一拍x'7 表示移位10次后的结果,x'6表示移位11次后的结果,x'1表示移位16次的结果,另外准备3个寄存器x'0,x'-1,x'-2,分别表示移位17,18,19次的结果。我们只需要关心下一拍的更新逻辑! 所以根据$M^{10}$我们可以得到如下更新逻辑: $$ \begin{align} x'_7 &= x_4 \oplus x_3 \\ x'_6 &= x_3 \oplus x_2 \\ x'_5 &= x_2 \oplus x_1 \\ x'_4 &= x_7 \oplus x_6 \oplus x_1 \\ x'_3 &= x_7 \oplus x_5 \\ x'_2 &= x_6 \oplus x_4 \\ x'_1 &= x_5 \oplus x_3\\ x'_0 &= x_4 \oplus x_2\\ x'_{-1} &= x_3 \oplus x_1\\ x'_{-2} &= x_7 \oplus x_6 \oplus x_2 \\ \end{align} $$ 同理对于其他PRBS,都可以生成任意比特的输出。 LFSR和特征函数 https://icfgblog.com/index.php/Digital/202.html 2021-05-06T14:47:00+08:00 测试课程碰到了随机向量生成方面的内容,碰到了线性反馈移位寄存器(Linear Feedback Shift Registers,LFSR)。课件上只简单提了一下,但没有说EE和IE两者结构的区别,以及对应特征函数的作用。全网搜了一通,也没看到说清楚的,最后还是在bing上搜到一篇比较好的课件,特来记录一番。LFSRs 一、LFSR是什么 LFSR有两者类型,外部反馈型和内部反馈型: $$ 图 1 $$ 两个电路明显的区别是,EF只更新最后一位,其余移位,且关键路径更长;IF不单纯移位,关键路径更短。 给定初始状态,每个周期会有新的输出,如果选择特定的反馈电路,那么寄存器组成的向量可以遍历除0向量外的其他$2^n-1$个向量,单端的输出便是以$2^n-1$为周期的伪随机数,因此这种电路经常用做伪随机数发生器,IF LFSR也会用来做CRC的编解码。 假设初始状态是1000,那么两个电路寄存器的更新序列如下: 序号 EF IF 1 1000 1000 2 1100 0100 3 1110 0010 4 0111 0001 5 0011 1101 6 0001 1110 7 1000 1000 两个电路的周期都是6,但如果更换电路,那么序列周期大不一样: $$ 图 2 $$ 序号 EF IF 1 1000 1000 2 0100 0100 3 0010 0010 4 1001 0001 5 1100 1100 6 0110 0110 7 1011 0011 8 0101 1101 9 1010 1010 10 1101 0101 11 1110 1110 12 1111 0111 13 0111 1111 14 0011 1011 15 0001 1001 16 1000 1000 这两个电路反馈的位置有某种对称性,是否有方法直接判断电路的周期数呢,或者该如何设计电路,让其产生$2^n-1$周期的伪随机数? 二、特征函数 多亏了数学家们的努力,这种LFSR电路可以用特征多项式的形式表示: 上面两个例子(图1、图2)对应特征多项式分别是: $$ \begin{aligned} f_1(x)&=x^4+x^3+x+1\\ f_2(x)&=x^4+x+1 \end{aligned} $$ 那么特征多项式有什么用呢? ### 1、判断周期 第一种电路的周期是6,我们可以验证:$x^6+1$能被$f_1(x)$整除: $$ x^6+1=(x^4+x^3+x+1)(x^2+x+1) $$ 注意这里的“加法”是异或逻辑,相同指数项相加,偶数个为0,奇数个为1,如$x^3+x^3=0,x^2+x^2+x^2=x^2$。 同理,第二种电路的周期是15,可以验证:$x^{15}+1$能被$f_2(x)$整除: $$ x^{15}+1=(x^4+x+1)(x^{11}+x^8+x^7+x^5+x^3+x^2+x+1) $$ 2、计算下一个向量序列 对于IE结构,如果当前向量为$S_0$,那么下一个向量$S_1$既可以通过电路得到,也可以由多项式得到: $$ S_1=(S_0 *x) \% f(x) $$ 比如$S_0=0011=x^2+x^3$,那么: $$ S_1=(x^2+x^3)x \% (x^4+x+1)=(x^4+x^3)\%(x^4+x+1)=x^3+x+1=1101 $$ ### 3、由本征f(x)构造伪随机数电路 如果我们想产生周期为$2^10-1=1023$的伪随机数,那么可以取本征多项式$f(x)=x^{10}+x^3+1$,得到相应EF或IF电路。 三、EF和IF关系 有一个奇怪的问题是,上面定义的EF和IF的电路从时序上看,它们产生序列的顺序并不一样,那么它们为什么对应相同的特征多项式? 这张图给出了答案: 相同的特征多项式表示电路产生的各类周期是一样的,它表示更抽象层面的相同结构,比如上述电路可以分为两个1周期,一个2周期,一个4周期的情况,总共是8种状态。