移位寄存器第三章答案汇总

1、第三章习题参考答案1.画出以f(x)=x6+x4+x2+1为联接多项式的线性移位寄存器逻辑框图，及其对应的状态7图。解:状态圈-1:状态圈-2:由f(x)=x6+x4+x2+1,得反馈函数为f(xi,x2，x6)=xi+x3+x5,故(limn(000000)状态圈-3:(010101)(101010)状态圈-4:状态圈-6：状态圈-5:(100110)(110011)(101110)(110111)状态圈-9:riorni：j(00D010)(000101)(001010)(100000)C0100005(101000)(010100)(000011)(000111)(0011115(011

2、110)(100001)(110000)(111000)(111100)状态圈-10:(00011D)(100011)C110001)C01100D)(001101)(011011)(110110)CIOHDO)(010011)(100111)(001110)C011100)(001001)(100100)tllOOlD)(111001)状态圈-12:状态圈-11:(001011)dooion(010010)(10100D(010110)(101101)(011010)(110100)(010111)(101011)(110101)(111010)(101111)(011111)(111110

3、)(111101)2.已知图3-2所示的7级线性反馈移位寄存器:图3-2(1)绘出该移位寄存器的线性递推式，联接多项式及特征多项式。(2)给出状态转移矩阵。(3)设初态为(1111111),给出输出序列a。解：(1)由逻辑框图得，递推式为：ak卡=ak书+akH3+ak(k-0)。联接多项式为：f(x)=1+x2+x4+x7。特征多项式为：f(x)=1,x3x5x7(2)状态转移矩阵:0 01 00 10 00 00 09 000001、000000000010001010000010100010,(3)输出序列：a=(111111111一)。3.设5级线性反馈移位寄存器的联接多项式为序列a。

4、_52f(x)=x+x+1,初态为(10101)。求输出解：由联接多项式得，反馈函数为:f(X1,X2，X5)=X1+X4。故以(10101)为初态的状态转移图为：10101)0101110111)0111011101)11011)10110)01100)1100010001 00011001110111111111111101110011001100110011001101 1101010100)01001)1001000100)01000)10000)000010001000101 0101010101由此可得，输出序列为：a=1010111011000111110011010010000

