【摘要】：覆蓋等效性檢測(cè)指驗(yàn)證2個(gè)具有不同表達(dá)式的組合邏輯電路是否實(shí)現(xiàn)相同的函數(shù)功能.通過擴(kuò)展余子式概念,提出一種基于乘積項(xiàng)余子式分解及重言式判別的組合邏輯電路覆蓋等效性檢測(cè)算法.首先將等效性檢測(cè)問題分解成電路包含檢測(cè)子問題,逐一求取其中一個(gè)電路表達(dá)式對(duì)另一個(gè)電路表達(dá)式各乘積項(xiàng)的余子式;然后在建立各乘積項(xiàng)余子式的香農(nóng)結(jié)構(gòu)圖基礎(chǔ)上判斷其是否重言式;最后根據(jù)重言式判別結(jié)果確定兩電路間是否覆蓋等效關(guān)系.該算法通過求取乘積項(xiàng)余子式對(duì)邏輯函數(shù)進(jìn)行分解和降階處理,從而加快了覆蓋等效性驗(yàn)證速度.電路測(cè)試結(jié)果表明,文中算法是穩(wěn)定有效的;對(duì)EXPRESSO軟件集成的3種算法所得電路的測(cè)試結(jié)果表明,與基于真值表和BDD的2種檢測(cè)算法相比,該算法具有明顯的速度優(yōu)勢(shì).
【圖文】：

仍?低于常規(guī)的指數(shù)時(shí)間,從而使算法能夠地有效解決較大規(guī)模電路的覆蓋等性檢測(cè)問題.1函數(shù)間包含關(guān)系判定定理1.1基本概念函數(shù)間包含關(guān)系判斷涉及蘊(yùn)含項(xiàng)、覆蓋、覆蓋等效、重言式和余子式等基本概念.在介紹這些概念的基礎(chǔ)上,將介紹擴(kuò)展性概念乘積項(xiàng)余子式.不失一般性,下文中邏輯函數(shù)表達(dá)式均是積之和形式.蘊(yùn)含項(xiàng).在組合邏輯函數(shù)表達(dá)式中,每個(gè)乘積項(xiàng)及其對(duì)應(yīng)的最小項(xiàng)都稱為該函數(shù)的蘊(yùn)含項(xiàng).同時(shí),乘積項(xiàng)間利用代數(shù)式等效操作得到的乘積項(xiàng)也是該函數(shù)的蘊(yùn)含項(xiàng)[10].對(duì)于兩變量函數(shù)11213123fxxxxxxx,其卡諾圖如圖1所示.顯然,121323123xx,xx,xx,xxx等都是f1的蘊(yùn)含項(xiàng)..圖1函數(shù)f1的卡諾圖覆蓋.任意一個(gè)包含且僅包含函數(shù)所有最小項(xiàng)信息的蘊(yùn)含項(xiàng)集合構(gòu)成函數(shù)的一個(gè)覆蓋.當(dāng)覆蓋中的乘積項(xiàng)都是最小項(xiàng)時(shí),稱為最小項(xiàng)覆蓋.函數(shù)的不同覆蓋之間是等效的,且任意邏輯函數(shù)均可用它的任意覆蓋來(lái)等效表示[11].結(jié)合圖1,兩蘊(yùn)含項(xiàng)集合1213{xx,xx}和123{xxx,23123xx,xxx}都是函數(shù)f1的覆蓋.覆蓋等效.若兩函數(shù)可用同一個(gè)最小項(xiàng)覆蓋表示,稱它們是覆蓋等效的.函數(shù)212323123fxxxxxxxx的3個(gè)乘積項(xiàng)顯然構(gòu)成它的一個(gè)覆蓋12323123{xxx,xx,xxx}.由于此覆蓋與函數(shù)f1對(duì)應(yīng)同一個(gè)最小項(xiàng)覆蓋,故函數(shù)f1和f2是覆蓋等效的.重言式.若對(duì)于輸入變量的任意確定性取值,某函數(shù)的值恒為邏輯1,稱該函數(shù)是重言式.容易驗(yàn)證,函數(shù)311fxx和函數(shù)412fxx131231xxxxxx都是重言式,因?yàn)檫@2個(gè)函數(shù)在各自輸入變量所有可能取值下的邏輯值都是1.其中函數(shù)f4的卡諾圖如圖2所示.余子式.式(1)所示邏輯函數(shù)的香農(nóng)展開中,1xf和1xf分別稱為此函數(shù)對(duì)于1x和1x的余子式.111111212(,,)(1,,,)(0,

2142計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)第29卷圖2函數(shù)f4的卡諾圖本文稱1x為拆分變量.2個(gè)余子式可通過把拆分變量的對(duì)應(yīng)形式(即原形或反變量)等于1代入原函數(shù)計(jì)算得到.對(duì)余子式的概念進(jìn)行擴(kuò)展,可得函數(shù)對(duì)具體乘積項(xiàng)的余子式.乘積項(xiàng)余子式.設(shè)某乘積項(xiàng)12kmxxx,函數(shù)f對(duì)于m的余子式fm的計(jì)算方法為1212((()))kkmxxxxxxfff(2)即把m的所有分量ix等于1代入函數(shù)f即得fm.式(2)中,分量ix(i1,2,,k)為對(duì)應(yīng)變量的原形ix或取反形式ix;fm的計(jì)算結(jié)果與拆分變量的選取順序無(wú)關(guān),即對(duì)于m的任意2個(gè)分量ix和jx(i,j=1,2,…,k,ij),有()()ijjixxxxff.顯然,變量或乘積項(xiàng)余子式的求取本質(zhì)上是基于某個(gè)或某些變量對(duì)原函數(shù)降階分解的過程.1.2函數(shù)包含關(guān)系及其判定定理函數(shù)表達(dá)式中,對(duì)于某個(gè)或某些變量未出現(xiàn)的乘積項(xiàng),總是可以應(yīng)用等式1iixx擴(kuò)展得到該乘積項(xiàng)對(duì)應(yīng)的所有最小項(xiàng).故基于覆蓋的定義,可以確定函數(shù)間是否存在包含關(guān)系.函數(shù)間的包含關(guān)系.對(duì)于2個(gè)組合邏輯函數(shù)f和g,若f的一個(gè)覆蓋包含g的所有乘積項(xiàng)信息,則該覆蓋必包含g的所有最小項(xiàng)信息,稱f包含g,記為fg.若兩函數(shù)f和g存在相互包含關(guān)系,則它們是覆蓋等效的.因?yàn)橄嗷グ砻?函數(shù)f的任一覆蓋必包含且僅包含g的所有最小項(xiàng),即f的任一覆蓋同時(shí)也是g的覆蓋.故f和g是覆蓋等效的.可見,包含關(guān)系判定是函數(shù)覆蓋等效性檢測(cè)的關(guān)鍵步驟.利用余子式和重言式概念,本文提出函數(shù)包含關(guān)系判定定理.定理1.對(duì)于函數(shù)f和g,若f對(duì)g的每個(gè)乘積項(xiàng)的余子式都是重言式,則f包含g.證明.設(shè)函數(shù)f對(duì)g的乘積項(xiàng)mi的余子式為.imfimf是重言式表明:把mi的每個(gè)分量ix等于1代入函數(shù)f,所得結(jié)果恒為1;或者說(shuō),mi為1時(shí)恒有f
【作者單位】： 寧波大學(xué)電路與系統(tǒng)研究所;
【基金】：國(guó)家自然科學(xué)基金(61306041,61234002) 浙江省自然科學(xué)基金(LY13F040003)
【分類號(hào)】：TN791

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 黃克峰;組合邏輯電路的應(yīng)用技術(shù)[J];邵陽(yáng)高等�？茖W(xué)校學(xué)報(bào);2000年04期

