基于DNA計(jì)算的組合電路測(cè)試生成研究.pdf

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

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

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