反馈移位寄存器（举例） 一个3-级的反馈移位寄存器，反馈函数fx=b2⊕b3,初 态为100，输出序列生成过程如下： 状态 输出位 100 0 b3b2b→ 00110110 110: 0 011- 1 101- 1 110 0 fb1b2,b3)=b2⊕b3 011 1 101 1 110 0 移位寄存器的周期是指输出序列中连续且重复出现部 分的长度。上面输出序列周期长度为3。 12 CNR@HEU http://machunguang.hrbeu.edu.cn
反馈移位寄存器（举例） 一 个 3 -级的反馈移位寄存器 级的反馈移位寄存器 ，反馈函数f(x)=b 2 ⊕ b 3 ， 初 态为100，输出序列生成过程如下： 状态 输出位 b 3 b 2 b 1 0 011011 0 状态 输出位 100 0 110 0 f(b b b )=b ⊕ b 110 0 3 2 1 011 1 101 1 110 0 f(b 1,b 2,b 3)=b 2 ⊕ b 3 110 0 011 1 101 1 110 0 移位寄存器的周期是指输出序列中连续且重复出现部 分的长度 上面输出序列周期长度为 110 0 12 。上面输出序列周期长度为 3
线性反馈移位寄存器 线性反馈移位寄存器((liner feedback shift register,.LFSR) 是一种特殊的FSR,其反馈函数是移位寄存器中某些位的异或， 参与运算的这些位叫做抽头位。其一般组成结构如下图所示。 In In-L b,b +输出位O 反馈函数f 特征：n-级LFSR的有效状态为2n1(全0状态除外，因全0状 态的输出序列一直为全0)，也即理论上能够产生周期为2n1 的伪随机序列。但要产生最大周期的输出序列，抽头位要有 要求。 13 CNR@HEU http://machunguang.hrbeu.edu.cn
线性反馈移位寄存器 线性反馈移位寄存器(liner feedback shift register LFSR) (liner feedback feedback shift register register,LFSR) 是一种特殊的FSR，其反馈函数是移位寄存器中某些位的异或， 参与运算的这些位叫做抽头位 参与运算的这些位叫做抽头位 参与运算的这些位叫做抽头位 。 其 般组成结构如下图所示 一般组成结构如下图所示 般组成结构如下图所示 。 b b 1 … b 2 b 1 rn rn-1 … r 2 r 1 b 输出位 Oi n bn- 1 … b 2 b 1 输出位 i 反馈函数 f 特征： n- 级 LFSR的有效状态为 2 n -1（全 0状态除外，因全 0 状 反馈函数 f 态的输出序列一直为全 0），也即理论上能够产生周期为 2 n -1 的伪随机序列。但要产生最大周期的输出序列，抽头位要有 要求 13
线性反馈移位寄存器（举例) 一个3-级的反馈移位寄存器，反馈函数fx)=b1⊕b3,初 态为100，输出序列生成过程如下： 状态 输出位 100: 0 b3 b2 b1 00111010 110: 0 111- 1 011- 1 101- 1 fb1b2bg)=b1⊕b3 010 0 001 100 0回到了寄存器的初始状态 上面输出序列周期长度为7。已达到最大周期23-1=7 √抽头位对输出周期长度的影响起着决定性的作用。 初态对输出周期长度没影响。 CNR@HEU http://machunguang.hrbeu.edu.cn
线性反馈移位寄存器（举例） 一个 3-级的反馈移位寄存器，反馈函数f(x)=b1⊕b3，初 态为100 ，输出序列生成过程如下： 状态 输出位 b 3 b 2 b 1 0011101 0 100 0 110 0 111 1 f(b 1,b 2,b 3)=b 1 ⊕ b 3 011 1 101 1 010 0 9 上面输出序列周期长度为7 010 0 001 1 100 0 9 上面输出序列周期长度为7。 9 抽头位对输出周期长度的影响起着决定性的作用。 14 9 初态对输出周期长度没影响。 回到了寄存器的初始状态 已达到最大周期2^3-1=7
m序列的简介 线性反馈移位寄存器输出序列的性质完全由其反馈函 数决定。n级线性反馈移位寄存器最多有2个不同的状态。 若其初始状态为0，则其状态恒为0。若其初始状态非0， 则其后继状态不会为0。因此，n级线性反馈移位寄存器的 状态周期小于等于21，其输出序列的周期与状态周期相 等，也小于等于2n1。 只要选择合适的反馈函数便可使序列的周期达到最大值 2n.1,周期达到最大值的序列称为m序列。 15 CNR@HEU http://machunguang.hrbeu.edu.cn
m序列的简介 线性反馈移位寄存器输出序列的性质完全由其反馈函 数决定。n级线性反馈移位寄存器最多有2n个不同的状态。 若其初始状态为0，则其状态恒为0。若其初始状态非0， 则其后继状态不会为 则其后继状态不会为0。因此，n级线性反馈移位寄存器的 级线性反馈移位寄存器的 状态周期小于等于2n-1，其输出序列的周期与状态周期相 等，也小于等于2n-1。 只要选择合适的反 只要选择合适的反馈数 使 大 函 便可使序列的周期达到最 序列的周期达到最大值 2n-1，周期达到最大值的序列称为m序列。 15
m-序列特性 0,1平衡性：在一个周期内，0、1出现的次数分别为2-11 和2n-1。 。游程特性：在一个周期内，总游程数为2n1;对1sisn-2,长 为的游程有2n-i1个，且0、1游程各半；长为n-1的0游程一 个，长为n的1游程一个。例如00110111，y依次称为0的2游程，1的2游程，0 的1游程，和1的3游程，总游程数为4 。x}的自相关函数为 1,t=0 R)= 0<x≤2”-2 20-1 R0=4。D,j=2,p为序列x的用期。 其中：A=0≤i<p,X,=x4D=k0≤i<P,X,≠X+ 16 CNR@HEU http://machunguang.hrbeu.edu.cn
m-序列特性 0,1平衡性：在一个周期内，0、1出现的次数分别为2n-1-1 和2n-1。 游程特性：在一个周期内，总游程数为2n-1；对1≤i≤n-2，长 为i的游程有2n-i-1个，且0、1游程各半；长为n-1的0游程一 个，长为n的1游程一个。 {xi}的自相关函数为 ⎧1 0 τ ( ) 1, 0 1 ,0 2 2 2 1 n n R τ τ τ ⎧ = ⎪ =⎨ < ≤ − − −⎪⎩ 2 1 }x{p;,2,1j,)j( = i − = " 为序列 的周期。 P DA R 16 其中： + jii ≠<≤==<≤= + jii ,}xx,pi0{D,}xx,pi0{A 例如00110111,y依次称为0的2游程，1的2游程，0 的1游程，和1的3游程, 总游程数为4