版權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須注明原文網址

　　http://www.rzrgm.cn/Colin-Cai/p/11938885.html 

　　作者：窗戶

　　QQ/微信：6679072

　　E-mail：6679072@qq.com

　　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可能面臨著兩次計算。

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