非线反馈移位寄存器探讨ppt课件

1、戚文峰戚文峰2345eSTREAM的特点：的特点：1.序列源的非线性序列源的非线性2.过滤函数简约过滤函数简约3.非线性序列代数构造描写困难非线性序列代数构造描写困难6目前关于非线性反响移位存放器序列目前关于非线性反响移位存放器序列(或非线性递归序或非线性递归序列列)的实际分析成果非常少的实际分析成果非常少,虽然对其研讨的历史并不短虽然对其研讨的历史并不短.7 Galois非线性反响移位存放器非线性反响移位存放器定义 设fi(x0, x1, xn1)是n元布尔函数, i 0,1, n 1, n级Galois型非线性反响移位存放器(简称Galois NFSR)如以下图定义f0(x0,xn1)f1

2、(x0,xn1)fn1(x0,xn1)x0 x1xn18称F ( f0(x0, xn1), fn1(x0, xn1)是NFSR的反响函数, 假设i时辰时(x0, xn1)的形状为(a0(i), an1(i), 那么i 1时辰的形状为(a0(i 1), an1(i 1) ( f0(a0(i), an1(i) , fn1(a0(i), an1(i)f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0 x1xn1并称aj (aj(0), aj(1),)为存放器xj的输出序列, 记Gj(F)为xj的输出序列全体. 特别称x0的输出为该反响移位存放器输出序列. 简记G(F) G0(F).9

3、 Fibonacci非线性反响移位存放器非线性反响移位存放器(FibonacciNFSR)f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0 x1xn1 假 设 f 0 x 1 , , f n 2 x n 1 , 并 令f(x0, xn1) fn1(x0, xn1).以f为反响函数的n级Fibonacci NFSR如右图,x0的输出序列全体记为G( f ). x0 x1xn1f(x0,xn1)10 GaloisNFSR与与FibonacciNFSR的等价问题的等价问题 设F ( f0(x0, xn1), fn1(x0, xn1)是Galois NFSR的反响函数, 思索能否存在

4、f(x0, xn1)和0 i n 1, 使得 G( f ) Gi(F)f0(x0,xn1)f1(x0,xn1)fn1(x0,xn1)x0 x1xn1x0 x1xn1f(x0,xn1)11ElenaDubrova(瑞典瑞典)研讨了该问题研讨了该问题定义 设n级Galois NFSR以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为x

5、j 的先导, xj 为 xi 的后继.E. Dubrova, “A Transformation from the Fibonacci to the Galois NLFSRs, IEEE Transactions on Information Theory, vol.55, pp.5263-5271, Nov.2021.12设f0(x0, x3) x1f1(x0, x3) x0 x2f2(x0, x3) x0 x3f3(x0, x3) x0 x1x3x0 x1x2x313定义定义设设U是是n级级NLFSR的反响有向图的反响有向图,xj是是U中一个顶点中一个顶点,假设假设xj有有独一的先导独一

6、的先导xi,那么删除顶点那么删除顶点xj,对对xj的每个后继的每个后继xk,edge(xj,xk)由由edge(xi,xk)替代替代,得到一个新的有向图得到一个新的有向图,这个图的变换称为替代变换这个图的变换称为替代变换.x0 x1x2x3x1x2x3对U的每个顶点反复进展替代变换, 直到不能再进展替代变换(即所到的图中没有顶点有独一的先导), 变换所得的有向图称为U的既约反响图.14 定理1 给定n级NFSR, U是其反响图, 假设U可以既约成单点xi, 那么x i 的 输 出 是 一 个 n 级 F i b o n a c c i N F S R , 即 存 在 n 元 布 尔 函 数g(x0, x1, xn1), 使得xi的恣意一条输出序列ai (ai(0), ai(1),)满足ai(k n) g(ai(k ), ai(k n 1), k 0,1,.E. Dubrova, “A Transformation from the Fibonacci to th