基于FPGA的8位硬件乘法器設(shè)計(jì)

1、PAGE 本科畢業(yè)設(shè)計(jì)基于FPGA的8位硬件乘法器設(shè)計(jì)摘 要VHDL（VHSIC Hardware Description Language）是當(dāng)今最流行的硬件描述語(yǔ)言之一，能夠?qū)ψ顝?fù)雜的芯片和最完整的電子系統(tǒng)進(jìn)行描述。以硬件描述語(yǔ)言作為設(shè)計(jì)輸入，經(jīng)過(guò)簡(jiǎn)單的綜合與布局，快速燒錄至FPGA（Field Programmable Gate Array）上進(jìn)行測(cè)試，是現(xiàn)代IC設(shè)計(jì)驗(yàn)證的技術(shù)主流。 乘法器是處理器進(jìn)行科學(xué)計(jì)算和數(shù)字信號(hào)處理的基本硬件結(jié)構(gòu)，是現(xiàn)代微處理器中的重要部件。乘法器完成一次乘法操作的周期基本上決定了微處理器的主頻。本文基于FPGA，采用VHDL語(yǔ)言，結(jié)合MAX+plus這個(gè)強(qiáng)大的

2、軟件平臺(tái)設(shè)計(jì)了8位二進(jìn)制乘法器，并對(duì)其進(jìn)行符號(hào)擴(kuò)展，使其可以統(tǒng)一處理8位帶符號(hào)數(shù)和無(wú)符號(hào)數(shù)。高速乘法器設(shè)計(jì)通常分為三個(gè)關(guān)鍵步驟：部分積產(chǎn)生、部分積累加和最終結(jié)果獲得。本文對(duì)部分積產(chǎn)生過(guò)程采用改進(jìn)Booth算法，有效減少部分積加法項(xiàng)；為了統(tǒng)一帶符號(hào)和無(wú)符號(hào)數(shù)，對(duì)部分積進(jìn)行符號(hào)擴(kuò)展；而對(duì)部分積的累加則采取3-2壓縮器和4-2壓縮器進(jìn)行壓縮；最終結(jié)果的獲得則以一個(gè)根據(jù)部分積累加結(jié)果到達(dá)時(shí)間的不同進(jìn)行延遲優(yōu)化的選擇進(jìn)位加法器將累加結(jié)果和累加進(jìn)位相加而得。 關(guān)鍵詞：乘法器 改進(jìn)Booth算法 壓縮器 選擇進(jìn)位加法器The Circuit Design of 8-bit Hardware Multipli

3、er Based on FPGAKe Xiuyan(College of Engineering, South China Agricultural University, Guangzhou 510642, China)Abstract: VHSIC Hardware Description Language, one of todays most popular hardware description languages, is used to describe the most complex chip and most complete electronic systems.The

4、multiplier is not only the basic hardware structure of the processor for scientific computing and digital signal processing but also an important component of modern microprocessors. This design for 8-bit binary multiplier is based on FPGA, using VHDL language, and proved by the MAX+plus software pl

5、atform. The multiplicand has an extended sign bit so that the multiplier can unify 8-bit signed and unsigned.High-speed multiplier design is usually divided into three key steps: partial product generation circuit, accumulator and adder. In this paper, the partial product generation process uses the

6、 modified Booth algorithm, so that the partial product addition terms can be effectively reduced. The accumulation of partial products takes 3-2 compressor and 4-2 compressor to compress. The final result is obtained with select carry adder.Key words: multiplier the modified Booth algorithm compress

7、or select carry adder 目 錄 TOC o 1-3 h z u HYPERLINK l _Toc356312486 1 前言 PAGEREF _Toc356312486 h 1 HYPERLINK l _Toc356312487 1.1 乘法器的研究背景和意義 PAGEREF _Toc356312487 h 1 HYPERLINK l _Toc356312488 1.2 乘法器的研究發(fā)展?fàn)顩r PAGEREF _Toc356312488 h 1 HYPERLINK l _Toc356312489 2 總體方案確定 PAGEREF _Toc356312489 h 2 HYPER

8、LINK l _Toc356312490 2.1 乘法器設(shè)計(jì)方案 PAGEREF _Toc356312490 h 2 HYPERLINK l _Toc356312491 2.2 硬件描述語(yǔ)言VHDL PAGEREF _Toc356312491 h 3 HYPERLINK l _Toc356312492 2.2.1 硬件描述語(yǔ)言 PAGEREF _Toc356312492 h 3 HYPERLINK l _Toc356312493 2.2.2 VHDL語(yǔ)言簡(jiǎn)介 PAGEREF _Toc356312493 h 3 HYPERLINK l _Toc356312494 2.2.3 VHDL的基本結(jié)構(gòu)

9、PAGEREF _Toc356312494 h 4 HYPERLINK l _Toc356312495 2.2.4 VHDL的優(yōu)點(diǎn) PAGEREF _Toc356312495 h 4 HYPERLINK l _Toc356312496 2.3 實(shí)驗(yàn)工具M(jìn)AX+plus PAGEREF _Toc356312496 h 5 HYPERLINK l _Toc356312497 2.3.1 MAX+plus簡(jiǎn)介 PAGEREF _Toc356312497 h 5 HYPERLINK l _Toc356312498 2.3.2 MAX+plus的設(shè)計(jì)流程 PAGEREF _Toc356312498 h

10、6 HYPERLINK l _Toc356312499 2.3.3 MAX+plus的特點(diǎn) PAGEREF _Toc356312499 h 6 HYPERLINK l _Toc356312500 2.4 現(xiàn)場(chǎng)可編輯門陣列（FPGA） PAGEREF _Toc356312500 h 7 HYPERLINK l _Toc356312501 2.4.1 FPGA簡(jiǎn)介 PAGEREF _Toc356312501 h 7 HYPERLINK l _Toc356312502 2.4.2 FPGA的基本結(jié)構(gòu) PAGEREF _Toc356312502 h 7 HYPERLINK l _Toc35631250

11、3 2.4.3 FPGA的特點(diǎn) PAGEREF _Toc356312503 h 8 HYPERLINK l _Toc356312504 3 理論分析及設(shè)計(jì) PAGEREF _Toc356312504 h 9 HYPERLINK l _Toc356312505 3.1 乘法器的數(shù)據(jù)格式 PAGEREF _Toc356312505 h 9 HYPERLINK l _Toc356312506 3.1.1 二進(jìn)制的表示 PAGEREF _Toc356312506 h 9 HYPERLINK l _Toc356312507 3.1.2 無(wú)符號(hào)數(shù)的運(yùn)算 PAGEREF _Toc356312507 h 9

12、HYPERLINK l _Toc356312508 3.1.3 帶符號(hào)數(shù)的運(yùn)算 PAGEREF _Toc356312508 h 9 HYPERLINK l _Toc356312509 3.1.4 帶符號(hào)數(shù)的符號(hào)擴(kuò)展表示 PAGEREF _Toc356312509 h 9 HYPERLINK l _Toc356312510 3.2 乘法器算法 PAGEREF _Toc356312510 h 10 HYPERLINK l _Toc356312511 3.2.1 移位相加算法 PAGEREF _Toc356312511 h 10 HYPERLINK l _Toc356312512 3.2.2 Boo

13、th算法 PAGEREF _Toc356312512 h 11 HYPERLINK l _Toc356312513 3.2.3 改進(jìn)型Booth算法 PAGEREF _Toc356312513 h 12 HYPERLINK l _Toc356312514 3.3 加法器 PAGEREF _Toc356312514 h 15 HYPERLINK l _Toc356312515 3.3.1 半加器 PAGEREF _Toc356312515 h 15 HYPERLINK l _Toc356312516 3.3.2 全加器 PAGEREF _Toc356312516 h 16 HYPERLINK l

