離散數(shù)學與網(wǎng)絡(luò)分析與綜合的聯(lián)系

1、離散數(shù)學與網(wǎng)絡(luò)分析與綜合的聯(lián)系班級：通信1103 姓名：張悅 學號：0909111903一、引言：離散數(shù)學(Discrete mathematics)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學學科，是現(xiàn)代數(shù)學的一個重要分支。其內(nèi)容包含：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論、組合學、數(shù)論等。隨著信息時代的到來，工業(yè)革命時代以微積分為代表的連續(xù)數(shù)學占主流的地位已經(jīng)發(fā)生了變化，離散數(shù)學的重要性逐漸被人們認識。離散數(shù)學課程所傳授的思想和方法，廣泛地體現(xiàn)在計算機科學技術(shù)及相關(guān)專業(yè)的諸領(lǐng)域，從科學計算到信息處理，從理論計算機科學到計算機應(yīng)用技術(shù)，從計算機軟件到計算機硬件，從人工智能到認知系統(tǒng)，無不與離散數(shù)學密切相關(guān)

2、。本文將詳細的介紹離散數(shù)學在信息科學中的應(yīng)用。信息科學專業(yè)主要學習電子信息科學與技術(shù)的基本理論和技術(shù)，受到科學實驗與科學思維的訓練，具有本學科及跨學科的應(yīng)用研究與技術(shù)開發(fā)的基本能力。本專業(yè)培養(yǎng)具備物理電子、光電子與微電子學領(lǐng)域內(nèi)寬廣理論基礎(chǔ)、實驗?zāi)芰蛯I(yè)知識，能在該領(lǐng)域內(nèi)從事各種電子材料、元器件、集成電路、乃至集成電子系統(tǒng)和光電子系統(tǒng)的設(shè)計、制造和相應(yīng)的新產(chǎn)品、新技術(shù)、新工藝的研究、開發(fā)等方面工作的高級工程技術(shù)人才。它以電子器件及其系統(tǒng)應(yīng)用為核心，重視器件與系統(tǒng)的交叉與融合，面向微電子、光電子、光通信、高清晰度顯示產(chǎn)業(yè)等國民經(jīng)濟發(fā)展需求，培養(yǎng)在通信、電子系統(tǒng)、計算機、自動控制、電子材料與器件

3、等領(lǐng)域具有寬廣的適應(yīng)能力、扎實的理論基礎(chǔ)、系統(tǒng)的專業(yè)知識、較強的實踐能力、具備創(chuàng)新意識的高級技術(shù)人才和管理人才，并掌握一定的人文社會科學及經(jīng)濟管理方面的基礎(chǔ)知識，能從事這些領(lǐng)域的科學研究、工程設(shè)計及技術(shù)開發(fā)等方面工作。主要課程：電子線路、計算機語言、微型計算機原理、電動力學、量子力學、理論物理、固體物理、半導體物理、物理電子與電子學以及微電子學等方面的專業(yè)課程。離散數(shù)學作為一個單獨的分枝，在世界上出現(xiàn)的時間并不久，不過幾十年，但它的各部分內(nèi)容中有相當一部分卻早已出現(xiàn)在數(shù)學中。為什么將各個數(shù)學分支中的一些內(nèi)容集中起來加以研究，并且冠上一個新的名稱離散數(shù)學呢？這主要是因為計算機科學的產(chǎn)生和發(fā)展。正

4、如恩格斯所說：“科學的狀況還更多的從屬于技術(shù)的狀況和需要。倘若社會上有了一種技術(shù)上的需要，那就比十個大學還更能推動科學前進?！倍⒄?網(wǎng)絡(luò)圖論在布局和布線中有指導作用，把構(gòu)成具有一定功能的電路所需的半導體、電阻、電容等元件及它們之間的連接導線全部集成在一小塊硅片上，然后焊接封裝在一個管殼內(nèi)，使電子元件向著微小型化、低功耗和高可靠性方面邁進。在縮小電子系統(tǒng)體積的同時，保持并提高系統(tǒng)的速度與性能成為擺程設(shè)計者面前的一個重要課題。進行電路分析時,利用網(wǎng)絡(luò)圖論的方法,能簡化運算過程,能把節(jié)點方程直接寫出,使電路分析的系統(tǒng)化更加便捷。最后根據(jù)平面圖定理, 通過對圖的回路矩陣B進行檢測,以判定圖的平面性

