移位寄存器 第三章答案

1、第三章习题参考答案1画出以为联接多项式的线性移位寄存器逻辑框图，及其对应的状态图。解：由，得反馈函数为，故（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），给出输出序列。解：(1)由逻辑框图得，递推式为： (。 联接多项式为：。特征多项式为： （2）状态转移矩阵：。

2、 （3）输出序列：。3设5级线性反馈移位寄存器的联接多项式为，初态为（10101）。求输出序列。解：由联接多项式得，反馈函数为：。故以为初态的状态转移图为：由此可得，输出序列为：。4证明：级线性反馈移位寄存器的状态转移变换是维线性空间上的线性变换。证明：设为级线性移位寄存器的状态转移变换，对，令，有：，。 对 ，。故级线性反馈移位寄存器的状态转移变换是为线性空间上的线性变换。5设二元周期序列的极小多项式为，是对应的状态转换矩阵，则，必两两不同。其中。证明：若，使得 （不妨设 ）。令 ，则 。于是，对，有 ，即 ，。从而（）为序列的周期，与为最小周期矛盾。故，必两两不同。6证明：若的极小多项式次

3、数为，则，必线性无关。证明：由题知，假设，线性相关，则存在不全为零一组数 使得令：，则也产生序列，而，与的极小多项式的次数为矛盾，故假设不成立，因此，必线性无关。7证明：若，则，构成的一组基当且仅当以为极小多项式。 证明：充分性：由知是维的。又，以为极小多项式，由上题结论可知，线性无关，故构成的一组基。必要性：设的极小多项式为，则，。令：，则，从而，线性相关。而，为的一组基，所以，即，故。即以为极小多项式。8证明：若，以为极小多项式，则中每个序列均可唯一地表成，并且的极小多项式为，其中，为延迟变换。从而中有个序列以为极小多项式，其中是次数，且和互素的多项式的个数。证明：（1）上题结论知，都可由

4、，为线性表出，则存在一组数 使得：令：，则有，即均可唯一的表示成的形式。（2）令：，则，。设的极小多项式为，则只须证明。 为的联接多项式，从而。 又，由知，从而，而，故，所以，即 为的极小多项式。（3）当时，以为极小多项式，而次数且与互素的多项式共有个。9设，。（1）证明中任一平移等价类中序列有相同的极小多项式与周期。（2）中有相同的极小多项式的序列是否一定在同一平移等价类中？为什么？在什么条件下，序列的极小多项式相同当且仅当序列属于同一平移等价类？ 证明：（1）设，（）是其平移等价序列，且有，。因为，。故，同理可证，所以。设的极小多项式为，的极小多项式为，则 ，从而，即是的联接多项式，于是，

5、同理可证。因此。（2）不一定。例如，是4次不可约多项式，中非零序列都以为的极小多项式，但中有3个周期为5的圈，显然这3个圈对应3个不同的平移等价类。（或令，但与不在同一等价类中。）当是本原多项式时，序列的极小多项式相同当且仅当序列属于同一平移等价类。10设，其中，。（1）证明以0 1 1 1 1 0 0 1 0 0 0 0 1 1为一个周期段的二元序列属于。（2）将上述序列分解成两个序列和之和，使得，。证明：（1）， 令初态为（01111），则产生的序列为：故以0 1 1 1 1 0 0 1 0 0 0 0 1 1为周期段的二元序列属于。 （2）方法一：由知，存在，使得令：，则+，记，=，即有

6、。由引理 3.3.3 的证明过程知， ，故和即为求：，。方法二，。 显然，周期为14的序列是由中17和中12唯一生成。 由 ，令初态为（011），输出序列为：。 由 ，令初态为（01），输出序列为：。 将上述两个输出序列异或求和有：。11设，试问中共有多少序列的平移等价类，每个平移等价类的周期是多少，对每个平移等价类构作出一个序列来。解：由已知得。而，故 中有4个平移等价类：一个周期为1的平移等价类； 一个周期为3的平移等价类； 两个周期为6的平移等价类。 周期为1的平移等价类中代表序列为零序列， 周期为3的平移等价类中代表序列为： 两个周期为6的平移等价类中代表序列分别为：和。12求联接多项

7、式为的线性移位寄存器的状态图中的圈长和圈数。解：令，且两两互素，又，。由上题知，。对于，。对于，。中有周期为1，3，7的圈各一个，2个周期为6的圈，周期为15，105的圈各4 个，周期为30，210的圈各6个，周期为21的圈1个，周期为42的圈2个。13设，为周期序列，为正整数。证明：（1）。（2）。（3）若，则。证明：（1） （2） （3）若，则 14设为次本原多项式，证明与的极小多项式为互反多项式。其中，。证明：设为的一根，因，故由定理3.4.4知：与都为级序列，对应的极小多项式和皆为本原多项式，且和分别为其次本元根。又，即两根互逆，从而和互反，所以与的极小多项式为互反多项式。15求全部7

8、级序列中平移等价类的个数。解：全部7级序列中平移等价类的个数为： 。16用迹函数表示法表示中序列，其中。解：设是在中的一个根，则中共有16条序列，设为，于是有：（1）（2） （3） (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) （16）17已知5级序列： （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次本原多项式。解：，则其中 ，。那么 (1) 设的极小多项式为：，则其对应的线性递推式为：。选的连续前10项：，将其代入线性递推式可得线性方程组：解

9、该线性方程组得：，故。（2）设的极小多项式为：，则其对应的线性递推式为：。选的连续前10项：，将其代入线性递推式可得线性方程组：解该线性方程组得：，。(3) 设的极小多项式为：，则其对应的线性递推式为：。选的连续前10项：，将其代入线性递推式可得线性方程组：解该线性方程组得：，若序列的联接多项式是本原多项式，则其特征多项式也为本原多项式，所以，所有5次本原多项式为：。18设是一周期序列，若中有长为的游程，则的极小多项式的次数一定。证明：假设的极小多项式的次数。若中有长为的1游程，则在级周期序列中至少有2个全1的状态与全1状态仅出现一次矛盾。若中有长为的0游程，则以为初态的序列只能产生零序列不能

10、出现的形式，所以假设不成立。故的极小多项式的次数一定19设是（）级序列，试求数对：，（，）为的次数。解一：一个周期段中0和1的个数分别为， 则为的总个数为 又重复度为 为的个数为解:和都是序列，序列中0有个，1有个，有（0，0），（0，1），（1，0），（1，1）四种情况，设（0，0）的个数为，（1,1）个数为,则根据0,1分布知（0，1）的个数为,（1，0）的个数为,故可解得即(0,0)的次数为20用梅西算法，求产生下列有限序列的最短线性反馈移位寄存器的联接多项式。（1）（1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0）。（2）（1 1 1 1 0 1 1 1

11、 1 0 ）。（1）解：设 第0步： 第1步：计算： 则： 第2步：计算： 则： 第3步：计算： 则： 第4步：计算：，又有使 则： 第5步：计算： 则： 第6步：计算：，又有使 则： 第7步：计算：，又有使 则： 第8步：计算：，又有使则： 第9步：计算：，又有使则： 第10步：计算：，又有使则： 第11步：计算： 则： 第12步：计算：则： 第13步：计算： 则： 第14步：计算： 则： 第15步：计算： 则： 第16步：计算： 则： 第17步：计算： 则： 第18步：计算： 则： 第19步：计算： 则： 第20步：计算： 则： 因此，就是产生此序列的最短线性移位寄存器 （2）解：设第0步

12、：第1步：计算： 则： 第2步：计算： 则： 第3步：计算： 则： 第4步：计算： 则： 第5步：计算： 则： 第6步：计算： 则： 第7步：计算：，又有使 则： 第8步：计算：则： 第9步：计算：则： 第10步：计算：则： 因此，就是产生此序列的最短线性移位寄存器21设周期序列（1 1 1 1 0 1，）的极小多项式为，求的有理分式表示。解： 因为为的极小多项式，故，则，故的有理分式为：。22设周期序列的有理分式表示为：，求序列及其周期。解：，令，为本原多项式 ，序列以为初态的序列为： 23设是周期为的二元周期序列，则序列的极小多项式为。证明：设的极小多项式为，则的形式幂级数表示为有理分式： 其中记，的极小多项式为，则的形式幂级数表示为有理分式： 其中令则： 又，。即与的极小多项式为互反多项式24设周期序列与