14、 _Toc356312517 3.3.3 串行進(jìn)位加法器 PAGEREF _Toc356312517 h 16 HYPERLINK l _Toc356312518 3.3.4 超前進(jìn)位加法器 PAGEREF _Toc356312518 h 17 HYPERLINK l _Toc356312519 3.3.5 選擇進(jìn)位加法器 PAGEREF _Toc356312519 h 18 HYPERLINK l _Toc356312520 3.4 壓縮器 PAGEREF _Toc356312520 h 19 HYPERLINK l _Toc356312521 4 測(cè)試與試驗(yàn)分析 PAGEREF _Toc3

15、56312521 h 22 HYPERLINK l _Toc356312522 4.1 乘法器的總體結(jié)構(gòu) PAGEREF _Toc356312522 h 22 HYPERLINK l _Toc356312523 4.2 乘法器各個(gè)模塊的仿真 PAGEREF _Toc356312523 h 23 HYPERLINK l _Toc356312524 4.2.1 Booth編碼器 PAGEREF _Toc356312524 h 23 HYPERLINK l _Toc356312525 4.2.2 Booth譯碼器 PAGEREF _Toc356312525 h 23 HYPERLINK l _Toc

16、356312526 4.2.3 部分積產(chǎn)生電路 PAGEREF _Toc356312526 h 24 HYPERLINK l _Toc356312527 4.2.4 壓縮器 PAGEREF _Toc356312527 h 25 HYPERLINK l _Toc356312528 4.2.5 加法器 PAGEREF _Toc356312528 h 26 HYPERLINK l _Toc356312529 4.2.6 頂層文件 PAGEREF _Toc356312529 h 27 HYPERLINK l _Toc356312530 5 結(jié)論 PAGEREF _Toc356312530 h 28 H

17、YPERLINK l _Toc356312531 參 考 文 獻(xiàn) PAGEREF _Toc356312531 h 29 HYPERLINK l _Toc356312532 附 錄 PAGEREF _Toc356312532 h 30 HYPERLINK l _Toc356312533 致 謝 PAGEREF _Toc356312533 h 33畢業(yè)設(shè)計(jì)成績(jī)?cè)u(píng)定表PAGE 411 前言1.1 乘法器的研究背景和意義微電子技術(shù)的迅猛發(fā)展，計(jì)算機(jī)技術(shù)的不斷進(jìn)步，帶動(dòng)了集成電路工藝的不斷增進(jìn)，數(shù)字芯片的集成度不斷提高。在經(jīng)歷了小規(guī)模、中規(guī)模、大規(guī)模的發(fā)展過(guò)程之后，目前集成電路已經(jīng)進(jìn)入超大規(guī)模和甚大規(guī)模

18、集成電路階段，SOC（System on Chip）時(shí)代也已經(jīng)到來(lái)。數(shù)字芯片的發(fā)展一直遵循著英特爾公司的主要?jiǎng)?chuàng)始人戈登摩爾（Gordon Moore）提出的摩爾定律：芯片的集成度每三年翻兩番，特征尺寸縮小倍。由于可使用的芯片面積增加，為了進(jìn)一步提高運(yùn)算性能，目前越來(lái)越多的處理器包含多個(gè)運(yùn)算單元，算術(shù)運(yùn)算單元已經(jīng)成為處理器結(jié)構(gòu)中的一個(gè)重要組成部分。而乘法器又是運(yùn)算器不可或缺的重要組成單元，所以對(duì)乘法器的研究具有一定的意義。在高速數(shù)字信號(hào)處理器、微處理器等各類芯片中，乘法器是必不可少的算術(shù)邏輯單元。乘法器往往處于關(guān)鍵延時(shí)路徑中，它對(duì)系統(tǒng)的運(yùn)算速度有很大影響。為實(shí)現(xiàn)流水線的正常工作，乘法運(yùn)算往往需要

19、在一個(gè)時(shí)鐘周期內(nèi)完成，另一方面，隨著便攜式可移動(dòng)數(shù)字產(chǎn)品市場(chǎng)和芯片集成度的不斷增加，要求系統(tǒng)在保持高速的同時(shí)，具有較低的功耗，才能保持設(shè)備的長(zhǎng)時(shí)間可靠工作。因此，高速低功耗的乘法器的設(shè)計(jì)是運(yùn)算器系統(tǒng)設(shè)計(jì)中的關(guān)鍵。目前在乘法器的實(shí)現(xiàn)中，制約其性能提高的因素主要有以下幾個(gè)方面：部分積生成速度與面積的沖突、部分積的相加延遲過(guò)大、版圖實(shí)現(xiàn)的規(guī)則性和緊湊性難以提高。乘法器的設(shè)計(jì)思想，就是在乘法器設(shè)計(jì)的結(jié)構(gòu)復(fù)雜度，以及乘法器最終的運(yùn)算速度，電路完成后的占用芯片的面積這幾個(gè)因素之間進(jìn)行均衡。1.2 乘法器的研究發(fā)展?fàn)顩r迄今為止，關(guān)于乘法器實(shí)現(xiàn)研究的著作和論文已經(jīng)有很多。乘法器作為處理器最主要的模塊之一，在大

20、量文獻(xiàn)中均有研究。過(guò)去的十年，修正Booth算法進(jìn)一步擴(kuò)展了 Booth編碼算法的空間，以傳輸管邏輯、多路選擇器和動(dòng)態(tài)技術(shù)為基礎(chǔ)的各種電路實(shí)現(xiàn)方法持續(xù)刷新著高性能乘法器的實(shí)現(xiàn)記錄。與此同時(shí)，與物理實(shí)現(xiàn)緊密相關(guān)的乘法器拓?fù)浣Y(jié)構(gòu)的研究也碩果累累。乘法器研究上的里程碑應(yīng)該從A.D.Booth在1951年提出的Booth編碼方法和Wallace的樹型壓縮開(kāi)始。其中Wallace介紹了著名的用于壓縮部分積的Wallace樹結(jié)構(gòu)。隨后在1961年O.L.Mcsorley把Booth算法中的每次交疊檢驗(yàn)乘法的兩位推廣到每次交疊檢驗(yàn)三位，即著名的修正Booth算法，或稱Booth2算法，這種方法使得部分積數(shù)目

21、減少一半。1965年Dadda提出的計(jì)數(shù)器的概念，可將3:2計(jì)數(shù)器推廣到4:2，5:2和9:2等，進(jìn)一步減少Wallace樹所需計(jì)數(shù)器個(gè)數(shù)。進(jìn)入上世紀(jì)九十年代之后，Bewick提出了冗余Booth3算法，使得Booth 3可以在略多于Booth 2的時(shí)間內(nèi)完成。進(jìn)一步擴(kuò)展到基16、基32、乃至基256的Booth算法也被提出和研究。拓?fù)浣Y(jié)構(gòu)方面，進(jìn)位保留加法器被廣泛使用，雙陣列、高階陣列用于提高陣列拓?fù)浣Y(jié)構(gòu)的速度。Shen和Weinberger提出了4:2壓縮器用于構(gòu)成較Wallace樹更規(guī)整的二進(jìn)制樹，延遲平衡樹Zuras和McAllister首先提出，倒階梯樹也可用于改善樹型結(jié)構(gòu)的規(guī)整性。

22、乘法器算法方面已經(jīng)日趨完善。與此相應(yīng)的，可用于乘法器最后求和運(yùn)算的各種加法器結(jié)構(gòu)層出不窮。在電路實(shí)現(xiàn)方面，1981年，Weinberger提出了具有更高壓縮比和對(duì)稱性的4:2壓縮單元以代替全加器和半加器完成部分積的求和工作。此舉不僅降低了布局困難，而且可以縮短關(guān)鍵路徑，平衡端口延遲，極大的提高了運(yùn)算速度。1995年Ohkubo基于傳輸管邏輯實(shí)現(xiàn)了4.4ns的54位乘法器，同時(shí)提出了新的4:2壓縮單元結(jié)構(gòu)和進(jìn)位選擇加法器結(jié)構(gòu)。1996年，Hanawa實(shí)現(xiàn)了4.3ns的54位乘法器，同一年，Makino實(shí)現(xiàn)了8.8ns的54位冗余二進(jìn)制編碼乘法器。1997年Inoue提出了符號(hào)選擇Booth解碼和

