精华内容
下载资源
问答
  • 丁石孙老师著的线性移位寄存器序列,讲解得清晰简洁,非常值得一学。
  • nnn级线性移位寄存器的结构如下图 当生成多项式g(x)g(x)g(x)为本原多项式时,产生的序列为m序列。例如 g(x)=x5+x2+1g(x)=x^5+x^2+1g(x)=x5+x2+1的本原多项式,初态为10000的5级m序列,其周期为25−1=312^5-1=3125−...

    移位寄存器的结构

    n n n级线性移位寄存器的结构如下图
    在这里插入图片描述
    当生成多项式 g ( x ) g(x) g(x)为本原多项式时,产生的序列为m序列。例如
    g ( x ) = x 5 + x 2 + 1 g(x)=x^5+x^2+1 g(x)=x5+x2+1的本原多项式,初态为10000的5级m序列,其周期为 2 5 − 1 = 31 2^5-1=31 251=31,结构如下图所示。
    在这里插入图片描述

    代码

    m序列的性质在此不多赘述,感兴趣的可查阅相关资料,MATLAB生成m序列的代码

    function mCode = mCodeGen(polynomial,reg)
        % m序列产生器函数
        % polynomial为本原多项式次数,如对x^5+x^2+1,polynomial = [5 2 0]
        % reg为置寄存器初始值,也相当于PN码的初始相位,如初态为[1 0 0 0 0]时,寄存器初始状态如上图所示
        
        ntap = length(polynomial);
        grade = polynomial(1); % 延时级数
        mlen = 2^grade-1; % m序列一个周期的长度
        mCode = zeros(1,mlen);
        tap = grade+1-polynomial(1:ntap-1); % 抽头位置
        
        % 产生一个周期的PN码
        % 寄存器为 0 0 0 0 1 右边输出
        for i = 1:mlen
            mCode(i)=reg(1);        
            m = mod(sum(reg(tap)),2);
            reg(1:grade-1) = reg(2:grade);
            reg(grade) = m;
        end
    end
    
    展开全文
  • 研究了由TSR所生成的序列的基本性质,并且给出了一个新的准则来判定一个线性变换移位寄存器系统的特征多项式是否不可约。利用这个准则,不需要在扩域上做运算来判定一个线性变换移位寄存器系统的特征多项式是否...
  • 里面生成GF(2)上任意阶本原多项式的算法花了一天才理解,觉得应该写下来,方便自己,也方便别人! 记n次多项式,所谓GF(2)上的多项式,即; 前面都好理解,直接说论文中寻找n阶本原多项式的算法。考虑的是形如的...

    给出论文出处:https://wenku.baidu.com/view/da6d8d85b9d528ea81c77922.html

    里面生成GF(2)上任意阶本原多项式的算法花了一天才理解,觉得应该写下来,方便自己,也方便别人!

    记n次多项式f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}x+a_{0},所谓GF(2)上的多项式,即a_{i}\in{0,1},i=0,\cdots,n

    前面都好理解,直接说论文中寻找n阶本原多项式的算法。考虑的是形如f(x)=x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}x+1的多项式,论文中假定\alpha\in GF(2^{n}),且f(\alpha)=0;首先,这里懵逼了好一会,既然之前f(0),f(1)均为1,怎么还会有\alpha使得f(\alpha)=0,后来才明白,当多项式f(x)的自变量是\alpha时,f(\alpha)=\alpha^{n}+a_{n-1}\alpha^{n-1}+\cdots+a_{1}\alpha+1的加法与乘法就变成了GF(2^{n})上的加法与乘法,不了解GF(2^{n})上加法与乘法的参见https://www.cnblogs.com/codingtao/p/5916786.html,讲得还行;概括地说,就是将GF(2^{n})中的元素转换为GF(2)上的多项式,那么GF(2^{n})上的加法就是两个多项式的对应系数异或,然后再转换为GF(2^{n})中的元素;而乘法就是两个多项式相乘,在模一个n次的不可约多项式(这样转换之后的元素仍在GF(2^{n})中)。

    好了,上面的疑问解决了。可能有人在想\alpha是多少,其实\alpha是多少并不重要,因为后面的计算并不需要。根据算法,由f(\alpha)=0\alpha^{n}+a_{n-1}\alpha^{n-1}+\cdots+a_{1}\alpha+1=0 \\ -\alpha^{n}=a_{n-1}\alpha^{n-1}+\cdots+a_{1}\alpha+1 \\ \alpha^{n}=a_{n-1}\alpha^{n-1}+\cdots+a_{1}\alpha+1

    由于GF(2^{n})上的加法所以第二行就是第三行。只要\alpha^{n+1},\cdots,\alpha^{2^{n}-2}不等于1,那么f(x)即为n次本原多项式。那么\alpha^{n+1},\cdots,\alpha^{2^{n}-2}该怎么算呢,利用\alpha^{n}=a_{n-1}\alpha^{n-1}+\cdots+a_{1}\alpha+1

    \alpha^{k}=b^{(k)}_{n-1}\alpha^{n-1}+b^{(k)}_{n-2}\alpha^{n-2}+\cdots+b^{(k)}_{0} \\=[b^{(k)}_{n-1},b^{(k)}_{n-2},\cdots,b^{(k)}_{0}]\cdot[\alpha^{n-1},\alpha^{n-2},\cdots,1]^{T} \\=b^{(k)}\cdot[\alpha^{n-1},\alpha^{n-2},\cdots,1]^{T}

    \alpha^{k+1}=\alpha\cdot\alpha^{k} \\=\sum_{i=0}^{n-1}b^{(k)}_{i}\cdot\alpha^{i+1} \\=\sum_{i=1}^{n-1}b^{(k)}_{i-1}\cdot\alpha^{i}+b^{(k)}_{n-1}\cdot\alpha^{n} \\=\sum_{i=1}^{n-1}b^{(k)}_{i-1}\cdot\alpha^{i},b^{(k)}_{n-1}=0 \\=\sum_{i=1}^{n-1}[b^{(k)}_{i-1}+a_{i}]\cdot\alpha^{i}+1,b^{(k)}_{n-1}=1

    从而得到b^{(k)}的递推式:

    b^{(k+1)}=b^{(k)}<<1,b^{(k)}_{n-1}=0 \\=(b^{(k)}<<1)+[a_{n-1},\cdots,a_{1},1],b^{(k)}_{n-1}=1

    k从n+1到2^{n}-2,若每轮b^{(k)}都不等于[0,\cdots,0,1],则f(x)为n次本原多项式。

    展开全文
  • 有趣的线性反馈移位寄存器(LFSR)

    万次阅读 2019-03-29 11:02:40
    有趣的线性反馈移位寄存器(LFSR) 最近一直在研究信道编码,发现在信道编码里面有一个电路比较重要也比较有趣,那就是线性反馈移位寄存器 LFSR ,相信大家对 LFSR 电路也不陌生了,在通信领域lfsr有着很广泛的应用,...

    有趣的线性反馈移位寄存器(LFSR)
      
    最近一直在研究信道编码,发现在信道编码里面有一个电路比较重要也比较有趣,那就是线性反馈移位寄存器 LFSR ,相信大家对 LFSR 电路也不陌生了,在通信领域lfsr有着很广泛的应用,比如说M序列,扰码,信道编码,密码学这方面都有很广泛的应用,LFRS的结构一般如下图:


     
    其中他需要一个生成多项式为:
     
    这个多项式是一个本原多项式,然后知道这个电路有一些有意思的性质,下面我以m  = 3 来做个例子具体的电路图如下所示:
     
     
    假设开始的时候(D2,D1,D0 ) = (0,0,1),那么每过一个时钟周期会进行跳变一次,
    可以看到具体的跳变如下所示:


     
    然后我们可以看到这个计数器循环起来了,很好玩吧,无论进入那样一个状态除了0之外,都可以循环着回来,其实这里就相当于了一个3bit的伪随机数,很有意思,不是所有的多项式都有这个特性,我们现在在从数学上面来看看这个问题,其实最上面的电路是可以看成是一个除法电路,在Galois域的一个除法电路。现在假设的是R(x)是寄存器中剩余的数据,M(x)是输入的码字多项式,然后数学公式可以表示成:
     
    然后我分别计算出了M(x)的各种情况,
     
      
    然后我们单独进行一下7次方的运算
     
    发现7次方的运算和0次的时候的余数是一样的
    然后我们发现其实在上面的电路中对多项式的除法也是可以循环起来的,可以验证的是
     把这个记成 
    上面的式子是可以循环的,然后我又想到了CRC的计算,CRC的计算也可以通过一个除法电路来实现,
    假设码子多项式为 
    生成多项式为
      
    那么CRC的码字为 这样我们同样可以用LFSR电路来进行实现
    首先对M(x)乘以一个x的r次方,然后去去除G(x),在电路上的表现就是
     
    所以在输入码字以后还需要多输入r拍的0这样才能使最后的CRC码字数据.
    同理这个电路也可以进行CRC校验,把生成的数据全部都依次输入进这个

    module RanGen(
        input               rst_n,    /*rst_n is necessary to prevet locking up*/
        input               clk,      /*clock signal*/
        input               load,     /*load seed to rand_num,active high */
        input      [7:0]    seed,     
        output reg [7:0]    rand_num  /*random number output*/
    );
    
    
    always@(posedge clk or negedge rst_n)
    begin
        if(!rst_n)
            rand_num    <=8'b0;
        else if(load)
            rand_num <=seed;    /*load the initial value when load is active*/
        else
            begin
                rand_num[0] <= rand_num[7];
                rand_num[1] <= rand_num[0];
                rand_num[2] <= rand_num[1];
                rand_num[3] <= rand_num[2];
                rand_num[4] <= rand_num[3]^rand_num[7];
                rand_num[5] <= rand_num[4]^rand_num[7];
                rand_num[6] <= rand_num[5]^rand_num[7];
                rand_num[7] <= rand_num[6];
            end
                
    end
    endmodule
    

     

    展开全文
  • 线性反馈移位寄存器,介绍了移位寄存器在除法器,编码器,解码器中的使用!
  • 线性反馈移位寄存器LFSR和循环冗余码CRC0 前言1 数学基础1.1 逻辑异或1.2 模2乘法 和 模2除法2 线性反馈移位寄存器LFSR2.1 抽头和特征多项式3 循环冗余码CRC 0 前言 线性反馈移位寄存器(Linear Feedback Shift ...

    0 前言

    线性反馈移位寄存器(Linear Feedback Shift Register,LFSR)和循环冗余码(Cyclic Redundancy Check,CRC)是微控制器中常用的底层原理。

    LFSR用于生成伪随机数,后者用于生成检错码。他们的数学原理都是一样的。

    1 数学基础

    1.1 逻辑异或

    异或运算使用符号或者nor表示,真值表如下
    F = A ⊕ B

    ABF
    000
    011
    101
    110

    异或运算可以有3种理解方式:

    1 相同得1,不同得0

    2 二进制加法,只留模2的余数,抛弃进位(模2加法)

    3 二进制减法,大数减小数,不借位(模2减法)

    1.2 模2乘法 和 模2除法

    两个二进制数的模2乘法是指在乘法竖式运算中需要做加法的地方都使用异或运算

    模2乘法1010 * 101=100010,下图红框中,1⊕0⊕1=0,没有进位

    在这里插入图片描述
    两个二进制数的模2除法是指在除法竖式运算中需要做减法的地方都使用异或运算

    模2除法10000 / 101=1011,下图红框中,0⊕1=1,没有借位
    在这里插入图片描述

    2 线性反馈移位寄存器LFSR

    以斐波那契(外部LFSR)为例,有n个二进制寄存器R0-Rn-1,每个寄存器值为01
    在这里插入图片描述
    k阶段,寄存器存在初值,(Rn-1, … R1, R0),称为seed
    k+1阶段,寄存器的值变为:

    k+1阶段
    Rn-1 = Rn-2
    Rn-2 = Rn-3
    R0 = f(R1, R2, …, Rn-1) = (Rn-1*gn)⊕(Rn-2*gn-1)⊕…⊕(R0*g1)*g0

    也就是说寄存器存储的结果 (Rn-1, … R1, R0) 每个时钟周期改变一次,其中R1-Rn-1是位移产生,R0是线性反馈函数 f(Rn-1, … R1, R0) 产生,所以称为线性反馈移位寄存器。

    线性反馈移位寄存器总是假定g0,gn1,否则 (Rn-1, … R1, R0) 将在n个周期后恒定为0

    2.1 抽头和特征多项式

    f(Rn-1, … R1, R0) = (Rn-1*gn)⊕(Rn-2*gn-1)⊕…⊕(R0*g1)*g0 可以用多项式表示为:

    G(x)=gnxn+gn-1xn-1+…+g1x+g0

    G(x)称为LFSR的特征多项式

    影响线性反馈寄存器下一个状态的 gi = 01叫做抽头,抽头的设定会决定线性反馈寄存器存储的结果 (Rn-1, … R1, R0) 的变化规律。

    通常N位的线性反馈寄存器最多有 2N 个不同的状态。但是如果出现初值为N个0的情况,线性反馈寄存器陷入死循环,要排除掉。所以N位线性反馈寄存器能产生最长的不重复序列为 2N-1。

    抽头的位置会影响LSFR的最大输出状态的个数
    例如:3位的抽头为(g3, g2, g1, g0) = (1, 1, 0, 1)会产生7个状态(多项式对应为:G(x)=x3+x2+1)
    若抽头为(g3, g2, g1, g0) = (1, 0, 1, 1),会产生2个状态(多项式对应为:x3+x+1)。

    使最大输出序列长度为2N-1的不可约多项式称为LFSR的本原多项式,本原多项式产生的寄存器序列为M序列

    当N位下,本原多项式不是唯一的。下表为不同的位下的本原多项式:
    在这里插入图片描述
    在这里插入图片描述

    2.2 3阶线性反馈移位寄存器实例

    在这里插入图片描述
    上图为3阶线性反馈移位寄存器
    抽头为(g3, g2, g1, g0) = (1, 1, 0, 1)
    多项式对应为:G(x)=x3+x2+1
    线性反馈函数R0 = f(R2, R1, R0) = R1⊕R2
    初始值为SEED = (R2, R1, R0) = (1, 0, 1)

    3阶线性反馈移位寄存器周期为7:

    k周期(R2, R1, R0)
    0(1, 0, 1)
    1(0, 1, 1)
    2(1, 1, 1)
    3(1, 1, 0)
    4(1, 0, 0)
    5(0, 0, 1)
    6(0, 1, 0)
    7(1, 0, 1)

    通过设定seed和抽头,LFSR最多可产生2N-1个序列,这些序列之间看似是随机产生的,之所以称之为伪随机,是因为这些数是通过具体的关系式产生,最终会实现循环。

    3 循环冗余码CRC

    现实的通信链路都不会是理想的。这就是说,比特在传输的过程中可能会产生差错:1可能会变成0,0可能会变成1,这就叫做比特差错。
    因此,为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检测措施。
    目前在数据链路层广泛使用了循环冗余检测CRC的检测技术

    3.1 CRC的原理

    CRC运算实际上就是在数据长为k的后面添加供差错检测用的n位冗余码,然后构成帧k+n位发送出去。

    在这里插入图片描述
    选择一个生成多项式,作为对接收的帧进行除法运算时的除数,生成多项式可以写为二进制形式;生成多项式的要求:
    ①最高位和最低位必须为1;
    ②当CRC码的任何一位发生错误时,新帧除生成多项式后余数不为0;
    ③不同位发生错误时,余数应该是不同的;

    计算n位冗余码
    现假定待传输的数据M = 101001(k = 6),除数p = 1101 (n = 3,p比n多一位)
    这n位冗余码可以用下面的方法得出。
    (1)用二进制的模2运算进行(2^n)乘M的运算,相当于在M后面添加n个0。
    即M后面添加3个0
    (2)现在得到M = 101001000(k+n = 9)位的数除以除数p(n = 3)位,
    得到余数R =001(n位),R就是冗余码FCS

    现在加上CRC后发送的帧是101001001

    在接收端把接收到的数据M = 101001001以帧为单位进行CRC检验:把收到的每一个帧都除以相同的除数p(模2运算),然后检查得到的余数R。
    如果在传输过程中没有差错,那么经过检验后得到余数R肯定是0。
    (读者可以自己检验下,被除数现在是M = 101001001,除数P= 1101,看余数是否为0)
    总之,在接收端对接收到的每一个帧经过CRC检验后,有两种情况:
    (1)余数R = 0,则判断这个帧没有问题,就接受
    (2)余数R != 0,则判断这个帧有差错,就丢弃。

    3.2 CRC的实例

    假设CRC生成多项式G(X)=X5+X4+X+1,要发送的二进制数据帧为100101110,求CRC校验码:

    ①把生成多项式转换为二进制数:110011;

    ②由生成多项式的位数为6可知,CRC校验码的位数为5,所以在数据帧后加5个0,变为10010111000000,将这个数使用模2除法除以生成多项式110011,得到余数即CRC校验码11010;
    在这里插入图片描述
    ③用得到的CRC校验码替换掉数据帧中的5个0,形成新的帧10010111011010,将这个新帧发送给接收端;

    ④接收端收到新帧后,用新帧除以上面的多项式110011(模2除法),如果余数为0,该数据帧在传输过程中没有出错,否则出错;(经验证余数为0)

    展开全文
  • LFSR(线性反馈移位寄存器)

    千次阅读 2021-07-19 19:45:02
    线性反馈移位寄存器LFSR,是移位寄存器的一种,通常用于在数字电路中产生伪随机数。寄存器中的初始值叫做种子,种子应该是非零的。LFSR的下一时刻输入为是由整个移位寄存器值的某些位做异或运算的结果。选取哪些位置...
  • 线性反馈移位寄存器

    2021-01-10 17:58:38
    n级LFSR产生的序列有最大周期2^n-1的必要条件是其特征多项式为不可约的;该定理的逆不成立,即LFSR的特征多项式为不可约多项式时,其输出序列不一定是m序列 寄存器存在于CPU中,速度很快,数目有限;计算机做运算时...
  • 线性反馈移位寄存器(LFSR):通常由移位寄存器和异或门逻辑组成。其主要应用在:伪随机数,伪噪声序列,计数器,BIST,数据的加密和CRC校验等。 线性反馈移位寄存器(LFSR)主要包括两大类 伽罗瓦(内部LFSR),又称one-...
  • 关于线性反馈移位寄存器在密码学中有着广泛的应用,就此提供32位线性反馈移位寄存器的相关源代码
  • 我们先来了解一下什么是线性反馈移位寄存器(LFSR) ...用反馈函数表示成y=a0x0+a1x+a2x2…反馈函数为线性的叫线性移位反馈序列,否则叫非线性反馈移位序列。 简单来说LFSR就是给定前一状态的输出,将
  • 简述线性反馈移位寄存器

    千次阅读 2020-04-12 17:39:20
    反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成,如下图所示: 在任意时刻,这些级的内容构成该反馈移位寄存器...
  • 【5】线性反馈移位寄存器

    千次阅读 2020-08-21 16:59:22
    文章目录反馈移位寄存器线性反馈移位寄存器 反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。 GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数 f(a1,a2,…,an)组成,如下图所示。 ...
  • FPGA实现的线性反馈移位寄存器LFSR

    千次阅读 2021-01-05 16:35:24
    线性反馈移位寄存器(linear feedback shift register, LFSR)是指,给定前一状态的输出,将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数:对寄存器的某些位进行异或操作后作为输入,...
  • 线性反馈移位寄存器实现产生伪随机数M序列 -----在CN03平台上,主要体现为Random功能的实现。 什么是线性反馈移位寄存器? 数学解释这里就不作介绍了,这里我们主要理解两个词语就行,一个是线性,它是指量与量...
  • 此程序是用verilog语言编写的8阶LFSR移位寄存器,压缩包里有word版的原理图,程序很详细,包括了使能信号和置数功能……已经通过验证!
  • 一、线性反馈移位寄存器(LFSR) 通过对事先选定的种子做运算使得人工生成的伪随机序列的过程,在实际中,随机种子的选择决定了输出的伪随机序列的不同,也就是说随机种子的选择至关重要。 产生伪随机数的方法最...
  • 移位密码和乘法密码All around us data is transferred faster than ever. Sensitive data is also part of our everyday life. To protect that data, we use encryption. When we encrypt data, it changes in ...
  • s = '10001010'#本源多项式x^8+x^4+x^3+x^2+1 a = s ls = len(s) for i in range(0,100000): s += str(int(s[i])^int(s[i+ls-4])^int(s[i+ls-3])^int(s[i+ls-2])) t1 = pow(2,ls)-1 t2 = s[ls:].find(a)+l...
  • 线性反馈移位寄存器 (LFSR) 是一种生成序列(包括伪随机数序列)的简单方法。 提供的 LFSR 代码非常不受限制,允许任何反馈多项式、初始状态或抽取因子。 该代码是为 32 位 LFSR 编写的,但稍作改动就可以使用 8-64 ...
  • LFSR代表线性反馈移位寄存器,它是一种在FPGA内部有用的设计。 LFSR易于合成,这意味着它们占用的资源相对较少,并且可以在FPGA内部以很高的时钟速率运行。
  • matlab自相关代码LFSR-线性反馈移位寄存器 链接: | | | | _安装: 目录 新的更新 用pylfsr绘制LFSR 更新: 修复了错误(1)缺少初始位(2)异常的问题 增加了LFSR的测试属性 (1)财产余额 (2)游程属性 (3)自...
  • 本文主要介绍matlab如何实现移位寄存器,首先介绍的是移位寄存器的原理及作用,其次介绍了m序列的生成原理及m序列的matlab 仿真实现,最后介绍了Matlab如何实现移位寄存器的代码。移位寄存器的原理及作用1、移位...
  • 本文主要介绍Matlab如何实现移位寄存器,首先介绍的是移位寄存器的原理及作用,其次介绍了m序列的生成原理及m序列的matlab 仿真实现,最后介绍了Matlab如何实现移位寄存器的代码。移位寄存器的原理及作用1、移位...
  • FPGA学习线性反馈移位寄存器(LFSR) 最近在学习FPGA的各种计数器的时候遇到了LFSR(线性反馈移位寄存器),感觉学起来还是比较难,在这里做个记录。。 刚开始接触LFSR真的是很难理解它,包括二进制数的各个Bit的...
  • B-M求线性移位寄存器

    千次阅读 2016-06-06 18:34:26
    1、B-M算法求线性综合解的过程 2、假设a(11)=(00100011101)是二元域GF(2)上的一个长度为11的序列,试用B-M算法求其线性综合解。#include using namespace std; void B_M(int a,int nn) { int i,j,k,n0; int c=1,m...
  • LFSR:线性反馈移位寄存器及其应用

    千次阅读 多人点赞 2020-03-07 17:54:16
    LFSR(Linear-feedback shift register)是一种特殊的的移位寄存器,他的输入取决于其先前状态。LFSR的使用异常广泛,可以说涉及到方方面面。以下对LFSR以及其行为、应用做简要介绍。
  • 今天主要是来研究梅森旋转算法,它是用来产生伪随机数的,实际上产生伪随机数的方法有很多种,比如线性同余法, 平方取中法等等。但是这些方法产生的随机数质量往往不是很高,而今天介绍的梅森旋转算法可以产生高...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 776
精华内容 310
关键字:

线性移位寄存器多项式