5、作了基本說明。三、相關(guān)概念 集成電路（integrated circuit,簡稱IC）是一種微型電子器件或部件。采用一定的工藝，把一個電路中所需的晶體管、二極管、電阻、電容和電感等元件及布線互連一起，制作在一小塊或幾小塊半導體晶片或介質(zhì)基片上，然后封裝在一個管殼內(nèi)，成為具有所需電路功能的微型結(jié)構(gòu)；其中所有元件在結(jié)構(gòu)上已組成一個整體，使電子元件向著微小型化、低功耗和高可靠性方面邁進了一大步。集成電路發(fā)明者為杰克·基爾比（基于硅的集成電路）和羅伯特·諾伊思（基于鍺的集成電路）。當今半導體工業(yè)大多數(shù)應(yīng)用的是基于硅的集成電路。集成電路是20世紀60年代初期發(fā)展起來的一種新型半導體器

6、件。它是經(jīng)過氧化、光刻、擴散、外延、蒸鋁等半導體制造工藝，把構(gòu)成具有一定功能的電路所需的半導體、電阻、電容等元件及它們之間的連接導線全部集成在一小塊硅片上，然后焊接封裝在一個管殼內(nèi)的電子器件。其封裝外殼有圓殼式、扁平式或雙列直插式等多種形式。集成電路技術(shù)包括芯片制造技術(shù)與設(shè)計技術(shù)，主要體現(xiàn)在加工設(shè)備，加工工藝，封裝測試，批量生產(chǎn)及設(shè)計創(chuàng)新的能力上。 圖論Graph Theory是數(shù)學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系。四、知識遷移（網(wǎng)絡(luò)分析

7、與綜合）  1、基本概念網(wǎng)絡(luò)圖論又稱為網(wǎng)絡(luò)拓撲學，適應(yīng)用圖的理論,對電路的結(jié)構(gòu)及其連接性質(zhì)進行分析和研究。網(wǎng)絡(luò)的圖又稱為拓撲圖，它是這樣定義的：一個圖G (Gragh) 是節(jié)點（點）和支路（線段）的集合，每條支路的兩端都聯(lián)到相應(yīng)的節(jié)點上。每一條支路代表一個電路元件，或者代表某些元件的組合。如上圖（a）、(b) 分別畫出了兩個具體的電路圖及與它們對應(yīng)的拓撲圖，如果給出支路電流和電壓的參考方向，可以看出雖然（a）、(b)圖中的支路內(nèi)容或元件性質(zhì)不一樣，但拓撲圖是一樣的，也就是說列出的KCL,KVL方程是一樣的。即i1=i2 +i3u1=u2 +u3u2 =u3這說明網(wǎng)絡(luò)的圖只與

8、連接結(jié)構(gòu)有關(guān)，而與支路元件性質(zhì)無關(guān)。網(wǎng)絡(luò)圖中所用的幾個名詞：(1)   支路：每個元件用一條線段表示，每條線段就是一個支路。也可以將電壓源與電阻串聯(lián)，電流源與電阻并聯(lián)，作為一條復合支路，即也用一條線段表示。(2)   節(jié)點：線段的端點叫節(jié)點。(3)   圖：線段與點的集合即為網(wǎng)絡(luò)的圖。(4)   有向圖:對圖中的支路電流指定出參考方向，即為有向圖。(5)   連通圖:圖中任意兩點間至少有一條路徑。就叫連通圖。(6)   非連通圖:從一點到另一點無路徑可走就叫非連通圖。(7)&

9、#160;  子圖:若圖G1的每個節(jié)點和支路也是圖G的節(jié)點和某些支路，則稱圖G1是圖G的一個子圖。在圖的定義中節(jié)點和支路各自是一個整體，因此，允許有孤立節(jié)點存在。所以有時會說把一條支路移去，但這并不意味著同時把它所連接的節(jié)點也移去；反之，如果把一個節(jié)點移去，則應(yīng)當把它連接的全部支路同時移去。(8)   自環(huán):圖中一條支路連接于一個節(jié)點，就叫自環(huán)。(9)   關(guān)連:任一支路恰好連接在二個節(jié)點上，稱此支路與這二個節(jié)點彼此關(guān)聯(lián)。 2、回路、樹、割集1、回路-有圖的支路所構(gòu)成的閉合路徑叫回路，但任一回路中的每個節(jié)點所關(guān)聯(lián)的支路樹應(yīng)當是2。2、

10、樹-滿足三點構(gòu)成樹：1）包含圖的全部節(jié)點；2）不包含回路；3）連通的。樹的支路叫樹支，其余的支路叫連支。3、割集-割集的定義如下：對一個連通圖切割一組支路應(yīng)滿足拿掉這組支路后（保留節(jié)點），原來的圖分成兩部分，如果少拿掉任意一條支路，圖仍然是連通的，則稱這組支路為割集。如下面連通圖所示，在上面畫一個閉合面（高斯面）如虛線所示，3，4，6支路就是一組割集。   3、關(guān)聯(lián)，回路、割集矩陣的概念和求法（1）、           關(guān)聯(lián)矩陣A關(guān)聯(lián)矩陣A表示圖G中節(jié)點與支路的關(guān)

