平面單折布線(xiàn)的判別準(zhǔn)則與算法實(shí)現(xiàn).pdf

1、布線(xiàn)問(wèn)題是集成電路設(shè)計(jì)中一個(gè)重要的問(wèn)題，隨著集成電路設(shè)計(jì)規(guī)模的不斷擴(kuò)大，布線(xiàn)問(wèn)題的解決越來(lái)越需要完備數(shù)學(xué)理論和先進(jìn)計(jì)算機(jī)技術(shù)的支持。近年來(lái)關(guān)于這兩個(gè)方面的研究成果可謂是見(jiàn)仁見(jiàn)智，然而即使如此，距離布線(xiàn)問(wèn)題的最終解決仍有很長(zhǎng)的路要走。 針對(duì)布線(xiàn)問(wèn)題中的一個(gè)具體問(wèn)題：在平面上實(shí)現(xiàn)單折布線(xiàn)。劉彥佩教授在其專(zhuān)著《縱橫布局論》中進(jìn)行了詳盡的研究，建立了判決圖的概念，并將這個(gè)問(wèn)題最終簡(jiǎn)化為一類(lèi)二次布爾方程的求解問(wèn)題。然而，如何從理論上判斷解

2、的存在性以及相關(guān)算法的計(jì)算機(jī)實(shí)現(xiàn)問(wèn)題還有待解決。 本文在劉彥佩教授的判決圖理論的基礎(chǔ)上，進(jìn)一步發(fā)展出判決圖的方向性、導(dǎo)出判決圖、不可解環(huán)等概念，得到一組平面單折布線(xiàn)問(wèn)題的判別準(zhǔn)則和一個(gè)基于此的算法，并對(duì)此算法的計(jì)算機(jī)實(shí)現(xiàn)進(jìn)行了具體的討論。 全文共分五部分： 第一章簡(jiǎn)要介紹了一些基本概念和相關(guān)定理。 第二章和第三章通過(guò)對(duì)問(wèn)題的分析得到了一組判別準(zhǔn)則和始單元算法，并對(duì)問(wèn)題中存在的禁用構(gòu)形進(jìn)行了分析。