2 唐廣芝;關(guān)于組合邏輯電路的教學(xué)體會(huì)[J];現(xiàn)代技能開發(fā);2003年03期

3 張京英;組合邏輯電路中的競(jìng)爭(zhēng)冒險(xiǎn)現(xiàn)象的判斷和消除[J];青海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年02期

4 侯文霞;組合邏輯電路中多余項(xiàng)的設(shè)計(jì)應(yīng)用[J];濰坊學(xué)院學(xué)報(bào);2003年06期

5 劉秀珍;“組合邏輯電路的設(shè)計(jì)方法”教學(xué)說(shuō)課設(shè)計(jì)[J];衛(wèi)生職業(yè)教育;2005年12期

6 魏萍;;組合邏輯電路的冒險(xiǎn)現(xiàn)象的仿真分析[J];光盤技術(shù);2008年10期

7 左全生;;組合邏輯電路設(shè)計(jì)的一種方法[J];現(xiàn)代電子技術(shù);2008年06期

8 卞元紅;;試談組合邏輯電路的分析和設(shè)計(jì)問題[J];科協(xié)論壇(下半月);2009年11期

9 何其貴;余春平;;組合邏輯電路的競(jìng)爭(zhēng)與險(xiǎn)象研究[J];信息系統(tǒng)工程;2010年05期

10 胡福云;;組合邏輯電路的競(jìng)爭(zhēng)冒險(xiǎn)及仿真[J];軟件導(dǎo)刊;2012年12期

相關(guān)會(huì)議論文 前1條

1 宋曉玫;韓德紅;;組合邏輯電路的系統(tǒng)講授學(xué)習(xí)方法[A];教育部中南地區(qū)高等學(xué)校電子電氣基礎(chǔ)課教學(xué)研究會(huì)第二十屆學(xué)術(shù)年會(huì)會(huì)議論文集（上冊(cè)）[C];2010年

相關(guān)重要報(bào)紙文章 前2條

1 廊坊市電子信息工程學(xué)院 朱翠芳;組合邏輯電路設(shè)計(jì)[N];電子報(bào);2007年

2 南昌 李春玲;“多輸入多無(wú)關(guān)項(xiàng)” 組合邏輯電路的設(shè)計(jì)方法[N];電子報(bào);2012年

相關(guān)碩士學(xué)位論文 前4條

1 韓健;針對(duì)組合邏輯電路的抗輻射加固研究[D];合肥工業(yè)大學(xué);2014年

2 林堯;NBTI效應(yīng)對(duì)數(shù)字集成電路組合邏輯延遲的影響研究[D];華東師范大學(xué);2016年

3 尚濤;組合邏輯電路自動(dòng)合成的方法研究[D];武漢科技大學(xué);2009年

4 周克城;基于FPGA的組合邏輯電路自動(dòng)合成的硬件實(shí)現(xiàn)[D];武漢科技大學(xué);2011年

，

本文編號(hào)：2526374