Scheme實現數字電路模擬(1)——組合電路

• 2019 年 12 月 16 日
• 筆記

　　版權申明：本文為部落客窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須註明原文網址    　　http://www.cnblogs.com/Colin-Cai/p/11938885.html    　　作者：窗戶    　　QQ/微信：6679072    　　E-mail：[email protected]

　　EDA是個很大的話題，本系列只針對其中一小部分，數字電路的模擬，敘述一點概念性的東西，並不會過於深入，這方面的內容實則是無底洞。本系列並不是真的要做EDA，按照SICP里的相關內容，採用Lisp的方言Scheme。再者，Lisp並不是只有函數式一種編程範式，真正做EDA，模擬的核心部分為了運行效率可以採用C/C++編寫，編程的思路也可以借鑒。

門級電路

　　學過數字電路，我們都知道與、或、非三個門。雖然從實際上真實電路的角度來說，與非門、或非路一般比起與、或門更為簡單，但一般情況下我們可能更喜歡從與、或、非說起。

　　與、或、非這三個門級的邏輯符號如下：

　　與門的真值表如下：

　　或門的真值表如下：

　　非門的真值表如下：

　　除此之外還有異或門、同或門比較常用，符號如下：

　　異或門的真值表如下：

　　同或門的真值表如下：

組合電路

　　將以上的門級電路連在一起，得到組合電路。前提是，組合電路沒有回饋。

　　解釋一下回饋的意思,

　　如果將組合電路看成一個有向圖，有向圖的頂點為各組短接在一起的導線，邊為每個門級上的輸入到輸出。

　　比如

　　在以上定義下，上面電路圖所對應的有向圖有7個頂點，a,b,c,d,e,f,g，邊為<a,e>，<b,f>，<c,f>，<e,g>，<f,g>，<e,d>，<g,d>。

　　如果有向圖沒有環，則該組合電路沒有回饋。

　　那麼有沒有有回饋的電路呢？舉一個例子如下：　　

　　四條邊<R,Q>，<P,Q>，<Q,P>，<S,P>中<P,Q>和<Q,P>組成了一個環，這就是回饋，產生了時序方面的東西，就不是組合電路了。實際上，這是一個RS觸發器。

組合電路的描述

　　以上的電路圖當然描述了電路，只是，處於模擬的需要，我們需要更為精確而簡潔的資訊。

　　我們可以把上述電路圖中的頂點提出來，稱為wire。

　　比如對於verilog,我們可以用以下來門級描述(實際上verilog可以有幾種看起來完全不一樣的RTL描述方式)：

wire a;  wire b;  wire c;  wire d;  wire e;  wire f;  wire g;  not u1(e, a);  or u2(f, b, c);  xor u3(g, e, f);  and u4(d, e, g);

　　以上顯然不符合Scheme的S-表達式，我們採用define，用定義變數的手段定義各個wire：

　　(define a (make-wire))

　　(define b (make-wire))

　　(define c (make-wire))

　　(define d (make-wire))

　　(define e (make-wire))

　　(define f (make-wire))

　　(define g (make-wire))

　　make-wire是函數，而各個wire用變數來表示。

　　用門將各個wire連起來，

　　(not-gate e a)

　　(or-gate f b c)

　　(xor-gate g e f)

　　(and-gate d e g)

　　not-gate、or-gate、xor-gate、and-gate都是用函數來表示門級，甚至於，我們可以通過與、或、非三個門來定義其中用異或門。

　　上面就是用與、或、非門實現的異或門，verilog實現如下：

module xor_gate(          output z,          input x,          input y);  wire nx;  wire ny;  wire p;  wire q;    not u1(nx, x);  not u2(ny, y);  and u3(p, nx, y);  and u4(q, x, ny);  or u5(z, p, q);  endmodule

　　Scheme模擬也一樣可以引入模組建構能力，按照上面Scheme的描述，不難寫出xor-gate的Scheme函數實現應該如下:

　　(define (xor-gate z x y)

　　 (let ((nx (make-wire))

　　 (ny (make-wire))

　　 (p (make-wire))

　　 (q (make-wire)))

(begin (not-gate nx x)

(not-gate ny y)

　　 (and-gate p nx y)

　　 (and-gate q x ny)

　　 (or-gate z p q))))

　　模擬

　　組合電路的模擬在於給定每個輸入的訊號，然後得到輸出的訊號，模擬比較簡單，

　　為了達到這個目的，我們可以定義一個set-signal函數，用於給wire設置訊號，高低電平我們一般用1、0表示。

