盧信嘉臺灣大學：電子工程學研究所張詠舜Chang, Yung-ShuenYung-ShuenChang2007-11-272018-07-102007-11-272018-07-102007http://ntur.lib.ntu.edu.tw//handle/246246/57666本篇論文可以分為兩大部分。第一部份是有關於元件的萃取，此部份大量應用計算幾何，利用計算幾何並設計演算法來辨識電路元件。電路元件包含電容、電感、分岔與通道。第二部份為電路網路鏈結生成，此部份為設計一演算法，以期能將在多邊形中的電路資訊快速鏈結。可以經由萃取多邊形的點的資訊和邊的關係而生成子網路鏈結，並經由結合全部的子網路鏈結生成全域網路鏈結。此兩部分為佈局對電路圖檢查(Layout vs. schematic check, LVS)之前段作業。There are two parts in this thesis. The first part is about the component extraction, and this part applies a lot of computation geometry algorithms. We use computational geometry to design an algorithm to recognize components. Circuit components extracted include capacitors, inductors, forks and vias. The second part is about netlist generation. In this part, we designed an algorithm to link up all information of polygon effectively. The sub-netlist can be extracted by extracting the point information and the edge relation of polygons, and generate the full netlist. The two parts are the front-end of layout vs. schematic check (LVS).誌謝................................................i 摘要...............................................ii Abstract..........................................iii Table of Contents..................................iv List of Figures....................................vi Chapter 1 Introduction..............................1 1.1 Motivation and organization.....................1 1.2 Netlist Extraction for digital circuits.........2 1.3 Introduction of LTCC technology.................3 1.3.1 Advantages of LTCC technology.................5 1.3.2 Disadvantages of LTCC technology..............6 1.4 Basic forms of inductors and capacitors.........6 Chapter 2 Components extraction.....................7 2.1 Introduction....................................7 2.2 Define corners..................................8 2.3 Intersection test of segment and segment........9 2.4 Point inside a polygon.........................13 2.5 Kd-Tree........................................14 2.6 Entry type port and exit type port.............15 2.7 Pair double-concave corners....................18 2.8 Inductor Extraction............................20 2.8.1 Parallel coupled inductor extraction.........22 2.8.2 Direction of spiral inductor rotation........23 2.9 Pair single-concave corners....................24 2.10 Shape variation of capacitors and fork........25 2.10.1 One-port capacitor..........................26 2.10.2 Two-port capacitor..........................27 2.10.3 Multi-port capacitor and Stable shape.......29 2.11 Combine capacitors............................30 2.12 Extraction flow...............................34 Chapter 3 Netlist generation.......................36 3.1 Introduction...................................36 3.2 Boolean operation..............................36 3.2.1 Calculate intersections......................37 3.2.2 Split polygon................................39 3.2.3 Perform operation............................40 3.3 Via connection.................................41 3.4 Pair capacitors................................42 3.5 Edge tracing...................................45 3.6 Netlist generation.............................47 3.7 Exception......................................48 Chapter 4 Results..................................49 4.1 Introduction...................................49 4.2 5.25GHz band pass filter.......................49 4.3 3~5GHz band pass filter........................53 4.4 3GHz low pass filter...........................57 4.5 Single band filter.............................60 Chapter 5 Conclusion...............................64 Reference..........................................65 Appendix A.........................................66844781 bytesapplication/pdfen-US電容電感萃取佈局對電路圖檢查計算機幾何capacitorinductorextractionlayout vs. schematic checkLVScomputational geometrythesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57666/1/ntu-96-R94943154-1.pdf