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

關(guān)鍵詞：最簡化；約束條件；組合邏輯電路設(shè)計(jì)；編碼器；奎恩-麥克拉斯基法

中圖分類號(hào)：TN710 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：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

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

1 新方法的基本思想

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

因?yàn)閝=q₁q₂…Q_t在輸出變量為1的組合中出現(xiàn)，在某個(gè)輸出變量為0的組合沒有出現(xiàn)，但不知道在其他輸出變量為0的組合會(huì)不會(huì)出現(xiàn)，所以q=q₁q₂…Q_t可以表示這個(gè)輸出變量的一部分，但不能表示這個(gè)輸出變量的全部。

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

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

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

與邏輯表示只有在決定事物結(jié)果的全部條件具備時(shí)，結(jié)果才發(fā)生的因果關(guān)系。輸出變量為1的某個(gè)組合的所有因子的與表示輸出變量為1的這個(gè)組合出現(xiàn)、所有輸出變量為0的組合均不出現(xiàn)，因而可以表示輸出變量為1的這個(gè)組合。

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

2 新方法舉例

例1：研究3位二進(jìn)制(8線-3線)編碼器，他的8個(gè)輸入變量I7I6I5I4I3I2I1I0允許8種組合，發(fā)現(xiàn)每種組合只有一個(gè)變量為1，其余變量為零；2個(gè)或2個(gè)以上的變量為1的組合都是不允許出現(xiàn)的。輸出變量Y2Y1Y0的每一位都有4個(gè)組合為1、4個(gè)組合為0，其他都是約束項(xiàng)(見表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的這個(gè)組合所有因子的與是I4，I0I1I2I3。取其最簡單的表達(dá)式，即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位二進(jìn)制數(shù)碼輸出的并行比較型模/數(shù)變換器的代碼轉(zhuǎn)換如表2所示：

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

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

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

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

最后可得D1的最簡表達(dá)式是：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的所有因子的與的最簡單的表達(dá)式是C1C2。同理，D0的第4種組合為1的所有因子的與的最簡單的表達(dá)式是C3C4；D0的第6種組合為1的所有因子的與的最簡單的表達(dá)式是C5C6；D0的第8種組合為1的所有因子的與的最簡單的表達(dá)式是C7。最后可得D0的最簡表達(dá)式是：C7+C5C6+C3C4+C1C2。

3 結(jié) 語

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

參考文獻(xiàn)

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

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

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

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。