　　比如，我們將a、b、c設為0、1、0，

　　(set-signal a 0)

　　(set-signal b 1)

　　(set-signal c 0)

　　再給個模擬函數sim用於推理出訊號的值，不需要返回值，但邏輯上是做了訊號的推理。

　　比如對於我們的需要來說，我們最終是為了觀察訊號g，那麼我們可以執行

　　(simulate g)

　　最後，我們可以再通過get-signal來獲取想要觀察的訊號，

　　(get-signal g)

　　對於這個電路，以及上述的輸入訊號，(get-signal g)會返回0。

實現

　　以上的模擬中，所有的wire都是變數，並且構建電路時使用函數。如果是純函數則不會影響全局的環境，只有改變了變數這樣的副作用發生，上面構建電路方法才是有效的。上述跡象表明，此時使用的絕對不是函數式編程。表示wire的變數顯然承載了整個電路的所有資訊，並且隨時可以通過閘電路函數讓任意兩個wire變數產生聯繫。我們可以通過序偶來實現這一切。

　　所有的Lisp里，最常用的手法當然是使用序偶(pair)來表示一切(其實Lisp也就是List Processing,list也是一種序偶)，序偶也是數學裡很基本的概念，用來表示有序的一對數據，所謂有序，意思就是序偶中的兩個數據分前後，這和兩個數據組成的集合不同。Scheme為序偶準備了三個函數：cons，car，cdr。cons用於生成一個序偶，car用於取序偶的第一個數據，cdr用於取序偶的第二個。

> (define s (cons 1 2)) > s (1 . 2) > (car s) 1 > (cdr s) 2

　　Lisp里的pair，像'(1 . 2)這樣一個pair是以下這樣的結構

　　這兩個箭頭代表的是，序偶里前後兩個存的是值的引用，而不是值。這一點非常重要，利用這個性質可以構造很多的數據結構，比如最簡單的列表(或者也可以叫鏈表)。

　　比如列表 '(1 2 3)實際上是'(1 . (2 . (3 . ())))，也就是如下圖這樣的結構

　　既然pair里存的是引用，Scheme早在最早的標準中就規定了set-car!和set-cdr!用於修改pair中所存儲的兩個引用，以此實現各種複雜的數據結構。我們使用set!似乎做到，比如可以這樣寫，

　　(define (my-set-car! v x) (set! v (cons (car v) x)))

　　(define (my-set-cdr! v x) (set! v (cons x (cdr v))))

　　但是set-car!和set-cdr!實現的顆粒可以更加的細，上述的my-set-car!和my-set-cdr!需要重新構建序偶，會破壞數據結構。

　　然後，我們可以考慮如何表示電路的數據結構了。

　　我們可以考慮用一個pair來表示wire，這個pair的第一個對象用來代表邏輯值，第二個對象用來代表wire的連接關係。

　　而原來電路

　　可以用以下這樣的數據結構來表示：

　　每個wire都對應著這樣的一個結構，如果是一個門(只限於與、或、非)的輸出，那麼右邊就是這樣的一個列表，列表第一個表元指向門的類型(用symbol表示)，後面的表元指向各個輸入的wire；而如果這wire是整個電路的輸入訊號，右邊則指向空列'()。

　　於是整個組合電路的數據結構就對應於上述定義下的一個圖（圖比較複雜，略）。

　　用個相對簡單的電路來表示一下整個數據結構：

　　其數據結構如下：

　　當我們用make-wire建立一個wire的時候，其邏輯值未定，wire也未與任何門相連，於是我們可以讓這個pair的第一個元給個默認邏輯值0，第二個元指向空列，即

