基于DNA計算的組合電路測試生成研究.pdf

1、隨著數(shù)字集成電路技術(shù)的飛速發(fā)展,集成電路的測試生成變得越來越困難,花費(fèi)的時間也越來越多。對于大規(guī)模的集成電路,傳統(tǒng)的測試生成算法已不再適用,尋找新型、有效的測試生成算法已成為一個重要的研究課題。
　　DNA計算是在計算科學(xué)和分子生物學(xué)的基礎(chǔ)上發(fā)展起來的一個新穎而極具發(fā)展?jié)摿Φ膶W(xué)科。它與遺傳算法(GA)天生就具有某種必然的聯(lián)系。本文采用GA作為DNA計算進(jìn)行復(fù)雜優(yōu)化問題求解的橋梁,在基于故障模擬的基礎(chǔ)上,建立了應(yīng)用DNA-GA解決組

2、合電路測試生成問題的算法流程。針對基于模擬的測試生成流程的特點,在算法流程中引入了兩個啟發(fā)性過程。本算法通過DNA的四字符集Σ={A, C, G, T}的編碼,引入基因級的遺傳操作,保證了種群的多樣性;控制測試生成不同階段中DNA鏈生成測試集的大小,減小了測試集的冗余,加快了測試生成速度。為將本算法與其他算法進(jìn)行比較,在國際標(biāo)準(zhǔn)電路iscas’85上對該算法進(jìn)行了驗證,并對結(jié)果進(jìn)行了分析。實驗結(jié)果表明本文算法獲得到了較高的故障覆蓋率,同

3、時生成的測試矢量集大幅度縮小,證明本算法用于組合電路測試生成是有效的。
　　從DNA生化實驗實現(xiàn)計算的角度,本文研究了組合電路測試生成的SAT解決方法,并建立了基于表面型的DNA生化計算模型。通過分析組合電路測試生成的CNF特點,引入了兩點改進(jìn)方法。在DNA計算模型中將原電路CNF和故障電路CNF的變量分別編碼,降低了DNA編碼的復(fù)雜度,使原電路CNF的DNA解鏈重復(fù)使用,降低了耗材。最后給出了應(yīng)用DNA計算解決組合電路測試生成的