邢建國(guó)

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

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

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

前言

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

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

設(shè)計(jì)案例

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

加法是算術(shù)邏輯單元中的重要組件。最簡(jiǎn)單的加法器是由多個(gè)1位全加器串聯(lián)起來(lái)的串行進(jìn)位加法器。由于進(jìn)位延遲大，該加法器速度與位數(shù)成反比。因此，實(shí)踐中一般采用超前進(jìn)位加法器，其基本思路是用專門(mén)的電路來(lái)并行計(jì)算出進(jìn)位。對(duì)于一個(gè)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]為生成項(xiàng)，記為g[i]，a[i] + b[i]為傳播項(xiàng)，記為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

可以使用樹(shù)形結(jié)構(gòu)分層產(chǎn)生進(jìn)位。為此筆者設(shè)計(jì)了gp模塊，其功能是根據(jù)輸入的兩個(gè)加法器的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中分別實(shí)現(xiàn)如圖1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面這段代碼：

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

等價(jià)的C代碼如圖8所示。

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

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

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

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

總結(jié)

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

參考文獻(xiàn)：

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

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