(define (make-wire) (cons 0 '()))

　　注意，後面是(cons 0 '())，而不能是已經構造好的'(0)，這樣，每次返回的才是不同的pair，這一點是必須的，而且是可能出錯的地方。

　　set-signal和get-signal這兩個函數用於設置、獲取wire的訊號，顯然就是對pair的第一個元素進行操作，於是很簡單就可以實現

　　(define (set-signal x v) (set-car! x v))

　　(define (get-signal x) (car x))

　　與或非門的實現，比如與門

　　實際上就是先造出列表來表示門和各個輸入訊號，然後再操作pair的第二個元素指向這個列表。

　　對於非門只會有一個輸入訊號，

　　(define (not-gate x y) (set-cdr! x (list 'not y)))

　　而對於與、或門，會有多個輸入訊號(可能不只兩個)，於是我們用可變參數的寫法了。

　　(define (and-gate x . input-list) (set-cdr! x (cons 'and input-list)))

　　(define (or-gate x . input-list) (set-cdr! x (cons 'or input-list)))

　　注意這裡，input-list是輸入訊號列表，本來就是列表，所以只需要用cons把'and或者'or接在前面即可造出需要的完整列表了。

　　其實，通過這麼一個圖，我們也很容易看出訊號模擬很明顯就是一個遞歸。

　　計算一個wire的邏輯值，則看它的第二個元是不是空表：

　　如果是，則代表這個wire肯定是整個電路的輸入訊號，沒有其他門的依賴，所以不用計算；

　　而如果不是，則一定是某個門的輸出，於是先計算出每個輸入的訊號，再最後計算值。

　　用程式碼來寫就是如下了：

(define (sim s) (if (null? (cdr s));第二個元指向的是不是一個空表 (do-nothing);如果是空表，則不需要計算了 (begin (for-each sim (cddr s));挨個去計算每一個輸入訊號 (case (cadr s);看一下是什麼門 ((not);非門 (if (zero? (caaddr s)) (set-car! s 1) (set-car! s 0))) ((and);與門 (set-car! s (cal-and (cddr s)))) ((or);非門 (set-car! s (cal-or (cddr s)))) (else (do-nothing))))))

　　cal-and和cal-or也很容易用遞歸實現，而不是用fold，因為以下效率比起fold每個都算還較高一些：

(define (cal-and wires) (cond ((null? wires) 1) ((zero? (caar wires)) 0) (else (cal-and (cdr wires))))) (define (cal-or wires) (cond ((null? wires) 0) ((eq? 1 (caar wires)) 1) (else (cal-or (cdr wires)))))

　　而do-nothing函數，Chez上可以用void。

變數作用域問題

　　我們上面用到的都是全局變數，很多時候我們或許不想污染全局環境。於是我們可以採用面向對象的方式，很多語言都可以直接在語言層次上支援。Lisp作為彈性十足的語言，有多種方式來支援面向對象。

　　問題簡單化一點，我們就設想一個銀行卡的簡單系統，支援存錢、取錢、查看錢、查看歷史四個操作，為了簡單起見，我們不去管利息，取錢也可以任意取，不用擔心透支。

(define (make-card q history) (lambda s (case (car s) ((存款) (begin (set! q (+ q (cadr s))) (set! history (cons (list q '存款 (cadr s)) history)) q)) ((取款) (begin (set! q (- q (cadr s))) (set! history (cons (list q '取款 (cadr s)) history)) q)) ((查餘額) q) ((查歷史) (reverse history)) ((else) '()))))

　　以上就是Scheme天然支援一種方式的面向對象，make-card函數就是為了產生對象，所謂對象就是構造了一個環境，其中q、history是對象的屬性，而存款、取款、查餘額、查歷史則是對象的方法。所有的處理都在對象的內部，不會影響到全局環境。

　　我們測試一下，

(define id-1 (make-card 0 '()));產生一個對象 (id-1 '存款 1000) (id-1 '存款 2000) (id-1 '取款 500) (id-1 '存款 3000) (display (format "餘額: ~a" (id-1 '查餘額))) (newline) (display "歷史:") (newline)

;查看所有的歷史 (for-each (lambda (x) (display (format "~a~a 餘額: ~a" (cadr x) (caddr x) (car x)))(newline)) (id-1 '查歷史))

　　運行一下，結果如下：

餘額: 5500 歷史: 存款1000 餘額: 1000 存款2000 餘額: 3000 取款500 餘額: 2500 存款3000 餘額: 5500

　　這樣的思路完全可以用來改造上述的模擬。

其他問題

　　然而，我們可能還是會去想，

　　(for-each sim (cddr s))

　　面對一個門，算出它每一個輸入，是不是應該如此。其實顯然不需要如此，上面這兩個cal-and和cal-or函數之所以不用fold就已經是優化了。

　　然而，任何情況下，整個電路里所有的wire都被計算了，實際上，很多情況可能不需要計算這麼多。

　　比如

　　根本不需要計算下面非門的輸出訊號，就可以知道最終訊號是1。

　　另外，還有訊號重複計算問題,比如

　　其中e可能面臨著兩次計算。

　　這些問題如何解決呢？當然，這已經上升到演算法問題了，脫離了本章的主題，這裡並不再給出答案，留給有興趣的讀者自己去考慮。