相容關系模型及其在邏輯優化中的應用*

王好為，閆繼雄，柴 晶，陳澤華

太原理工大學 信息工程學院，太原 030024

1 引言

邏輯表達式化簡技術[1]是數字電路中的一個重要內容，其作用是能在保證原電路功能不變的情況下，減少輸入電路中門電路的個數，使得電路更簡潔、更安全。

傳統的邏輯表達式化簡方法有公式法[2]、卡諾圖法[2]、Q-M算法[3]和立方體法[4]等。其中公式法不僅需要熟練使用邏輯代數的相關知識，而且不易編程；卡諾圖法是一種直觀的邏輯表達式化簡方法，但是當輸入變量個數超過6時，難以表達；Q-M算法是基于卡諾圖法的一種改進算法，但是算法復雜度依舊很高；立方體法具有較低的時間復雜度，但是對于多變量表達式，其計算過程不易理解。

近年來，有很多學者在邏輯表達式化簡方面進行了研究，并取得了較大的進展。他們對傳統方法進行了改進，包含對卡諾圖法的改進算法[5-6]和對Q-M算法的改進算法[7-8]。Gómez等人[9]依據邏輯表達式的拓撲和統計特性提取了其中的質蘊涵項，將表達式的化簡過程轉化為最小項的化簡過程，從而降低了計算的復雜性；Chowdhury等人[10]基于MZI（Mach-Zehnder interferometer）的模式匹配方案將邏輯表達式轉化為邏輯電路，根據去除電路的輔助線達到約簡的目的，但該方法依賴于硬件電路的實驗結果，并且實驗成本較高，不具有實用性；陳澤華等人[11]基于粗糙集的等價關系模型實現了普通真值表的快速并行約簡，但是該方法處理邏輯表達式時需要將其展開為最小項，并轉化為完整輸入狀態的真值表，轉化過程較為繁瑣，也會增加額外的空間復雜度。……