移位寄存器 第三章答案

1、第三章習(xí)題參考答案1畫出以為聯(lián)接多項(xiàng)式的線性移位寄存器邏輯框圖，及其對應(yīng)的狀態(tài)圖。解：由，得反饋函數(shù)為，故（1）邏輯框圖：（2）狀態(tài)圖： 狀態(tài)圈-1： 狀態(tài)圈-2： 狀態(tài)圈-3： 狀態(tài)圈-4：狀態(tài)圈-5： 狀態(tài)圈-6： 狀態(tài)圈-7： 狀態(tài)圈-8： 狀態(tài)圈-9： 狀態(tài)圈-10： 狀態(tài)圈-11： 狀態(tài)圈-12：2已知圖3-2所示的7級線性反饋移位寄存器：圖3-2（1）繪出該移位寄存器的線性遞推式，聯(lián)接多項(xiàng)式及特征多項(xiàng)式。（2）給出狀態(tài)轉(zhuǎn)移矩陣。（3）設(shè)初態(tài)為（1 1 1 1 1 1 1），給出輸出序列。解：(1)由邏輯框圖得，遞推式為： (。 聯(lián)接多項(xiàng)式為：。特征多項(xiàng)式為： （2）狀態(tài)轉(zhuǎn)移矩陣：。

2、 （3）輸出序列：。3設(shè)5級線性反饋移位寄存器的聯(lián)接多項(xiàng)式為，初態(tài)為（10101）。求輸出序列。解：由聯(lián)接多項(xiàng)式得，反饋函數(shù)為：。故以為初態(tài)的狀態(tài)轉(zhuǎn)移圖為：由此可得，輸出序列為：。4證明：級線性反饋移位寄存器的狀態(tài)轉(zhuǎn)移變換是維線性空間上的線性變換。證明：設(shè)為級線性移位寄存器的狀態(tài)轉(zhuǎn)移變換，對，令，有：，。 對 ，。故級線性反饋移位寄存器的狀態(tài)轉(zhuǎn)移變換是為線性空間上的線性變換。5設(shè)二元周期序列的極小多項(xiàng)式為，是對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣，則，必兩兩不同。其中。證明：若，使得 （不妨設(shè) ）。令 ，則 。于是，對，有 ，即 ，。從而（）為序列的周期，與為最小周期矛盾。故，必兩兩不同。6證明：若的極小多項(xiàng)式次

3、數(shù)為，則，必線性無關(guān)。證明：由題知，假設(shè)，線性相關(guān)，則存在不全為零一組數(shù) 使得令：，則也產(chǎn)生序列，而，與的極小多項(xiàng)式的次數(shù)為矛盾，故假設(shè)不成立，因此，必線性無關(guān)。7證明：若，則，構(gòu)成的一組基當(dāng)且僅當(dāng)以為極小多項(xiàng)式。 證明：充分性：由知是維的。又，以為極小多項(xiàng)式，由上題結(jié)論可知，線性無關(guān)，故構(gòu)成的一組基。必要性：設(shè)的極小多項(xiàng)式為，則，。令：，則，從而，線性相關(guān)。而，為的一組基，所以，即，故。即以為極小多項(xiàng)式。8證明：若，以為極小多項(xiàng)式，則中每個(gè)序列均可唯一地表成，并且的極小多項(xiàng)式為，其中，為延遲變換。從而中有個(gè)序列以為極小多項(xiàng)式，其中是次數(shù)，且和互素的多項(xiàng)式的個(gè)數(shù)。證明：（1）上題結(jié)論知，都可由

4、，為線性表出，則存在一組數(shù) 使得：令：，則有，即均可唯一的表示成的形式。（2）令：，則，。設(shè)的極小多項(xiàng)式為，則只須證明。 為的聯(lián)接多項(xiàng)式，從而。 又，由知，從而，而，故，所以，即 為的極小多項(xiàng)式。（3）當(dāng)時(shí)，以為極小多項(xiàng)式，而次數(shù)且與互素的多項(xiàng)式共有個(gè)。9設(shè)，。（1）證明中任一平移等價(jià)類中序列有相同的極小多項(xiàng)式與周期。（2）中有相同的極小多項(xiàng)式的序列是否一定在同一平移等價(jià)類中？為什么？在什么條件下，序列的極小多項(xiàng)式相同當(dāng)且僅當(dāng)序列屬于同一平移等價(jià)類？ 證明：（1）設(shè)，（）是其平移等價(jià)序列，且有，。因?yàn)?，。故，同理可證，所以。設(shè)的極小多項(xiàng)式為，的極小多項(xiàng)式為，則 ，從而，即是的聯(lián)接多項(xiàng)式，于是，