5、-o一个周期4 .证明：n级线性反馈移位寄存器的状态转移变换是n维线性空间F2n上的线性变换。证明：设Tf为n级线性移位寄存器的状态转移变换，对Vot,PwF2n，令s=(a0,a1,，an)，P=(b0,b1,，bnQ,有:n(3)-Tf(a0,a1,7anJ=(a1,a2,ZGan-J,i1nTf(P)=Tf(b0,n,，bn)=(b1,b2,GbnG。i=1Tf()=Tf(a0b0,a1bl，anbn)nU(a1b1,a2b2,rCi(an4bn_i)iWnn二(a1,a2,rCian_i)(b1,b2,Cibn_i)i1i1=Tf(:)Tf()对Vk=F2,nTf(ka)=Tf(ka0

6、,ka1,，kan)=(ka1,ka2,，*GanG=k(Tf俨)。iZ故n级线性反馈移位寄存器的状态转移变换是n为线性空间F2n上的线性变换。5 .设二元周期序列a#0的极小多项式为f(x),T是f(x)对应的状态转换矩阵，则SST,，STp(a)必两两不同。其中S=区o,，an)。证明：若，j,0Mi#jMp(a)-1,使得STi=STj(不妨设ij)。令丁=ij,则STf=S。于是，对vSk,有Sk=STk=ST盯k=SkTT,即ak女=ak，从而T(p(a)为序列a的周期，与P(a)为最小周期矛盾。故S, ST,STP(a)_1必两两不同。6 .证明：若awG(f)的极小多项式次数为n

7、(21),则a,La,，Lna必线性无关。证明：由题知a=0,假设a,La,，Ln，a线性相关，则存在不全为零一组数c0,c1,，cn使得c0a-c1La：卜、-+cnjLn1a=0=(c0c1L+-一+CnLn)a=0令：(x)=C0+CiX+十Cnxn，,则g(x)也产生序列a,而dg(x)En-1,与a的极小多项式f(x)的次数为n矛盾，故假设不成立，因此，a，La，Ln,a必线性无关。7 .证明：若awG(f),$f(x)=n,a=0，则a，La,，Ln，_a构成G(f)的一组基当且仅当a以f(x)为极小多项式。证明：充分性：由dof(x)=门知6(与是n维的。又aG(f),a以f(x

8、)为极小多项式，由上题结论可知a,La,，Lna线性无关，故构成G(f)的一组基。必要性：设a的极小多项式为ma(x),doma(x)=m，则ma(x)|f(x),mn。令:ma(x)=1+c1x+c2x2+cmxm,+xm,则ma(L)a=0,从而,ma,La,，La线性相关。而a，La,，Lna为G(f)的一组基，所以mn1,即m之n,故ma(x)=f(x)。即a以f(x)为极小多项式。8 .证明：若awG(f),df(x)=n,a以f(x)为极小多项式，则G(f)中每个序列均可唯从而G(f)中有中(f)个序列以f(x)为极小多项式，其中邛(f)是次数a0f,且和f(x)互素的多项式的个数

9、。一地表成g(D)a,并且g(D)a的极小多项式为f(x)(g(x), f(x),其中 60g(x) n ,D为延迟变换。证明：(1)上题结论知，vgwG(f),都可由亘，La，Lna为线性表出，则存在一组数Co,Ci,，品使得：b二c0a-c1Lgi+cnLna=0=(c0,c1L+-+cnLn)a令：(x)=/+cx+C2X2+Cnxn，,则有b=(L)aub=g(D)a,即VbwG(f)均可唯一的表示成g(D)a的形式。令：(f(x),g(x)=d(x),则f(x)=d(x)fi(x),g(x)=d(x)gi(x),(fi(x),gi(x)=1。设g(D)a的极小多项式为f2(x),则只

10、须证明f2(x) = fi(x) =f(x)(f (x), g(x)fi(D)(g(D)a)=fi(D)d(D)gi(D)a=f(D)gi(D)a=gi(D)f(D)a=0二fi(x)为g(D)a的联接多项式,从而f2(x)|fi(x)o又，由f2(D)(g(D)a=f2(D)d(D)gi(D)a=0知,f(x)|f2(x)d(x)gi(x),从而fi(x)|f2(x)gi(x),而(fi(x),gi(x)=i,故fi(x)|fz(x),所以fz(x)=fi(x),即f)为g(D)a的极小多(f(x),g(x)-项式。(3)当(g(x),f(x)=i时，g(D)a以f(x)为极小多项式，而次数

11、n且与f(x)互素的多项式g(x)共有9(f)个。9 .设f(x)WF2x,f(0)#0。(i)证明G(f)中任一平移等价类中序列有相同的极小多项式与周期。(2)G(f)中有相同的极小多项式的序列是否一定在同一平移等价类中？为什么？在什么条件下，序列的极小多项式相同当且仅当序列属于同一平移等价类？证明：(1)设aWG(f),b=Lta(0tp(a)i)是其平移等价序列，且有bk=ak由，k之0。因为bk4p(a)=ak+与(a)=ak4=bk，k-0o故p(b)p(a),同理可证p(a)p(b),所以p(b)=p(a)。设a的极小多项式为ma(x),b的极小多项式为mb(x),则ma(L)a=

12、0,从而ma(L)b=ma(L)Lta=Ltma(L)a=0ma(D)b=0,即ma(x)是b的联接多项式，于是mb(x)|ma(x),同理可证ma(x)1mb(x)。因此ma(x)=mb(x)。(2)不一定。例如，f(x)=x4+x3+x2+x+1是4次不可约多项式，G(f)中非零序列都以f(x)为的极小多项式，但Gf中有3个周期为5的圈，显然这3个圈对应3个不同的平移等价类。(或令a=11000，b=10111，a，bwG(f),但a与b不在同一等价类中。)当f(x)是本原多项式时，序列的极小多项式相同当且仅当序列属于同一平移等价类。3210 .设f(x)=f(x)f2(x),其中f(x)

13、=1+x+x,f2(x)=1+xuF2x。(1)证明以01111001000011为一个周期段的二元序列属于G(f)。(2)将上述序列分解成两个序列a和b之和，使得awG(f1),bG(f2)。52证明：(1)f(x)=f(x)f2(x)=x+x+x+1,令初态为S0=(01111),则f(x)广生的序列为：01111001000011，故以01111001000011为周期段的二元序列属于G(f)。(2)方法一:由(f1(x),fz(x)=1知，存在g(x)=1,g2(x)=x，使得1-g1(x)f1(x)g2(x)f2(x)令：c=01111001000011，则c=Icug2(D)f2(

14、D)c+g1(D)f1(D)c,记a=g2(D)f2(D)c,b=g2(D)f2(D)c,即有c=a+b。由引理3.3.3的证明过程知，aWG(f1)，bWG(fz),故a和b即为求：_3_,_3a=(D+D)c=1101001，b=(D+D+1)c=10,10，。方法二:Gf=Gf1Gf2,Gf1=11+17,Gf2=21+12。Gf=GfCf2=2(1,2)1,1(1,1)1,22(1,2)7,1(1,1)7,2=21217114显然，周期为14的序列是由Gf1中17和Gf2中12唯一生成。由f(x)=1+x+x3,令初态为S0=(01001110100111010011101一。由f2(

15、x)=1十X2,令初态为S0=(01),输出序列为：0101010101-将上述两个输出序列异或求和有：00111010011101001110T010101010101010101010011011110010000110111上述序列a=110100#,。b=10,10：11.设f(x)=(x2+x+1)2WF2x,试问G(f)中共有多少序列的平移等价类，每个平移等价类的周期是多少，对每个平移等价类构作出一个序列来。解：由已知得n=2,e=2,m=1,令f(x)=f12(x),f1(x)=x2+x+1。而p(f1)=3,故f122 -1= 113322222 - 222 3=111326二

16、G(f)中有4个平移等价类：一个周期为1的平移等价类;一个周期为3的平移等价类;两个周期为6的平移等价类。周期为1的平移等价类中代表序列为零序列，周期为3的平移等价类中代表序列为：011，两个周期为6的平移等价类中代表序列分别为：111001，和110110，。12 .求联接多项式为f(x)=(x2+x+1)2(x3+x+1)(x4+x+1)的线性移位寄存器的状态图Gf中的圈长和圈数。234解：令f1(x)=x+x+1,f2(x)=x+x+1,f3(x)=x+x+1,且f1(x),f2(x),f3(x)两两互素，又p(f1)=3,p(f?)=7,p(f3)=15。由上题知，G-=11+13+2

17、6of1对于f2(x),Gf2=11+17。对于f3(x),Gf3=11+115。.Gf=Gf2Gf2Gf3=(1113a6)(11115)(111)=(111151331526630)(1117)=11171151105121133153105262426306210=1113261741512124263041056210,Gf中有周期为1,3,7的圈各一个，2个周期为6的圈，周期为15,105的圈各4个，周期为30,210的圈各6个，周期为21的圈1个，周期为42的圈2个。13 .设a,b为周期序列，S,r为正整数。证明:(1)(a)(r)=a(sr)。(a+b)(s)=a(s)+b(s

18、)。(3)若s三rmodp(a),则a(r)=a。证明：(1)(a(s)(r)=(a0,as,a2s,)(r)aks-bk=(QUM,)(r)=(b0，br，b2r，)二也凤但“，)(rs)二a(2)(a b)=(a。b,a1n,a2b2,)二(a。bo,asbs,a2sb?s,)二(a0,as,a2s,)(b0,bs,b2s,)(5) .(S)二ab(3)若s 三 r modp(a)，则 s = kp(a) + r (k w N)13ajsajkp(a)jrajra(a0,as,a2s,)=(a0,ar,a2r,)14 .设“*)为门次本原多项式，a#0wG(f)，证明a与a口“)的极小多项

19、式为互反多项式。其中，SWZ2n。证明：设为f(x)的一根，因(s,2n1)=1，(s,2n1s)=1,故由定理3.4.4知：a与a(2n都为n级m序列，对应的极小多项式fs(x)和02nl.(x)皆为本原多项式，且于(2-1.s)和产口分别为其n次本元根。又ys./口=y2n-1=1u(/)二产，即两根互逆，从而fs(x)和f(2n/(x)互反,所以a与a(2n二的极小多项式为互反多项式。15 .求全部7级m序列中平移等价类的个数。解：全部7级m序列中平移等价类的个数为：(2n-1)(2-1)(127)do=18。16 .用迹函数表示法表示G(f)中序列，其中f(x)=x4+x+1。解：设a

20、是在f(x)=x4+x3+1F24中的一个根，则F24=F2x(x)=0,a0,a1,a2,a3,，a22.2二0,1,1,1,-,23333、工2-1、工3、工31、:3:3-11,a3+a2,a3+o(2+1,a3+a2+a,a3+a2+a+1G(f)中共有16条序列,设为ai(i=0,1,15)，于是有：(1) P=0a0=：Tr(0),Tr(0：),Tr(012);一)=(000000(2) P=1a1=：Tr(1),Tr(11),Tr(1；2),二011110101100100(3) B=a、.2、a2=Tr(:),Tr(、工、t),Tr(、工、工),=111101011001000

21、(4) -:1a3=Tr(：1),Tr(：1)二),Tr(：1)：-2),=100011110101100一2a4=Tr(：2),Tr(二2：),Tr(：2：2),=111011011001000T(6)=:21a5=Tr(：.21),Tr(：21)：),Tr(：21)：2),=100100011110101：=:-2n2222a6=Tr(二：),Tr(：)：),Tr(：)：),=00011110101100(8) -:2，：工，1a7=Tr(：2，1),Tr(二2，：-1)二),Tr(二2：，1)：-2),011001000111101(9) -=：-33332a8=Tr(：.),Tr(：-

22、：),Tr(：二),=110101100100011(10) =:31a9=(Tr(ot3+1),Tr(a3+1)a),Tr(a3+1)。2),)=(10101100100011L)(11):=:3ya10#Tr(：.3+.N),Tr(：3二二)：),Tr(：3二二)二)广一)=(00100011110101T(12) -3-工-1an=Tr(：3-1),Tr(：3-1)：),Tr(：3:F)：2)广7二(01011001000111T(13) -3上工2a12=Tr(-3-2),Tr(-3-2):),Tr(-312);2),=001111010110010(14) ：=3:。21a13=(T

23、r(a3+a2+1),Tr(a3+u2+1_)”Tr(u3+口2+1)02),)=010001111010110(15) -3-工2人，a14=Tr(-3-2:),Tr(:3-2:),Tr(-3：2：)二2),二(110010001111010(16) ：=：3匕2一二Ta15=Tr(:3+q/，1),Tr(:3,工2，：工T):),Tr(：3+q=2r工-1):2),101100100011110(17) 知5级m序列：a=(111110001110101000010010101100,)求出全部5次本原多项式。解：Z31=1,23-，30),则Z31=H3H5H7H11H15H其中H=6,

24、2,4,8,16),3H=3,6,17,12,24,5H=(5,9,10,18,20),7H=7,14,19,25,28),11H=51,13,21,22,26),15H=115,23,27,29,30。那么a二(1011100010101101000011001001110,)a二(001010010110101010111110101,1000a=(0001110111110010011000010110101,)(11)a()二(1111011001110000110101001000101；)(1)设a的极小多项式为：f(x)=1+cx+c2x2+c3x3+c4x4+c5x5,则其对应

25、的线性递推式为：a5=c1ak书+c2aky*C3ak%*C4ak(k之0)。选a的连续前10项：1111100011,将其代入线性递推式可得线性方程组：,G+C2+C3+C4+C5=0C2+C3+C4+C5=06+C4+C5=0C4+C5=1GC5=1解该线性方程组得：c1=0,c2=0,c3=1,c4=0,c5=1,故f(x)=1十x3+x5。(2)设a的极小多项式为：f2(x)=1+Cx+c2x2+c3x3+c4x4+c5x5,则其对应的线性递推式为：ak45=c1ak七十c2akH3+C3ak七*C4ak(k0)选a的连续前10项：1011100010,将其代入线性递推式可得线性方程组

26、：G+c2+c3+c5=0c2+c3+c4=0，c3+c4+c5=0c4cc5=1Jclc50解该线性方程组得：C1=1,c2=1,c3=1,c4=0,c5=1,f2(x)=1+x+x2+x3+x5。(3)设a的极小多项式为：f3(x)=1+c1x+c2x2+c3x3+c4x4+c5x5,则其对应的线性递推式为：ak书=cak*+aaky+c3ak节+c4ak(k之0)。选a的连续前10项：0010101100,将其代入线性递推式可得线性方程组：3+c3=0c2+c4=1“C1cc3+C5=1C1+c2+c4=0c2c3c5=0解该线性方程组得：c1=1,c2=0,c3=1,c4=1,c5=1

27、,f3(x)=1+x+x3+x4+x5若序列的联接多项式是本原多项式，则其特征多项式也为本原多项式，所以，所有5次本原多项式为：一35f1(x)=1+x+x。235f2(x)=1+x+x+x+x。f3(x)=1+x+x3+x4+x5。一25f4(x)=1+x+x。f5(x)=1+x2+x3+x4+x5of6(x)=1+x+x2+x4+x5。18 .设a是一周期序列，若a中有长为n的游程，则a的极小多项式的次数一定之n。证明：假设a的极小多项式的次数kn。若q中有长为n的1游程，则在k级周期序列中至少有2个全1的状态与全1状态仅出现一次矛盾。若a中有长为n的0游程，则以00000，为初态的序列只

28、能产生零序列不能出现k个故a的极小多项式的次数一定之n19 .设a=(a0,ai,a3,)是n(之1)级m序列，试求数对：(ak,a),(k=0,1，2n_2,1MtM2n-2)为(0,0)的次数。解一：a一个周期段中0和1的个数分别为2n1,2n则(ak,ak+)为(0,0)的总个数为c-1一,一n二.又重复度为2-1c一-1(ak,ak+)为(0,0)的个数为c2n解:Lt(a)和a+Lt)都是m；J列，m序列中0有2n-1个，1有2n/个，(ak,ak+)有(0,0),(0,1),(1,0),(1,1)四种情况，设(0,0)的个数为x,(1,1)个数为y,则根据0,1分布知(0,1)的个

29、数为2n,1-x,.x+y=2n,-1n 1n 1x 2- y = 2-1(1,0)的个数为2n-y,故|“7n可解得x=2n-1即(0,0)的次数为2H-120 .用梅西算法，求产生下列有限序列的最短线性反馈移位寄存器的联接多项式。(1)2=(11101110001010110100)。b=(1111011110)。(1) a=(111011100001011010。解：设a01,a1-a2=1,a30,a4=1,a5=1,a6=1,a701a80,a90a101,a110,a12=1,a13=0,a14=1,a15=1,a16=0,a17=1,a18=0,a19=0第0步：f0(x)=1,

30、第1步：计算d0：d0=a0=1,l0=0则：f1(x)=1x11=1第2步：计算d1：d1=a1+a0=0贝U：f2(x)=fl(x)=1x12=ll=1第3步：计算d2：d2=a2+a1=0则：f3(x)=f2(x)=1x13=12=1第4步：计算d3：d3=a3+a2=1,又有m=0使1011=12=13=1则:f4(x)=f3(x)x3f0(x)=1xx314=maX13,4-13)=3第5步：计算d4：d4=a4+a3+a1=0则：f5(x)=f4(x)=1xx315=14=3第6步：计算d5：d5=a5+a4+a2=1,又有m=3使1314=15=3则:f6(x)=f5(x)x5J

31、3f3(x)=1xx216-max(15,6-15)=3第7步：计算d6：d6=a6+a5+a4=1,又有m=3使1314=k=L=3则：f7(x)=f6(x)x3f3(x)=1xx2x3x417二max(16,7-L)=4第8步：计算d7：d7=a7+a6+a5+a4+a3=1,又有m=6使1617=4则：f8(x)=f7(x)xf6(x)=1x418=max；17,8-17)=4第9步：计算d8：dg=a8+a4=1,又有m=6使161=4=4则：f9(x)=f8(x)x2f6(x)=1x2x319=max(18,9-18)=5第10步：计算d9：d9=a9+a7+a6=1,又有m=8使1