11、聯(lián)關(guān)系，它可以根據(jù)網(wǎng)絡(luò)的有向圖直接寫出。設(shè)有向圖的節(jié)點數(shù)為n 支路數(shù)為b，并且把全部節(jié)點和支路分別編號。關(guān)聯(lián)矩陣A可用一個的矩陣來描述。它的行對應(yīng)于節(jié)點，它的列對應(yīng)于支路，它的每一元素 定義如下：        對于同一網(wǎng)絡(luò)，由于選擇不同的參考節(jié)點，可以得到不同的關(guān)聯(lián)矩陣A，但公式Ai=0總是成立的。              （a）     &#

12、160;                          (b) 例： (b)的關(guān)聯(lián)矩陣A解  圖(b) 的關(guān)聯(lián)矩陣A      A=  （2）、回路矩陣B基本回路    樹包含圖的全部節(jié)點，不包含回路，可見對任意一個樹，每加一 個連支便

13、形成一個回路。由這個單連支構(gòu)成的回路就是基本回路，而且這組基本回路又是獨立的，因為每一個其它回路包含了一條其它回路所沒有的支路。基本回路是單連支回路，但獨立回路并不一定是基本回路。 基本回路矩陣B表示圖G中回路與支路的關(guān)聯(lián)關(guān)系，它可以根據(jù)網(wǎng)絡(luò)的有向圖直接寫出。如果回路中包含某一支路，則稱此回路與支路有關(guān)聯(lián)，其基本回路數(shù)就是連支數(shù)。將圖中的回路和支路分別編號，基本回路矩陣B 可用一個的矩陣來表示。它的行對應(yīng)回路，它的列對應(yīng)支路，它的每一元素定義如下：    例：列寫上圖(a)的回路矩陣B ，以3、4、5為樹支，則1、2、6是連支，單連支回路為基本

14、回路，方向與連支同方向。   B=（3）、割集矩陣Q基本割集   單樹支割集就是基本割集。其基本割集個數(shù)就是樹支個數(shù)。正如獨立回路不一定是基本回路一樣，獨立割集也不一定是基本割集。因此說基本割集是獨立割集，但獨立割集不一定是基本割集。 基本割集矩陣表示圖G割集與支路的關(guān)聯(lián)關(guān)系，它也可以根據(jù)網(wǎng)絡(luò)的有向圖直接寫出，基本割集數(shù)就是樹支數(shù)，將圖中的割集和支路分別編號，基本割集矩陣可用一個的矩陣來表示。它的行對應(yīng)割集，列對應(yīng)支路，的任一元素定義如下：    關(guān)聯(lián)矩陣A， 回路矩陣B， 割集矩陣Q之間的關(guān)系如果前面講的三種矩陣

15、A，B和Q都是屬于同一個拓撲圖，而且支路編號及選樹 都一樣，可以得到下列幾個主要的關(guān)系式ABT = 0   BQT = 0BAT = 0   QBT = 0 五、應(yīng)用圖論進行集成電路布局的設(shè)計 當前集成電路產(chǎn)業(yè)向深亞微米工藏不斷摧進，正力圖突破45nm甚至15nm大關(guān)?，F(xiàn)有EDA工具難以應(yīng)付復雜度呈指數(shù)增長的諸多VLSI電路設(shè)計難題，也缺乏對深亞微米工藝下一系列新問題的考慮。另一方面，在計算智能領(lǐng)域，各種優(yōu)化技術(shù)日新月異，為解決非NP和NP復雜度的大規(guī)模、超大規(guī)模問題展示了廣闊的前景。研究通道布線和單元上通道布線在深亞微米工藝下VLSI生產(chǎn)工序

16、中關(guān)鍵環(huán)節(jié)物理設(shè)計中的應(yīng)用。 隨著VLSI電路的工藝向深亞微米的推進，由于問題規(guī)模的急劇增大，電路物理設(shè)計中的布線問題，都迫切需要更有效的優(yōu)化算法解決方案。 同時，由于近年來IC工藝的發(fā)展，使得其速度越來越高。由此可見，國IC芯片構(gòu)成的電予系統(tǒng)是朝著大規(guī)模、小體積、高速度的方向飛速發(fā)展的，而且發(fā)震速度越來越快。在縮小電子系統(tǒng)體積的同時，保持并提高系統(tǒng)的速度與性能成為擺程設(shè)計者面前的一個重要課題。集成電路設(shè)計流程集成電路設(shè)計的流程一般先要進行軟硬件劃分，將設(shè)計基本分為兩部分：芯片硬件設(shè)計和軟件協(xié)同設(shè)計。芯片硬件設(shè)計包括：1功能設(shè)計階段。 設(shè)計人員產(chǎn)品的應(yīng)用場合，設(shè)定一些諸如功能、操作速度、接口規(guī)

