移位寄存器第三章答案

1、图。第三章习题参考答案1画出以 f ( x) x6 x 4 x2 1为联接多项式的线性移位寄存器逻辑框图，及其对应的状态642解：由 f (x) x6 x4 x2 1，得反馈函数为 f (x1,x2, ,x6) x1 x3 x5，故1) 逻辑框图：2) 状态图：状态圈 -2：状态圈 -1：状态圈 -3：状态圈 -4：状态圈 -6：状态圈 -5 ：状态圈 -8：状态圈 -7：状态圈 -9：状态圈 -10：状态圈 -11 ：状态圈 -12：2已知图 3-2 所示的 7 级线性反馈移位寄存器：图 3-21)绘出该移位寄存器的线性递推式，联接多项式及特征多项式。2)给出状态转移矩阵。3) 设初态为(

2、1 1 1 1 1 1 1)，给出输出序列 a。解： ( 1) 由逻辑框图得，递推式为：ak 7 ak 5 ak 3 ak ( k 0) 。联接多项式为： f (x) 1 x2 x4 x7 。特征多项式为： f(x) 1 x3 x5 x70000001100000001000002)状态转移矩阵：00100010001000000010100000103)输出序列： a (111111111) 。3设 5 级线性反馈移位寄存器的联接多项式为f ( x) x 5 x2 1，初态为( 10101)。求输出序列 a 。解：由联接多项式得，反馈函数为： f(x1,x2, ,x5) x1 x4。故以 (

3、10101)为初态的状态转 移图为：10101 01011 10111 01110 11101 11011 10110 01100 11000 100010001100111011111111111110111001100110011 00110 011011101010100010011001000100010001000000001 00010 0010101010 10101由此可得，输出序列为： a 1010111011000111110011010010000 。一个周期4证明： n级线性反馈移位寄存器的状态转移变换是n维线性空间 F2n 上的线性变换。证明：设Tf 为n级线性移位寄

