第二章作业参考答案
1．3 级线性反馈移位寄存器在 c
3
＝1 时可有 4 种线性反馈函数，设其初始状态为(a
1
,a
2
,a
3
)=(1,0,1)，求各
线性反馈函数的输出序列及周期。
解：此时线性反馈函数可表示为 f(a
1
,a
2
,a
3
)=a
1
c
2
a
2
c
1
a
3
当 c
1
＝0，c
2
＝0 时，f(a
1
,a
2
,a
3
)=a
1
c
2
a
2
c
1
a
3
＝a
1
，
输出序列为 101101…， 周期＝3
当 c
1
＝0，c
2
＝1 时，f(a
1
,a
2
,a
3
)=a
1
c
2
a
2
c
1
a
3
＝a
1
a
2
，
输出序列为 10111001011100…，周期＝7
当 c
1
＝1，c
2
＝0 时，f(a
1
,a
2
,a
3
)=a
1
c
2
a
2
c
1
a
3
＝a
1
a
3
，
输出序列为 10100111010011…，周期＝7
当 c
1
＝1，c
2
＝1 时，f(a
1
,a
2
,a
3
)=a
1
c
2
a
2
c
1
a
3
＝a
1
a
2
a
3
，
有输出序列为 1010…， 周期＝2
2．设 n 级线性反馈移位寄存器的特征多项式为 p(x)，初始状态为(a
1
,a
2
, …,a
n-1
,a
n
)=(00…01)，证明输出序
列的周期等于 p(x)的阶
证：设 p(x)的阶为 p，由定理 2-3，由 r|p，所以 rp
设 A(x)为序列{a
i
}的生成函数，并设序列{a
i
}的周期为 r，则显然有 A(x)p(x)＝
(x)
又 A(x)＝a
1
+a
2
x+…+a
r
x
r-1
+x
r
(a
1
+a
2
x+…+a
r
x
r-1
)+(x
r
)
2
(a
1
+a
2
x+…+a
r
x
r-1
)+…
＝a
1
+a
2
x+…+a
r
x
r-1
/(1-x
r
)＝a
1
+a
2
x+…+a
r
x
r-1
/(x
r
-1)
于是 A(x)=(a
1
+a
2
x+…+a
r
x
r-1
)/(x
r
-1)＝
(x)/p(x)
又(a
1
,a
2
, …,a
n-1
,a
n
)=(00…01)
所以 p(x)(a
n
x
n-1
+…+a
r
x
r-1
)=
(x)(x
r
-1) 即 p(x)x
n-1
(a
n
+…+a
r
x
r-n
)=
(x)(x
r
-1)
由于 x
n-1
不能整除 x
r
-1，所以必有 x
n-1
|
(x)，而
(x)的次数小于 n，所以必有
(x)＝x
n-1
所以必有 p(x)|(x
r
-1)，由 p(x)的阶的定义知，阶 pr
综上所述：p＝r #
3．设 n＝4，f(a
1
,a
2
,a
3
,a
4
)=a
1
a
4
1a
2
a
3
，初始状态为(a
1
,a
2
,a
3
,a
4
)＝(1,1,0,1)，求此非线性反馈移位寄存器
的输出序列及周期。
解：由反馈函数和初始状态得状态输出表为
(a
4
a
3
a
2
a
1
) 输出 (a
4
a
3
a
2
a
1
) 输出
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 0 0 1 0 1 1 1（回到初始状态）
所以此反馈序列输出为：11011…周期为 5
4．设密钥流是由 m＝2s 级 LFSR 产生，其前 m+2 个比特是(01)
s+1
，即 s＋1 个 01。问第 m+3 个比特有无
可能是 1，为什么？
解：不能是 1。
可通过状态考察的方法证明以上结论。
首先 m 级 LFSR 的状态是一个 m 维的向量，则前 m 个比特构成一个状态 S
0
，可表示为(01)
s
，
第 m＋1 个比特是 0，所以 S
0
的下一个状态是 S
1
＝(10)
s
，
第 m＋2 个比特是 1，所以 S
1
的下一个状态是 S
2
＝(01)
s
＝S
0
，回到状态 S
0
，
所以下一个状态应是 S
3
=S
1
＝(10)
s
，也即第 m+3 个比特应该为 0。
5．设密钥流是由 n 级 LFSR 产生，其周期为 2
n
－1，i 是任一正整数，在密钥流中考虑以下比特对
(S
i
, S
i+1
), (S
i+1
, S
i+2
), …, (S
i+2
n
－
3
, S
i+2
n
－
2
), (S
i+2
n
－
2
, S
i+2
n
－
1
),
love87421
- 粉丝: 0
- 资源: 6万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减4.47元 开通VIP
相关推荐
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0
最新资源