23、改進(jìn)的4:2壓縮單元結(jié)構(gòu)，實(shí)現(xiàn)了4.lns的54位乘法器。1998年Hagihara基于動(dòng)態(tài)技術(shù)和傳輸管邏輯實(shí)現(xiàn)了2.7ns的54位乘法器，同年Carlson介紹了6.0ns的64位乘法器實(shí)現(xiàn)方法。2001年Itoh實(shí)現(xiàn)了一個(gè)600MHz的兩級(jí)流水線的54位乘法器。2003年，Cho基于標(biāo)準(zhǔn)單元庫(kù)實(shí)現(xiàn)了一個(gè)3.25ns的54位乘法器，并提出了改進(jìn)的進(jìn)位選擇加法器結(jié)構(gòu)。除了提高乘法器的速度以外，各種結(jié)構(gòu)的編碼單元，改進(jìn)的規(guī)整的樹型壓縮結(jié)構(gòu)，以及乘法器的低功耗設(shè)計(jì)等也得到了廣泛而深入的研究。2 總體方案確定2.1 乘法器設(shè)計(jì)方案本文采用了一種改進(jìn)Booth編碼算法，實(shí)現(xiàn)8位帶/無(wú)符號(hào)并行乘法器，并

24、選擇3-2壓縮器和4-2壓縮器組成的部分積累加器及選擇進(jìn)位加法器為最終加法器結(jié)構(gòu)實(shí)現(xiàn)乘法器的設(shè)計(jì)（王定，等，2007）。高速乘法器的關(guān)鍵就是要提高并行計(jì)算量，減少后續(xù)的計(jì)算量。Booth編碼算法是廣泛采用的算法，它可以減少一半的乘法乘積項(xiàng)，大大提高運(yùn)算速度。而部分積的相加采用3-2壓縮器和4-2壓縮器，它可以將乘法的時(shí)間復(fù)雜度降低。最終加法器則用選擇進(jìn)位加法器實(shí)現(xiàn)。算法運(yùn)算可分為3部分來(lái)實(shí)現(xiàn)：Booth編碼和譯碼；壓縮器；最終加法器（李磊，等，2008）。 2.2 硬件描述語(yǔ)言VHDL2.2.1 硬件描述語(yǔ)言 所謂硬件描述語(yǔ)言，就是利用該語(yǔ)言可以描述硬件電路的邏輯功能、電路結(jié)構(gòu)和連接形式。硬件

25、描述語(yǔ)言是一種用于設(shè)計(jì)硬件電子系統(tǒng)的計(jì)算機(jī)語(yǔ)言，適合大規(guī)模電路系統(tǒng)的設(shè)計(jì)。例如一個(gè)32位的加法器，利用傳統(tǒng)的圖形輸入軟件需要輸入500至1000個(gè)門，而利用VHDL語(yǔ)言只需要書寫一行代碼A=B+C即可。而且VHDL語(yǔ)言可讀性強(qiáng)，易于發(fā)現(xiàn)錯(cuò)誤和修改。硬件描述語(yǔ)言可以在不同的層次上描述數(shù)字系統(tǒng)。比如，描述電阻、晶體管及其之間相互連線關(guān)系的，稱為開(kāi)關(guān)級(jí)描述；描述基本邏輯門、觸發(fā)器及其之間相互連線關(guān)系的，稱為門級(jí)描述；在更高層面上描述寄存器及其之間數(shù)據(jù)傳遞的，稱為寄存器傳輸級(jí)描述。目前得到廣泛認(rèn)可的硬件描述語(yǔ)言有VHDL 和 Verilog兩種。2.2.2 VHDL語(yǔ)言簡(jiǎn)介 VHDL的英文全名是 VH

26、SIC(Very High Speed Integrated Circuit) Hardware Description Language，于1983年由美國(guó)國(guó)防部正式推出，1986年VHDL被建議作為IEEE 標(biāo)準(zhǔn)，經(jīng)過(guò)多次更改后，直到1987年12月，它才被IEEE接納為硬件描述語(yǔ)言標(biāo)準(zhǔn)(IEEE STD 1076)，該標(biāo)準(zhǔn)經(jīng)過(guò)不斷完善和更新，最近的標(biāo)準(zhǔn)為 IEEE 1164標(biāo)準(zhǔn)，己經(jīng)被IC生產(chǎn)廠家和 EDA工具提供商所接受。當(dāng)前幾乎所有的 EDA軟件，比如SYNOPSYS,MENTOR GRAPHICS,COMPASS,CADANCE等都支持該項(xiàng)標(biāo)準(zhǔn)。VHDL已經(jīng)成為硬件描述語(yǔ)言的業(yè)界標(biāo)

27、準(zhǔn)之一。 VHDL是一種全方位的硬件描述語(yǔ)言，包括系統(tǒng)行為級(jí)、寄存器傳輸級(jí)和邏輯門級(jí)多個(gè)設(shè)計(jì)層次,支持結(jié)構(gòu)、數(shù)據(jù)流、行為三種描述形式的混合描述，因此VHDL幾乎覆蓋了以往各種硬件描述語(yǔ)言的功能，整個(gè)自頂向下或自底向上的電路設(shè)計(jì)過(guò)程都可以用VHDL來(lái)完成。VHDL主要用于描述 HYPERLINK /view/987445.htm t _blank 數(shù)字系統(tǒng)的結(jié)構(gòu)、行為、功能和接口。除了含有許多具有硬件特征的語(yǔ)句外，VHDL的語(yǔ)言形式和描述風(fēng)格與句法是十分類似于一般的 HYPERLINK /view/786587.htm t _blank 計(jì)算機(jī)高級(jí)語(yǔ)言。VHDL的程序結(jié)構(gòu)特點(diǎn)是將一項(xiàng)工程設(shè)計(jì)，或

28、者稱作設(shè)計(jì)實(shí)體（可以是一個(gè)元件，一個(gè)電路模塊或一個(gè)系統(tǒng)）分成外部（或者稱可視部分,及端口)和內(nèi)部（或者稱不可視部分），既涉及實(shí)體的內(nèi)部功能和算法完成部分。在對(duì)一個(gè)設(shè)計(jì)實(shí)體定義了外部界面后，一旦其內(nèi)部開(kāi)發(fā)完成后，其他的設(shè)計(jì)就可以直接調(diào)用這個(gè)實(shí)體。這種將設(shè)計(jì)實(shí)體分成內(nèi)外部分的概念是VHDL系統(tǒng)設(shè)計(jì)的基本點(diǎn)。2.2.3 VHDL的基本結(jié)構(gòu)一個(gè)VHDL設(shè)計(jì)系統(tǒng)是由若干個(gè)VHDL文件構(gòu)成，每個(gè)文件主要包含如下三個(gè)部分中的一個(gè)或全部，分別是程序包（Package）、實(shí)體（Entity）和結(jié)構(gòu)體（Architecture）。已在設(shè)計(jì)實(shí)體中定義過(guò)的數(shù)據(jù)類型、子程序或數(shù)據(jù)對(duì)象對(duì)于其他設(shè)計(jì)實(shí)體是不可用的，或者說(shuō)是

