多值邏輯電路的測試及多階級合成之研究

Abstract

本論文旨在研究多值邏輯組合電路的測試及多階級合成。在測試部份，首 先分析(K+1)值PLA架構電路的障礙關係，根據所得的結果，就二階級函數 而言，總是存在一個K值使得用(K+1)值設計的電路會比用二元邏輯設計的 電路在障礙合併之後考慮較少的障礙數目。之後，我們對ㄧ多值邏輯函數 定義了完整測試集，並開發一個快速產生完整測試集的演算法。除此之外 ，我們用多值邏輯和二元邏輯去設計同一邏輯函數，並比較各完整測試集 的大小，模擬結果顯示，大部份的函數被表示成多值邏輯函數時，有較小 的完整測試集。在多階級合成部份，提出多值邏輯的代數除法程序。藉著 引入兩個布林特性到除法運算中，進一步將它改善成混合代數除法程序， 此新除法可在處理多值邏輯函數的多階級合成上，得到更好的結果。平均 而言，混合代數除法可比純代數除法額外減少20.6 %的成本。除此我們將 多值邏輯函數的因式化問題格式化成矩形涵蓋的問題。首先我們提出一種 純代數因式化的演算法，之後再藉由兩個布林特性的輔助，進一步將它改 善成能進行部份布林因式化以得到更好結果的布林因式化演算法。實驗結 果顯示，用布林因式化方法得到函數所需要實踐多階級的製作成本，要比 用純代數因式化的方法節省13.7%的成本。 On testing, it first analyzes of fault relationships on the ( K+1)-valued PLA structure logic circuits. For a two-level funct- ion, there exists a value K for which the number of remaining faults of the (K+1)-valued circuit is smaller than that of the binary circuit after the collapsing. Then it proposes a complete test set for MVL Min/Max networks. An algorithm to generate CTS is also developed. Experimental results show that, for most of functions, the sizes of compete test sets can be reduced when they are represented as MVL functions. On synthesis, it presents the agebraic division procedure. By introducing two MVL Boolean properties into the division operation, it further improves the procedure to be a mix- algebraic one, which can obtain more efficient algebraic division . Besides, we formulate the factorization problem of MVL logic functions as a rectangular covering problem and gives its solut- ion . It first, develops an purely algebraic factorization algorithm, then by incorporating with two MVL Boolean properties, it further improves the algorithm to be a Boolean one which can perform a subset of Boolean factorization to obtain a better factorization for MVL functions.