【數位邏輯設計】Multiplexers, Decoders, and Programmable Logic Devices Part III
本文為清華大學開放式課程上課心得整理。
Programmable Logic Devises
可程式化邏輯元件有許多不同種類，這邊介紹 PLA 與 PAL 兩種。
PLA 是一個 2 Level 的邏輯電路，由一個 AND array 與一個 OR array 組成，PLA 中的 AND array 是可程式化的，因此不再是 2 ** n 條線， 可能會略少一點。
PLA 和 ROM 都是 SOP，差別為 ROM 是真值表的直接實現，而 PLA 的 AND array 可以有所變化。此處依然使用二極體來實現 AND Gate，二極體 AND Gate 串接方向與 OR Gate 相反，如此當輸入端是低電位時，電流便會從高電位處流過來，此時輸出端 Z 偵測到的結果便會是低電位（0），且只要有一個輸入端是低電位便成立；反之，當所有的輸入都是高電位時，二極體不會接通，I 和 V 都是 0，沒有任何電壓損耗，輸出等於 V+（1）。
PLA 不實現真值表，而是利用上述二極體的特性直接完成電路的輸入輸出判斷，參下圖。
當然這些電路圖也會有前述過於複雜混亂的情形，所以可以簡化如下圖：
PLA 電路設計的流程如下：
・根據 minterm／maxterm expansion 找出每個項的對應函式，根據函式畫出 PLA table（類似真值表）。
・根據 PLA table 畫出 AND Plain，黑點便是二極體連接的地方，因為是 AND Gate，所以負極會接在項這邊。
・根據 minterm／maxterm expansion 畫出 OR Plain，二極體接法與 AND Gate 相反。
PAL 是特殊型態的 PLA，LA 的全名是邏輯陣列（Logic Array），PAL 則剛好相反，意指 Array Logic。在 PLA 中，OR 與 AND Plan 都可以程式化，但在 PAL 中只有 AND Plan 可以程式化，由於 PAL 的 OR Plan 是固定的，所以在設計時要盡可能讓 product term 降到最低，以滿足 PAL 的條件限制。
各種設備內的邏輯閘是否可以程式化的整理如下：
Field Programmable Gate Arrays
現場可程式化閘陣列（Field Programmable Gate Array，FPGA）是一種由許多相同邏輯的元件所組成的巨大積體電路（Integrated Circuit，IC），裡面會搭配一些可以程式化的接線，下圖便是一個典型的 FPGA 架構圖。
FPGA 是一塊實際的電路板，可以配合相應的程式將電路設計載入電路板中執行，觀察設計實際運行的狀況與模擬運行之間的落差（例如：電路延遲等模擬時可能忽略的情況），以降低實際下線生產之後成品的不良率。
當然程式有大有小，要如何在電路板上完整執行便需要一些 partition 與 mapping 的技巧，以下便介紹 FPGA 將程式放進電路板中以模仿實際運行的方法。
FPGA 裡面的每個小區塊稱為 CLB，每個 CLB 裡面都有一個 LUT（Lookup Table），以下圖為例，圖中的 LUT 可以實現任何有四個輸入的函式，中間的梯形符號是 MUX，打了星號的是可程式化的 MUX，可以根據需求改變判定行為。
由於 LUT 的輸入只有四個，當出現五個以上的輸入時，就需要做一些修改讓 FPGA 可以執行。這時可以將函式做拆解（decomposition），這裡要使用 Shannon’s expansion theorem：
F(x1,x2,...xi, xi+1,...) = xi'F0 + xiF1舉例來說，若有一個四個輸入的函式 F(x1, x2, x3, x4)，現在要針對 x1 做拆解，則 x1 = x1・Fx1 ＋ x1'・Fx1'，其中 Fx1 與 Fx1' 稱為 cofactor，代表在原始函式中只要出現 x1 的都各自代入 1 以及 0 去做展開，例如函式為：
x1x2' + (x3 + x4)x1'當 x1 代入 1 時會變成：
x1x2' # 當 x1 為 1 時 x1' 為 0，故後項消去，下同x1 帶 0 時變成：
(x3 + x4)x1'合起來依舊等於原函式。
Shannon’s expansion theorem 保證拆解之後原函式不變，也可以針對不同的變數執行，執行之後變數也會減少，正確操作就可以讓程式輸入符合 FPGA 的限制。
如果拆解之後輸入依舊大於限制，那就要用 MUX expansion 處理，較小的 MUX 如何實現較大函式的方法前文已提及，不贅述。