29、不可見(jiàn)的。為了使已定義的常數(shù)、數(shù)據(jù)類型、元件調(diào)用說(shuō)明以及子程序等能被更多其他設(shè)計(jì)實(shí)體方便地訪問(wèn)和共享，可以將它們收集在一起作為一個(gè)程序包。多個(gè)程序包可以并入一個(gè)VHDL庫(kù)中，使之適用于更一般的訪問(wèn)和調(diào)用范圍。程序包主要是用來(lái)定義結(jié)構(gòu)體和實(shí)體中要用到的數(shù)據(jù)類型、元件和子程序等。VHDL實(shí)體作為一個(gè)設(shè)計(jì)實(shí)體（獨(dú)立的電路功能結(jié)構(gòu)）的組成部分，其功能是對(duì)這個(gè)設(shè)計(jì)實(shí)體與外部電路進(jìn)行接口描述，即定義了一個(gè)設(shè)計(jì)模塊的外部輸入和輸出端口。實(shí)體是設(shè)計(jì)實(shí)體的表層設(shè)計(jì)單元，實(shí)體說(shuō)明部分規(guī)定了設(shè)計(jì)單元的輸入輸出接口信號(hào)或引腳，描述了一個(gè)元件或一個(gè)模塊與其他部分之間的連接關(guān)系，它是設(shè)計(jì)實(shí)體對(duì)外的一個(gè)通信界面。一個(gè)設(shè)計(jì)可

30、以包含有多個(gè)實(shí)體，只有處于最高層的實(shí)體稱為頂層實(shí)體，EDA工具的編譯和仿真都是對(duì)頂層實(shí)體進(jìn)行的。處于低層的各個(gè)實(shí)體可作為單個(gè)元件，被高層實(shí)體調(diào)用。 結(jié)構(gòu)體是實(shí)體所定義的設(shè)計(jì)實(shí)體中的一個(gè)組成部分。結(jié)構(gòu)體描述設(shè)計(jì)實(shí)體的內(nèi)部結(jié)構(gòu)和外部設(shè)計(jì)實(shí)體端口間的邏輯關(guān)系。結(jié)構(gòu)體通常包括對(duì)數(shù)據(jù)類型、元件等元素的說(shuō)明部分、描述實(shí)體邏輯行為的功能描述語(yǔ)句和外部元件端口的連接。每個(gè)實(shí)體可以有多個(gè)結(jié)構(gòu)體，每個(gè)結(jié)構(gòu)體對(duì)應(yīng)著實(shí)體的不同結(jié)構(gòu)和算法實(shí)現(xiàn)方案，其間的各結(jié)構(gòu)體的地位是同等（王志功，等，2010）。 2.2.4 VHDL的優(yōu)點(diǎn)與其他硬件描述語(yǔ)言相比，使用VHDL進(jìn)行工程設(shè)計(jì)有以下優(yōu)點(diǎn)：VHDL支持自上向下和基于庫(kù)的設(shè)計(jì)

31、方法，而且支持同步電路、異步電路、現(xiàn)場(chǎng)可編程門陣列器件(FPGA)以及其他隨即電路的設(shè)計(jì)。VHDL具有比其他硬件描述語(yǔ)言更強(qiáng)大的行為描述能力，基于抽象的行為描述風(fēng)格避開(kāi)了具體的器件結(jié)構(gòu)，使設(shè)計(jì)人員能從邏輯行為上描述和設(shè)計(jì)大規(guī)模電子系統(tǒng)。目前流行的EDA工具和VHDL綜合器大都能實(shí)現(xiàn)行為描述到RTL描述的轉(zhuǎn)換。VHDL具有強(qiáng)大的系統(tǒng)硬件描述能力。VHDL具有多層次的設(shè)計(jì)描述功能，既可以描述系統(tǒng)級(jí)電路，又可以描述門級(jí)電路。而描述既可以采用行為描述、寄存器傳輸描述或結(jié)構(gòu)描述，也可以采用三者混合的混合級(jí)描述。另外，VHDL支持慣性延遲和傳輸延遲，還可以準(zhǔn)確地建立硬件電路模型。VHDL支持預(yù)定義的和自定

32、義的數(shù)據(jù)類型，給硬件描述帶來(lái)較大的自由度，使設(shè)計(jì)人員能夠方便地創(chuàng)建高層次的系統(tǒng)模型。VHDL對(duì)設(shè)計(jì)的描述具有相對(duì)獨(dú)立性。設(shè)計(jì)人員用VHDL進(jìn)行設(shè)計(jì)時(shí)，不需要首先考慮選擇完成設(shè)計(jì)的器件，就可以集中精力進(jìn)行設(shè)計(jì)的優(yōu)化。當(dāng)設(shè)計(jì)描述完成后，可以用多種不同的器件結(jié)構(gòu)來(lái)實(shí)現(xiàn)其功能。設(shè)計(jì)者可以不懂硬件的結(jié)構(gòu)，也可以不管最終設(shè)計(jì)的目的器件是什么，而進(jìn)行獨(dú)立的設(shè)計(jì)。VHDL支持廣泛、易于修改。由于VHDL已經(jīng)成為IEEE標(biāo)準(zhǔn)所規(guī)范的硬件描述語(yǔ)言，目前大多數(shù)EDA工具都支持VHDL，這為VHDL的進(jìn)一步推廣和廣泛應(yīng)用奠定了基礎(chǔ)。在硬件電路設(shè)計(jì)過(guò)程中，主要的設(shè)計(jì)文件是用VHDL編寫的源代碼，因?yàn)閂HDL易讀和結(jié)構(gòu)化

33、，所以易于修改設(shè)計(jì)。VHDL具有強(qiáng)大的移植能力，易于共享和調(diào)用。VHDL是一種標(biāo)準(zhǔn)化的硬件描述語(yǔ)言，同一個(gè)設(shè)計(jì)描述可以被不同的工具所支持，使得設(shè)計(jì)描述的移植成為可能。采用基于庫(kù)(Library)的設(shè)計(jì)方法，可以建立各種可再次利用的模塊。這些模塊可以預(yù)先設(shè)計(jì)或使用以前設(shè)計(jì)中的存檔模塊，將這些模塊存放到庫(kù)中，就可以在以后的設(shè)計(jì)中進(jìn)行調(diào)用，可以使設(shè)計(jì)成果在設(shè)計(jì)人員之間進(jìn)行交流和共享，減少硬件電路設(shè)計(jì)。由于VHDL具有類屬描述語(yǔ)句和子程序調(diào)用等功能，對(duì)于完成的設(shè)計(jì)，在不改變?cè)闯绦虻臈l件下，只需改變類屬參量或函數(shù)，就能輕易地改變?cè)O(shè)計(jì)的規(guī)模和結(jié)構(gòu)。VHDL語(yǔ)句的行為描述能力和程序結(jié)構(gòu)，也決定它對(duì)具有支持大

34、規(guī)模設(shè)計(jì)的分解和已有設(shè)計(jì)的再利用功能。VHDL具有豐富的仿真語(yǔ)句和庫(kù)函數(shù)，使得門電路級(jí)的功能仿真、檢查成為可能，可隨時(shí)對(duì)系統(tǒng)進(jìn)行仿真模擬，使設(shè)計(jì)者在任何大系統(tǒng)的設(shè)計(jì)早期就能對(duì)整個(gè)工程設(shè)計(jì)的結(jié)構(gòu)和功能的可行性做出判斷。VHDL作為一種IEEE的工業(yè)標(biāo)準(zhǔn)，使VHDL的設(shè)計(jì)成果便于重復(fù)利用和交流。這就更進(jìn)一步推動(dòng)了VHDL語(yǔ)言的推廣和完善。另外,由于其語(yǔ)法嚴(yán)格,給閱讀和使用帶來(lái)極大的便利。2.3 實(shí)驗(yàn)工具M(jìn)AX+plus2.3.1 MAX+plus簡(jiǎn)介MAX+plus(或?qū)懗蒑axplus2,或MP2)是Altera公司推出的第三代PLD開(kāi)發(fā)系統(tǒng)。 MAX+plus界面友好，使用便捷，容易上手，使用

