基于多項式符號代數(shù)的數(shù)字電路形式驗證方法研究.pdf

1、隨著數(shù)字集成電路設(shè)計規(guī)模的增大和功能復(fù)雜性的提高，功能驗證已經(jīng)成為設(shè)計流程中的瓶頸。傳統(tǒng)的模擬驗證方法無法滿足現(xiàn)時復(fù)雜集成電路設(shè)計帶來的巨大的驗證需求。形式驗證技術(shù)，例如模型檢驗和等價驗證，因此發(fā)展成為模擬驗證方法的一種重要補充，正日益受到學(xué)術(shù)界的關(guān)注。現(xiàn)有的形式驗證技術(shù)大多基于傳統(tǒng)的位級方法，例如BDD或布爾SAT，它們主要針對低層次門級電路和以控制流為主的電路的驗證，難以勝任以數(shù)據(jù)流為主的高層次復(fù)雜電路設(shè)計的驗證。作為一種新近提出的

2、電路表示和計算方法，多項式符號代數(shù)能夠克服BDD和布爾SAT方法的某些不足。本文深入研究了多項式符號代數(shù)方法在數(shù)字電路形式驗證中的應(yīng)用，取得了如下創(chuàng)新性成果：
　　 (1)提出了基于多項式符號代數(shù)的模型檢驗方法。首先，擴展了傳統(tǒng)的Kripke結(jié)構(gòu)的概念，得到了所謂狀態(tài)轉(zhuǎn)換系統(tǒng)的新概念。用該狀態(tài)轉(zhuǎn)換系統(tǒng)代替?zhèn)鹘y(tǒng)的Kripke結(jié)構(gòu)來抽象高層次設(shè)計中的控制邏輯，并統(tǒng)一用多項式方法描述高層次設(shè)計中的數(shù)據(jù)通路和控制邏輯，從而有效地避免了數(shù)

3、據(jù)域和控制域之間頻繁的約束傳播和回溯操作。進而，給出了一個高層次設(shè)計模型檢驗的方法框架。在該方法框架之下，原有的模型檢驗問題被轉(zhuǎn)化為一個假設(shè)和結(jié)論均具有多項式形式的一階邏輯定理證明問題，一個基于多項式符號計算的判定過程被用來有效地解決該定理證明問題。針對典型高層次設(shè)計的實驗結(jié)果表明，與現(xiàn)有的基于非線性求解器的高層次模型檢驗方法相比，該方法在保證驗證準(zhǔn)確性的情況下，平均要快1到5倍。
　　 (2)提出了基于多項式符號代數(shù)的等價驗證

4、方法。該方法直接在高層次建模數(shù)據(jù)通路設(shè)計，給出了高層次數(shù)據(jù)通路的多項式集合表示的一般形式及構(gòu)造方法。由于避免了將高層次數(shù)據(jù)通路設(shè)計展開為門級網(wǎng)表，對于同樣的驗證問題，該方法涉及的信號變量的數(shù)目和約束表達式的數(shù)目要比基于BDD和布爾SAT的等價驗證方法少得多。進而，從多項式集合公共零點的角度定義了高層次數(shù)據(jù)通路的功能等價性，并給出了一個基于多項式符號計算的有效的代數(shù)求解算法。針對高層次基準(zhǔn)數(shù)據(jù)通路的實驗結(jié)果表明，與現(xiàn)有的基于*BMD和整數(shù)

5、線性規(guī)劃的高層次等價驗證方法相比，該方法在保證錯誤診斷能力的情況下，平均要快1倍到1個數(shù)量級。
　　 (3)提出了基于多項式符號代數(shù)的層次化驗證方法。首先，引入了一種基于廣義表數(shù)據(jù)結(jié)構(gòu)的層次化電路表示模型?；诖朔N層次化表示，并應(yīng)用多項式代數(shù)中的消元定理和擴張定理，得到了一種層次化的電路功能計算方法。該方法將原本規(guī)模較大的計算問題劃分為一些小的計算問題，并以一種逐層遞歸的方式完成原有計算，從而有效地提高了計算效率。進而，將這種新