近幾年來積體電路技術快速的發展，在進入深次微米製程之後，電路的體積隨著技術不斷的進步愈做愈小，工作速度也愈來愈快。更多數位電路和類比電路被整合進單一晶片中。當電路工作於低電壓系統，晶片對於雜訊變得非常靈敏。
串音效應是兩條平行線間的耦合電容所產生的，在進入深次微米製程後已成為連接線訊號延遲主要的來源。耦合效應會影響訊號轉移的速度，進而造成晶片功能錯誤。在本篇論文中，我們提出一個時序導向的通道繞線演算法來降低串音問題。我們的方法與其他方法相比較，主要是考慮了所有訊號不同的訊號到達時間，因此可較準確的估算串音效應對訊號所造成的實際時間延遲，做為最佳化之成本函數。本演算法已使用c++語言來實現，並驗證在不同的測試電路。實驗結果顯示，我們的方法可以有效且快速的降低了實際會發生之串音效應。

The wire-to-wire spacing in a VLSI chip becomes closer as the VLSI fabrication technology rapidly evolves in current years. With VLSI design entering the deep sub-micron, the feature sizes continues to decrease and the operating frequency more and more highly. Many of digital and analog circuits were integrated into single chip. When the circuits work at low-voltage system, the chip becomes very sensitivity for noise.
The crosstalk effects are between coupling capacitance of two parallel wires that becomes the main source of signal delay. The coupling effect can affect speed of signal transition, then the crosstalk can make fault function of chip. In this thesis, we will propose a timing driven gridded channel routing algorithms for the minimization of crosstalk problem. Compared with previous works, the main distinction of our approach is that it considers the signal arrival time. So that we can precisely estimate the actual delay degradation caused by crosstalk effect. This algorithm was implemented in C++ programming language and run on different benchmark circuits. Experimental data consistently shows that our approach is effective and efficient for crosstalk minimization.

中文摘要1
Abstract2
第一章導論4
1-1研究背景………………………………………………………..4
1-2研究動機和目的………………………………………………..6
1-3論文架構與流程………………………………………………..11
第二章問題描述與定義12
2-1問題描述………………………………………………………..12
2-2名詞解釋……………………………………………………….13
2-3串音效應分析………………………………………………….14
2-4相關視窗方法（ＲＷＭ）………………………………………17
第三章繞線演算法26
3-1軌道重排方法…………………………….…………………….26
3-2區段連接線重排方法…………………….……………….…28
3-3Dogleg　繞線方法……………………..……………………..31
第四章串音模型和分析33
4-1電路模型model建立和分析…………………………….……33
4-2Delay Degradation和耦合長度的關係...……………………35
第五章時序導向繞線演算法39
5-1時序導向繞線成本函式(cost function)………………………39
5-2區段連接線交換演算法………….……………………………40
5-3Dogleg的演算法……………………………………………….42
5-4時序導向繞線演算法………………………………………….43
第六章實驗結果與結論49
6-1實驗結果………………………………………………………..49
6-2結論與未來展望…………………………..……………………51
參考資料……………….…………………………………………………52
附件一……………………………………………………………………..56