35、MAX+plus的設(shè)計(jì)者不需精通器件內(nèi)部的復(fù)雜結(jié)構(gòu)。設(shè)計(jì)者在MAX+plus上可以用自己熟悉的設(shè)計(jì)工具（如原理圖輸入或者是硬件描述語(yǔ)言）完成設(shè)計(jì)輸入、元件適配、時(shí)序和功能仿真、編程下載整個(gè)流程。MAX+plus提供了一種與結(jié)構(gòu)無(wú)關(guān)的設(shè)計(jì)環(huán)境，方便設(shè)計(jì)者進(jìn)行設(shè)計(jì)輸入、快速處理和器件編程，同時(shí)其設(shè)計(jì)速度非?？欤瑢?duì)于一般幾千門的電路設(shè)計(jì)，使用MAX+plus，從設(shè)計(jì)輸入到器件編程完畢，到用戶拿到設(shè)計(jì)好的邏輯電路，大約只需要幾小時(shí)，而設(shè)計(jì)處理一般在幾分鐘內(nèi)完成。MAXplus開(kāi)發(fā)工具在國(guó)內(nèi)使用很普遍，同時(shí)擁有完備的在線幫助，被公認(rèn)為是最易使用、人機(jī)界面最友善的PLD開(kāi)發(fā)軟件。初學(xué)者可以很快學(xué)習(xí)掌握該工

36、具的使用，完成高性能的設(shè)計(jì)。2.3.2 MAX+plus的設(shè)計(jì)流程MAXplus的設(shè)計(jì)流程包括設(shè)計(jì)輸入編輯、編譯網(wǎng)表提取、數(shù)據(jù)庫(kù)建立、邏輯綜合、邏輯分割、適配、延時(shí)網(wǎng)表提取、編程文件匯編（裝配）及編程下載9個(gè)步驟。具體可分為五大步驟，如圖1所示。設(shè)計(jì)輸入綜合或編譯適配器件下載仿真圖1 MAXplus設(shè)計(jì)流程2.3.3 MAX+plus的特點(diǎn)（1）開(kāi)放的界面。MAX+plus支持與Cadence，Exemplarlogic，Mentor Graphics，Synplicty，Viewlogic和其它公司所提供的EDA工具接口。（2）與結(jié)構(gòu)無(wú)關(guān)。MAX+plus系統(tǒng)的核心Complier支持Alt

37、era公司的FLEX10K、FLEX8000、FLEX6000、MAX9000、MAX7000、MAX5000和Classic可編程邏輯器件，提供了世界上唯一真正與結(jié)構(gòu)無(wú)關(guān)的可編程邏輯設(shè)計(jì)環(huán)境。 （3）完全集成化。MAX+plus的設(shè)計(jì)輸入、處理與較驗(yàn)功能全部集成在統(tǒng)一的開(kāi)發(fā)環(huán)境下，這樣可以加快動(dòng)態(tài)調(diào)試、縮短開(kāi)發(fā)周期。 （4）豐富設(shè)計(jì)庫(kù)。MAX+plus提供豐富的庫(kù)單元供設(shè)計(jì)者調(diào)用，其中包括74系列的全部器件和多種特殊的邏輯功能（Macro-Function）以及新型的參數(shù)化的兆功能（Mage-Function）。 （5）模塊化工具。設(shè)計(jì)人員可以從各種設(shè)計(jì)輸入、處理和較驗(yàn)選項(xiàng)中進(jìn)行選擇從而使設(shè)

38、計(jì)環(huán)境用戶化。 （6）MAX+plus軟件支持各種HDL設(shè)計(jì)輸入選項(xiàng)，包括VHDL、Verilog HDL和Altera自己的硬件描述語(yǔ)言AHDL。（7）MAX+plus軟件具有開(kāi)放核的特點(diǎn)，允許設(shè)計(jì)人員添加自己認(rèn)為有價(jià)值的宏函數(shù)。2.4 現(xiàn)場(chǎng)可編輯門陣列（FPGA）2.4.1 FPGA簡(jiǎn)介FPGA的英文全名是 Field Programmable Gate Array?，F(xiàn)場(chǎng)可編程門陣列，是一個(gè)含有可編輯元件的半導(dǎo)體設(shè)備，是一個(gè)可供使用者程式化的邏輯門元件。 以硬件描述語(yǔ)言（Verilog 或 VHDL）作為設(shè)計(jì)輸入，經(jīng)過(guò)簡(jiǎn)單的綜合與布局，快速的燒錄至 FPGA 上進(jìn)行測(cè)試，是現(xiàn)代 IC 設(shè)計(jì)

39、驗(yàn)證的技術(shù)主流。這些可編輯元件可以被用來(lái)實(shí)現(xiàn)一些基本的邏輯門 HYPERLINK /w/index.php?title=%E9%9B%BB%E8%B7%AF&variant=zh-cn 電路（比如AND、OR、XOR、NOT）或者更復(fù)雜一些的組合功能比如解碼器或數(shù)學(xué)方程式。在大多數(shù)的FPGA里面，這些可編輯的元件里也包含記憶元件例如觸發(fā)器或者其他更加完整的記憶塊。系統(tǒng)設(shè)計(jì)師可以根據(jù)需要通過(guò)可編輯的連接把FPGA內(nèi)部的邏輯塊連接起來(lái)。一個(gè)出廠后的成品FPGA的邏輯塊和連接可以按照用戶的設(shè)計(jì)而改變，這樣可以實(shí)現(xiàn)滿足用戶要求的專用集成電路，真正達(dá)到了用戶自行設(shè)計(jì)、自行研制和自行生產(chǎn)集成電路的目的。2

40、.4.2 FPGA的基本結(jié)構(gòu)FPGA一般由三種可編程電路和一個(gè)用于存放編程數(shù)據(jù)的靜態(tài)存儲(chǔ)器SRAM組成。這三種可編程電路是：可編程邏輯塊CLB (Configurable Logic Block)、輸入/輸出模塊IOB (I/O Block)和可編程內(nèi)部連線PI（Programmable Interconnect）。FPGA的基本結(jié)構(gòu)如圖2所示，可編程邏輯塊(CLB)是實(shí)現(xiàn)邏輯功能的基本單元，它們通常規(guī)則地排列成一個(gè)陣列，散布于整個(gè)芯片；可編程輸入/輸出模塊(IOB)主要完成芯片上的邏輯與外部封裝腳的接口，它通常排列在芯片的四周；可編程內(nèi)部連線包括各種長(zhǎng)度的連線線段和一些可編程連接開(kāi)關(guān)，它們將

41、各個(gè)CLB之間或CLB、IOB之間以及IOB之間連接起來(lái)，構(gòu)成特定功能的電路（潘松，等，2005）。FPGA的功能由邏輯結(jié)構(gòu)的配置數(shù)據(jù)決定。工作時(shí)，這些配置數(shù)據(jù)存放在片內(nèi)的SRAM或熔絲圖上。基于SRAM的FPGA器件，在工作前需要從芯片外部加載配置數(shù)據(jù)，配置數(shù)據(jù)可以存儲(chǔ)在片外的EPROM或其他存儲(chǔ)體上。用戶可以控制加載過(guò)程，在現(xiàn)場(chǎng)修改器件的邏輯功能，即所謂的現(xiàn)場(chǎng)編程?？删幊虄?nèi)部連線PI輸入輸出塊IOB可編程邏輯塊CLB圖2 FPGA的結(jié)構(gòu)原理2.4.3 FPGA的特點(diǎn)總的來(lái)說(shuō)，F(xiàn)PGA器件具有下列優(yōu)點(diǎn)：高密度、高速率、系列化、標(biāo)準(zhǔn)化、小型化、多功能、低功耗、低成本，設(shè)計(jì)靈活方便，可無(wú)限次反復(fù)

