鄧 建， 徐 潔

(電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 成都 611731)

0 引 言

Wallace樹型乘法器[1]自上世紀(jì)60年代提出以來，由于具有并行性和低延遲的優(yōu)點(diǎn)[2-3]，一直是通用乘法器[4-7]、數(shù)字信號處理(Digital Signal Process，DSP)中的乘法運(yùn)算[8-10]、浮點(diǎn)運(yùn)算[11]、模糊控制[12]和近似計(jì)算[13]等研究領(lǐng)域的熱點(diǎn)。目前通常采用超高速集成電路，硬件描述語言(Very-High-Speed Integrated Circuit Hardware Description Language, VHDL)[14]或Verilog[15]來進(jìn)行乘法器硬件的設(shè)計(jì)和仿真。

在文獻(xiàn)[16]中討論了Wallace樹型乘法器的結(jié)構(gòu)和設(shè)計(jì)，但在實(shí)驗(yàn)過程中發(fā)現(xiàn)：在8×8無符號位Wallace樹型乘法器的Verilog源代碼中存在3個(gè)錯(cuò)誤；在后續(xù)的第9、10、11、13、14章使用了位數(shù)更多的Wallace樹型乘法器，但書中未提供相應(yīng)的Verilog源代碼。為解決上述問題，根據(jù)文獻(xiàn)[16]中的Wallace樹型乘法器結(jié)構(gòu)，設(shè)計(jì)了一個(gè)自動生成Verilog源代碼的應(yīng)用程序。

1 無符號位乘法器的工作原理

無符號位二進(jìn)制數(shù)的乘法運(yùn)算可以通過每兩個(gè)二進(jìn)制位相乘、移位和加法來實(shí)現(xiàn)。以兩個(gè)兩位無符號位數(shù)相乘為例，設(shè)a、b分別為兩位無符號位二進(jìn)制數(shù)，則

z=(a[1]a[0])×(b[1]b[0])=

(a[1]a[0])×b[0]+(a[1]a[0])×b[1]×21=

a[0]b[0]+(a[1]b[0]+a[0]b[1])×21+

a[1]b[1]×22

(1)

式(1)中有4個(gè)乘積項(xiàng)，每個(gè)乘積項(xiàng)可以通過邏輯“與”實(shí)現(xiàn)。如圖1所示，如果a、b分別為8位無符號位二進(jìn)制數(shù)，則總共有64個(gè)乘積項(xiàng)，圖1中的每個(gè) “●”代表一個(gè)乘積項(xiàng)。

圖1 8×8無符號位乘法器中的乘積項(xiàng)

設(shè)a、b分別為M和N位無符號位二進(jìn)制數(shù)，則總共有M×N個(gè)乘積項(xiàng)。

2 Wallace樹型乘法器的結(jié)構(gòu)

對圖1中的乘積項(xiàng)進(jìn)行累加是乘法器中耗時(shí)最多的操作[3]，Wallace樹型乘法器[1]采用分級并行累加的方法進(jìn)行操作。圖2是對圖1中的乘積項(xiàng)進(jìn)行第1級的并行累加結(jié)構(gòu)圖。

圖2 8×8無符號位Wallace樹型乘法器的第1級

圖2中的每個(gè)方框代表一個(gè)加法器，方框內(nèi)有3個(gè) “●”使用全加器，方框內(nèi)有2個(gè) “●”可以使用半加器或全加器，不在方框中 “●”直接送到下一級。每個(gè)加法器輸出一個(gè)向高位的進(jìn)位、一個(gè)本位和。

圖3 8×8無符號位Wallace樹型乘法器的第2級

在圖2中，第1級共需要21個(gè)加法器，輸出的21個(gè)向高位的進(jìn)位、21個(gè)本位和，總共42個(gè)輸出，它們作為第2級的輸入。圖3是第2級的結(jié)構(gòu)圖，圖3中的“○”代表來自圖2中加法器的輸出。第2級的輸出作為第3級的輸入，第3級的輸出作為第4級的輸入，圖4、5分別表示第3、第4級的結(jié)構(gòu)。

