邢建國

摘要：本文介紹了一款開源數(shù)字電路仿真軟件Digital在數(shù)字邏輯和計算機(jī)組成等課程實驗中的應(yīng)用，并呈現(xiàn)出四個不同復(fù)雜度的組合和時序電路的設(shè)計與實現(xiàn)。實踐表明，該軟件適合于計算機(jī)類專業(yè)學(xué)生學(xué)習(xí)和掌握諸如處理器一類復(fù)雜數(shù)字系統(tǒng)設(shè)計。

關(guān)鍵詞：數(shù)字邏輯；計算機(jī)組成；Digital; 實驗設(shè)計

中圖分類號：G434? 文獻(xiàn)標(biāo)識碼：A? 論文編號：1674-2117（2023）08-0095-06

前言

開源軟件Logisim數(shù)字仿真軟件是由Carl Burch開發(fā)的一款開源、免費(fèi)的數(shù)字系統(tǒng)仿真軟件。筆者所在學(xué)校用該軟件重構(gòu)了已有的大部分實驗，很多學(xué)生利用該軟件設(shè)計的系統(tǒng)也達(dá)到了實驗要求。但在教學(xué)過程中筆者發(fā)現(xiàn)，Logisim無法直接使用Verilog模塊，這對一些復(fù)雜模塊如狀態(tài)機(jī)、浮點運(yùn)算器來說實現(xiàn)起來不方便，也難以調(diào)試。由Helmut Neemann開發(fā)的開源軟件Digital則針對Logisim存在的一些問題重新進(jìn)行了設(shè)計，并在底層架構(gòu)上做了重大調(diào)整，增加了很多新的特色功能，比Logisim更適合于復(fù)雜數(shù)字系統(tǒng)的仿真實現(xiàn)，其主要特點包括：①支持與、或、非等基本邏輯模塊，以及一些輸入輸出設(shè)備、計算、存儲等復(fù)雜模塊。②支持真值表、卡諾圖、邏輯表達(dá)式以及狀態(tài)機(jī)的電路綜合。③支持波形顯示，提供了測試用例（實際上提供了一種編寫測試用例的小語言）。④支持Telent協(xié)議，外部應(yīng)用可以與設(shè)計的電路系統(tǒng)進(jìn)行通信，這為調(diào)試圖像處理器的復(fù)雜系統(tǒng)提供了較大的便利。⑤可以將Verilog和VHDL編寫的模塊集成到設(shè)計的電路中（這些模塊的仿真是通過Icarus Verilog和ghdl外部模擬器來實現(xiàn)的），也可以把設(shè)計的系統(tǒng)導(dǎo)出為Verilog和VHDL文件。

下面，筆者將通過具體的教學(xué)案例來說明該軟件在數(shù)字邏輯、計算機(jī)組成等課程中的實際應(yīng)用。案例包括超前進(jìn)位加法器（組合邏輯）、最大公因子GCD電路（有限狀態(tài)自動機(jī)）、階乘Factorial電路（下推自動機(jī)）以及一個8指令處理器BrainFxxK（圖靈機(jī)）的實現(xiàn)。

設(shè)計案例

1.組合電路設(shè)計：超前進(jìn)位加法器

加法是算術(shù)邏輯單元中的重要組件。最簡單的加法器是由多個1位全加器串聯(lián)起來的串行進(jìn)位加法器。由于進(jìn)位延遲大，該加法器速度與位數(shù)成反比。因此，實踐中一般采用超前進(jìn)位加法器，其基本思路是用專門的電路來并行計算出進(jìn)位。對于一個n位加法：

{cout， sum} = a + b + cin

其第i+1位的進(jìn)位邏輯表達(dá)式為：

c[i+1] = a[i] b[i] + （a[i] + b[i]） c[i]

其中a[i] b[i]為生成項，記為g[i]，a[i] + b[i]為傳播項，記為p[i]。則c[i+1]可以表示為：

c[i+1] = g[i] + p[i] c[i]

