第二节
线性反馈移位寄存器序列
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 序列.
定义4.1 设a是LFSR序列, 称a的次数最小的特征多项式为a的极小多项式.
定理4.1 设a是LFSR序列, 则a的极小多项式是唯一的.
6
进一步, 设m
(x)是a的极小多项式, 则f(x)是a的一
a
(x)|f(x).
个特征多项式当且仅当m
a
显然, LFSR序列的极小多项式刻画了生成该序列的最短LFSR,而定理4.1进一步说明, 这样的最短LFSR是唯一的.
7
8
设f (x )是F 2上n 次多项式, a =(a 0,a 1,a 2,…)是以f (x )为特征多项式的线性递归序列, 则a 由前n 比特a 0,a 1,…,a n ?1唯一确定.
例如: 设f (x )=x 3+x +1, a =(0,1,1,…)是以f (x )为特征多项式的线性递归序列, 则
a =(0,1,1,1,0,0,1,0,1,1,1,…).
定义4.2 对于F
上序列a, 若存在非负整数k和正
2
整数T, 使得对任意i≥k, 都有a
=a i, 则称a是准周
i+T
期序列, 最小这样的T称为a的周期, 记为per(a); 若k=0, 则称a是(严格)周期序列.
注4.1 设per(a)=T, R是正整数, 若对任意i≥k, 有a i+R=a i, 则T|R.
9
显然, LFSR是一种有限状态机, 因此, 由LFSR生成的序列必然是准周期的. 下面的定理表明反之也是成立的, 即所有的准周期序列都可用LFSR来生成.
定理4.2 a是准周期序列当且仅当a是LFSR序列.
10
利用序列的极小多项式可以判断序列是否严格周期.
(x)是a的极小多项定理4.3 设a是LFSR序列, m
a
(0)≠0.
式, 则a是周期序列当且仅当m
a
11
进一步, 序列的周期由其极小多项式的周期完全确定.
定理4.4 设a是周期序列, f(x)是它的极小多项式, 则per(a)=per(f(x)).
12
注4.2 若a是非严格周期序列, 定理4.4也成立. 由于非周期序列总可以转化成周期序列, 并且实际中使用的序列也都是周期序列, 故后面的讨论仅针对周期序列.
13
推论4.1 设f(x)是F
上不可约多项式, 则以f(x)为
2
特征多项式的非零序列a有per(a)=per(f(x)).
14
最后, 我们给出LFSR序列的根表示.
[x]是n次无重因子多项式,f(0)≠0, 定理4.5 设f(x)∈F
2
F2m是f(x)的分裂域, α1,α2,…,αn∈F2m是f(x)的全部根, 则
,a1,…), 存在唯对任意以f(x)为特征多项式的序列a=(a
一一组β
,β2,…,βn∈F2m, 使得
1
a k=β1α1k+β2α2k+???+βnαn k, k≥0.
15
反之,设β
,β2,…,βn∈F2m,若
1
a k=β1α1k+β2α2k+???+βnαn k∈F2, k≥0,
,a1,…)以f(x)为特征多项式, 且f(x)是a的极则a=(a
≠0, 1≤i≤n.
小多项式当且仅当β
i
16
m-序列
注意到LFSR总是将0状态转化成0状态, 因此对于一个n级LFSR, 最多可输出周期为2n?1的周期序列.
定义4.3 设a是n级LFSR序列, 若per(a)=2n?1, 则称a为n级最大周期序列, 简称为n级m-序列.
17
由定义显然有
定理4.6 设a是n级LFSR序列, 则a是n级m-序列当且仅当a的极小多项式是n次本原多项式
18
定理4.7 若a是以n次本原多项式f(x)为极小多项式的m-序列, 则0, a, La,…, L2n?2a是以f(x)为特征多项式的序列全体.
定理4.7说明, 由同一个本原多项式生成的两条m-序列彼此平移等价. 由定理4.7, 容易证明m-序列满足以下平移可加性.
19
定理4.8 设a是n级m-序列, 则对于非负整数s和t, 有L s a+L t a=L k a或0, 其中0≤k≤2n?2.
注4.3 实际上, 定理4.8给出的平移可加性是m-序列的特有性质, 即对于周期为T的序列a, 非负整数s和t, 若L s a+L t a=L k a或0, 0≤k≤2n?2, 则a是m-序列.
20
第三章习题参考答案 1．画出以1)(2 4 6 +++=x x x x f 为联接多项式的线性移位寄存器逻辑框图，及其对应的状态图。 解：由1)(2 46+++=x x x x f ，得反馈函数为531621),,,(x x x x x x f ++=Λ，故 （1）逻辑框图： （2）状态图： 状态圈-1： 状态圈-2： 状态圈-3： 状态圈-4： 状态圈-5： 状态圈-6： 状态圈-7： 状态圈-8：
状态圈-9： 状态圈-10： 状态圈-11： 状态圈-12： 2．已知图3-2所示的7级线性反馈移位寄存器： 图3-2 （1）绘出该移位寄存器的线性递推式，联接多项式及特征多项式。 （2）给出状态转移矩阵。 （3）设初态为（1 1 1 1 1 1 1），给出输出序列a 。 解：(1)由逻辑框图得，递推式为： k k k k a a a a ++=+++357 ()0≥k 。 联接多项式为：7 4 2 1)(x x x x f +++=。 特征多项式为：7531)(~ x x x x f +++=
（2）状态转移矩阵：? ? ???? ? ?? ? ? ??0100000 101000000010001000100 000001000000011000000。 （3）输出序列：)111111111(ΛΛ=- a 。 3．设5级线性反馈移位寄存器的联接多项式为1)(2 5 ++=x x x f ，初态为（10101）。求输出序列a 。 解：由联接多项式得，反馈函数为：41521),,,(x x x x x f +=Λ。故以)10101(为初态的状态转移图为： 10101 01010001010001000001100000100000100100100100110100110100110100110100111100111100111101111101111001110001110001110000110010110110111110101110101110101110101→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→ 由此可得，输出序列为：=a 44444443444444421一个周期 0110100100000011111001010111011…。 4．证明：n 级线性反馈移位寄存器的状态转移变换是n 维线性空间n F 2上的线性变换。 证明：设f T 为n 级线性移位寄存器的状态转移变换，对n F 2,∈?βα，令),,,(110-=n a a a Λα， ),,,(110-=n b b b Λβ，有： ),,,(),,,()(121110∑=--==n i i n i n f f a c a a a a a T T ΛΛα， ),,,(),,,()(1 21110∑=--==n i i n i n f f b c b b b b b T T ΛΛβ。 ) ()() ,,,(),,,() )(,,,() ,,,()(1 211 2112211111100βαβαf f i n n i i i n n i i n i i n i n i n n f f T T b c b b a c a a b a c b a b a b a b a b a T T +=+=+++=+++=+-=-==----∑∑∑ΛΛΛΛ 对 2F k ∈?， ))((),,,(),,,()(1 21110ααf i n n i i n f f T k a c k ka ka ka ka ka T k T ===-=-∑ΛΛ。 故n 级线性反馈移位寄存器的状态转移变换是n 为线性空间n F 2上的线性变换。
最近一直在研究信道编码，发现在信道编码里面有一个电路比较重要也比较有趣，那就是线性反馈移位寄存器LFSR ，相信大家对LFSR 电路也不陌生了,在通信领域lfsr有着很广泛的应用,比如说M序列,扰码,信道编码,密码学这方面都有很广泛的应用,LFRS的结构一般如下图： 其中他需要一个生成多项式为: 这个多项式是一个本原多项式，然后知道这个电路有一些有意思的性质，下面我以m = 3 来做个例子具体的电路图如下所示： 假设开始的时候（D2，D1，D0 ）= （0，0，1），那么每过一个时钟周期会进行跳变一次， 可以看到具体的跳变如下所示：
然后我们可以看到这个计数器循环起来了，很好玩吧，无论进入那样一个状态除了0之外，都可以循环着回来，其实这里就相当于了一个3bit的伪随机数，很有意思，不是所有的多项式都有这个特性，我们现在在从数学上面来看看这个问题,其实最上面的电路是可以看成是一个除法电路，在Galois域的一个除法电路。现在假设的是R（x）是寄存器中剩余的数据，M(x)是输入的码字多项式，然后数学公式可以表示成： 然后我分别计算出了Ｍ（ｘ）的各种情况，
然后我们单独进行一下７次方的运算 发现７次方的运算和０次的时候的余数是一样的 然后我们发现其实在上面的电路中对多项式的除法也是可以循环起来的,可以验证的是
把这个记成 上面的式子是可以循环的,然后我又想到了CRC的计算,CRC的计算也可以通过一个除法电路来实现, 假设码子多项式为 生成多项式为 那么CRC的码字为这样我们同样可以用LFSR电路来进行实现 首先对M(x)乘以一个x的r次方,然后去去除G(x),在电路上的表现就是 所以在输入码字以后还需要多输入r拍的0这样才能使最后的CRC码字数据. 同理这个电路也可以进行CRC校验，把生成的数据全部都依次输入进这个 Love is not a maybe thing. You know when you love someone.
第二章作业参考答案1．3级线性反馈移位寄存器在c3＝1时可有4种线性反馈函数，设其初始状态为 (a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。 解：此时线性反馈函数可表示为f(a1,a2,a3)=a1?c2a2?c1a3 当c1＝0，c2＝0时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1， 输出序列为101101…，周期＝3 当c1＝0，c2＝1时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a2， …，周期＝7 当c1＝1，c2＝0时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a3， …，周期＝7 当c1＝1，c2＝1时，f(a1,a2,a3)=a1?c2a2?c1a3＝a1?a2?a3， 有输出序列为1010…，周期＝2 2．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,a n-1,a n)=(00…01)，证明输出序列的周期等于p(x)的阶 证：设p(x)的阶为p，由定理2-3，由r|p，所以r?p 设A(x)为序列{a i}的生成函数，并设序列{a i}的周期为r，则显然有A(x)p(x)＝?(x) 又A(x)＝a1+a2x+…+a r x r-1+x r(a1+a2x+…+a r x r-1)+(x r)2(a1+a2x+…+a r x r-1)+… ＝a1+a2x+…+a r x r-1/(1-x r)＝a1+a2x+…+a r x r-1/(x r-1) 于是A(x)=(a1+a2x+…+a r x r-1)/(x r-1)＝?(x)/p(x) 又(a1,a2,…,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)的阶的定义知，阶p?r 综上所述：p＝r# 3．设n＝4，f(a1,a2,a3,a4)=a1?a4?1?a2a3，初始状态为(a1,a2,a3,a4)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。 解：由反馈函数和初始状态得状态输出表为 (a4 a3 a2 a1)输出(a4 a3 a2 a1)输出 1011111111 1101101111 1110010111（回到初始状态） 所以此反馈序列输出为：11011…周期为5 4．设密钥流是由m＝2s级LFSR产生，其前m+2个比特是(01)s+1，即s＋1个01。问第m+3个比特有无可能是1，为什么？ 解：不能是1。 可通过状态考察的方法证明以上结论。 首先m级LFSR的状态是一个m维的向量，则前m个比特构成一个状态S0，可表示为(01)s， 第m＋1个比特是0，所以S0的下一个状态是S1＝(10)s， 第m＋2个比特是1，所以S1的下一个状态是S2＝(01)s＝S0，回到状态S0， 所以下一个状态应是S3=S1＝(10)s，也即第m+3个比特应该为0。 5．设密钥流是由n级LFSR产生，其周期为2n－1，i是任一正整数，在密钥流中考虑以下比特对 (S i,S i+1),(S i+1,S i+2),…,(S i+2n－3,S i+2n－2),(S i+2n－2,S i+2n－1), 问有多少形如(S j,S j+1)＝(1,1)的比特对？证明你的结论。
移位寄存器及其应用 一、实验目的 1、掌握中规模4位双向移位寄存器逻辑功能及使用方法。 2、熟悉移位寄存器的应用—实现数据的串行、并行转换和构成环形计数器。 二、原理说明 1、移位寄存器是一个具有移位功能的寄存器，是指寄存器中所存的代码能够在移位脉冲的作用下依次左移或右移。按代码的移位方向可分为左移、右移和可逆移位寄存器，只需要改变左、右移的控制信号便可实现双向移位要求。根据移位寄存器存取信息的方式不同又可分为：串入串出、串入并出、并入串出、并入并出四种形式。 本实验选用的4位双向通用移位寄存器，型号为CC40194或74LS194，两者功能相同，可互换使用，其逻辑符号及引脚排列如图8-3-3-1所示。 其中 D0、D1、D2、D3为并行输入端；Q0、Q1、Q2、Q3为并行输出端；S R为右移串行输入 C为直接无条件清零端； 端，S L为左移串行输入端；S1、S0为操作模式控制端；R CP为时钟脉冲输入端。 CC40194有5种不同操作模式：即并行送数寄存，右移(方向由Q0→Q3)，左移（方向由Q3→Q0），保持及清零。 S1、S0和R C端的控制作用如表8-3-3-1。 图8-3-3-1 CC40194的逻辑符号及引脚功能 表8-3-3－1 CC40194功能表
2、移位寄存器应用很广，可构成移位寄存器型计数器；顺序脉冲发生器；串行累加器；可用作数据转换，即把串行数据转换为并行数据，或把并行数据转换为串行数据等。本实验研究移位寄存器用作环形计数器和数据的串、并行转换。 (1)环形计数器 把移位寄存器的输出反馈到它的串行输入端，就可以进行循环移位， 如图8-3-3-2所示，把输出端 Q3和右移串行输入端S R 相连接，设初始状态Q0Q1Q2Q3＝1000，则在时钟脉冲作用下Q0Q1Q2Q3将依次变为0100→0010→0001→1000→……，如表10－2所示，可见它是一个具有四个有效状态的计数器，这种类型的计数器通常称为环形计数器。图8-3-3－2 电路可以由各个输出端输出在时间上有先后顺序的脉冲，因此也可作为顺序脉冲发生器。其状态表如表8-3-3-2所示。 表8-3-3－2 环形计数器状态表 图 8-3-3－2 环形计数器 如果将输出Q O与左移串行输入端S L相连接，即可达左移循环移位。 (2)实现数据串、并行转换 ①串行/并行转换器 串行/并行转换是指串行输入的数码，经转换电路之后变换成并行输出。 图8-3-3-3是用二片CC40194（74LS194）四位双向移位寄存器组成的七位串/并行数据转换电路。
第10章移位寄存器 本章大纲 10.1 基本移位寄存器功能 10.2 串行进入／串行输出移位寄存器 10.3 串行进入／并行输出移位寄存器 10.4 并行进入／串行输出移位寄存器 10.5 并行进入/ 并行输出移位寄存器 10.6 双向移位寄存器 10.7 移位寄存器计数器 10.8 移位寄存器应用 10.9 故障检测 10.10 关联标注的逻辑符号 10.11 CPLD简介 10.12 数字系统应用 本章学习目标 ?识别移位寄存器中数据运动的基本方式 ?解释串行进入／串行输出、串行进入／并行输出、并行进入／串行输出和并行进入/并 行输出移位寄存器是怎样运行的 ?描述双向移位寄存器怎样运行 ?确定约翰逊计数器的序列 ?设置环形计数器以产生指定序列 ?从移位寄存器中构建环形计数器 ?使用移位寄存器作为时间延迟设备 ?使用移位寄存器来实现串行到并行数据的变换器 ?实现基本移位寄存器控制的键盘译码器 ?通过用已知的测试模式“运行”系统来对数字系统进行故障检测 ?解释关联标注的ANSI/IEEE标准91-1984移位寄存器 ?描述基本的CPLD ?在系统应用中使用移位寄存器 重要术语 ?寄存器 ?级
?移位 ?载入 ?双向 ?CPLD ?逻辑阵列块(LAB) ?宏单元 简介 移位寄存器是紧密关联于数字计数器的序列逻辑电路的一种类型。寄存器主要用来存 储数字数据并且一般不具有特征内部状态序列，而计数器则具有这样的序列。但是也有例外，我们将在10.7节介绍它们。 在本章中，我们将学习移位寄存器的基本类型并展示几个应用。同时，我们还介绍了一种重要的故障检测方法。本章还介绍了复杂可编程逻辑设备(CPLD)。 固定功能逻辑器件 74HC164 74HC165 74HC174 74HC194 74HC195 可编程逻辑器件 MAX 7000 ·数字系统应用概述 数字系统应用阐释了本章中的概念。我们介绍了一个控制建筑物中警报器的安全进入系统。该系统使用两种类型的寄存器以及前几章所介绍的其他类型的设备。该系统同时还含有一个存储器，其将是第12章数字系统应用的重点。 学习本章内容可访问https://www.doczj.com/doc/3b10379382.html,/floyd。 10.1 基本移位寄存器功能 移位寄存器由一组触发器组成，在数字系统中涉及数据存储和移位方面的应用中是很 重要的。寄存器和计数器不同，除了一些特别专业的应用之外，都没有特定的状态序列。一般来说，寄存器主要用来存储和移位外部数据源进入其中的数据（1和0），并且一般不具有特征内部状态序列。 学完本节之后，你应当能够 ?解释触发器怎样存储一个数据位 ?定义移位寄存器的存储容量 ?定义寄存器的移位能力 □寄存器可以由一个或者多个用以存储和移位数据的触发器组成。 寄存器是一种具有两种基本功能的数字电路：数据存储和数据移动。寄存器的存储能
1. 3级线性反馈移位寄存器在 C 3 = 1时可有4种线性反馈函数，设其初始状态为 (a i , a 2, a 3)=(1,0,1)，求 各线性反馈函数的输出序列及周期。 解：此时线性反馈函数可表示为 f (a 1, a 2, a 3)= a C 2a 2 C 1 a 3 当 C 1 = 0, C 2= 0 时， f (ai, a 2, a 3)= :a 1 C 2a 2 C ￡3= a 1, 输出序列为 101101 …， 周期=3 当 C 1 = 0, C 2= 1 时， f (ai,a 2, a 3)= :a 1 C 2a 2 C 1 a 3= a 1 a 2, 输出序列为 0… …，周期=7 当 C 1= 1, C 2= 0 时， f (ai,a 2, a 3)= :a 1 C 2a 2 oa 3= a 1 a 3, 输出序列为 1… …，周期=7 当 C 1= 1, C 2= 1 时， f (ai,a 2, a 3)= :a 1 C 2a 2 C 1 a 3= a 1 82 a 3, 有输出序列为 1010 …， 周期=2 2. 设n 级线性反馈移位寄存器的特征多项式为 p (x )，初始状态为 (a i ,a 2,…,a n-i , a n )=(00…01)，证明输 出序列的周期等于 p (x )的阶 证：设p (x )的阶为p ,由定理2-3，由r | p ，所以r p 设A (x )为序列｛a 。的生成函数，并设序列｛a ｝的周期为r ,则显然有A (x )p (x ) = (x ) 又 A (x ) = a+a 2x +…+ax +x (a 1+a 2x +…+a 「x )+( x ) (a+a 2x +…+ax )+ … r-1 r r -1 r =a 1+a 2x +…+a r x /(1- x ) = a+a 2x +…+a 「x /( x -1) 于是 A (x )=( a+a 2x +…+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 +?? ?+ a r x )= (x )( x -1) 即 p (x )x (a n +…+ a 「x )= (x )( x -1) 由于x n-1不能整除x r -1，所以必有x n-1| (x )，而(x )的次数小于n ,所以必有 (x ) = x n-1 所以必有p (x ) | (x r -1)，由p (x )的阶的定义知，阶 p r 综上所述：p = r # 3. 设 n = 4, f ( a, a 2, a 3, a 4)= a 1 a 4 1 a 2a 3，初始状态为(a, a 2, a 3, a 4)= (1,1,0,1),求此 非线性反馈移位 寄存器的输出序列及周期。 解: 由反馈函数和初始状态得状态输出表为 (a 4 a 3 32 a 1) 输出 ( a 4 a 3 a ? 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,g 卩s + 1个01。问第m+3个比特有无可 能是1，为什么 解：不能是1。 可通过状态考察的方法证明以上结论。 首先m 级LFSR 的状态是一个 m 维的向量，则前 m 个比特构成一个状态 S 0,可表示为(01) s , 第m + 1个比特是0,所以S c 的下一个状态是 S = (10) s , 第 耐2个比特是1,所以S 1的下一个状态是 S. = (01) s = S 0,回到状态S 0, 所以下一个状态应是 S 3=S = (10) s ,也即第m+3个比特应该为0。 5?设密钥流是由n 级LFSR 产生，其周期为2n - 1, i 是任一正整数，在密钥流中考虑以下比特对 ( S , S +1), ( S +1, S +2),…,(S +2n — 3, S i +2n - 2), ( S +2〔 2, S i+二1),
第二章作业参考答案 1．3级线性反馈移位寄存器在c3＝1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。 解：此时线性反馈函数可表示为f(a1,a2,a3)=a1c2a2c1a3 当c1＝0，c2＝0时，f(a1,a2,a3)=a1c2a2c1a3＝a1， 输出序列为101101…，周期＝3 当c1＝0，c2＝1时，f(a1,a2,a3)=a1c2a2c1a3＝a1a2， 输出序列为10111001011100…，周期＝7 当c1＝1，c2＝0时，f(a1,a2,a3)=a1c2a2c1a3＝a1a3， 输出序列为10100111010011…，周期＝7 当c1＝1，c2＝1时，f(a1,a2,a3)=a1c2a2c1a3＝a1a2a3， 有输出序列为1010…，周期＝2 2．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2, …,a n-1,a n)=(00…01)，证明输出序列的周期等于p(x)的阶 证：设p(x)的阶为p，由定理2-3，由r|p，所以r p 设A(x)为序列{a i}的生成函数，并设序列{a i}的周期为r，则显然有A(x)p(x)＝(x) 又A(x)＝a1+a2x+…+a r x r-1+x r(a1+a2x+…+a r x r-1)+(x r)2(a1+a2x+…+a r x r-1)+… ＝a1+a2x+…+a r x r-1/(1-x r)＝a1+a2x+…+a r x r-1/(x r-1) 于是A(x)=(a1+a2x+…+a r x r-1)/(x r-1)＝(x)/p(x) 又(a1,a2, …,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)的阶的定义知，阶p r 综上所述：p＝r # 3．设n＝4，f(a1,a2,a3,a4)=a1a41a2a3，初始状态为(a1,a2,a3,a4)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。 解：由反馈函数和初始状态得状态输出表为 (a4 a3 a2 a1) 输出 (a4 a3 a2 a1) 输出 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个比特构成一个状态S0，可表示为(01)s， 第m＋1个比特是0，所以S0的下一个状态是S1＝(10)s， 第m＋2个比特是1，所以S1的下一个状态是S2＝(01)s＝S0，回到状态S0， 所以下一个状态应是S3=S1＝(10)s，也即第m+3个比特应该为0。 5．设密钥流是由n级LFSR产生，其周期为2n－1，i是任一正整数，在密钥流中考虑以下比特对
线性反馈移位寄存器实现产生伪随机数M序列 -----在CN03平台上，主要体现为Random功能的实现。 什么是线性反馈移位寄存器？ 数学解释这里就不作介绍了，这里我们主要理解两个词语就行，一个是线性，它是指量与量之间的一种按比例、成直线的关系。这里面有一点点的数学知识，就是说在ai∈(0,1)的存储单元，ai的个数表示为反馈移位寄存器的级，在某一个时刻，这些寄存器会有一个状态，共有2^n个状态，每个状态对应于域GF(2)上的一个N维向量,用(a1,a2,a3,……an)表示。作为某一个时刻的状态，可以用一个函数f(a1,a2,a3…..an)来表示，从而称为该反馈寄存器的反馈函数，因此线性的意思，就是指如果这个反馈函数是a1,a2,a3….an的线性函数，那么这个反馈移位寄存器，就叫做线性反馈移位寄存器，比如f(a1,a2,a3,…an)=kna1⊕kn-1a2⊕….⊕k2an-1⊕k1an,其中系数ki∈{0，1}i=(1,2,3,…,n)。 另外一个词，就是反馈，这个词在我理解，就是说需要获得下一个状态就需要通过获得一个反馈值来实现。这个反馈的值可以在接下来的两种实现LFSR的方式的解释过程中得到更深刻的理解。 为什么要使用线性反馈移位寄存器？ 使用线性反馈移位寄存器的作用： 在很多领域上都有使用到LFSR，譬如说密码学、白噪声，还有我们这里的随机功能实现，之所以把它使用到我们的radio的随机功能里面，除了它可以产生伪随机数序列实现随机播放功能之外，更重要的是我们利用了它的两个特点。其
一，只需要在代码中开辟几个byte的位置，就能够实现随机序列的产生，需要的空间很少。其二，是它的记忆功能，我们在随机的功能里面，选择了下一曲，则上一曲可以通过调整抽头数的序列来从新获得，而不需要开辟空间进行存储。怎样产生伪随机数M序列？ M序列的意思就是最大序列，专业点来说就是周期，就是这些不同的伪随机数在什么时候才会回到初始的输入状态，M序列的最大值为2^n-1，因为全0的初始状态不起作用，所以不能以全0的状态作为初始输入。 M序列就是我们在随机功能中获得的那个随机播放的序列。 它有些很好的特性： 1、通过反馈抽头数可以获得与之前输出的值的输入值，这也是我们所说的记 忆功能。 2、这些给定的反馈抽头数永远都是偶数的，而且只包括最高位，不包括最低 位。 3、还有另外一些特征，这里就不一一列出(这些规律的东西，我们只需要理解 我们用到的)。 两种LFSR的产生形式 这里有两种LFSR的实现方式，伽罗瓦(Galois)和斐波那契(Fibonacci)两种形式，也有人称为外部(External)执行方式和内部(Internal)执行方式。所以这两种方式也是有着本质的区别的。 1、伽罗瓦方式(Internal)
第二章作业参考答案 ．级线性反馈移位寄存器在＝时可有种线性反馈函数，设其初始状态为()()，求各线性反馈函数的输出序列及周期。 解：此时线性反馈函数可表示为()⊕⊕ 当＝，＝时，()⊕⊕＝， 输出序列为…，周期＝ 当＝，＝时，()⊕⊕＝⊕， 输出序列为…，周期＝ 当＝，＝时，()⊕⊕＝⊕， 输出序列为…，周期＝ 当＝，＝时，()⊕⊕＝⊕⊕， 有输出序列为…，周期＝ ．设级线性反馈移位寄存器的特征多项式为()，初始状态为(,…)(…)，证明输出序列的周期等于()的阶 证：设()的阶为，由定理，由，所以≤ 设()为序列{}的生成函数，并设序列{}的周期为，则显然有()()＝φ() 又()＝…(…)()(…)… ＝…()＝…() 于是()(…)()＝φ()() 又(, …)(…) 所以()(…)φ()() 即()(…)φ()() 由于不能整除，所以必有φ()，而φ()的次数小于，所以必有φ()＝ 所以必有()()，由()的阶的定义知，阶≤ 综上所述：＝ ．设＝，()⊕⊕⊕，初始状态为()＝()，求此非线性反馈移位寄存器的输出序列及周期。 解：由反馈函数和初始状态得状态输出表为 () 输出() 输出 （回到初始状态） 所以此反馈序列输出为：…周期为 ．设密钥流是由＝级产生，其前个比特是()，即＋个。问第个比特有无可能是，为什么？ 解：不能是。 可通过状态考察的方法证明以上结论。 第一步级的状态是一个维的向量，则前个比特构成一个状态，可表示为()， 第＋个比特是，所以的下一个状态是＝()， 第＋个比特是，所以的下一个状态是＝()＝，回到状态， 所以下一个状态应是＝()，也即第个比特应该为。 ．设密钥流是由级产生，其周期为－，是任一正整数，在密钥流中考虑以下比特对 (, ), (, ), …, (－, －), (－, －), 问有多少形如(, )＝()的比特对？证明你的结论。 答：共有() 证明： 证明方法一：由于产生的密钥流周期为－，且的级数为，所以是序列 以上比特对刚好是个周期上，两两相邻的所有比特对，其中等于()的比特对包含在所有大于等于的游程中。由序列的性质，所有长为的游程(≤≤)有个，没有长为－的游程，有个长为的游程。 长为(>)的游程可以产生个()比特对，
设计内容及要求 基于MATLAB产生m序列 要求： 1．通过matlab编程产生m序列的产生原理及其产生方法。 2．对特定长度的m序列，分析其性质，及其用来构造其它序列的方法。 第二章m序列设计方案的选择 2.1 方案一 MATLAB编程非常简单，无需进行变量声明，可以很方便的实现m序列。 2.2 方案二 图2.1 Simulink实现m序列 Simulink是MATLAB最重要的组件之一，它提供了一个动态系统建模，仿真和综合分析的集成环境。在此环境中无需大量书写程序，而只需通过简单直观的鼠标操作，就可构造出复杂的系统。Simulink具有适应性广，结构及流程清晰及仿真精细等优点，基于以上优点，Simulink已被广泛的运用到控制理论和数字信号处理的复杂仿真和设计。
通过比较方案一和方案二，发现方案一的有点具有通用性而方案二利用MATLAB的Simulink直接搭建模块，在移位寄存器较少的情况下利用此方法比较简单，可是当移位寄存器的个数增多时，要搭建那么多的模块就显的很繁琐了，缺乏通用性，因此本次实验选择方案一。 第三章m序列的产生及性质 3.1 m序列的产生原理、结构及产生 m序列是最长线性反馈移位寄存器序列的简称，m序列是由带线性反馈的移位寄存器产生的。 由n级串联的移位寄存器和反馈逻辑线路可组成动态移位寄存器，如果反馈逻辑线路只由模2和构成，则称为线性反馈移位寄存器。 带线性反馈逻辑的移位寄存器设定初始状态后，在时钟触发下，每次移位后各级寄存器会发生变化，其中任何一级寄存器的输出，随着时钟节拍的推移都会产生一个序列，该序列称为移位寄存器序列。 n级线性移位寄存器的如图3.1所示： 图3.1 n级线性移位寄存器 图中C i表示反馈线的两种可能连接方式，C i=1表示连线接通，第n-i 级输出加入反馈中；C i=0表示连线断开，第n-i级输出未参加反馈。 因此，一般形式的线性反馈逻辑表达式为 ------表达式3.1将等式左边的a n移至右边，并将a n=C0a n(C0=1)带入上式，则上式可以 写成 -------表达式3.2
有趣的线性反馈移位寄存器(LFSR) 最近一直在研究信道编码，发现在信道编码里面有一个电路比较重要也比较有趣，那就是线性反馈移位寄存器LFSR ，相信大家对LFSR 电路也不陌生了,在通信领域lfsr有着很广泛的应用,比如说M序列,扰码,信道编码,密码学这方面都有很广泛的应用,LFRS的结构一般如下图： 其中他需要一个生成多项式为: 这个多项式是一个本原多项式，然后知道这个电路有一些有意思的性质，下面我以m = 3 来做个例子具体的电路图如下所示： 假设开始的时候（D2，D1，D0 ）= （0，0，1），那么每过一个时钟周期会进行跳变一次， 可以看到具体的跳变如下所示：
然后我们可以看到这个计数器循环起来了，很好玩吧，无论进入那样一个状态除了0之外，都可以循环着回来，其实这里就相当于了一个3bit的伪随机数，很有意思，不是所有的多项式都有这个特性，我们现在在从数学上面来看看这个问题,其实最上面的电路是可以看成是一个除法电路，在Galois域的一个除法电路。现在假设的是R（x）是寄存器中剩余的数据，M(x)是输入的码字多项式，然后数学公式可以表示成： 然后我分别计算出了Ｍ（ｘ）的各种情况，
然后我们单独进行一下７次方的运算 发现７次方的运算和０次的时候的余数是一样的 然后我们发现其实在上面的电路中对多项式的除法也是可以循环起来的,可以验证的是
把这个记成 上面的式子是可以循环的,然后我又想到了CRC的计算,CRC的计算也可以通过一个除法电路来实现, 假设码子多项式为 生成多项式为 那么CRC的码字为这样我们同样可以用LFSR电路来进行实现 首先对M(x)乘以一个x的r次方,然后去去除G(x),在电路上的表现就是 所以在输入码字以后还需要多输入r拍的0这样才能使最后的CRC码字数据. 同理这个电路也可以进行CRC校验，把生成的数据全部都依次输入进这个
实验七移位寄存器及其应用 一、实验目的 1.移位寄存器74LS194的逻辑功能及使用方法； 2.熟悉4位移位寄存器的应用。 二、实验预习要求 1.了解74LS194的逻辑功能； 2.用4位移位寄存器构成8位移位寄存器； 3.了解移位寄存器构成环形计数器的方法。 三、实验原理 1. 移位寄存器是指寄存器中所存的代码能够在移位脉冲的作用下依次左移或右移。74 LS194是一个4位双向移位寄存器，最高时钟脉冲为36MHz，其逻辑符号及引脚排列如图实验7.1所示。 图实验7.1 74 LS194逻辑符号及引脚排列 其中：D0～D1为并行输入端；Q0～Q3为并行输出端；SR－右移串引输入端；SL－左移串引输入端；S1、S0－操作模式控制端；/CR－为直接无条件清零端；CP－为时钟脉冲输入端。74LS194模式控制及状态输出如表实验7.1所示。 2. 用74LS194构成8位移位寄存器 电路如图实验7.2所示，将芯片（1）的Q3接至芯片（2）的SR，将芯片（2）的Q4接至芯片（1）的SL，即可构成8位的移位寄存器。注意：/CR端必须正确连接。3. 74LS194构成环形计数器 把移位寄存器的输出反馈到它的串行输入端，就可以进行循环移位，如图实验7.3所示。设初态为Q3Q2Q1Q0=1000，则在CP作用下，模式设为右移，输出状态依次为： 表实验7.1 74LS194工作状态表
2. 用74LS194构成8位移位寄存器 电路如图实验7.2所示，将芯片（1）的Q3接至芯片（2）的SR，将芯片（2）的Q4接至芯片（1）的SL，即可构成8位的移位寄存器。注意：/CR端必须正确连接。 图实验7.2 8位移位寄存器 3. 74LS194构成环形计数器 把移位寄存器的输出反馈到它的串行输入端，就可以进行循环移位，如图实验7.3所示。设初态为Q3Q2Q1Q0=1000，则在CP作用下，模式设为右移，输出状态依次为：
第31卷第10期电子与信息学报Vol.31No.10 2009年10月 Journal of Electronics & Information Technology Oct. 2009 线性反馈移位寄存器的差分能量攻击 臧玉亮韩文报 (解放军信息工程大学信息工程学院郑州 450002) 摘要：能否有效去除算法噪声的影响，直接关系到能量攻击成败。该文以线性反馈移位寄存器(LFSR)相邻两个时钟周期的能量消耗差异为出发点，提出了一种新的差分能量攻击算法。它从根本上去除了密码算法噪声在攻击过程中带来的影响。由于该算法随机选择初始向量(initialization vector)，从而使攻击者能够容易地将其推广到具有类似结构的流密码体制。为了进一步验证攻击算法的有效性，该文利用软件仿真的方法对DECIM进行了模拟攻击。 仿真结果表明，该攻击算法能够有效降低LFSR的密钥搜索的复杂度。 关键词：流密码；差分能量攻击；线性反馈移位寄存器；DECIM；复杂度 中图分类号：TN918.4 文献标识码：A 文章编号：1009-5896(2009)10-2406-05 Differential Power Attack on Liner Feedback Shift Register Zang Yu-liang Han Wen-bao (Institute of Information Engineering, PLA Information Engineering University, Zhengzhou 450002, China) Abstract: Whether the algorithm noise can be effectively wiped off decides the success or loss of the power analysis attack. This paper offers a new differential power analysis attack algorithm, which is based on the consumed power differences between two neighboring clock cycles of liner feedback shift register. This new attack algorithm radically wipes off the effect of cipher algorithm noise in the process of attack. Because this algorithm randomly chooses initialization vectors, the attackers can easily extend the algorithm to other stream ciphers that have similar structures. In order to further validate the algorithm’s availability, simulative attacks on DECIM are carried on with the method of software simulation. And the result shows that this algorithm can effectively reduce the complexity of the exhaustive search on LFSR. Key words: Stream cipher; Differential Power Attack (DPA); Liner Feedback Shift Register (LFSR); DECIM; Complexity 1引言 一个完整的密码系统由密码算法设计者，硬件设计者和软件设计者共同开发完成，但他们的工作又相互独立，各层设计者通常只考虑本层的安全问题，并且一层的设计者并不一定了解其他层设计者的工作，比如密码算法设计者并不一定具有较高的硬件知识水平。其次，由于现代制造工艺的限制，无法做到在硬件中的任何运算都消耗相同的能量。因此综合上述两个原因，使得密码系统在旁道攻击[1,2]面前出现了诸多可被攻击者利用的漏洞。 自密码算法设计之初，设计者就开始考虑其算法自身抗已知攻击的能力，如代数攻击[3]。因此，攻击者从密码算法的角度来分析一个密码体制变得越来越困难。然而，旁道攻击的出现给密码算法带来了严重威胁。 从Kocher提出能量攻击方法[4]以来，它被广泛应用于分组密码(如AES, DES)和公钥密码(如RSA, 2008-10-14收到，2009-06-25改回ECC)分析。研究的广泛性说明了能量攻击方法对于这两种密码体制的有效性。但是我们却很少看到对流密码的能量攻击研究。文献[5]给出了eSTREAM[6]第3阶段相关候选算法抗旁道攻击的理论评估。文献[7]对GSM手机使用的A5/1流密码算法和蓝牙中所使用的E0流密码算法进行了能量攻击理论分析，给出了已知初始IV的攻击算法。文献[8]通过观察能量消耗与LFSR初态之间的关系建立方程，进而求得初态。文献[9]是第1篇对基于硬件的流密码进行实际能量攻击的文章。它针对eSTREAM中的Grain 算法和Trivium算法提出了选择IV的攻击算法。有针对性地选择16个IV来降低密码算法噪声对攻击的影响，虽然作者成功获得了算法密钥，但是如何针对不同的算法来选择IV并没有给出选择规则，因此给该攻击算法的广泛适用带来了影响。 当攻击者对于一个流密码算法进行能量攻击时，如何克服算法噪声给攻击过程带来的影响是他必须考虑的问题。当LFSR的状态在某一个时钟发生变化时，攻击者可以从示波器上看到当前时钟整
第1章移位寄存器与反馈节点 在本书的所有内容中，将不再关注LABVIEW版本的问题，也不会详细讨论LABVIEW中各 个函数的具体用法。我们重点关注的是采用自底向上的编程方法，一步一步地学习如何利用 LABVIEW构建比较大的应用程序。 任何程序都离不开数据，LABVIEW程序中的数据一般都是存储于与数据类型相适应的控件 之中，唯一的例外是移位寄存器和反馈节点。其中反馈节点出现在8.X版本后，而移位寄存 器从LABVIEW诞生之日起就一直存在，因此本书从移位寄存开始谈起。 移位寄存器（Shift Register）通常简称为SR,为叙述方便，我们也会采用SR来表示移位寄 存器。 1.1.什么是移位寄存器 如果我们学习过其它编程语言，就会发现在常规的编程语言中，很少会提及移位寄存器。 这是因为移位寄存器的定义来自于硬件，现实世界中我们的确可以找到各类基于移位寄存器 的芯片。 既然如此，我们有必要从硬件的角度简单介绍一下移位寄存器，了解移位寄存器的特点， 这有助于我们理解LABVIEW中的移位寄存器，因为二者的作用是基本一致。 图中包括了四个移位寄存器。从硬件移位寄存器的角度来看，每个一位寄存器中包含一个 二进制位。我们不必拘泥于移位寄存器存储的数据类型，我们假设移位寄存器中可以存储任 意类型的数据。 移位寄存器具有几个非常重要特点： l 移位寄存器是由相同的寄存单元所组成。 l 所有寄存单元共用一个时钟。 l 所有寄存器单元串行级联。 图1- 1 移位寄存器示意图 移位寄存器由相同的寄存单元组成，这意味着每个寄存单元中存储的数据类型必须相同。 通常的移位寄存单元包含三个输入端和两个输出端，每个接线端的作用简述如下：
第八章序列密码和移位寄存器 香农证明了“一次一密”密码体制在理论上是不可破译的，促使人们长期以来一直寻求某种能仿效“一次一密”密码的密码体制，序列密码就是所寻求的方法之一。目前，序列密码是世界军事、外交等领域应用的主流密码体制。 序列密码的加、解密过程： [1]将报文、语音、图像、数据等原始明文转换成明文数据序列； [2]将转换后的数据序列用密钥序列进行逐位加密生成密文数据序列并发送 给接收者； [3]接收者用相同的密钥序列对密文数据序列进行逐位解密恢复出明文序列。 ●序列密码不存在数据扩展和错误传播，实时性好，加解密实现容易。 序列密码的发展历程： ●Vernam密码最早的二进制序列密码系统。当Vernam密码中的密钥序列 为完全随机的二进制序列时，它就是“一次一密”密码。但其密钥产生分配和管理都极为困难，故未得到广泛应用。 ●随着微电子技术和数学理论的发展，基于伪随机序列的序列密码成为当前 最通用的密码系统。这种序列密码中，加、解密的密钥序列都是伪随机序列。 ●伪随机序列是由密钥流产生器产生的。密钥流产生器实际上就是通过给定 算法产生通常是0-1数据流的密钥流。 伪随机序列： 序列密码可看成多表密码的一种，其密钥流是有周期的，因为密钥流是周期的，所以要完全做到随机非常困难。一般，希望密钥流的周期尽可能大，至少应与明文的长度相等。由于这种密码的密钥序列不可能做到随机，只要求截获比周期短的一段密文时不至泄露更多的信息，故这样的序列称为伪随机序列。 序列密码的安全保密性主要依赖于密钥序列，因此研究什么样的伪随机序列可以作为序列密码的密钥序列就成为序列密码研究中的主要问题，即序
1．试用74194附加门电路设计一个101001序列信号发生器，并用时钟验证，画出时钟脉冲及输出波形 若采用左移方式，直接由序列从左向右每三位得一状态，写出真值表 SL B D B C D Q Q +Q Q = 若采用右移方式，则序列反写，从右往左，每三位一个状态，写出真值表 S R A C A B D Q Q +Q Q = 电路图略。 P153 J3 用标准数字器件中的移位寄存器设计一个序列信号发生器，其输入信号为时钟CP ，输出信号为序列码F ，实验任务要求是：①序列发生器模值M=8;②各个码位上的码值为00011101，最右端码位为最先输出的低位；③测量时钟信号CP 与F 的波形。 解： 时钟信号波形CP 和输出波形F 如图所示，产生的序列码实际为10111000 方法一：采用两片74194实现 将左移/右移控制端S1,S0接逻辑电平开关K1,K0，置数输入端接序列码，先设定K1K0=11,CP 上升沿到来后，该码值被置到两片194的输出端，然后设定K1K0=01，则输出端序列信号进行循环右移，则实现该序列信号。194输出各端均为该序列信号。 此方法优点是若将置数输入端接至逻辑电平开关，可设置实现任意序列信号。
方法二：采用74194＋门电路实现 相当于实现序列信号10111000，分左移和右移方式 先确定需使用移位寄存器输出端的位数，保证不出现相同的状态，8位码，至少需3位。判断该序列每3位定一个状态，无重态。则取三位即可。 左移：直接由序列从左向右每三位得一状态，写出真值表 S L B D B C B C D D Q Q +Q Q +Q Q Q = 右移：序列反写，从右往左，每三位一个状态，写出真值表 SR A C B C A B C D Q Q Q Q Q Q Q =++