第三章习题参考答案1．画出以1)(246+++=x x x x f 为联接多项式的线性移位寄存器逻辑框图，及其对应的状态图。

解：由1)(246+++=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 。

联接多项式为：7421)(x x x x f +++=。

特征多项式为：7531)(~x x x x f +++=（2）状态转移矩阵：⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0100000101000000010001000100000001000000011000000。

（3）输出序列：)111111111(ΛΛ=-a 。

3．设5级线性反馈移位寄存器的联接多项式为1)(25++=x x x f ，初态为（10101）。

求输出序列a 。

解：由联接多项式得，反馈函数为：41521),,,(x x x x x f +=Λ。

故以)10101(为初态的状态转移图为：1010101010001010001000001100000100000100100100100110100110100110100110100111100111100111101111101111001110001110001110000110010110110111110101110101110101110101→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→ 由此可得，输出序列为：=a 44444443444444421一个周期0110100100000011111001010111011…。

4．证明：n 级线性反馈移位寄存器的状态转移变换是n 维线性空间nF 2上的线性变换。

证明：设f T 为n 级线性移位寄存器的状态转移变换，对nF 2,∈∀βα，令),,,(110-=n a a a Λα，),,,(110-=n b b b Λβ，有：),,,(),,,()(121110∑=--==ni i n i n f f a c a a a a a T T ΛΛα，),,,(),,,()(121110∑=--==n i i n i n f f b c b b b b b T T ΛΛβ。

)()(),,,(),,,())(,,,(),,,()(12112112211111100βαβαf f i n ni i i n n i i ni 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 ∈∀，))((),,,(),,,()(121110ααf i n ni i n f f T k a c k ka ka ka ka ka T k T ===-=-∑ΛΛ。

故n 级线性反馈移位寄存器的状态转移变换是n 为线性空间nF 2上的线性变换。

5．设二元周期序列a 0≠的极小多项式为，T 是对应的状态转换矩阵，则S ，ST ，…，1)(-a p ST必两两不同。

其中),,,(120-=n a a a S Λ。

证明：若∃j i ,，1)(0-≤≠≤a p j i ，使得j i ST ST = （不妨设 j i <）。

令 j i -=τ，则 S ST =τ。

于是，对k S ∀，有 ττT S T ST ST S k k k k ===，即k k a a =+τ ，0≥k 。

从而τ（)(a p <）为序列a 的周期，与)(a p 为最小周期矛盾。

故S ，ST ，…，1)(-a p ST必两两不同。

6．证明：若a )(f G ∈的极小多项式次数为)1(≥n ，则a ，a L ，…，a L n 1-必线性无关。

证明：由题知0≠a ，假设a ，a L ，…，a L n 1-线性相关，则存在不全为零一组数110,,,-n c c c Λ使得0)(011101110=+++==+++----a L c L c c a L c a L c a c n n n n ΛΛ令：)(~x g 1110--+++=n n x c x c c Λ，则)(x g 也产生序列a ，而1)(0-≤∂n x g ，与a 的极小多项式)(x f 的次数为n 矛盾，故假设不成立，因此，a ，a L ，…，a Ln 1-必线性无关。

7．证明：若a )(f G ∈，n x f =∂)(0，0≠a ，则a ，a L ，…，a L n 1-构成)(f G 的一组基当且仅当a 以)(x f 为极小多项式。

证明：充分性：由n x f o=∂)(知)(f G 是n 维的。

又a )(f G ∈，a 以)(x f 为极小多项式，由上题结论可知a ，a L ，…，a Ln 1-线性无关，故构成)(f G 的一组基。

必要性：设a 的极小多项式为)(x m a ，m x m a o =∂)(，则)(|)(x f x m a ，n m ≤。

令：m m m a x x c x c x c x m +++++=--112211)(Λ，则0)(~=a L m a，从而， a ，a L ，…，a L m线性相关。

而a ，a L ，…，a Ln 1-为)(f G 的一组基，所以1->n m ，即n m ≥，故)()(x f x m a =。

即a 以)(x f 为极小多项式。

8．证明：若a )(f G ∈，n x f =∂)(0，a 以)(x f 为极小多项式，则)(f G 中每个序列均可唯一地表成a D g )(，并且a D g )(的极小多项式为))(),(()(x f x g x f ，其中n x g <∂)(0，D 为延迟变换。

从而)(f G 中有)(f ϕ个序列以)(x f 为极小多项式，其中)(f ϕ是次数f 0∂≤，且和)(x f 互素的多 项式的个数。

证明：（1）上题结论知，)(f G b ∈∀，都可由a ，a L ，…，a L n 1-为线性表出，则存在一组数110,,,-n c c c Λ 使得：a L c L c c a L c a L c a cb n n n n )(011101110----+++==+++=ΛΛ令：112210)(~--++++=n n x c x c x c c x g Λ，则有a D g b a L g b )()(~=⇔=，即)(f G b ∈∀均可唯一的表示成a D g )(的形式。

（2）令：)())(),((x d x g x f =，则)()()(1x f x d x f =，)()()(1x g x d x g =，1))(),((11=x g x f 。

设a D g )(的极小多项式为)(2x f ，则只须证明))(),(()()()(12x g x f x f x f x f ==。

)()()()()()()())()((11111====a D f D g a D g D f aD g D d D f a D g D f Θ∴)(1x f 为a D g )(的联接多项式，从而)(|)(12x f x f 。

又，由0)()()()()((122==a D g D d D f a D g D f 知，)()()(|)(12x g x d x f x f ，从而)()(|)(121x g x f x f ，而1))(),((11=x g x f ，故)(|)(21x f x f ，所以)()(12x f x f =，即 ))(),(()(x g x f x f 为-a D g )(的极小多项式。

（3）当1))(),((=x f x g 时，-a D g )(以)(x f 为极小多项式，而次数n <且与)(x f 互素的多项式)(x g 共有)(f ϕ个。

9．设)(x f ][2x F ∈，0)0(≠f 。

（1）证明)(f G 中任一平移等价类中序列有相同的极小多项式与周期。

（2）)(f G 中有相同的极小多项式的序列是否一定在同一平移等价类中？为什么？在什么条件下，序列的极小多项式相同当且仅当序列属于同一平移等价类？证明：（1）设a )(f G ∈，a L b t=（1)(0-≤≤a p t ）是其平移等价序列，且有t k k a b +=，0≥k 。

因为k t k a p t k a p k b a a b ===++++)()(，0≥k 。

故)(|)(a p b p ，同理可证)(|)(b p a p ，所以)()(a p b p =。

设a 的极小多项式为)(x m a ，b 的极小多项式为)(x m b ，则 0)(~=a L m a，从而 0)(0)(~)(~)(~=⇔===b D m a L m L a L L m b L m aa t t a a ， 即)(x m a 是b 的联接多项式，于是)(|)(x m x m a b ，同理可证)(|)(x m x m b a 。

因此)()(x m x m b a =。

（2）不一定。

例如，1)(234++++=x x x x x f 是4次不可约多项式，)(f G 中非零序列都以)(x f 为的极小多项式，但f G 中有3个周期为5的圈，显然这3个圈对应3个不同的平移等价类。

（或令Λ11000=a ，Λ10111=b ，)(,f G b a ∈，但a 与b 不在同一等价类中。

）当)(x f 是本原多项式时，序列的极小多项式相同当且仅当序列属于同一平移等价类。

10．设)(x f )()(21x f x f =，其中311)(x x x f ++=，221)(x x f +=][2x F ∈。

（1）证明以0 1 1 1 1 0 0 1 0 0 0 0 1 1为一个周期段的二元序列属于)(f G 。

（2）将上述序列分解成两个序列a 和b 之和，使得)(1f G a ∈，)(2f G b ∈。

证明：（1）1)()()(2521+++==x x x x f x f x f ， 令初态为=0S （01111），则)(x f 产生的序列为：Λ,00110111100100故以0 1 1 1 1 0 0 1 0 0 0 0 1 1为周期段的二元序列属于)(f G 。