4、存器的状态转移变换， 对 ,F2n，令(a0,a1, ,an 1)，(b0 , b1 , ,bn 1) ，有：nTf( ) Tf(a0,a1, ,an1) (a1,a2, , cian i)，i1 nTf( ) Tf (b0,b1, ,bn1) (b1, b2 , , cibn i)。i1Tf() Tf(a0 b0,a1 b1, ,an 1 bn 1)n(a1 b1,a2 b2, , ci (an i bn i )i1nn(a1,a2, , cian i) (b1,b2, , cibn i)i 1 i1Tf ( ) Tf( )对 k F2 ，nTf(k ) Tf (ka0 , ka1 , ,k

5、an 1) (ka1 , ka2 , ,k cian i) k(Tf ( ) 。i15设二元周期序列 a 0的极小多项式为 f(x)，T 是 f (x)对应的状态转换矩阵，则S，ST ， ST 必两两不同。其中 S (a0,a2, ,an 1) 。证明：若 i,j ，0 i j p(a) 1，使得STi STj (不妨设 i j )。令 i j ，则 STS 。于是，对 Sk ，有 Sk STk ST T k SkT ，即akak ， k 0。从而 ( p(a) )为序列 a 的周期，与 p(a) 为最小周期矛盾。故S ， ST ， STp(a) 1必两两不同。6证明：若 a G( f )的极

6、小多项式次数为 n( 1)，则 a， La， Ln 1a必线性无关。 证明：由题知 a 0，假设 a，La，Ln 1 a线性相关， 则存在不全为零一组数 c0,c1, ,cn 1 使得c0 a c1Lacn 1Ln 1a 0 (c0 c1 Lcn 1Ln 1 )a 0令： g(x) c0 c1xcn 1xn 1，则 g(x) 也产生序列 a ，而 0g(x) n 1，与 a的极小多项式 f(x)的次数为 n矛盾，故假设不成立，因此， a，La， Ln 1 a必线性无关。7证明：若 a G(f)， 0f(x) n， a 0，则 a，La， Ln 1a构成 G(f)的一组基 当且仅当 a以 f (

7、 x)为极小多项式。证明： 充分性：由 of(x) n知G(f)是n维的。又 a G(f )， a以 f (x)为极小多项式， 由上题结论可知 a， La， Ln 1a线性无关，故构成 G( f )的一组基。必要性：设 a的极小多项式为 ma(x)， oma(x) m，则 ma(x)| f(x)， m n。令：ma(x) 1 c1x c2x2cm1xm 1 xm，则 ma(L)a 0 ，从而，a， La， Lma线性相关。而a ，La ，Ln 1a为G( f )的一组基，所以 m n 1，即 m n，故 ma(x) f(x)。 即 a以 f (x) 为极小多项式。8证明：若 a G(f ) ，

8、 0f (x) n，a以 f ( x)为极小多项式，则 G(f )中每个序列均可唯 一地表成 g(D)a，并且 g(D)a的极小多项式为f(x) ，其中 0g(x) n，D 为延迟变换。(g(x), f (x)从而G(f)中有 ( f )个序列以 f(x)为极小多项式，其中 (f)是次数0f ，且和 f(x)互素的多项式的个数。证明：( 1)上题结论知， b G(f)，都可由 a， La ， Ln 1a为线性表出，则存在一组数 c0 ,c1, ,cn 1 使得：n 1 n 1b c0 a c1Lacn 1L a 0 (c0 c1 Lcn 1L )a令： g(x)c0c1xc2 xcn 1 x，

9、则有 bg(L )abg(D )a ，即 bG ( f ) 均可唯一的表示成 g(D)a 的形式。(2)令：(f (x),g(x) d(x)，则 f(x) d(x) f1(x) ，g(x) d(x)g1(x)，( f1 (x), g1( x) 1。 设 g( D)a的极小多项式为 f2 (x) ，则只须证明 f2(x) f1(x)f (x)。( f ( x), g( x)f 1(D)( g( D)a) f1( D)d(D )g1( D)af (D)g1(D)a g1(D) f(D)a 0f1(x)为g(D)a的联接多项式，从而 f2(x)| f1(x)。又，由 f2(D)(g(D)a f2(D

10、)d(D)g1(D)a 0知， f (x) | f2(x)d(x)g1(x)，从而f1(x)| f2(x)g1(x)，而(f1(x),g1(x) 1，故 f1(x)| f2(x)，所以 f2(x) f1 ( x) ，即f(x)为g(D)a的极小多(f (x),g(x)项式。(3)当(g(x), f(x) 1时，g(D)a以 f ( x)为极小多项式，而次数n且与 f ( x)互素的多项式g(x)共有 (f )个。9设 f(x) F2x， f(0) 0。(1)证明 G( f )中任一平移等价类中序列有相同的极小多项 式与周期。( 2) G( f )中有相同的极小多项式的序列是否一定在同一平移等价

11、类中？为什么？在什 么条件下，序列的极小多项式相同当且仅当序列属于同一平移等价类？证明：( 1)设 a G( f ) ，b L a( 0 t p(a) 1)是其平移等价序列， 且有 bk ak t ，k 0。因为故 p(b) | p(a) ，同理可证 p(a)| p(b) ，所以 p(b) p(a) 。设 a的极小多项式为 ma(x)， b的极小多项式为 mb (x) ，则 ma (L)a 0，从而ma(L)b ma(L)Lt a Ltma(L)a 0 ma(D)b 0，即 ma (x)是b的联接多项式， 于是 mb ( x) |ma (x) ，同理可证 ma ( x) | mb ( x) 。

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

13、0 1 1 为一个周期段的二元序列属于 G(f)。(2)将上述序列分解成两个序列 a和b之 和，使得 a G(f1)， b G(f2)。52证明：( 1) f(x) f1(x) f2(x) x5 x2 x 1， 令初态为 S0 ( 01111)，则 f(x)产生的 序列为： 0111100100 0011, 故以 0 1 1 1 1 0 0 1 0 0 0 0 1 1 为周期段的二元序列属于 G(f)。(2)方法一 ：由 ( f1 ( x), f2(x) 1知，存在 g1(x) 1， g2(x) x，使得1 g1(x) f1(x) g2(x) f2(x)令： c 01111001000011,

14、 ，则c Ic g2(D)f2(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 的证明过程知，a G(f1) ，b G(f2)，故 a和b即为求：a (D3 D)c 1101001, ， b (D3 D 1)c 10,10, 。方法二Gf Gf1Gf2，Gf1 11 17 ，Gf2 21 12。Gf G f1Gf2 2(1,2)1,1 (1,1)1,2 2(1,2) 7,1 (1,1) 7,221 2 17 114显然，周期为 14 的序列是由 Gf 中 17和 Gf 中 12唯一生成。3由 f1(x) 1

15、x x3 ，令初态为 S0 (011)，输出序列为：00111010011101001110 1 。由 f 2(x) 1 x 2 ，令初态为 S0 (01)，输出序列为： 0101010101 。 将上述两个输出序列异或求和有：001110100111010011101010101010101010101010011011110010000110111上述序列a 1101001 ,。 b 10,10,11设 f(x) (x2 x 1)2 F2 x ，试问 G(f )中共有多少序列的平移等价类，每个平移等 价类的周期是多少，对每个平移等价类构作出一个序列来。解：由已知得 n 2,e 2,m 1,

16、令f (x) f12(x), f1(x) x2 x 1。而 p(f1) 3，故f122 311 2 3 13 2 2 323 2 311 13 2 6G( 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 中的圈长和圈数。解：令 f

17、1(x) x2 x 1 ，f2(x) x3 x 1，f3(x) x4 x 1，且 f1(x),f2(x),f3(x)两两互素，又 p( f1 ) 3 ， p( f 2 ) 7 ， p( f3 ) 15。由上题知， G 2 11 13 2 6 。f1对于 f2(x) ，Gf2 11 17。对于 f3(x) ，Gf3 11 115 。Gf Gf 2 Gf2 Gf3(11 13 2 6)(11 115)(11 17)(11 115 13 315 26 630)(11 17)11 17 115 1105 121 13 315 3105 26 242 630 621011 13 26 17 415 12

18、1 242 630 4105 6 210Gf 中有周期为 1，3，7 的圈各一个， 2 个周期为 6 的圈，周期为 15， 105 的圈各 4个，周期为 30，210的圈各 6个，周期为 21的圈 1个，周期为 42 的圈 2个。13设 a ， b为周期序列， s， r为正整数。证明：(1) (a(s)(r) a(sr)。(2) (a b)(s) a(s) b(s)。(3)若 s r mod p(a)，则 a(r) a(s) 。 证明：(1)(a(s)(r)aks bk(b0,b1,b2, )(r)(b0,br ,b2r, )(a0,ars,a2rs, )a(rs)2)(a b)(s) (a0

19、 b0,a1 b1,a2 b2 , )(s) (a0 b0,as bs,a2s b2s, ) (a0,as,a2s, ) (b0,bs,b2s, )(s) (s)ab3)若 s r mod p(a) ，则 s kp(a) r (k N)a js ajkp(a) jr a jra(s)(a0, as,a2s, )(a0,ar ,a2r, )(r)14设 f(x)为n次本原多项式， a 0 G(f )，证明 a(s)与a(2 1 s )的极小多项式为互反多项 式。其中， s Z2*n 1 。证明：设 为 f (x)的一根，因 (s,2n 1) 1， (s,2n 1 s) 1，故由定理 3.4.4知

20、：a(s)与a(2 1 s)都为 n级m序列，对应的极小多项式 fs(x)和 f(2n 1 s) (x)皆为本原多项式， 且( 2 1 s)和 2 1 s 分别为其 n 次本元根。又 s 2 1s 2 1 1 ( s) 1 2 1 s ，即两根互逆，从而 fs(x)和 f(2n 1 s)(x)互反， 所以a(s)与a(2 1 s)的极小多项式为互反多项式。15求全部 7级 m序列中平移等价类的个数。 解：全部 7级 m序列中平移等价类的个数为：(2 n 1) (2 7 1) (127)18。n 7 716用迹函数表示法表示 G( f )中序列，其中 f (x) x4 x 1。解：设 是在 f(

21、x) x4 x3 1 F24中的一个根，则F24F2x f(x)0, 0, 1, 2, 3， ， 14 2 2 2 0 ,1 , , 1, , 1, ,21 , 3 , 3 1 , 3 , 3 1,32 , 3 2 1 , 3 2 , 3 2 1G ( f ) 中共有 16 条序列，设为 ai (i 0,1, ,15) ，于是有：( 1)0a0 Tr (0),Tr(0 ),Tr (0 2), 000000( 2)1a1 Tr (1),Tr(1 ),Tr(1 2), 011110101100100a2 Tr( ),Tr( ),Tr( 2), 111101011001000(4) 1a3 Tr(

22、1),Tr( 1) ),Tr( 1) 2),100011110101100(5)2a4Tr(2),Tr(2 ),Tr( 2 2 ), 1110110110010001(6)21a5Tr( 21),Tr (21),Tr(21)2),100100011110101(7)22222a6Tr( 2),Tr(2),Tr(2)2),000111101011001(8)21a7 Tr( 21), Tr ( 2 1) ),Tr( 2 1) 2),011001000111101(9) 3a8 Tr( 3),Tr( 3 ),Tr( 3 2), 110101100100011(10)31a9 Tr( 3 1),Tr

23、 ( 3 1) )，Tr( 3 1) 2),101011001000111(11)3a10 Tr( 3 ),Tr( 3) ),Tr( 3 ) ),001000111101011(12)31a11 Tr( 31),Tr ( 3 1) ),Tr( 3 1) 2),010110010001111(13) 323232322a12Tr(32 ),Tr (32 ) ),Tr( 32)2), 001111010110010(14) 321a13 Tr( 3 2 1),Tr( 3 2 1_) ),Tr( 3 2 1) 2 ), 010001111010110(15) 3 2a14 Tr( 3 2 ),Tr(

24、 3 2 ) ),Tr ( 3 2 ) 2), 110010001111010( 16)3 2 1a15 Tr( 3 21),Tr ( 3 2 1) ),Tr ( 3 2 1) 2),10110010001111017已知 5级 m序列：a (1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 ，)求出全部 5 次本原多项式。解： Z31 1,2,3 ,30 ，则Z31 H 3H 5H 7H 11H 15H其中 H 1,2,4,8,16 ， 3H 3,6,17,12,24 ， 5H 5,9,10,18,20 ， 7H 7,14

