組合邏輯電路設計的一種方法

摘 要：在ASIC設計和PLD設計中組合邏輯電路設計的最簡化是很重要的，在設計時常要求用最少的邏輯門或導線實現。在ASIC設計和PLD設計中需要處理大量的約束項，值為1或0的項卻是有限的，提出組合邏輯電路設計的一種新方法。該方法不考慮這些約束項，只考慮那些值為1或0的項，因而可以簡化設計步驟。該方法特別適合于有大量約束項的組合邏輯電路設計。例舉2個組合邏輯電路實例，說明按照這個改進的方法可以大大減少組合邏輯電路設計步驟。

關鍵詞：最簡化；約束條件；組合邏輯電路設計；編碼器；奎恩-麥克拉斯基法

中圖分類號：TN710 文獻標識碼：B

文章編號：1004-373X(2008)06-006-02

A New Method about Combinational Circuit Synthesis

ZUOQuansheng

(Changzhou Institute of Technology，Changzhou，213002，China)

Abstract：Minimization is an important step in both ASIC design and in PLD-based design.It is highly desirable to find the simplest implementation that is the one with the smallest number of gates or wires.A large number of constraint terms are dealt with in both ASIC design and in PLD-based design，but the terms whose value is 1 or 0 is limited. A new method about combinational-circuit synthesis is proposed.This method can′t deal with these constraint terms.It can only deal with those terms whose value is 1 or 0.So the steps of synthesis is simplied.It is specialized utilized in those combinational circuit synthesis which has a large number of constraint terms.Two actual examples are proposed to give evidence that according to this method we can minimize the steps of synthesis.

Keywords：minimization；constraint condition；combinational circuit synthesis；encoder；Quine-McClusky algorithm

組合邏輯電路設計的最簡化無論在ASIC設計和PLD設計中都很重要。因為組合邏輯電路中多余的門和輸入端需要ASIC芯片的更多面積，因而也增加了他的成本；PLD的門電路是固定的，組合邏輯電路中有多余的門和輸入端就需要容量更大、速度更慢、價格更高的PLD。因為用一般的邏輯表達式實現的組合邏輯電路的規模隨輸入變量的數目增加而成指數級增加，所以直接用一般的邏輯表達式實現邏輯電路是不經濟的。現在組合邏輯電路設計有很多種方法，但這些方法對那些有大量約束項的組合邏輯電路設計不是最好的。工程上常見的組合邏輯電路常有很多輸入變量，對多輸入變量的組合邏輯電路設計，文獻\\[1\\]和文獻\\[2\\]介紹的公式法和卡諾圖法都不適用。這些組合邏輯電路常有很多約束條件，使用文獻\\[1\\]介紹的奎恩-麥克拉斯基法步驟很多。例如3位二進制(8線-3線)編碼器有8個輸入變量I7I6I5I4I3I2I1I0，3個輸出變量Y2Y1Y0。8個輸入變量I7I6I5I4I3I2I1I0只有8種允許的組合，即00000001，00000010，00000100，00001000，00010000，00100000，01000000，10000000。另外248種組合是不允許出現的約束項。任何一個輸出變量實際上只有4種組合為1，4種組合為0。又如并行比較型模/數變換器ADC0881芯片中有255個時鐘鎖存器(可用C255C254…C2C1表示)。這255個變量的組合數量是很大的，但他的編碼器的輸出是8位二進制數(用D7D6D5D4D3D2D1D0表示)，也就是說這255個變量只有256種組合是允許出現的，其他大量的組合是不允許出現的約束項。編碼器的每位輸出變量實際上只有128種組合為1，128種組合為0。傳統的公式法和卡諾圖法等組合邏輯電路設計方法主要是通過對為1的組合和約束項進行處理，對為0的組合基本不處理。對于多輸入變量的組合邏輯電路設計而言，大量的約束項大大地增加了設計的復雜度。通過研究發現：利用這些有限的1和0就能設計組合邏輯電路，很多約束條件在設計時可以不用處理，這就可以大大簡化邏輯電路的分析和設計。

1 新方法的基本思想

引理1 比較輸出變量為1的組合與某個輸出變量為0的組合，找出其中不同的變量及其組合，例如輸出變量為1的組合有q=q₁q₂…Q_t，而某個輸出變量為0的組合沒有q=q₁q₂…Q_t，則q=q₁q₂…Q_t是該輸出變量為1的組合的一個因子。

因為q=q₁q₂…Q_t在輸出變量為1的組合中出現，在某個輸出變量為0的組合沒有出現，但不知道在其他輸出變量為0的組合會不會出現，所以q=q₁q₂…Q_t可以表示這個輸出變量的一部分，但不能表示這個輸出變量的全部。

引理2 設Q=Q₁Q₂…Q_T是輸出變量為1的組合出現，而所有輸出變量為0的組合均不出現，則該輸出變量為1的組合可以用Q=Q₁Q₂…Q_T表示。

