《非线反馈移位寄存器探讨》由会员分享，可在线阅读，更多相关《非线反馈移位寄存器探讨（20页珍藏版）》请在金锄头文库上搜索。
1、非线性反馈移位寄存器探讨戚文峰戚文峰23eSTREAMeSTREAM中中中中TriviumTrivium4eSTREAMeSTREAM中中中中GrainGrain5eSTREAM的特点：的特点：1.序列源的非线性序列源的非线性2.过滤函数简洁过滤函数简洁3.非线性序列代数结构刻画困难非线性序列代数结构刻画困难6目目前前关关于于非非线线性性反反馈馈移移位位寄寄存存器器序序列列(或或非非线线性性递递归归序序列列)的理论分析成果非常少的理论分析成果非常少,尽管对其研究的历史并不短尽管对其研究的历史并不短.7 Galois非线性反馈移位寄存器非线性反馈移位寄存器定义 设fi(x0,x1,xn1)是n元
2、布尔函数, i0,1,n1, n级Galois型非线性反馈移位寄存器(简称GaloisNFSR)如下图定义f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0x1xn18称F(f0(x0,xn1),fn1(x0,xn1)是NFSR的反馈函数,若i时刻时(x0,xn1)的状态为(a0(i),an1(i),则i1时刻的状态为(a0(i1),an1(i1)(f0(a0(i),an1(i),fn1(a0(i),an1(i)f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0x1xn1并称aj(aj(0),aj(1),)为寄存器xj的输出序列,记Gj(F)为xj的输出序列全体
3、.特别称x0的输出为该反馈移位寄存器输出序列.简记G(F)G0(F).9 Fibonacci非线性反馈移位寄存器非线性反馈移位寄存器(FibonacciNFSR)f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0x1xn1若f0x1,fn2xn1,并令f(x0,xn1)fn1(x0,xn1).以f为反馈函数的n级FibonacciNFSR如右图,x0的输出序列全体记为G(f).x0x1xn1f(x0,xn1)10 GaloisNFSR与与FibonacciNFSR的等价问题的等价问题设F(f0(x0,xn1),fn1(x0,xn1)是GaloisNFSR的反馈函数,考虑是否存在
4、f(x0,xn1)和0in1,使得G(f)Gi(F)f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0x1xn1x0x1xn1f(x0,xn1)11ElenaDubrova(瑞典瑞典)研究了该问题研究了该问题定义设n级GaloisNFSR以F(f0(x0,xn1),fn1(x0,xn1)为反馈函数,定义其反馈有向图为:以n个寄存器x0,x1,xn1为n个顶点,对于xi和xj(i和j可以相同),若fj(x0,xn1)含变元xi,则xi到xj有一有向弧,记为edge(xi,xj),此时,称xi为xj的先导,xj为xi的后继.E.Dubrova,“ATransformationfro
5、mtheFibonaccitotheGaloisNLFSRs,”IEEETransactionsonInformationTheory,vol.55,pp.5263-5271,Nov.2009.12设f0(x0,x3)x1f1(x0,x3)x0x2f2(x0,x3)x0x3f3(x0,x3)x0x1x3x0x1x2x313定定义义设U是n级NLFSR的反馈有向图,xj是U中一个顶点,若xj有唯一的先导xi,则删除顶点xj,对xj的每个后继xk,edge(xj,xk)由edge(xi,xk)代替,得到一个新的有向图,这个图的变换称为代替变换.x0x1x2x3x1x2x3对U的每个顶点重复进行代替
6、变换,直到不能再进行代替变换(即所到的图中没有顶点有唯一的先导),变换所得的有向图称为U的既约反馈图.14定定理理1给定n级NFSR,U是其反馈图,若U可以既约成单点xi,则xi的输出是一个n级FibonacciNFSR,即存在n元布尔函数g(x0,x1,xn1),使得xi的任意一条输出序列ai(ai(0),ai(1),)满足ai(kn)g(ai(k),ai(kn1),k0,1,.E.Dubrova,“ATransformationfromtheFibonaccitotheGaloisNLFSRs,”IEEETransactionsonInformationTheory,vol.55,pp.5263-5271,Nov.2009.151617181920谢谢 谢谢 ! !