25、,19,25,28 ，11H 11,13,21,22,26 ， 15H 15,23,27,29,30 。那么a(3) (1011100010 1011010000 1100100111 0, )a(5) (0 0 1 0 1 0 01 1 10 10 10 10 1 1 10 10, 1)0 0 0a (7) (0001110111 1100100110 00010110101, )(11)a (11) (1111011001110000110101001000101, )(1) 设 a 的极小多项式为： f1(x) 1 c1x c2x2 c3 x3 c4x4 c5x5 ，则其对应的线性递推

26、式为：ak 5 c1ak 4 c2ak 3 c3ak 2 c4ak (k 0)。选 a的连续前 10项： 1111100011 ，将其代入线性递推式可得线性方程组：c1 c2 c3 c4 c5 0c2 c3 c4 c5 0c3 c4 c5 0c4 c5 1c1 c5 1解该线性方程组得：c10,c20,c31,c40,c51，故f1 (x)1x3x5 。(2)设 a (3 )的极小多项式为： f2(x) 1 c1x c2x2 c3x3 c4x4 c5 x5 ，则其对应的线性递 推式为：ak 5 c1ak 4 c2ak 3 c3ak 2 c4ak (k 0)。选 a (3)的连续前 10 项：

27、1011100010 ，将其代入线性递推式可得线性方程组：c1 c2 c3 c5 0c2 c3 c4 0c3 c4 c5 0c4 c5 1c1 c5 0解该线性方程组得： c1 1,c2 1,c3 1,c4 0,c5 1， f2(x) 1 x x2 x3 x5 。(3) 设 a(5) 的极小多项式为： f3(x) 1 c1x c2x2 c3x3 c4x4 c5x5 ，则其对应的线性递 推式为：ak 5 c1ak 4 c2ak 3 c3ak 2 c4ak (k 0)。选a(5)的连续前 10项： 0010101100 ，将其代入线性递推式可得线性方程组：c1c30c2c41c1c3c51c1c2