因為Q=Q₁Q₂…Q_T在所有輸出變量為0的組合均不出現，這說明含Q=Q₁Q₂…Q_T的所有項要么是1，要么是約束項，因而該輸出變量為1的組合可以用Q=Q₁Q₂…Q_T表示。

引理3 輸出變量為1的某個組合的所有因子的與可以表示該輸出變量為1的組合。

與邏輯表示只有在決定事物結果的全部條件具備時，結果才發生的因果關系。輸出變量為1的某個組合的所有因子的與表示輸出變量為1的這個組合出現、所有輸出變量為0的組合均不出現，因而可以表示輸出變量為1的這個組合。

引理4 一個輸出變量所有為1的組合的或可以表示該輸出變量。

2 新方法舉例

例1：研究3位二進制(8線-3線)編碼器，他的8個輸入變量I7I6I5I4I3I2I1I0允許8種組合，發現每種組合只有一個變量為1，其余變量為零；2個或2個以上的變量為1的組合都是不允許出現的。輸出變量Y2Y1Y0的每一位都有4個組合為1、4個組合為0，其他都是約束項(見表1)。

Y2的第5種組合為1，這種組合有而他為0的第1種組合沒有的因子是I4，I0，I0I4；這種組合有而他為0的第2種組合沒有的因子是I4，I1，I1I4；這種組合有而他為0的第3種組合沒有的因子是I4，I2，I2I4；這種組合有而他為0的第4種組合沒有的因子是I4，I3，I3I4；輸出變量為1的這個組合所有因子的與是I4，I0I1I2I3。取其最簡單的表達式，即Y2的第5種組合可以表示為I4。同理可得：Y2的第6種組合可以表示為I5；Y2的第7種組合可以表示為I6；Y2的第8種組合可以表示為I7。最后可得：Y2=I4+I5+I6+I7；

同理可得：Y0=I1+I3+I5+I7；Y1=I2+I3+I6+I7。

例2：3位二進制數碼輸出的并行比較型模/數變換器的代碼轉換如表2所示：

D2的第5種組合為1，這種組合有而他為0的第1種組合沒有的因子是C4，C3，C2，C1；這種組合有而他為0的第2種組合沒有的因子是C4，C3，C2；這種組合有而他為0的第3種組合沒有的因子是C4，C3；這種組合有而他為0的第4種組合沒有的因子是C4。

D2的這種種組合為1的所有因子的與的最簡單表達式是C4，即D2的第5種組合可以表示為C4；同理，D2的第6種組合為1的所有因子的與的最簡單表達式是C4，C5，即D2的第6種組合可以表示為C4或C5；D2的第7種組合為1的所有因子的與的最簡單表達式是C4，C5，C6，即D2的第7種組合可以表示為C4或C5，C6；D2的第8種組合為1的所有因子的與的最簡單的表達式是C4，C5，C6，C7，即D2的第8種組合可以表示為C4或C5，C6，C7。最后得D2的最簡表達式是：D2=C4。

D1的第3種組合為1，這種組合有而他為0的第1種組合沒有的因子是C2，C1；這種組合有而他為0的第2種組合沒有的因子是C2；這種組合有而他為0的第5種組合沒有的因子是C4，C3；這種組合有而他為0的第6種組合沒有的因子是C5，C4，C3。

D1的這種種組合為1的所有因子的與的最簡單的表達式是C2C4或C2C3；同理，D1的第4種組合為1的所有因子的與的最簡單的表達式是C1C4或C2C4；D1的第7種組合為1的所有因子的與的最簡單的表達式是C6；D1的第8種組合為1的所有因子的與的最簡單的表達式是C6或C7。

最后可得D1的最簡表達式是：C6+C2C4。D0的第2種組合為1，這種組合有而他為0的第1種組合沒有的因子是C1；這種組合有而他為0的第3種組合沒有的因子是C2；這種組合有而他為0的第5種組合沒有的因子是C4，C3，C2；這種組合有而他為0的第7種組合沒有的因子是C6，C5，C4，C3，C2。D0的這種種組合為1的所有因子的與的最簡單的表達式是C1C2。同理，D0的第4種組合為1的所有因子的與的最簡單的表達式是C3C4；D0的第6種組合為1的所有因子的與的最簡單的表達式是C5C6；D0的第8種組合為1的所有因子的與的最簡單的表達式是C7。最后可得D0的最簡表達式是：C7+C5C6+C3C4+C1C2。

3 結 語

類似的例子可以舉很多，通過上述例子分析可知，利用本文介紹的方法，這些約束條件許多可以不加處理，這可以大大簡化邏輯電路的分析和設計。

參考文獻

[1]Brian H，Clive W.Digital Logic Design\\[M\\].北京：人民郵電出版社，2006.

[2]閻石.數字電子技術基礎\\[M\\].北京：高等教育出版社，2005.

[3]Katz R H.Contemporary Logic Design\\[M\\].北京：電子工業出版社，2005.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。