1、基于有限狀態(tài)機的乘法器設(shè)計與實現(xiàn)n乘法器是運算器不可或缺的重要組成單元，而運算器是微處理器的重要組成部分，所以研究高性能微處理器芯片離不開乘法器的研究。n如今，我們的生活離不開手機、平板電腦等便攜設(shè)備，而其中的嵌入式芯片對乘法器的性能同樣十分依賴。n人們對便攜設(shè)備即要求高性能，又要求較長的待機時間，這就要求在芯片設(shè)計時既要考慮性能的提高又要合理控制功耗。1.乘法器n1.1.什么是乘法器n乘法器的運算速度（運算延遲時間）時間上n設(shè)計電路的芯片面積（所使用的邏輯器件數(shù)量）空間上n電路運行產(chǎn)生的功耗1.2 評估乘法器性能的參數(shù)1.2 評估乘法器性能的參數(shù)n在乘法器設(shè)計中，Booth算法被認為是乘法器

2、設(shè)計的里程碑。nBooth算法通過分析乘數(shù)編碼產(chǎn)生部分積，整體上減少了部分積的數(shù)目，提高了部分積求和速度。n但是，當乘數(shù)的位數(shù)較長時，Booth 算法中編碼的階數(shù)增加，導(dǎo)致邏輯電路的設(shè)計變的十分復(fù)雜，整個運算過程的延遲也明顯增加。因此，Booth 算法不適宜于應(yīng)用在較高階的乘法器設(shè)計中。1.3 booth算法n行旁路乘法器，就是將2選1多路選擇器引入陣列乘法器的設(shè)計中，在每一個全加器下增加了一個多路選擇器，乘數(shù)中的各個數(shù)據(jù)位作為選擇器的輸出控制信號，當乘數(shù)中的某一位為零時，避免了一次加法操作，也減少了加法器的數(shù)量。1.4 行旁路乘法器n使用時序電路實現(xiàn)指令控制或者進行復(fù)雜運算時，一般會按照時鐘

3、周期逐條執(zhí)行指令，很多時候一條指令可能需要多個時鐘周期才能完成。而有限狀態(tài)機從一個狀態(tài)到另一個狀態(tài)的狀態(tài)變換只需一個時鐘周期就可以完成，并且在一個狀態(tài)中狀態(tài)機可以完成許多并行運算和控制操作。因此，在運算規(guī)律比較簡單并且變化狀態(tài)比較有限的情況下，使用有限狀態(tài)機實現(xiàn)的硬件系統(tǒng)比使用時序電路完成相同的功能在速度上會有較高的優(yōu)勢。n有限狀態(tài)機（Finite State Machine，簡稱 FSM）是一種具有離散輸入和輸出系統(tǒng)的數(shù)學(xué)模型，是數(shù)字邏輯電路以及數(shù)字系統(tǒng)的重要組成部分，尤其應(yīng)用于數(shù)字系統(tǒng)核心部件的設(shè)計，以實現(xiàn)高效率高可靠性的邏輯控制。n可以將狀態(tài)機理解為寄存器寄存器和觸發(fā)器觸發(fā)器的集合，寄存

4、器用于存儲所有狀態(tài)狀態(tài)，觸發(fā)器用于實現(xiàn)狀態(tài)之間的轉(zhuǎn)移轉(zhuǎn)移。2 有限狀態(tài)機（FSM）n有限狀態(tài)機的三要素n輸入輸入：狀態(tài)機中各狀態(tài)之間轉(zhuǎn)移的條件。例如，四位乘法器中，乘數(shù)共有 16 種可能的情況，分別用 00001111 表示，這 16 種數(shù)值將作為狀態(tài)機各個狀態(tài)之間的跳轉(zhuǎn)條件。n狀態(tài)狀態(tài)：也稱狀態(tài)變量。例如，可以將寄存器的變化序列作為狀態(tài)。在狀態(tài)機設(shè)計中還包含了“陷阱”狀態(tài)，當輸入非法數(shù)據(jù)時，電路進入“陷阱”狀態(tài)，很快就能恢復(fù)到正常狀態(tài)。這也體現(xiàn)了狀態(tài)機設(shè)計的穩(wěn)定性和安全性。n 輸出輸出：當?shù)竭_某一個特定狀態(tài)時發(fā)生的事件。2.1 FSM的組成n狀態(tài)轉(zhuǎn)換圖n狀態(tài)轉(zhuǎn)移列表nHDL 語言描述n時序圖

5、n算法狀態(tài)機圖，也稱 ASM 圖（類似于流程圖）2.2 FSM的描述方式n邏輯抽象，畫出狀態(tài)轉(zhuǎn)換圖：把一個實際邏輯關(guān)系表示為時序邏輯函數(shù)，用狀態(tài)轉(zhuǎn)換表或者狀態(tài)轉(zhuǎn)換圖來描述n狀態(tài)化簡：合并等價狀態(tài)，得到最簡化的狀態(tài)轉(zhuǎn)換圖。n狀態(tài)分配：即狀態(tài)編碼（格雷碼、獨熱碼等）n選定觸發(fā)器的類型，計算出狀態(tài)方程、驅(qū)動方程和輸出方程n根據(jù)方程畫出邏輯圖2.3 設(shè)計FSM的一般步驟n將有限狀態(tài)機引入乘法器設(shè)計，主要是因為：需要一種電路，能夠隨時記住自己所處的狀態(tài)，而且只在時鐘信號的跳變時刻來臨，并且滿足觸發(fā)條件時，進行狀態(tài)之間的跳轉(zhuǎn)，不滿足條件，則停留在當前的狀態(tài)。而有限狀態(tài)機的工作機制就是狀態(tài)之間的轉(zhuǎn)移。n利用