28、c40c2c3c50解该线性方程组得： c1 1,c2 0,c3 1,c4 1,c5 1 ， f 3(x) 1 x x3 x4 x5 若序列的联接多项式是本原多项式，则其特征多项式也为本原多项式，所以，所有 5 次本原多 项式为：f1(x) 1 x3 x5 。f 2(x) 1 x x2 x3 x5。f 3(x) 1 x x3 x4 x5 。25f4(x) 1 x2 x5 。f5(x) 1 x2 x3 x4 x5 。f6(x) 1 x x2 x4 x5 。18设 a 是一周期序列，若a 中有长为 n 的游程，则 a 的极小多项式的次数一定n。证明：假设 a 的极小多项式的次数 k n 。若 a

29、中有长为 n 的 1 游程，则在 k 级周期序列中至少有 2 个全 1 的状态与全 1 状态仅出现一次矛盾。若 a中有长为 n的 0 游程，则以 00000, 为初态的序列只能产生零序列不能出现 k个(0 0001, ) 的形式，所以假设不成立。故 a 的极小多项式的次数一定n19设 a (a0,a1,a3, )是n( 1)级 m序列，试求数对：(ak,ak t )，(k 0,1, ,2n 2，1 t 2n 2) 为 (0, 0)的次数。解一： a一个周期段中 0和1的个数分别为 2n1 1，2n n 1 n 1 x 2 y 2可解得 x 2n 2 1即(0,0)的次数为 2n 2 120用