5、同理可證。因此。（2）不一定。例如，是4次不可約多項(xiàng)式，中非零序列都以為的極小多項(xiàng)式，但中有3個(gè)周期為5的圈，顯然這3個(gè)圈對應(yīng)3個(gè)不同的平移等價(jià)類。（或令，但與不在同一等價(jià)類中。）當(dāng)是本原多項(xiàng)式時(shí)，序列的極小多項(xiàng)式相同當(dāng)且僅當(dāng)序列屬于同一平移等價(jià)類。10設(shè)，其中，。（1）證明以0 1 1 1 1 0 0 1 0 0 0 0 1 1為一個(gè)周期段的二元序列屬于。（2）將上述序列分解成兩個(gè)序列和之和，使得，。證明：（1）， 令初態(tài)為（01111），則產(chǎn)生的序列為：故以0 1 1 1 1 0 0 1 0 0 0 0 1 1為周期段的二元序列屬于。 （2）方法一：由知，存在，使得令：，則+，記，=，即有

6、。由引理 3.3.3 的證明過程知， ，故和即為求：，。方法二，。 顯然，周期為14的序列是由中17和中12唯一生成。 由 ，令初態(tài)為（011），輸出序列為：。 由 ，令初態(tài)為（01），輸出序列為：。 將上述兩個(gè)輸出序列異或求和有：。11設(shè)，試問中共有多少序列的平移等價(jià)類，每個(gè)平移等價(jià)類的周期是多少，對每個(gè)平移等價(jià)類構(gòu)作出一個(gè)序列來。解：由已知得。而，故 中有4個(gè)平移等價(jià)類：一個(gè)周期為1的平移等價(jià)類； 一個(gè)周期為3的平移等價(jià)類； 兩個(gè)周期為6的平移等價(jià)類。 周期為1的平移等價(jià)類中代表序列為零序列， 周期為3的平移等價(jià)類中代表序列為： 兩個(gè)周期為6的平移等價(jià)類中代表序列分別為：和。12求聯(lián)接多項(xiàng)

7、式為的線性移位寄存器的狀態(tài)圖中的圈長和圈數(shù)。解：令，且兩兩互素，又，。由上題知，。對于，。對于，。中有周期為1，3，7的圈各一個(gè)，2個(gè)周期為6的圈，周期為15，105的圈各4 個(gè)，周期為30，210的圈各6個(gè)，周期為21的圈1個(gè)，周期為42的圈2個(gè)。13設(shè)，為周期序列，為正整數(shù)。證明：（1）。（2）。（3）若，則。證明：（1） （2） （3）若，則 14設(shè)為次本原多項(xiàng)式，證明與的極小多項(xiàng)式為互反多項(xiàng)式。其中，。證明：設(shè)為的一根，因，故由定理3.4.4知：與都為級序列，對應(yīng)的極小多項(xiàng)式和皆為本原多項(xiàng)式，且和分別為其次本元根。又，即兩根互逆，從而和互反，所以與的極小多項(xiàng)式為互反多項(xiàng)式。15求全部7

8、級序列中平移等價(jià)類的個(gè)數(shù)。解：全部7級序列中平移等價(jià)類的個(gè)數(shù)為： 。16用跡函數(shù)表示法表示中序列，其中。解：設(shè)是在中的一個(gè)根，則中共有16條序列，設(shè)為，于是有：（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次本原多項(xiàng)式。解：，則其中 ，。那么 (1) 設(shè)的極小多項(xiàng)式為：，則其對應(yīng)的線性遞推式為：。選的連續(xù)前10項(xiàng)：，將其代入線性遞推式可得線性方程組：解