32、819=5则：f10(x)=f9(x)xf8(x)=1xx2x3x5l10=max(l9,10-l9)=5第11步：计算dio:dio=a0+a9+a8+a7+a5=0则：f11(x)=f10(x)=1xx2x3x5111=l10=5第12步：计算d11：d1=a1+a0+a9+a8+a6=0则：f12(x)=f11(x)=1xx2x3x5112=111=5第13步：计算d12:d12=a2+a1+a0+a9+a7=0则：f13(x)=f12(x)=1xx2x3x5113=112=5第14步：计算d13:d13=a13+a2+a+a0+a8=0则：f14(x)=f13(x)=1xx2x3x51

33、14=113=5第15步：计算d14:d14=a4+a3+a2+a+ag=0则:f15(x)=f14(x)=1xx2x3x5115=114=5第16步：计算d15：d15=为5+为4+43+a12+a10=0则:f16(x)=f15(x)=1xx2x3x5116=115=5第17步：计算d16：d16=a6+a5+a4+a3+a110则：f17(x)=f16(x)=1xx2x3x5117=116=5第18步：计算d：d17=a十a6+a5+a4+ag=0则：f18(x)=f17(x)=1xx2x3x5118=117=5第19步：计算d18：d18=a18a”+a6+a5+a3=0则:f9(x)