30、梅西算法 ，求产生下列有限序列的最短线性反馈移位寄存器的联接多项式。(1)a (1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0)。(2)b (1 1 1 1 0 1 1 1 1 0 )。1) a (11101110001010110100 )解 ： 设a01, a11，a21,a30, a41,a51, a61, a70,a80, a90则(ak,ak t )为( 0,0)的总个数为 c22n1 1 1n1又重复度为 2n 1 1(ak,ak t )为(0,0)的个数为 c2n112n1 1 2n 2 1解:Lt(a)和a Lt(a)都是m序列， m序列中 0有

31、2n1 1个，1有2n 1个，(ak,ak t) 有(0，0)，(0，1)，(1，0)，(1，1)四种情况，设(0，0)的个数为 x ，(1,1)个数为 y,则根据 0,1分布知(0，1)的个数为 2n 1 1-x,n11， 0)的个数为 2n 1y,故a101, a110, a121, a13 0, a14 1, a15 1, a16 0, a17 1,a18 0, a19 0 第 0x y 2 1步： f0(x) 1, l0 0则：f1 (x) 1 x l1 1第 2 步：计算 d1 ： d 1 a1 a 0 0则：f2 (x)f1 (x)1 xl2l1 1第 3 步：计算 d 2 ： d

32、 2 a2 a1 0则：f3(x)f2 (x)1 xl3l2 1第 4 步：计算 d3 ： d3 a3 a2 1，又有 m 0 使 l0 l1 l 2 l3 1 则： f4(x) f3(x) x3 f0 (x) 1 x x3l4 max(l 3 , 4 l3) 3第 5步：计算 d4 ： d4 a4 a3 a1 0则：f5 (x) f4 (x) 1 x x3 l5 l4 3第 6 步：计算 d5 ： d5 a5 a4 a2 1，又有 m 3 使 l3 l4 l5 3则：f6(x) f5(x) x5 3 f3 (x) 1 x x2l6max(l5 ,6 l5 ) 3第 7步：计算 d6： d6

33、a6 a5 a4 1，又有 m 3使 l3 l4 l5 l6 3则：f7(x) f6(x) x3 f3 (x) 1 x x2 x3 x4l7max(l6,7 l6 ) 4第 8步：计算 d7 ： d7 a7 a6 a5 a4 a3 1，又有 m 6使 l6 l7 4 则：f8(x) f7(x) xf6 (x) 1 x4l8max(l 7 ,8 l7 ) 4第 9 步：计算 d8 ： d8 a8 a 4 1，又有 m 6 使 l 6 l7 l8 4则：f9(x) f 8(x) x2 f6(x) 1 x2 x3l9max(l8,9 l8 ) 5则：f10(x) f9 (x) xf8(x) 1 x

34、x2 x3 x5l10 max(l9 ,10 l9) 5第 11 步：计算 d10： d10 a10 a9 a8 a7 a5 0则：f11( x) f10(x) 1 x x2 x3 x5l11 l10 5第 12 步：计算 d11： d11 a11 a10 a9 a8 a 6 0则：f12 (x) f11(x) 1 x x2 x3 x5l12l 11 5第 13 步：计算 d12： d12 a12 a11 a10 a9 a7 0则：f13 (x) f12 (x) 1 x x2 x3 x5l13l 12 5第 14 步：计算 d13： d13 a13 a12 a11 a10 a 8 0则：f14