9、該線性方程組得：，故。（2）設(shè)的極小多項(xiàng)式為：，則其對應(yīng)的線性遞推式為：。選的連續(xù)前10項(xiàng)：，將其代入線性遞推式可得線性方程組：解該線性方程組得：，。(3) 設(shè)的極小多項(xiàng)式為：，則其對應(yīng)的線性遞推式為：。選的連續(xù)前10項(xiàng)：，將其代入線性遞推式可得線性方程組：解該線性方程組得：，若序列的聯(lián)接多項(xiàng)式是本原多項(xiàng)式，則其特征多項(xiàng)式也為本原多項(xiàng)式，所以，所有5次本原多項(xiàng)式為：。18設(shè)是一周期序列，若中有長為的游程，則的極小多項(xiàng)式的次數(shù)一定。證明：假設(shè)的極小多項(xiàng)式的次數(shù)。若中有長為的1游程，則在級周期序列中至少有2個(gè)全1的狀態(tài)與全1狀態(tài)僅出現(xiàn)一次矛盾。若中有長為的0游程，則以為初態(tài)的序列只能產(chǎn)生零序列不能

10、出現(xiàn)的形式，所以假設(shè)不成立。故的極小多項(xiàng)式的次數(shù)一定19設(shè)是（）級序列，試求數(shù)對：，（，）為的次數(shù)。解一：一個(gè)周期段中0和1的個(gè)數(shù)分別為， 則為的總個(gè)數(shù)為 又重復(fù)度為 為的個(gè)數(shù)為解:和都是序列，序列中0有個(gè)，1有個(gè)，有（0，0），（0，1），（1，0），（1，1）四種情況，設(shè)（0，0）的個(gè)數(shù)為，（1,1）個(gè)數(shù)為,則根據(jù)0,1分布知（0，1）的個(gè)數(shù)為,（1，0）的個(gè)數(shù)為,故可解得即(0,0)的次數(shù)為20用梅西算法，求產(chǎn)生下列有限序列的最短線性反饋移位寄存器的聯(lián)接多項(xiàng)式。（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）解：設(shè) 第0步： 第1步：計(jì)算： 則： 第2步：計(jì)算： 則： 第3步：計(jì)算： 則： 第4步：計(jì)算：，又有使 則： 第5步：計(jì)算： 則： 第6步：計(jì)算：，又有使 則： 第7步：計(jì)算：，又有使 則： 第8步：計(jì)算：，又有使則： 第9步：計(jì)算：，又有使則： 第10步：計(jì)算：，又有使則： 第11步：計(jì)算： 則： 第12步：計(jì)算：則： 第13步：計(jì)算： 則： 第14步：計(jì)算： 則： 第15步：計(jì)算： 則： 第16步：計(jì)算： 則： 第17步：計(jì)算： 則： 第18步：計(jì)算： 則： 第19步：計(jì)算： 則： 第20步：計(jì)算： 則： 因此，就是產(chǎn)生此序列的最短線性移位寄存器 （2）解：設(shè)第0步

12、：第1步：計(jì)算： 則： 第2步：計(jì)算： 則： 第3步：計(jì)算： 則： 第4步：計(jì)算： 則： 第5步：計(jì)算： 則： 第6步：計(jì)算： 則： 第7步：計(jì)算：，又有使 則： 第8步：計(jì)算：則： 第9步：計(jì)算：則： 第10步：計(jì)算：則： 因此，就是產(chǎn)生此序列的最短線性移位寄存器21設(shè)周期序列（1 1 1 1 0 1，）的極小多項(xiàng)式為，求的有理分式表示。解： 因?yàn)闉榈臉O小多項(xiàng)式，故，則，故的有理分式為：。22設(shè)周期序列的有理分式表示為：，求序列及其周期。解：，令，為本原多項(xiàng)式 ，序列以為初態(tài)的序列為： 23設(shè)是周期為的二元周期序列，則序列的極小多項(xiàng)式為。證明：設(shè)的極小多項(xiàng)式為，則的形式冪級數(shù)表示為有理分式： 其中記，的極小多項(xiàng)式為，則的形式冪級數(shù)表示為有理分式： 其中令則： 又，。即與的極小多項(xiàng)式為互反多項(xiàng)式24設(shè)周期序列與