圖4 8×8無符號位Wallace樹型乘法器的第3級

圖5 8×8無符號位Wallace樹型乘法器的第4級

圖5中輸出的第00-04位可以直接作為最終輸出，第05-15位還需要送到輸出級再做一次累加，圖6為輸出級的結(jié)構(gòu)。圖5、6中第15位向第16位的進(jìn)位可以忽略。

圖6 8×8無符號位Wallace樹型乘法器的輸出級

3 Verilog源代碼生成算法

Wallace樹型乘法器由于乘積項(xiàng)和中間的加法器數(shù)量多，采用Verilog進(jìn)行設(shè)計(jì)時(shí)工作量大。為提高設(shè)計(jì)效率，根據(jù)無符號位二進(jìn)制數(shù)的乘法器的工作原理和Wallace樹型乘法器的結(jié)構(gòu)，設(shè)計(jì)了一個(gè)自動生成Verilog代碼的應(yīng)用程序。整體算法為:

GenerateWallaceTreeUnsigned(M,N, *FileName )

1. ifM=N

2. then modulename←"wallace_tree "+M

3. else modulename←"wallace_tree "+M+"x"+N

4. FileName ← modulename+ ".v"

5.fp← fopen(FileName， "wt+" )

6. GenerateFileHeader(fp， modulename，M，N)

7. products ← GenerateUnsignedProduct (fp，M，N)

8. product_tree←GenerateItemTree(M,N, products)

9. adder_tree ← new TList

10. level ← 1

11. success←GenerateAdderTreeTopLevel(fp， level， M, N， product_tree, adder_tree)

12. while success = TRUE

13. do

14. level ← level +1

15. success = GenerateAdderTreeNextLevel(fp， level，M,N， adder_tree)

16. OutputLastUnsigneLevel(fp，M，N， level )

17. if(fp≠NIL )

18. then fclose(fp)

算法中的第1～5步進(jìn)行初始化工作，按照文獻(xiàn)[16]第3章和第9章的源代碼，生成對應(yīng)的Verilog模塊名稱，創(chuàng)建Verilog源文件。第6步向輸出文件輸出Verilog代碼的開始部分，包括模塊和輸入輸出定義。第7步根據(jù)本文的圖1和文獻(xiàn)[16]第79頁生成乘積項(xiàng)，并輸出對應(yīng)的Verilog代碼。第8步創(chuàng)建樹型乘法器每一級中加法器的輸入變量名稱，根據(jù)第7步生成的乘積項(xiàng)和本文的圖2確定第1級結(jié)構(gòu)中每個(gè)加法器所使用的乘積項(xiàng)名稱。第9～11步創(chuàng)建Wallace樹型乘法器的第1級，adder_tree中包含每級所使用的加法器的輸入和輸出變量名稱，第12～15步循環(huán)創(chuàng)建后續(xù)每一級，直到不需要繼續(xù)創(chuàng)建為止。第16步創(chuàng)建輸出級。在創(chuàng)建Wallace樹型乘法器的過程中，同時(shí)輸出對應(yīng)的Verilog代碼。第17～18步關(guān)閉Verilog文件。

在本算法的基礎(chǔ)上，根據(jù)文獻(xiàn)[16]中第74～77頁的方法編寫帶符號位的二進(jìn)制Wallace樹型乘法器。本算法可以很方便的生成位數(shù)更多的Wallace樹型乘法器的Verilog源代碼。

在文獻(xiàn)[16]中第271～276頁的浮點(diǎn)乘法器中要用到24×24位Wallace樹型乘法器，書中只提供了Wallace樹型乘法器的結(jié)構(gòu)圖，沒有提供對應(yīng)的Verilog源代碼。采用本算法自動生成了8×8、24×24、24×26、24×28、26×24、26×26模塊。如表1所示，隨著位數(shù)的增加，由于乘積項(xiàng)變得更多，所以Wallace樹型乘法器的級數(shù)更多。如果由設(shè)計(jì)人員手工輸入，不僅效率低，而且容易出錯(cuò)。