[1] H. H. Chen and C. K. Wong, “Wiring and Crosstalk Avoidance in Multi-Chip Module Design”, in the Proc. of Custom Integrated Circuits Conference, pp. 28.6.1-28.6.4, 1992.[2] W. M. Dai, R. Kong, J. Jue, and M. Sato, “Rubber Band Routing and Dynamic Data Representation”, in the Proc. of IEEE International Conference on Computer-Aided Design, pp. 52-55, 1990.[3] T. Gao and C. L. Liu, “Minimum Crosstalk Channel Routing”, in the Proc. of IEEE International Conference on Computer-Aided Design, pp. 692-696, 1993.[4] K. S. Jhang, S. Ha, and C. S. Jhon, “A segment Rearrangement Approach to Channel Routing under the Crosstalk Constraints”, in the Proc. of IEEE Asia-Pacific Conference on Circuits and Systems, pp. 536-541, Dec 1994.[5] K. S. Jhang, S. Ha, and C. S. Jhon, “COP: A Crosstalk Optimizer for Gridded Channel Routing”, in IEEE Trans. on Computer-Aided Design, vol. 15, no. 4, pp. 424-429, April 1996.[6] J.D Cho and M.S. Chang, “LEXA: A Left-Edge based Crosstalk-Minimum k-color Permutation in VHV Channels”, in the Proc. of IEEE International Symposium on Circuits and Systems, vol.3, pp. 1740-1707, 1997.[7] K.C. Hsu, Y.C. Lin, P.X. Chiu, and T.M. Hsieh, “Minimum Crosstalk Channel Routing with Dogleg”, in the Proc. of International Symposium on Circuits and Systems, pp. 73-76, vol. 3, 2000.[8] C.H. Lee, C.M. Chung, W.Y. Fu and T.M. Hsieh. “Channel Routing Crosstalk Minimization”, in the Chung Yuan Journal, pp. 103-109, Vol. 29, No.1, 2001.[9] Y. Sasaki and G. De Micheli, “Crosstalk Delay Analysis using Relative Window Method”, in the Proc. International ASIC/SOC Conference, pp. 9-13, 1999.[10] Y. Sasaki and K.Yano, “Multi-aggressor Relative Window Method for Timing Analysis including Crosstalk Delay Degradation”, in the Proc. of Custom Integrated Circuits Conference, pp. 496-498, 2000.[11] Y. Sasaki and K. Yano, “Building a Crosstalk Library for Relative Window Methods - Timing Analysis that Includes Crosstalk Delay Degradation”, in the Proc. of the Second IEEE Asia Pacific ASIC Conference, pp. 371-374, 2000.[12] D. Sylvester and C. Wu, “Analytical modeling and characterization of deep sub-micron interconnect”, Proceedings of the IEEE, Vol. 89, Issue: 5, pp. 634-664, May 2001. [13] D. H. Cho Y. S. Eo, M. Seung, N. H. kim, J. w. Wee, O.K. kwon, and H. S. Park, “Interconnect Capacitance, Crosstalk, and Signal Delay for 0.35um CMOS Technology, “ in IEDM Tech. Dig., PP.616-622.[14] Yamashita, K.; Odanaka, S.,” Impact of crosstalk on delay time and a hierarchy of interconnects” Electron Devices Meeting, 1998. IEDM '98 Technical Digest International 1998, PP 291 -294.[15] M.Burstein and R. Pelavin, “Hierarchical channel router,” Integration VLSI., Vol. 1,PP 21-38 1983.[16] J.S. Cherng, S.J.Chen and J.M. Ho” Crosstalk Minimization in river Routing,” The 8th VLSI Design/CAD Symposium, 1997, 265-268.[17] H. H. Chen and E. S. Kuh, “Glitter: A gridless variable width channel router,” IEEE Trans. Computer Aided Design, Vol. CAD-5, PP. 4590465, 1986.[18] T.T Ho, S. S. Iyengar, and S. Q. Zheng, “A general greedy Channel Routing, “ IEEE Trans. Computer Aided Design, Vol. 15, No. 4,PP. 424-429, April 1996.[19] S. Kipartick, C.D. Gelatt Jr. and M. p. Vecchi, “ Optimization by Simulated-Annealing,” Science, Vol220, 1983, PP671-680.[20] A set by Chung Yuan Journal No3. Vol.29[21] T.Gao and C. L. Liu, “ Minimum Crosstalk Switch-box Routing,” IEEE/ACM International Conference on Computer Aided Design, 1994, PP. 610-615.[22] T. Yoshimura and E.S. Kuh, “Efficient algorithm for channel routing”, IEEE Trans. On CAD of IC and Systems, Vol. CAD-1, No. 1, Jan. 1982.[23] A. Onozawa, K. Chaudhary and E.S. Kuh, Performance Driver Spacing Algorithm Using Attractive and Repulsive Constraints for Submicron LSI’s IEEE Trans. Computer Aided Design, Jun. 1995, Vol. 14, No. 6, PP. 707-719.[24] Deutsch, D. N., “Dogleg channel router,” Proc. 13th Design Automation Conf. ,IEEE, 1976, PP. 425-433.[25] Thomas G. Szymanski, “ Dogleg channel routing is NP-COMPLETE,” IEEE Trans. On CAD, vol. CAD-4, no. l, Jan. 1985, PP.41-40.[26] A. Sangiovanni-Vincentelli, M. Santomauro et al., “ A new gridless channel router: Yet another channel router (YACR-II), “ Proc. Int. Conf. Computer Aided Design, 1984, PP. 72-77.