Abstract
可程式邏輯陣列（PLA-Programmable Logic Array），由於其高度規則性結構，非常適合利用計算機輔助設計（CAD-Computer-Aided Design ）的方法進行自動化組建（automatic systhesis ）。但也因其有佔用面積大與訊號通過時間長等缺點，有必要進行邏輯與結構上的化簡。我們可以簡單認定其佔用面積與遲滯時間都正比於陣列中乘積項（product term）數目之多寡。本文研究的是陣列中邏輯方程的化簡（logicminimization），尤其是可程式邏輯陣列之輸入變數設定（input variable assign-ment）問題。對於一個可程式邏輯陣列而，言我們可在它輸入陣列的前端加上一些解碼器（decod-er），並將其輸入位元劃分為若干群，每一群變數均先連結輸入到一個解碼器中，而後以解碼所得作為該邏輯陣列的實際輸入訊號。如此，陣列面積將節省很多。以往，我們有一個現成的演算法（algorithm ），可是它限定解碼器只能痭二條輸入線，而且未考慮到附加解碼器的新增面積。在此，我們將這些狀況作了一個推廣，允許使用多條輸入線（multi-input ）的解碼器，並且把新增面積列入通盤考量之中。於是，我們手邊的是一個多值式可程式邏輯陣列（decoded-PLA ），而面臨的問題將為：每一個解碼器要連結幾個輸入位元﹖連結的是那些輸入變數﹖這個問題的解空間（sol-ution space ）為指數級至n 階層（ n！）之間，我們把三個既有與新設計的演算法作一實驗上的比較。三個演算法在開頭的地方完全相同。首先，針對進行處理的函數求得其近似最簡的乘積和（sum-of-products ）；然後建立其設定圖（assignment graph，請參照本文定義），以下情況則有所不同。演算法－將問題轉化為設定圖中之最小配對（minmummatching）問題。演算法二是基於一種事前預估（k-step look-ahead ）的策略，每執行一個輪迴，有一次合併動作。如果K 等於１，就是一種貪婪（greedy）法則；若K 為 N（輸入位元數），則變成一種地氈式搜尋（exhaustive-searching）。演算法三則是在設定圖上找出一條具最小加權數之漢米頓路徑（minimum weight Hamilton-ian path），以對所有輸入變數建立一次序性，而後以動態規劃（dynamic program-ming）的方法，將輸入位元區分為若干群，每一群變數相對一個解碼器。實驗結果顯示：第二、三演算法比第一個演算法好很多。而第二演算法又略優於第三演算法。演算法中之後二者，都利用到一個面積估計函數，但由於連續的合併動作間不能完全配合，節省面積並不具加成性，以致合併過程中會有程度不一的錯估。日後研究若能控制此關鍵，則多值式可程式邏輯陣列的輸入設定問題將有更完美的解答。