34、二f8(x)=1xx2x3x5I19=118=5第20步：计算d19：d19=a19+a18*a17+a16*a14=0贝U：f20(x)=f19(x)=1xx2x3x5I20=I19=5因此，1+x+x2+x3+x5,5下就是产生此序列的最短线性移位寄存器(2) b=(111101111。解：设a。=1a1二1a2=1,a3=1,a4=0,a=1,a6=1a7=1a8=1,a=0第。步：fo(x)=1,lo=。第1步：计算do：do=a0=1,i=0则：f1(x)=1x11=1第2步：计算d1：d1=a1+a0=0则：f2(x)=f1(x)=1xl2=11=1第3步：计算d2：d2=a2+a

35、1=0则：f3(x)=f2(x)=1xl3=l2=1第4步：计算d3：d3=a3+a2=0则：f4(x)=f3(x)=1xl4-l3-1第5步：计算d4：d4=a4+a3=1则:f5(x)=f4(x)x4f0(x)=1xx4l5=max(l4,5-14)=4第6步：计算d5：d5=a5+a4+a1=0则：f6(x)=f5(x)=1xx4l6=l5=4第7步：计算d6：d6=a6+a5+a2=1，又有m=4使l4l5=l6=4则：f7(x)=f6(x)x2f4(x)=1xx2x3x4l7=max：l6,7-l6)=4第8步：计算d7：d7=a7+a6+a5+a4+a3=0则：f8(x)=f7(x

36、)=1xx2x3x4l8=l7=4第9步：计算d8：d8=a8+a7+a6+a5+a4=0则：f9(x)=f8(x)=1xx2x3x4I9=18=4第10步：计算d9：d9=a9+a8+a7+a6+a5=0则：f10(x)=f9(x)=1xx2x3x4110=19=4因此，1十x+x2+x3+x4,4A就是产生此序列的最短线性移位寄存器19i92i.设周期序列a =(i i i i o i,)的极小多项式为x6 +x+i,求a的有理分式表示。解：a(x)=aixi因为f(x)为a的极小多项式，故dg(x)/f(x)=6,则54 d,、 x x 1a(x) 6x x x 1-Tf(x)-45g(

37、x)=f(x)a(x)=1+x+x,故a的有理分式为:341xxx22.设周期序列a的有理分式表不为：a(x)=2一3一4一67,求序列a及其周期。1xxxxxx解：a(x)=(1 x 2x2)(13x2)5-(1 x x )(1 x x )1 x21 x3 x5 令f(x)=1+x3 +x5,为本原多项式5p(a)=2 1=31,序列以11111为初态的序列为:111110001101110101000010010110023.设a =90e1,，ap.a0,a1,)是周期为p的二元周期序列,则序列 1a -(ap,apW ,a0,ap4,ap2)的极小多项式为ma(x)。证明：设a的极小多项式为 m1(x),则a的形式哥级数表示为有理分式:od、aixi i fa。. ax .apxpJ1 二