第二节
1
基本概念和性质
反馈移位寄存器, 特别线性反馈移位寄存器是许多密钥序列生成器的重要部件, 这一节引进线性反馈移位寄存器的模型, 并用数学(特别是代数)工具描述线性反馈移位寄存器.
2
设n是正整数, n级反馈移位寄存器的模型见下图
a k+n−1 a k+n−2……… a k+1a k输出
f (x n,…, x2, x1)
反馈函数其中f(x1,…, x n)是一逻辑函数, 即f(x1,…, x n)∈2[x1,…, x n]这里2= {0, 1}表示二元域, n≥ 1.
3
当f(x1,…, x n)是线性函数时, 即
f(x1, x2, … , x n) =c1x1+c2x2+ … +c n x n, c i∈2,
称对应的反馈移位寄存器为线性反馈移位寄存器(简称LFSR), 所产生的序列称为线性(反馈)移位寄存器序列, 简记为LFSR序列.
4
5此时所产生的序列适合关系式
a n +k = 1
0n i −=∑c n −i a k +i , k = 0, 1, 2, ….
并称序列a = (a 0, a 1,…)为n 级线性递归序列。
线性递归序列是LFSR 序列的数学描述, 但为书写简便, 以后在称谓上我们就用LFSR 序列.