17、格、環(huán)境溫度及消耗功率等規(guī)格，以做為將來電路設(shè)計時的依據(jù)。更可進一步規(guī)劃軟件模塊及硬件模塊該如何劃分，哪些功能該整合于SOC 內(nèi)，哪些功能可以設(shè)計在電路板上。2設(shè)計描述和行為級驗證 功能設(shè)計完成后，可以依據(jù)功能將SOC 劃分為若干功能模塊，并決定實現(xiàn)這些功能將要使用的IP 核。此階段將接影響了SOC 內(nèi)部的架構(gòu)及各模塊間互動的訊號，及未來產(chǎn)品的可靠性。決定模塊之后，可以用VHDL 或Verilog 等硬件描述語言實現(xiàn)各模塊的設(shè)計。接著，利用VHDL 或Verilog 的電路仿真器，對設(shè)計進行功能驗證（function simulation，或行為驗證 behavioral simulation

18、）。3邏輯綜合確定設(shè)計描述正確后，可以使用邏輯綜合工具（synthesizer）進行綜合。綜合過程中，需要選擇適當?shù)倪壿嬈骷欤╨ogic cell library），作為合成邏輯電路時的參考依據(jù)。硬件語言設(shè)計描述文件的編寫風格是決定綜合工具執(zhí)行效率的一個重要因素。事實上，綜合工具支持的HDL 語法均是有限的，一些過于抽象的語法只適于作為系統(tǒng)評估時的仿真模型，而不能被綜合工具接受。邏輯綜合得到門級網(wǎng)表。4門級驗證門級功能驗證是寄存器傳輸級驗證。主要的工作是要確認經(jīng)綜合后的電路是否符合功能需求，該工作一般利用門電路級驗證工具完成。布局和布線 布局指將設(shè)計好的功能模塊合理地安排在芯片上，規(guī)劃好它們

19、的位置。布線則指完成各模塊之間互連的連線。注意，各模塊之間的連線通常比較長，因此，產(chǎn)生的延遲會嚴重影響SOC的性能，尤其在0.25 微米制程以上，這種現(xiàn)象更為顯著。 目前，這一個行業(yè)仍然是中國的空缺，開設(shè)集成電路設(shè)計與集成系統(tǒng)專業(yè)的大學還比較少，越來越有趨勢走上當年軟件行業(yè)的道路。六、圖論在電路分析中的應(yīng)用-節(jié)點電壓方程的矩陣形式 1、支路電壓和節(jié)點電壓的關(guān)系  在大多數(shù)網(wǎng)絡(luò)中，例如電力系統(tǒng)的潮流計算，電子線路分析等等，其獨立節(jié)點樹往往少于獨立回路樹，因此，節(jié)點電壓分析法是目前計算機輔助分析和設(shè)計中被廣泛應(yīng)用的一種方法。  用關(guān)聯(lián)矩陣A表示的KVL的矩陣

20、形式為： u=ATun  上式就是支路電壓u和節(jié)點電壓un之間的關(guān)系，它說明電路中各支路電壓可以用與該支路關(guān)聯(lián)的兩個節(jié)點電壓來表示，這是節(jié)點分析法的基本思想。 2、典型支路的分析 網(wǎng)絡(luò)是由數(shù)條支路聯(lián)接而成的，為使編寫網(wǎng)絡(luò)方程式系統(tǒng)化，需要先將支路規(guī)范化。為此，先定義典型支路（也叫標準支路），因為它能代表各種可能的情況或其特例。 典型支路的聯(lián)接及參考方向如下圖所示。圖中采用了向量法。并不是說電路中每條支路都必須符合這種規(guī)定，可以允許一條支路缺少某些元件。如果實際支路無電壓源時，則將 用短路代替，無電流源時，則將 以開路代替。若采用運算法，獨立源中還可能包含由初始條件

21、引起的附加電源。  節(jié)電電壓方程的矩陣形式典型支路的分析對于第條典型支路可以列出下列方程可以導出 令                          則          如果網(wǎng)絡(luò)中有條支路，每一支路用列向量表示，即于是，對整個電路有所有支路電流的矩陣形式為 而支路電壓的矩陣形式為 式中是支