6、有限狀態(tài)機能產(chǎn)生復(fù)雜的以時鐘跳變沿為前提的同步時序邏輯，并能提供操作邏輯系統(tǒng)的開關(guān)陣列所需要的復(fù)雜控制時序。有限狀態(tài)機和時鐘信號的共同控制能使系統(tǒng)中所有數(shù)據(jù)的流動和處理按照同一時鐘節(jié)拍有序進行，有效地避免競爭冒險現(xiàn)象對邏輯運算的破壞，解決了時延問題。2.4 引入FSM的原因n有限狀態(tài)機的設(shè)計離不開狀態(tài)轉(zhuǎn)換圖：n極小化狀態(tài)轉(zhuǎn)換圖，目的是減少不必要的狀態(tài)，節(jié)約資源，開關(guān)的活動減少n在狀態(tài)編碼的過程中，對狀態(tài)進行最優(yōu)分配，減少狀態(tài)間的活動次數(shù)n總體來說，減少了開關(guān)的活動頻率，減少了功耗2.4 引入FSM的原因n行旁路乘法器：行旁路乘法器采用跳躍進位加法器和全加器相結(jié)合完成部分積的相加運算，同時在每一

7、行的部分積中加入了旁路設(shè)計旁路設(shè)計，即將2選選1多多路選擇器路選擇器連接在每一個加法器上。多路選擇器的兩條輸入數(shù)據(jù)分別是與其連接的全加器的其中一條輸入數(shù)據(jù)，以及全加器的輸出數(shù)據(jù)。該設(shè)計的優(yōu)勢優(yōu)勢在于，當乘數(shù)中的某一位為零時，不必計算上一級部分積與該零行的加法運算，而是直接將上一級部分積輸出到下一級加法器中，因而提高了整個乘法過程的運算速度。n本文的FSM乘法器是基于行旁路乘法器設(shè)計的。3 FSM乘法器n具體來說，F(xiàn)SM乘法器就是，將行旁路乘法器的乘法運算過程中與乘數(shù)對應(yīng)的部分積表示為狀態(tài)機中的狀態(tài)，并用狀態(tài)轉(zhuǎn)換圖完成對乘法過程的描述。借助狀態(tài)機良好的時序邏輯控制能力，F(xiàn)SM 乘法器可以快速準確

8、的完成乘法運算，并且由于使用的邏輯器件相對較少，F(xiàn)SM 乘法器的功耗也有所降低。3.1 FSM乘法器設(shè)計n3.1 FSM乘法器設(shè)計n3.2 FSM乘法器算法設(shè)計狀態(tài)轉(zhuǎn)換算法:1：IF 復(fù)位信號為“1” THEN2：DO 將S0賦予當前狀態(tài)；3：ELSIF 時鐘信號為“1”THEN4：DO 將下一狀態(tài)設(shè)置為當前狀態(tài)5：END IF3.2 FSM乘法器算法設(shè)計控制信號輸出算法:1：WHEN 輸入為“0000”2： DO 將S1作為當前狀態(tài)；3： 將P0賦值Y；4：WHEN 輸入為“0001”5： DO 將S2作為當前狀態(tài)；6： 將P1賦值Y；7：8：WHEN 輸入為“1111”9： DO 將S15

9、作為當前狀態(tài)；10： 將P15賦值Y；3.2 FSM乘法器算法設(shè)計n采用時序邏輯電路設(shè)計的乘法器仿真圖3.3 仿真實驗結(jié)果3.3 仿真實驗結(jié)果n采用有限狀態(tài)機設(shè)計的乘法器仿真圖n由仿真圖可知，采用時序電路設(shè)計的乘法器仿真過程中出現(xiàn)“毛刺”，而采用狀態(tài)機設(shè)計的乘法器有效避免了“毛刺”的產(chǎn)生。信號在信號在FPGA器件內(nèi)部通過連線和邏輯器件內(nèi)部通過連線和邏輯單元單元時，都有一定的延時時，都有一定的延時。延時的大小與連線的長短和邏輯單元的數(shù)目有關(guān)，同時還受器件的制造工藝、工作電壓、溫度等條件的影響。信號的高低電平轉(zhuǎn)換也需要一定的信號的高低電平轉(zhuǎn)換也需要一定的過渡過渡時間時間。由于存在這兩方面因素，多路

10、信號的電平值發(fā)生變化時，在信號變化的瞬間，組合邏輯的輸出有先后順序，并不是同時變化，往往會出現(xiàn)一些不正確的尖峰信號，這些尖峰信號稱為“毛刺”。如果一個組合邏輯電路中有“毛刺”出現(xiàn)，就說明該電路存在“冒險”。因此，應(yīng)避免產(chǎn)生“毛刺”。3.4 結(jié)果分析3.4 結(jié)果分析n兩種乘法器對比乘法器設(shè)計乘法器設(shè)計邏輯器件數(shù)量邏輯器件數(shù)量功耗（功耗（mW）運算延遲（運算延遲（ns）行旁路乘法器50/51364.3813.931FSM乘法器26/51364.2112.420n整個乘法運算過程是一個時序邏輯過程，但是當乘數(shù)的每一個數(shù)據(jù)位進入電路時，所進行的部分積的運算是一個組合邏輯過程，組合邏輯的輸出有先有后，信號不是同時進行變化，所以容易產(chǎn)生毛刺。n采用有限狀態(tài)機設(shè)計的乘法器，每一個乘數(shù)的數(shù)據(jù)位決定了一個部分積，這個部分積的產(chǎn)生是同時產(chǎn)生的，不存在組合邏輯中的先后問題，所以有效地避免了毛刺的產(chǎn)生。同時，