42、編程，并可現(xiàn)場(chǎng)模擬調(diào)試驗(yàn)證。使用FPGA器件，一般可以在幾天到幾周內(nèi)完成一個(gè)電子系統(tǒng)的設(shè)計(jì)和制作，縮短研制周期，達(dá)到快速上市和進(jìn)一步降低成本的要求。其基本特點(diǎn)有：一是采用FPGA設(shè)計(jì)ASIC電路，用戶不需要投片生產(chǎn)，就能得到合用的芯片。 二是FPGA可做其它全定制或半定制ASIC電路的中試樣片。 三是FPGA內(nèi)部有豐富的觸發(fā)器和I/O引腳。 四是FPGA是ASIC電路中設(shè)計(jì)周期最短、開(kāi)發(fā)費(fèi)用最低、風(fēng)險(xiǎn)最小的器件之一。 五是FPGA采用高速CHMOS工藝，功耗低，可以與CMOS、TTL電平兼容。 FPGA是由存放在片內(nèi)RAM中的程序來(lái)設(shè)置其工作狀態(tài)的，因此，工作時(shí)需要對(duì)片內(nèi)的RAM進(jìn)行編程。用戶

43、可以根據(jù)不同的配置模式，采用不同的編程方式。 加電時(shí)，F(xiàn)PGA芯片將EPROM中數(shù)據(jù)讀入片內(nèi)編程RAM中，配置完成后，F(xiàn)PGA進(jìn)入工作狀態(tài)。掉電后，F(xiàn)PGA恢復(fù)成白片，內(nèi)部邏輯關(guān)系消失，因此，F(xiàn)PGA能夠反復(fù)使用。FPGA的編程無(wú)須專用的FPGA編程器，只須用通用的EPROM、PROM編程器即可。當(dāng)需要修改FPGA功能時(shí)，只需換一片EPROM即可。這樣，同一片F(xiàn)PGA，不同的編程數(shù)據(jù)，可以實(shí)現(xiàn)不同的電路功能，使用非常靈活。FPGA有多種配置模式：并行主模式為一片F(xiàn)PGA加一片EPROM的方式；主從模式可以支持一片PROM編程多片F(xiàn)PGA；串行模式可以采用串行PROM編程FPGA；外設(shè)模式可以將

44、FPGA作為微處理器的外設(shè)，由微處理器對(duì)其編程。3 理論分析及設(shè)計(jì)3.1 乘法器的數(shù)據(jù)格式3.1.1 二進(jìn)制的表示二進(jìn)制數(shù)用0和1兩個(gè)數(shù)碼來(lái)表示數(shù)，而且分為無(wú)符號(hào)數(shù)和帶符號(hào)數(shù)。無(wú)符號(hào)數(shù)的所有位都可以表示數(shù)值的大小，帶符號(hào)數(shù)的最高有效位表示數(shù)值的正負(fù)，其余位表示數(shù)值大小。帶符號(hào)數(shù)可以采用原碼、反碼和補(bǔ)碼三種表示法，實(shí)際上，任何正數(shù)的反碼和補(bǔ)碼都和原碼表示相同，但負(fù)數(shù)的原碼、反碼、補(bǔ)碼則各自有不同的表達(dá)方式。正負(fù)在計(jì)算機(jī)中只能用0和1表示，正數(shù)的符號(hào)位用0表示，負(fù)數(shù)的符號(hào)位用1表示。符號(hào)位用0和1表示正負(fù)，數(shù)值部分用二進(jìn)制絕對(duì)值表示數(shù)值大小，這種表示法稱為原碼。正數(shù)的反碼與原碼相同，符號(hào)位為0，其

45、余為數(shù)值位。而負(fù)數(shù)的反碼是將負(fù)數(shù)的原碼符號(hào)位保持不變，而數(shù)值部分按位取反。負(fù)數(shù)的補(bǔ)碼是在數(shù)值原碼在不改變符號(hào)位的基礎(chǔ)上，將其余數(shù)據(jù)位取反并在最低位加 1。3.1.2 無(wú)符號(hào)數(shù)的運(yùn)算與十進(jìn)制一樣，二進(jìn)制也可以進(jìn)行加減乘除四則運(yùn)算，加法的規(guī)則是逢二進(jìn)一，減法的規(guī)則是借一當(dāng)二，乘法的規(guī)則是1與1乘為1，其他為0。3.1.3 帶符號(hào)數(shù)的運(yùn)算帶符號(hào)數(shù)用其補(bǔ)碼表示后，其運(yùn)算方法與二進(jìn)制的運(yùn)算相同，但也會(huì)出現(xiàn)其特有的問(wèn)題。帶符號(hào)數(shù)的符號(hào)占用了1個(gè)二進(jìn)制數(shù)的最高有效位，當(dāng)運(yùn)算結(jié)果數(shù)值超過(guò)二進(jìn)制數(shù)所能表達(dá)的范圍時(shí)，其值就進(jìn)入符號(hào)位，因而可能改變其運(yùn)算結(jié)果的符號(hào)，得到錯(cuò)誤的結(jié)果，運(yùn)算結(jié)果超出了數(shù)值范圍，故稱為“溢

46、出”。在帶符號(hào)數(shù)的運(yùn)算中，判別其運(yùn)算結(jié)果是否溢出可以歸結(jié)為，若運(yùn)算結(jié)果的數(shù)值向前進(jìn)位（稱為CP），其符號(hào)運(yùn)算向前進(jìn)位（稱為CF），則溢出的判別為CPCF。這種邏輯“異或”操作結(jié)果為1，則運(yùn)算結(jié)果有溢出。3.1.4 帶符號(hào)數(shù)的符號(hào)擴(kuò)展表示在補(bǔ)碼數(shù)相加的過(guò)程中，由于數(shù)據(jù)寬度不同，所以在進(jìn)行某些運(yùn)算時(shí)需要將數(shù)據(jù)進(jìn)行符號(hào)擴(kuò)展，否則運(yùn)算過(guò)程中可能結(jié)果會(huì)出錯(cuò)。無(wú)符號(hào)數(shù)擴(kuò)展，僅在其數(shù)據(jù)擴(kuò)展位加上若干位0即可；而帶符號(hào)數(shù)的擴(kuò)展實(shí)際是擴(kuò)展其符號(hào)，即正數(shù)前補(bǔ)0，負(fù)數(shù)前補(bǔ)1。例如-1+1=0，圖3顯示了不使用符號(hào)擴(kuò)展和使用符號(hào)擴(kuò)展進(jìn)行計(jì)算的過(guò)程。 圖3 有符號(hào)數(shù)相加由上圖可知，左邊的運(yùn)算沒(méi)有使用符號(hào)擴(kuò)展，-1的數(shù)據(jù)

47、寬度為4，而1的數(shù)據(jù)寬度為8，兩個(gè)數(shù)相加得到的和為16，這明顯是錯(cuò)誤的。而右邊的運(yùn)算使用了符號(hào)擴(kuò)展，將-1的數(shù)據(jù)寬度擴(kuò)展到8位，兩個(gè)8位數(shù)-1和1相加，結(jié)果溢出，得到了正確的結(jié)果0。3.2 乘法器算法乘法器的實(shí)現(xiàn)可以采用多種算法，比較常用的有移位相加算法、Booth算法、改進(jìn)型 Booth算法等，各個(gè)算法都有自己的特點(diǎn)，下面對(duì)這些算法進(jìn)行簡(jiǎn)單的比較和分析。3.2.1 移位相加算法移位相加算法是一種簡(jiǎn)單且容易理解的算法。這個(gè)算法將n位帶符號(hào)數(shù)分成一位符號(hào)位和n-1位數(shù)碼位，處理過(guò)程包括對(duì)符號(hào)位和對(duì)數(shù)碼位處理的兩個(gè)過(guò)程。對(duì)于符號(hào)位，可以用異或門處理，如果符號(hào)位相同，則最后的符號(hào)為 0，如果符號(hào)位不