= g[i] + p[i] g[i-1] + p[i] p[i-1] g[i-2] + ... + p[i] p[i-1]...p[1] p[0]cin

可以使用樹形結(jié)構(gòu)分層產(chǎn)生進(jìn)位。為此筆者設(shè)計了gp模塊，其功能是根據(jù)輸入的兩個加法器的g0、p0和g1、p1以及低位進(jìn)位cin生成g、p和cout，其邏輯表達(dá)式為：

g = g1 | （p1 & g0）

p = p1 & p0

cout = g0 | （p0 & cin）

1位加法器模塊為：

sum = a ^ b ^ cin

g = a & b

p = a | b

其在Ditigal中分別實現(xiàn)如圖1所示。

可以使用2個1位加法器和1個gp構(gòu)造一個2位加法器，如圖2所示。

同樣，可以使用2個2位加法器和1個gp構(gòu)造1個4位加法器以及更多位數(shù)的加法器。

通過這個例子，可以發(fā)現(xiàn)Ditigal對一些簡單的組合邏輯可以很方便進(jìn)行抽象、重用，由此可以構(gòu)造更復(fù)雜的系統(tǒng)。

2.有限狀態(tài)自動機(jī)設(shè)計：最大公因子（gcd）

本案例是展示如何使用Digital的Verilog模塊來簡化狀態(tài)機(jī)的實現(xiàn)。該例子用歐幾里算法來計算兩個正整數(shù)的最大公因子。該算法的Python實現(xiàn)如上頁圖3所示。

系統(tǒng)使用a和b兩個寄存器、一個取模運(yùn)算部件、一個比較器，其數(shù)據(jù)通路如圖4所示。

另外，對應(yīng)的狀態(tài)機(jī)（增加了讀取輸入）的下一狀態(tài)及對應(yīng)輸出如表1所示。

上述狀態(tài)機(jī)對應(yīng)的控制器，可以使用Digital的外部模塊Verilog來實現(xiàn)下一狀態(tài)、輸出邏輯，其VerilogHDL代碼如圖5所示?？梢钥吹?，采用Verilog描述的狀態(tài)機(jī)更易于理解和調(diào)試。

3.下推自動機(jī)設(shè)計：階乘（fact）

本案例展示了Digital能夠?qū)崿F(xiàn)下推自動機(jī)這樣的復(fù)雜系統(tǒng)。階乘遞歸實現(xiàn)的Python代碼如圖6所示。

與案例二相比，除了最后一條語句，兩者在結(jié)構(gòu)上非常類似。在gcd中，最后一條語句是尾遞歸（Tail-recursion），即gcd（b，a%b）后面沒有其他的計算了。而在fact中則不是，為了計算fact（n），要先計算fact（n-1），然后再計算n*fact（n-1）。而計算fact（n-1），又需要先計算fact（n-2）…，直到fact（0）計算完成，然后再計算fact（1）…fact（n-1）、fact（n）。我們稱n*fact（n-1）是 fact（n-1）的延續(xù)（continuation），在軟件中是函數(shù)調(diào)用后的返回地址，在硬件中則視為一個計算狀態(tài)，可將其存儲在堆棧中，當(dāng)fact（n-1）計算完成后，再從堆棧中恢復(fù)continuation，完成fact（n）的計算。

筆者設(shè)計了一個包括n、val（保存計算結(jié)果）和continue（用于存儲返回狀態(tài)/地址）三個寄存器和一個堆棧（用于保存和恢復(fù)寄存器n、continue）、乘法器等部件的系統(tǒng)來實現(xiàn)階乘，其數(shù)據(jù)通路如上頁圖7所示。

該系統(tǒng)要比gcd系統(tǒng)復(fù)雜得多，其對應(yīng)的控制器狀態(tài)轉(zhuǎn)換如上頁表2所示。