表1 M×N位無符號位Wallace樹型乘法器模塊

4 實(shí)驗(yàn)仿真

采用Xilinx ISE 14.7版本設(shè)計(jì)軟件，對自動生成的Verilog源代碼進(jìn)行仿真，輸入數(shù)據(jù)a分別為0和255，輸入數(shù)據(jù)b分別為0、1、2、4、8、16、32、64、255，得到與文獻(xiàn)[16]第82頁相同的仿真結(jié)果。

圖7 8×8無符號位Wallace樹型乘法器仿真結(jié)果[16]

但是圖7中的測試數(shù)據(jù)太少，如果采用窮盡測試，編寫雙重循環(huán)，對0～255的每兩個(gè)數(shù)進(jìn)行乘法運(yùn)算，發(fā)現(xiàn)文獻(xiàn)[16]中的Verilog代碼會出現(xiàn)運(yùn)算不正確的情況。經(jīng)過仔細(xì)核對，發(fā)現(xiàn)第80～81頁的源代碼共存在3處錯(cuò)誤，經(jīng)過修訂后才能得到正確的結(jié)果。造成錯(cuò)誤的原因估計(jì)是因?yàn)槌朔e項(xiàng)和中間加法器的輸出項(xiàng)目多，手工輸入源代碼容易出錯(cuò)。采用本文提出的方法，自動生成Verilog代碼，將Wallace樹型乘法器的硬件輸出與軟件的乘法結(jié)果進(jìn)行65536次窮盡對比，結(jié)果一致，沒有發(fā)現(xiàn)錯(cuò)誤。測試模塊的算法如下：

wallace_tree8_tb

1. // Inputs

2. reg [7:0]a

3. reg [7:0]b

4. // Outputs

5. wire [15:0]z

6. wallace_tree8 uut (.a(a), .b(b), .z(z))

7. task Check ;

8. input [15:0] expect

9. if(z!= expect )

10. then

11. error_count ← error_count + 1

12. $display("error :a= %x，b= %x， expect %x， but the output is %x"，a，b， expect，z)

13. else

14. success_count ← success_count + 1

15. endtask

16. initial begin

17. error_count ← 0

18. success_count ← 0

19. for i from 0 to 255

20. do

21.a←i

22. for j from 0 to 255

23. do

24.b←j

25. #10 //延遲10ns

26. Check(i*j)

27. display("total_count = %d， success_count = %d， error_count = %d"， success_count + error_count， success_count， error_count )

28. end

在上述算法的第25步需要延遲10 ns，目的是等待Wallace樹型乘法器的硬件結(jié)果。對于24×24、24×26、24×28、26×24、26×26模塊，也進(jìn)行了仿真，取得與文獻(xiàn)[16]相同的結(jié)果。

5 結(jié) 語

本文提出了一種自動生成Wallace樹形乘法器Verilog源代碼的方法，可以克服人工輸入源代碼的錯(cuò)誤，提高設(shè)計(jì)效率和質(zhì)量。在以后的教學(xué)過程中，還可以在以下幾個(gè)方面繼續(xù)改進(jìn)：① 增強(qiáng)對測試代碼的重視，通過大量的測試來考察乘法器的輸出是否正確；② 將乘法器下載到FPGA開發(fā)板上進(jìn)行實(shí)際運(yùn)行，分析其邏輯資源占用情況和延遲；③ 進(jìn)一步改進(jìn)Verilog代碼生成算法，在生成的Verilog代碼中自動增加注釋。采用自動生成Wallace樹形乘法器Verilog源代碼的方法可以提高同學(xué)們的學(xué)習(xí)熱情，愿意接受高難度實(shí)驗(yàn)項(xiàng)目的挑戰(zhàn)。