移位寄存器第三章答案.doc

图第三章习题参考答案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) 设初态为( 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故以 (10101)为初态的状态转 移图为：10101 01011 10111 01110 11101 11011 10110 01100 11000 1000100011 00111 01111 11111 11110 11100 11001 10011 00110 0110111010 10100 01001 10010 00100 01000 10000 00001 00010 0010101010 10101由此可得，输出序列为： a 1010111011000111110011010010000 ⋯一个周期4．证明： n级线性反馈移位寄存器的状态转移变换是 n维线性空间 F2n 上的线性变换证明：设Tf 为n级线性移位寄存器的状态转移变换， 对 , 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 , ,kan 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 ，则 ST S 于是，对 Sk ，有 Sk STk ST T k SkT ，即ak ak ， k 0从而 ( p(a) )为序列 a 的周期，与 p(a) 为最小周期矛盾故S ， ST ，⋯， STp(a) 1必两两不同6．证明：若 a G( f )的极小多项式次数为 n( 1)，则 a， La，⋯， Ln 1a必线性无关 证明：由题知 a 0，假设 a，La，⋯，Ln 1 a线性相关， 则存在不全为零一组数 c0,c1, ,cn 1 使得c0 a c1La cn 1Ln 1a 0 (c0 c1 L cn 1Ln 1 )a 0令： g~(x) c0 c1x cn 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 ( 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 c2x2 cm1xm 1 xm，则 m~a(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 ) ， 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 c1La cn 1L a 0 (c0 c1 L cn 1L )a令： g~(x) c0 c1x c2 x cn 1 x ，则有 b g~(L )a b g(D )a ，即 b G ( 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)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) F2[x]， f(0) 01)证明 G( f )中任一平移等价类中序列有相同的极小多项 式与周期 2) G( f )中有相同的极小多项式的序列是否一定在同一平移等价类中？为什么？在什 么条件下，序列的极小多项式相同当且仅当序列属于同一平移等价类？证明：( 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) ，则 m~a (L)a 0，从而m~a(L)b m~a(L)Lt a Ltm~a(L)a 0 ma(D)b 0，即 ma (x)是b的联接多项式， 于是 mb ( x) |ma (x) ，同理可证 ma ( x) | mb ( x) 因此 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 F2[x]1)证明以 0 1 1 1 1 0 0 1 0 0 0 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, ，则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 1[1] 1[7] ，Gf2 2[1] 1[2]Gf G f1Gf2 2(1,2)[[1,1]] (1,1)[[1,2]] 2(1,2)[[ 7,1]] (1,1)[[ 7,2]]2[1] [2] 1[7] 1[14]显然，周期为 14 的序列是由 Gf 中 1[7]和 Gf 中 1[2]唯一生成3由 f1(x) 1 x x3 ，令初态为 S0 (011)，输出序列为：00111010011101001110 1 由 f 2(。