1 例 2-3
已知线性反馈移位寄存器的初始状态为 ({1,0,0,1,1})，转移函数为 (f(a_1,a_2,a_3,a_4,a_5)=a_1oplus a_4)，求输出状态和周期。
1.1 图标法
画表：
| (a_1) | (a_2) | (a_3) | (a_4) | (a_5) | (f) |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
周期为 31，输出序列为 1001101001000010101110110001111。
1.2 程序法
#include<bits/stdc++.h>
#define n 5
using namespace std;
int main()
{
bitset<n>bint(19);
bitset<n>str(bint);
string s1;
cout << "初始状态为："<<bint.to_string() << endl;
int co=0;
do
{
s1 += bint[4]+'0';
int j = bint[4] ^ bint[1];
bint.operator<<=(1);
bint[0] = j;
co++;
}
while (str.to_string() != bint.to_string());
cout<<"输出序列为："<<s1<<endl;
cout<<"周期为："<<co<<endl;
return 0;
}
运行结果：
1.3 特征多项式法
其特征多项式为 (p(x)=x^4+x+1)，其输出序列的递推关系为 (a_k=a_{k-2}oplus a_{k-5}，k>=5)
则可以轻松得到输出序列 1001101001000010101110110001111。
相比之下这种方法比较简单。
2 习题 2.1
3级线性反馈寄存器在(c_3=1)时可有 4 种线性反馈函数，设其初始状态 ({a_1,a_2,a_3}=(1,0,1))，求各线性反馈寄存器的输出序列及周期。
解：其特征多项式可能为 (p(x)=x+1)、(p(x)=x^3+x+1)、(p(x)=x^2+x+1)、(p(x)=x^3+x^2+x+1)，依次讨论：
3 习题 2.3
设 (n=4，f(a_1,a_2,a_3,a_4)=a_1oplus a_2oplus a_3oplus a_4)，初始状态为 ((a_1,a_2,a_3,a_4)=(1,1,0,1))，求此非线性反馈移位寄存器的输出序列及周期。
解：
| (a_1) | (a_2) | (a_3) | (a_4) | (f) |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
输出序列为 11011101……，周期为 4。
4 习题 2.4
设密钥流是由 (m=2s) 级 LFSR 产生，其前 (m+2) 个比特是 ((01)^{s+1})，即 (s+1) 个 (01)。问第 (m+3) 个比特有无可能是 (1)，为什么？
解：
由题知该 LFSR 状态转移图为
| (f_1) | (0) | (1) |
|---|---|---|
| (s_0) | 1 | - |
| (s_1) | - | 0 |
| (f_2) | (0) | (1) |
|---|---|---|
| (s_0) | (s_1) | - |
| (s_1) | - | (s_0) |
输出序列的周期为 2，输出序列为 01 的循环，且第 (m+2) 个比特为 1 ，由状态转移方程得第 (m+3) 个比特为 0，不可能为 1。
5 习题 2.5
设密钥流是由 n 级 LFSR 产生，其周期为 (2^n-1)，(i) 是任一正整数，在密钥流中考虑一下比特对：
((S_{i},S_{i+1}),(S_{i+1},S_{i+2}),cdots ,(S_{i+2^n-3},S_{i+2^n-2}),(S_{i+2^n-2},S_{i+2^n-1}))
问有多少形如 ((S_{i},S_{i+1})=(1,1)) 的比特对？证明你的结论。
解：
共 (((i+2^n-2)-(i))/2=(2^{n-1}-1)) 对比特对，包含的比特位总数 (=2^n-1) ，为 1 周期
假设前 (2^{n-2}-1) 对比特对均为形如 ((S_{i},S_{i+1})=(0,0)) 的比特对，由定理 2-7 可得，({1}) 出现的次数为 $ 2^n-1 - {0出现的次数} = 2^{n-1}$，即剩下的比特对均为形如
((S_{i},S_{i+1})=(1,1)) 的比特对，即答案为 (2^{n-2})。
下面证明一般性：
由定理 2-7-(2) 可得，长为 (i) 的游程有 (2^{n-i-1}/2) 个，且 (0、1) 各半，长为 (n) 的 (1) 游程一个而长为 (i) 的 (1) 游程，可组成 (i-1) 个形如 ((S_{i},S_{i+1})=(1,1)) 的比特对。
(N=sum_{i=2}^{n-2}2^{n-i-1}/2*(i-1)+n=2^{n-2})
6 习题 2.6
已知流密码的密文串 (1010110110) 和明文串 (0100010001) ，而且已知密钥流是使用三级线性反馈移位寄存器产生的，试破译该密码系统。
解：参考例 2-6 ，将密文串与明文串异或运算得到密钥流 (1110100111) ，取密文串与明文串前六个字符建立如下方程
7 习题 2.7
若 GF(2) 上的二元加法流密码的密钥生成器是 n 级线性反馈移位寄存器，产生的密钥是 m 序列。2.5 节已知，敌手若是知道一段长为 (2n) 的明密文对就可破译密钥流产生器。如果敌手仅仅知道长为 (2n-2) 的明密文对，问如何破译密钥流生成器。
解：敌手对于未知的 (2n-1，2n) 穷举可能的情况为 ({00,01,10,11}) ，对 4 种情况逐一尝试，即可破译。
8 习题 2.8
设 JK 触发器中 ({a_k}) 和 ({b_k}) 分别为 3 级和 4 级 m 序列密，且
求输出序列 ({c_k}) 及周期。
解
(gcd(3,4)=1，周期 p=(2^3-1)*(2^4-1)=7*15=105)
由JK触发器的表达式
令 (c_{-1}=0) 输出序列为:{110010010101111110100101100011110001100100111110010101101111110101100010111110100100101111110101101100111}
C++ 实现 JK 触发器:
#include<bits/stdc++.h>
#define N 105
using namespace std;
int main(){
string a="1110100";
string b="001011011011000";
while(a.size()<=N)a+=a;
while(b.size()<=N)b+=b;
int tmp=a[0]-'0';
cout<<tmp;
for(int i=1;i<N;++i,tmp=tmp==0?a[i]-'0':b[i]=='0'?1:0)cout<<tmp;
return 0;
}
p.s. JK触发器好像在数电里学过……(望天)
9 习题 2.9
设基本钟控序列产生器钟 ({a_k}) 和 ({b_k}) 分别为 2 级和 3 级 (m) 序列，且
({a_k}=10101cdots)
({b_k}=10011011001101cdots)
求输出序列 ({c_k}) 及周期。
解:
序列 ({a_k}) 的周期为 3，序列 ({b_k}) 的周期为 7，则序列 ({c_k}) 的周期为 (3*7=21)
输出序列为：100011100111000111011
C++实现：
#include<bits/stdc++.h>
#define N 21
using namespace std;
int main(){
string a="101";
string b="1001101";
while(a.size()<=N+1)a+=a;
while(b.size()<=N+1)b+=b;
int j=0;
int tmp=b[j]-'0';
for(int i=0;i<N;++i){
cout<<tmp;
if(a[i]=='1')tmp=b[++j]-'0';
}
return 0;
}
10 习题 2.2
设 n 级线性反馈移位寄存器的特征多项式为 (p(x))，初始状态为 ((a_1,a_2,cdots ,a_n)=(00cdots 01))，证明输出序列的周期等于 (p(x)) 的阶
11