35、 (x) f13 (x) 1 x x2 x3 x5l14l 13 5第 15 步：计算 d14： d14 a14 a13 a12 a11 a9 0则：f15 (x) f14 (x) 1 x x2 x3 x5l15l 14 5第 16 步：计算 d15 ：d 15 a15 a14 a13 a12 a10 0则：f16 (x) f15 (x) 1 x x2 x3 x5l16l 15 5第 17 步：计算 d16 ：d 16 a16 a15 a14 a13 a11 0则：f17 ( x) f16 (x) 1 x x2 x3 x5l17l 16 5第 18 步：计算 d17 ：d17 a17 a16

36、a15 a14 a9 0则：f18 (x) f17 (x) 1 x x2 x3 x5l18l 17 5第 19 步：计算 d18 ：d 18 a18 a17 a16 a15 a13 0则：f19 (x) f18 (x) 1 x x2 x3 x5l19l 18 5第 20 步：计算 d19 ：d 19 a19 a18 a17 a16 a14 0则：f20 ( x) f19 (x) 1 x x2 x3 x5l20l19 5因此， 1 x x2 x3 x5 , 5 就是产生此序列的最短线性移位寄存器2) b (1111011110 )解：设 a01,a11，a 21, a31, a 40, a 51

37、, a 61, a71, a81, a90第 0 步： f 0 ( x) 1, l 0 0第1 步：计算 d0 ：d0 a0 1, l0 0则：f1 (x) 1 x l1 1第2 步：计算 d1 ：d1 a1 a0 0则：f2 (x) f1(x) 1 x l2 l1 1第3 步：计算 d2 ：d2 a2 a1 0则：f3 (x) f2 (x) 1 x l3 l 2 1第4 步：计算 d3 ：d3 a3 a2 0则：f 4(x) f3(x) 1 xl 4 l3 1第 5 步：计算 d 4 ： d4 a4 a3 1则： f5(x) f4(x) x4 f0(x) 1 x x4l5 max(l 4 ,

38、5 l4 ) 4第 6 步：计算 d5 ： d5 a5 a4 a1 0则： f6 (x) f5(x) 1 x x4l6 l 5 4第 7步：计算 d6： d6 a6 a5 a2 1，又有 m 4使l4 l5 l6 4 则： f7(x) f6(x) x2 f4(x) 1 x x2 x3 x4l7 max(l6 ,7 l6 ) 4第 8 步：计算 d 7 ： d7 a7 a6 a5 a4 a3 0l8 l7 4第 9 步：计算 d8 ： d8 a8a7 a6a5a40则： f9 (x)f8 (x) 1xx2x3x4l 9 l8 4第 10 步：计算 d9 ： d9 a9a8 a7a6a50则： f

39、10 (x)f9 (x) 1xx2x3x4l 10 l9 4因此， 1 x x2 x 3 x4 , 4 就是产生此序列的最短线性移位寄存器21设周期序列 a (1 16)的极小多项式为 x6 x 1，求 a 的有理分式表示。解： a(x)ai xii0g(x)f(x)因为 f (x)为 a的极小多项式，故 0g(x) 0f (x) 6，则45g(x) f (x) a(x) 1 x4 x5 ，故 a 的有理分式为：54x x 1 a(x) 6 。x x 122设周期序列 a 的有理分式表示为： a(x)1 x21 x3 x5解：a(x) (1(1x xx2)x( 3 4 6 7 ，求序列 a及其

40、周期。1)(1x3x2)x5)35，令 f(x) 1 x1 x x x x x x x5 ，为本原多项式p(a) 2 1 31 ，序列以 11111为初态的序列为：111110001101110101000010010110023设 a (a0,a1, ,ap 1,a0,a1, )是周期为 p 的二元周期序列，则序列1a (ap 1,ap 2,a0 , ap 1,ap 2 , )的极小多项式为ma (x) 。证明：设a 的极小多项式为 m1(x)，则 a 的形式幂级数表示为有理分式：aii0a0 a1xap 1xp 11 x pmg11(xx) 其中 (g1(x),m1(x) 1bixii0b0 b1xbp 1x p 1mg22(xx) 其中 (g2(x),m2(x) 1令 h1(x