48、同，則為 1。對(duì)數(shù)碼位的處理是通過(guò)逐項(xiàng)移位相加原理來(lái)實(shí)現(xiàn)，首先從乘數(shù)的最低位開(kāi)始，每次取一位，判斷該位乘數(shù)是1還是0，若是1，則該位乘數(shù)與被乘數(shù)相乘產(chǎn)生的部分積是被乘數(shù)本身，若是0，則產(chǎn)生的部分積為0。然后將產(chǎn)生的部分積與上次部分積相加后邏輯右移一位。接著取乘數(shù)的高一位，繼續(xù)重復(fù)上述步驟，直至乘數(shù)移到的最高位，則移位相加的操作結(jié)束。最后還需要將符號(hào)位與數(shù)碼位的處理結(jié)果統(tǒng)一，才能得到最終乘積。移位相加算法在處理帶符號(hào)數(shù)乘法運(yùn)算上非常簡(jiǎn)單明了，但它對(duì)帶符號(hào)數(shù)的處理只是單純將符號(hào)位與數(shù)碼位分開(kāi)，這樣存在兩個(gè)明顯的缺點(diǎn)。首先，符號(hào)位是單獨(dú)處理的，這使得最終乘積的符號(hào)還需根據(jù)符號(hào)位的運(yùn)算結(jié)果進(jìn)行修正，增

49、加了控制部件的難度；其次，數(shù)碼位運(yùn)算中存在著許多不必要的運(yùn)算，這樣的運(yùn)算不僅沒(méi)有減少乘數(shù)數(shù)目，也沒(méi)有減少部分積數(shù)目，將導(dǎo)致運(yùn)算速度的降低?？傊?，移位相加算法是建立在無(wú)符號(hào)數(shù)運(yùn)算基礎(chǔ)上的一種間接補(bǔ)碼乘法算法。它對(duì)數(shù)碼位的處理類似于無(wú)符號(hào)數(shù)的操作，因而該算法延時(shí)比較長(zhǎng)，運(yùn)算速度較慢（傅志暉，等，2003）。3.2.2 Booth算法A.D.Booth 在 1951 年提出了Booth算法，主要是為了解決帶符號(hào)位乘法運(yùn)算中出現(xiàn)的符號(hào)修正問(wèn)題。下面簡(jiǎn)單介紹這種算法。設(shè)帶符號(hào)乘數(shù) ，同時(shí)設(shè)置一個(gè)附加位用于輔助運(yùn)算，并規(guī)定。此時(shí)對(duì)乘數(shù)B進(jìn)行一些變換如下公式所示 則可以推出乘積補(bǔ)碼，如下式所示。 由上式可知

50、，該算法通過(guò)取乘數(shù)的和的差來(lái)產(chǎn)生對(duì)應(yīng)的部分積，和的取值可以有表1所示的四種組合，當(dāng)和的差值為0時(shí)，部分積的對(duì)應(yīng)值為0左移j位；當(dāng)和的差值為-1時(shí)，部分積的對(duì)應(yīng)值為被乘數(shù)的補(bǔ)碼且左移j位；當(dāng)和的差值為1時(shí)，部分積的對(duì)應(yīng)值為被乘數(shù)左移j位。如表1所示。表1 Booth算法的編碼結(jié)果0000110110該算法對(duì)于用補(bǔ)碼表示的兩位數(shù)相乘不需要進(jìn)行符號(hào)位修正，但是對(duì)于帶符號(hào)數(shù)乘法來(lái)說(shuō)，該算法會(huì)產(chǎn)生n個(gè)編碼項(xiàng)和n個(gè)部分積，需要 n 次移位。由表1可知，一個(gè)部分積為0的概率為1/2，由于部分積為0實(shí)際上不需要相加，所以平均需要 n/2 次加法。相對(duì)于傳統(tǒng)的移位加算法，所以它并不能很好的減少完成一次乘法所需要

51、的時(shí)鐘周期數(shù)。該算法并沒(méi)有提高乘法器的速度，并且部分積編碼和產(chǎn)生邏輯更復(fù)雜，使得硬件面積增加。3.2.3 改進(jìn)型Booth算法1961 年 O.L.Macsorley 將Booth 算法中的乘數(shù)每次兩位交疊檢驗(yàn)推廣到每次三位交疊檢驗(yàn)，這種算法即著名的 Booth-MacSorley 算法也叫改進(jìn) Booth 算法。改進(jìn) Booth 算法使編碼數(shù)減少一半，即使部分積的個(gè)數(shù)減少一半，從而提高了乘法器的運(yùn)算速度并降低了硬件復(fù)雜度。同樣設(shè)帶符號(hào)乘數(shù)B，對(duì) B 的補(bǔ)碼進(jìn)行變換，如下公式所示，假設(shè) n 為偶數(shù)（Booth A D，1951）。 則可以推出乘積補(bǔ)碼，如下式所示。 由上式可知，該算法通過(guò)重疊掃

52、描乘數(shù)的3位，取乘數(shù)的和的和減去2倍來(lái)產(chǎn)生對(duì)應(yīng)的部分積。上式是適用于n為偶數(shù)的情況下，當(dāng)乘數(shù)為奇數(shù)為時(shí)，乘數(shù)需要通過(guò)符號(hào)擴(kuò)展使位數(shù)變成偶數(shù)個(gè)，即將最高符號(hào)位向高一位擴(kuò)展作為輔助位，這個(gè)擴(kuò)展的輔助位不會(huì)影響編碼結(jié)果（應(yīng)征，等，2003）。根據(jù)位數(shù)奇偶把輔助位補(bǔ)上之后，便可以開(kāi)始對(duì)乘數(shù)進(jìn)行編碼，從最低輔助位向高位選擇連續(xù)的三位，然后保留選取的最高位，繼續(xù)向高位選取連續(xù)的兩位組成新的三位，以此類推，相應(yīng)的取值可以有表2所示的八種組合，而實(shí)際上對(duì)被乘數(shù)進(jìn)行的處理產(chǎn)生的部分積只有5種，如表2所示。表2 改進(jìn)Booth算法的編碼結(jié)果000000101001121001011101110 圖4通過(guò)以下幾個(gè)步

53、驟詳細(xì)說(shuō)明兩個(gè)9 位的帶符號(hào)數(shù)采用了改進(jìn)Booth算法相乘的過(guò)程。從圖4可知，9個(gè)實(shí)心圓表示9位帶符號(hào)數(shù)，乘數(shù)是奇數(shù)位，所以向高一位擴(kuò)展一位符號(hào)數(shù)，用空心圓表示，同時(shí)補(bǔ)上一位輔助位，用三角符號(hào)表示。首先對(duì)乘數(shù)進(jìn)行改進(jìn) Booth 編碼，產(chǎn)生的5個(gè)編碼用實(shí)心三角符號(hào)表示。每個(gè)編碼對(duì)應(yīng)產(chǎn)生一個(gè)部分積，5個(gè)編碼對(duì)應(yīng)產(chǎn)生6個(gè)部分積。因?yàn)樵撍惴ú捎玫氖茄a(bǔ)碼運(yùn)算，所以當(dāng)編碼結(jié)果為負(fù)數(shù)時(shí)，要把被乘數(shù)逐位取反并在最低位加上1。如果將最低位要加的數(shù)用s表示，那么s的取值剛好跟編碼結(jié)果的正負(fù)一樣，若編碼結(jié)果為正，則s為0，若為負(fù)，則s為1。 圖4 8位數(shù)相乘過(guò)程 每次產(chǎn)生的部分積最后都需要和其他的部分積進(jìn)行相加，

