《非線反饋移位寄存器探討》由會(huì)員分享，可在線閱讀，更多相關(guān)《非線反饋移位寄存器探討（20頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、戚 文 峰 2 3 4 5 eSTREAM的特點(diǎn)： 1.序列源的非線性2.過濾函數(shù)簡(jiǎn)潔3.非線性序列代數(shù)結(jié)構(gòu)刻畫困難 6 目前關(guān)于非線性反饋移位寄存器序列(或非線性遞歸序列)的理論分析成果非常少,盡管對(duì)其研究的歷史并不短. 7 Galois非線性反饋移位寄存器定義 設(shè)fi(x0,x1,xn1)是n元布爾函數(shù),i0,1,n1,n級(jí)Galois型非線性反饋移位寄存器(簡(jiǎn)稱GaloisNFSR)如下圖定義f0(x0,xn1)f1(x0,xn1)f n1(x0,xn1)x0 x1 xn1 8 稱F(f0(x0,xn1),fn1(x0,xn1)是NFSR的反饋函數(shù),若i時(shí)刻時(shí)(x0,xn1)的狀態(tài)為(a
2、0(i),an1(i),則i1時(shí)刻的狀態(tài)為(a0(i1),an1(i1)(f0(a0(i),an1(i),fn1(a0(i),an1(i)f 0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0 x1 xn1并稱aj(aj(0),aj(1),)為寄存器xj的輸出序列,記Gj(F)為xj的輸出序列全體.特別稱x0的輸出為該反饋移位寄存器輸出序列.簡(jiǎn)記G(F)G0(F). 9 Fibonacci非線性反饋移位寄存器(FibonacciNFSR)f 0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0 x1 xn1若f0 x1,fn2xn1,并令f(x0,xn1)fn1(x0
3、,xn1).以f為反饋函數(shù)的n級(jí)FibonacciNFSR如右圖,x0的輸出序列全體記為G(f). x0 x1 xn1f(x0,xn1) 10 GaloisNFSR與FibonacciNFSR的等價(jià)問題設(shè)F(f0(x0,xn1),fn1(x0,xn1)是GaloisNFSR的反饋函數(shù),考慮是否存在f(x0,xn1)和0in1,使得G(f)Gi(F)f 0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0 x1 xn1 x0 x1 xn1f(x0,xn1) 11 ElenaDubrova(瑞典)研究了該問題定義設(shè)n級(jí)GaloisNFSR以F(f0(x0,xn1),fn1(x0,xn1
4、)為反饋函數(shù),定義其反饋有向圖為:以n個(gè)寄存器x0,x1,xn1為n個(gè)頂點(diǎn),對(duì)于xi和xj(i和j可以相同),若fj(x0,xn1)含變?cè)獂i,則xi到xj有一有向弧,記為edge(xi,xj),此時(shí),稱xi為xj的先導(dǎo),xj為xi的后繼. E.Dubrova,“ATransformationfromtheFibonaccitotheGaloisNLFSRs,”IEEETransactionsonInformationTheory,vol.55,pp.5263-5271,Nov.2009. 12 設(shè)f0(x0,x3)x1f1(x0,x3)x0 x2f2(x0,x3)x0 x3f3(x0,x3)
5、x0 x1x3 x0 x1x2 x3 13 定義設(shè)U是n級(jí)NLFSR的反饋有向圖,xj是U中一個(gè)頂點(diǎn),若xj有唯一的先導(dǎo)xi,則刪除頂點(diǎn)xj,對(duì)xj的每個(gè)后繼xk,edge(xj,xk)由edge(xi,xk)代替,得到一個(gè)新的有向圖,這個(gè)圖的變換稱為代替變換.x0 x1x 2 x3 x1x2 x3 對(duì)U的每個(gè)頂點(diǎn)重復(fù)進(jìn)行代替變換,直到不能再進(jìn)行代替變換(即所到 的圖中沒有頂點(diǎn)有唯一的先導(dǎo)),變換所得的有向圖稱為U的既約反饋圖. 14 定理1給定n級(jí)NFSR,U是其反饋圖,若U可以既約成單點(diǎn)xi,則xi的輸出是一個(gè)n級(jí)FibonacciNFSR,即存在n元布爾函數(shù)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. 15 16 17 18 19 20
非線反饋移位寄存器探討