可以看到，為了實現(xiàn)fact的遞歸計算，筆者使用了16個狀態(tài)和一個堆棧，這一設(shè)計要比案例二復(fù)雜很多。同樣，使用Digital的外部Verilog模塊可以大大簡化這個狀態(tài)機(jī)邏輯的實現(xiàn)，調(diào)試也更方便。

4.圖靈機(jī)設(shè)計：Brainfxxk語言處理器

本案例是一個8指令處理器的Digital實現(xiàn)。Brainfxxk是由Urban Müller在1993年發(fā)明的一種只有8條指令的編程語言，該極小化的語言是圖靈完備的，這意味著它可以實現(xiàn)其他任何一種圖靈完備語言（如C語言或Python）完成的計算，甚至可以用它來寫一個Brainfxxk自身的解釋器。

該機(jī)器包括一個數(shù)組data、一個指向該數(shù)組某個單元的指針ptr、程序代碼code、程序計數(shù)器pc，以及輸入和輸出裝置。數(shù)組data里元素都初始化為零，數(shù)據(jù)指針初始時指向數(shù)組的第一個字節(jié)，pc指向第一條指令。其8條指令及其語義分別為：

'>'：將數(shù)據(jù)指針加一。

'<'：將數(shù)據(jù)指針減一。

'+'：將數(shù)據(jù)指針?biāo)傅膯卧右弧?/p>

'-'：將數(shù)據(jù)指針?biāo)傅膯卧獪p一。

'，'：從輸入流中讀取一個字節(jié)，存入數(shù)據(jù)指針?biāo)竼卧?/p>

'.'：輸出數(shù)據(jù)指針?biāo)竼卧淖止?jié)。

'['：如果當(dāng)前單元是 0，那么跳轉(zhuǎn)到對應(yīng)的 ']' 的下一條指令，否則繼續(xù)執(zhí)行。

']'：如果當(dāng)前單元不是 0，那么跳轉(zhuǎn)到對應(yīng)的 '[' 的下一條指令，否則繼續(xù)執(zhí)行。

其對應(yīng)的C代碼如表3所示。

下面這段代碼：

+++>++<[->+<]>.

等價的C代碼如圖8所示。

該段代碼首先將data第一個單元賦值為3（+++），第二個單元賦值為2（++），然后進(jìn)入循環(huán)（[->+<]），如果第一個單元不為0，則將其減一，把第二個單元加一。在循環(huán)結(jié)束后，打印第二個單元的值（>.），結(jié)果為5。該代碼的作用是將第一個單元值加到第二個單元，并打印。

該處理器除了兩條循環(huán)指令實現(xiàn)比較復(fù)雜之外，其余6條指令的實現(xiàn)是比較簡單的。上頁圖9為該處理器的一個參考實現(xiàn)。

圖9中從左到右，依次為PC及計算下一PC值模塊、程序ROM、控制器controller、數(shù)據(jù)指針ptr、數(shù)據(jù)data以及打印、輸入模塊。在圖的左下方為一個堆棧stack，用于記錄循環(huán)語句中的起始地址。

控制器的Verilog實現(xiàn)代碼如圖10所示。可以看到，Digital中對Verilog的支持大大簡化了有關(guān)模塊的設(shè)計，使設(shè)計更清晰、更易于理解和排錯。

總結(jié)

對于初步具備數(shù)字電路基本知識以及C語言程序設(shè)計能力的計算類專業(yè)學(xué)生而言，使用Digital軟件可以很容易了解復(fù)雜數(shù)字系統(tǒng)的設(shè)計和仿真，為進(jìn)一步完成如流水線、指令動態(tài)調(diào)度以及轉(zhuǎn)移指令預(yù)測等復(fù)雜模塊提供基礎(chǔ)。

參考文獻(xiàn)：

[1]李亞民.計算機(jī)原理與設(shè)計——Verilog HDL版[M].清華大學(xué)出版社，2011.

[2]David Patterson & John Hennessy.計算機(jī)組成與設(shè)計——軟硬件接口（RISC-V版）[M].北京：機(jī)械工業(yè)出版社，2020.