54、但是每次產(chǎn)生的部分積數(shù)據(jù)寬度不用，正如上文提到，在補(bǔ)碼數(shù)相加的過(guò)程中，如果補(bǔ)碼數(shù)的數(shù)據(jù)寬度不同，需要將數(shù)據(jù)進(jìn)行符號(hào)擴(kuò)展，否則運(yùn)算過(guò)程中可能結(jié)果會(huì)出錯(cuò)。所以每個(gè)部分積都需要擴(kuò)展成18位數(shù)，擴(kuò)展位用E表示。E的取值由編碼結(jié)果的符號(hào)和被乘數(shù)的符號(hào)共同決定，并且規(guī)定編碼得到的部分積為0，則E為0。用表3來(lái)簡(jiǎn)單說(shuō)明，其中正用0表示，負(fù)用1表示。表3 Booth編碼中的有關(guān)符號(hào)位Booth2 編碼符號(hào) 最低位要加的數(shù)s被乘數(shù)的符號(hào)部分積的符號(hào) E0000001111011110 部分積擴(kuò)展符號(hào)位后增加了部分積的位數(shù)，明顯影響到乘法器的速度。 因此，可以采用符號(hào)擴(kuò)展簡(jiǎn)化技術(shù)對(duì)部分積進(jìn)行處理，即將連續(xù)的n個(gè)E

55、用連續(xù)的n個(gè)1乘以表示。假設(shè)一個(gè)擴(kuò)展數(shù)EEEEXXXXX，則會(huì)有這樣的等價(jià)關(guān)系1111XXXXX =EEEEXXXXX。對(duì)部分積進(jìn)行簡(jiǎn)化處理之后，擴(kuò)展符號(hào)位出現(xiàn)了固定的連續(xù)的數(shù) 1，而且相加會(huì)得到固定的結(jié)果，所以在部分積壓縮中利用這種關(guān)系可以簡(jiǎn)化符號(hào)擴(kuò)展。 3.3 加法器3.3.1 半加器半加器和全加器是算術(shù)運(yùn)算電路中的基本單元，它們完成的是1位二進(jìn)制數(shù)相加的一種組合邏輯電路（康華光，2006）。如果只考慮兩個(gè)加數(shù)本身，而沒(méi)有考慮低位進(jìn)位的加分運(yùn)算，稱為半加。實(shí)現(xiàn)半加運(yùn)算的邏輯電路稱為半加器。兩個(gè)1位二進(jìn)制數(shù)的半加運(yùn)算的邏輯真值表可用表4所示。其中A、B是兩個(gè)加數(shù)，S表示和，C表示進(jìn)位數(shù)。表4

56、 半加器的真值表ABCS0000010110011110 用邏輯表達(dá)式來(lái)表示輸出為S =AB C = AB 從上述表達(dá)式可知，半加器有異或門和與門組成。半加器也可以作為壓縮器使用，它把和值信號(hào)傳到同權(quán)值的下級(jí)，進(jìn)位信號(hào)傳到高一位權(quán)值的下級(jí)，不進(jìn)行級(jí)聯(lián)。 3.3.2 全加器全加器能進(jìn)行加數(shù)、被加數(shù)和低位來(lái)的進(jìn)位信號(hào)相加，并根據(jù)求和結(jié)果給出該位的進(jìn)位信號(hào)，即全加器能實(shí)現(xiàn)兩個(gè)二進(jìn)制數(shù)和一個(gè)進(jìn)位信號(hào)相加的功能，邏輯真值表如表 5所示，其中A和B分別是被加數(shù)和加數(shù)，Cin是低位進(jìn)位數(shù)，S為本位和，Cout為向高位的進(jìn)位數(shù)。表5 全加器的真值表ABCinCoutS000000010101001011101

57、0001101101101011111用邏輯表達(dá)式來(lái)表示輸出為S = ABCin Cout=AB+（AB）Cin 從上述表達(dá)式可知，全加器是有兩個(gè)半加器和一個(gè)或門構(gòu)成的。3.3.3 串行進(jìn)位加法器若有多位數(shù)相加，則可采用并行相加串行進(jìn)位的方式來(lái)完成。如果有兩個(gè)n位二進(jìn)制數(shù)相加，可以采用n-1個(gè)全加器和一個(gè)半加器，如圖5所示。FA 代表全加器，HA 代表半加器。圖5 串行進(jìn)位加法器每個(gè)加法器的低位進(jìn)位輸出作為下一個(gè)加法器的進(jìn)位輸入，最低位由于沒(méi)有進(jìn)位輸入只需要半加器。任意1位的加法運(yùn)算必須在低1位的運(yùn)算完成之后才能進(jìn)行，這種進(jìn)位方式成為串行進(jìn)位，此種加法器稱為串行進(jìn)位加法器。這種加法器的邏輯電路

58、比較簡(jiǎn)單，面積小，易于理解，但是運(yùn)算速度不高，延時(shí)大。其關(guān)鍵路徑是所有加法器的進(jìn)位鏈路徑，延時(shí)正比于相加位數(shù)，為O(n)。3.3.4 超前進(jìn)位加法器在串行進(jìn)位加法器中，每個(gè)加法器要等到上一級(jí)加法器產(chǎn)生進(jìn)位輸出才能產(chǎn)生有效的和值，因此加法器的速度受到進(jìn)位信號(hào)的限制。為了解決這一問(wèn)題，人們?cè)O(shè)計(jì)了一種多位數(shù)超前進(jìn)位加法邏輯電路，使每位的進(jìn)位只由加數(shù)和被加數(shù)決定，而與低位進(jìn)位無(wú)關(guān)。下面介紹它產(chǎn)生的機(jī)理。在全加器中我們得出Cout = AB+( AB)Cin，可以表示為Cout=G+PCin。其中G表示A和B的邏輯與，只有A和B同時(shí)為1，G才為1。P表示 A和B的異或，當(dāng)A和B取值不同時(shí)，P為1，因而G

59、和P不會(huì)同時(shí)為1。當(dāng) G=1 時(shí)，Cout 為 1，即產(chǎn)生進(jìn)位；當(dāng) P=1 時(shí)，Cout= Cin，可以認(rèn)為低位的進(jìn)位能傳送到高位的進(jìn)位輸出端。這可以用圖6來(lái)表示。圖6 超前進(jìn)位加法器將P和G代入全加器的邏輯表達(dá)式可得S=PCinCout=G+PCin則各位的進(jìn)位信號(hào)的邏輯表達(dá)式如下 從上述的表達(dá)式可知，采用這種連續(xù)代入的方式后發(fā)現(xiàn)進(jìn)位信號(hào)只與變量，和有關(guān)，而是最低位的進(jìn)位信號(hào)，其值0，所以各位的進(jìn)位信號(hào)都只與兩個(gè)加數(shù)有關(guān)，只要兩個(gè)加數(shù)的各位同時(shí)到達(dá)，那么相應(yīng)的和將同時(shí)產(chǎn)生，各位進(jìn)位信號(hào)也將基本同時(shí)產(chǎn)生。超前進(jìn)位加法器進(jìn)位產(chǎn)生時(shí)間大大減少，不像串行進(jìn)位加法器需要進(jìn)位延時(shí)，因而其速度很快。但是它

60、需要較多的邏輯電路，是一種以面積來(lái)?yè)Q取速度的加法器。特別是當(dāng)位數(shù)增加時(shí)面積增大了很多，同時(shí)扇入扇出也很多，增加了進(jìn)位延時(shí)。實(shí)際上位數(shù)太多時(shí)實(shí)現(xiàn)起來(lái)是困難的，所以超前進(jìn)位加法器的加數(shù)位數(shù)通?？刂圃?4 位以內(nèi)，需要實(shí)現(xiàn)多位超前進(jìn)位加法器時(shí)可以通過(guò)級(jí)聯(lián)實(shí)現(xiàn)。3.3.5 選擇進(jìn)位加法器為了減少進(jìn)位傳遞的延時(shí)，也可以使用另一種快速的加法器進(jìn)位選擇加法器。例如要構(gòu)成一個(gè)16位的進(jìn)位選擇加法器，可以分為4部分，每部分4位。第一個(gè)4位加法器的進(jìn)位輸入是已知的，正常計(jì)算出和值S0、S1、S2、S3和進(jìn)位輸出C1。第二個(gè)4位加法器的進(jìn)位輸入要么是0，要么是1。用兩個(gè)4位加法器分別計(jì)算出進(jìn)位輸入是0和1的和值及進(jìn)