Motivated by the design of high speed switching fabrics, in this thesis we propose a bit-stuffing algorithm for generating forbidden transition codes that avoid opposite transitions on any two adjacent wires in order to mitigate the crosstalk effect between adjacent wires in long on-chip buses. We first model a bus under the constraint that there are no opposite transitions on any two adjacent wires of the bus as a forbidden transition channel, and derive the Shannon capacity of such a channel which serves as the fundamental limit on the coding rate of any forbidden transition code. Then we perform a worst-case analysis and a probabilistic analysis for the bit-stuffing algorithm. We show by both theoretic analysis and simulations that the coding rate of the bit-stuffing encoding scheme for independent and identically distributed (i.i.d.) Bernoulli input data traffic is quite close to the Shannon capacity, and hence is much better than those of the existing forbidden transition codes in the literature, including the Fibonacci representation. Furthermore, we extend the bit-stuffing encoding scheme for generating forbidden overlap codes that avoid the two transition patterns“010→101”and“101→010”on any three adjacent wires. Finally, we derive energy consumption analyses for several bus encoding schemes, including the bit-stuffing encoding scheme, the bus-invert coding scheme, and forbidden pattern codes, based on a bus energy consumption model for deep submicron technology. Our analyses show that the bit-stuffing encoding scheme also achieves good energy efficiency.

因應高速交換核心的設計需求，在這篇論文中我們提出一個位元填充演算法用以產生一個禁制轉變碼 (forbidden transition codes)，將資料在晶片內高速匯流排中傳送前編碼，以減低資料傳送時鄰近導線之間的串擾效應 (crosstalk effect)。禁制轉變碼乃藉由避免相鄰兩條導線同時產生相反方向的信號轉變，進而達到減低串擾的效果。在相鄰兩條導線不可出現相反方向的信號轉變的限制條件之下，我們首先將高速匯流排轉化為一個禁制轉變通道模型，並推導出其Shannon通道容量，而該通道容量即為所有可能的禁制轉變碼的編碼率之理論最佳值。接著我們針對所提出的位元填充演算法進行最壞情況 (worst-case) 分析及機率分析。透過理論分析及模擬結果，我們證明位元填充編碼架構對於獨立且同分佈的伯努利輸入資料，其編碼率相當接近Shannon通道容量，同時也遠超過文獻中的其他禁制轉變碼之編碼架構，包括費伯納西表示法 (Fibonacci representation)。此外，我們將位元填充編碼架構延伸並用於產生禁制重疊碼 (forbidden overlap codes)，藉由避免相鄰三條導線產生010→101及101→010的信號轉變，進而達到減低串擾的效果。最後，我們基於一個考慮深次微米製程的匯流排能量消耗模型，針對幾種匯流排編碼架構進行能量消耗分析，其中包括位元填充編碼架構、匯流排反相 (bus-invert) 編碼架構、及禁制樣型碼 (forbidden pattern codes)。透過理論分析，我們證明位元填充編碼架構從能量消耗的觀點來看也具有良好的效率。

中文摘要 i
致謝辭 iii
Abstract v
Contents vii
List of Figures xi
List of Tables xiii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . 1
1.2 Contributions and Outline of the Thesis . . . . . . 3
2 Forbidden Transition Codes 7
2.1 Forbidden Transition Channels . . . . . . . . . . . 7
2.2 The Bit-Stuffing Algorithm . . . . . . . . . . . . 10
2.2.1 Worst-Case Analysis . . . . . . . . . . . . . . . 14
2.2.2 Probabilistic Analysis . . . . . . . . . . . . . 16
2.2.3 An Approximate Probabilistic Analysis . . . . . . 22
3 Forbidden Overlap Codes 25
3.1 Forbidden Overlap Channels . . . . . . . . . . . . 25
3.2 The Bit-Stuffing Algorithm . . . . . . . . . . . . 27
3.2.1 Worst Case Analysis . . . . . . . . . . . . . . . 30
3.2.2 Probabilistic Analysis . . . . . . . . . . . . . 36
3.2.3 Approximate Probabilistic Analysis . . . . . . . 43
4 Energy Consumption Analysis 47
4.1 Uncoded Scheme . . . . . . . . . . . . . . . . . . 49
4.2 Bit-Stuffing Encoding Scheme . . . . . . . . . . . 50
4.3 Bus-Invert Coding Scheme . . . . . . . . . . . . . 55
4.4 Forbidden Pattern Codes . . . . . . . . . . . . . . 60
5 Conclusion 69
Appendix A Proofs of Lemmas and Theorems in Chapter 2 73
A.1 Proof of Lemma 2 . . . . . . . . . . . . . . . . . 73
A.2 Proof of Lemma 8 . . . . . . . . . . . . . . . . . 74
A.3 Proof of Lemma 9 . . . . . . . . . . . . . . . . . 75
A.4 Proof of Theorem 10 . . . . . . . . . . . . . . . . 77
A.5 Proof of Theorem 11 . . . . . . . . . . . . . . . . 78
Appendix B Proofs of Lemmas and Theorems in Chapter 3 81
B.1 Proof of Lemma 12 . . . . . . . . . . . . . . . . . 81
B.2 Proof of Lemma 17 . . . . . . . . . . . . . . . . . 84
B.3 Proof of Lemma 18 . . . . . . . . . . . . . . . . . 86
B.4 Proof of Theorem 19 . . . . . . . . . . . . . . . . 88
B.5 Proof of Theorem 20 . . . . . . . . . . . . . . . . 90
Appendix C Proofs of Lemmas and Theorems in Chapter 4 97
C.1 Proof of Theorem 23 . . . . . . . . . . . . . . . . 97
C.2 Proof of Lemma 26 . . . . . . . . . . . . . . . . . 101
C.3 Proof of Theorem 27 . . . . . . . . . . . . . . . . 102
Bibliography 113

[1] International Technology Roadmap for Semiconductors, 2003, Semiconductor Industry Association. [Online]. Available: http://www.itrs.net/Links/2003ITRS/Home2003.htm

[2] International Technology Roadmap for Semiconductors, 2005, Semiconductor Industry Association. [Online]. Available: http://www.itrs.net/Links/2005ITRS/ExecSum2005.pdf

[3] B. Victor,“Bus encoding to prevent crosstalk delay,”M. S. Thesis, University of California, Berkeley, CA, USA, 2001.

[4] P. P. Sotiriadis,“Interconnect modeling and optimization in deep submicron technologies,”Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 2002.

[5] S. R. Sridhara,“Communication inspired design of on-chip buses,”Ph.D. Dissertation, University of Illinois, Urbana, IL, USA, 2006.

[6] J. D. Z. Ma and L. He,“Formulae and applications of interconnect estimation considering shield insertion and net ordering,”in Proceedings IEEE/ACM International Conference on Computer-Aided Design (ICCAD'01), San Jose, CA, USA, November 4-8, 2001, pp. 327-332.

[7] B. Victor and K. Keutzer,“Bus encoding to prevent crosstalk delay,”in Proceedings IEEE/ACM International Conference on Computer-Aided Design (ICCAD'01), San Jose, CA, USA, November 4-8, 2001, pp. 57-63.

[8] C. Duan, A. Tirumala, and S. P. Khatri,“Analysis and avoidance of cross-talk in on-chip buses,”in Proceedings IEEE Annual Symposium on High Performance Interconnects (HOTI'01), Stanford, CA, USA, August 22-24, 2001, pp. 133-138.

[9] C. Duan and S. P. Khatri,“Exploiting crosstalk to speed up on-chip buses,”in Proceedings Conference and Exhibition on Design, Automation, and Test in Europe (DATE'04), Paris, France, February 16-20, 2004, vol. 2, pp. 778-783.

[10] M. Mutyam,“Preventing crosstalk delay using Fibonacci representation,”in Proceedings International Conference on VLSI Design (VLSID'04), Mumbai, India, January 5-9, 2004, pp. 685-688.

[11] S. R. Sridhara, A. Ahmed, and N. R. Shanbhag,“Area and energy-efficient crosstalk avoidance codes for on-chip buses,”in Proceedings IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'04), San Jose, CA, USA, October 11-13, 2004, pp. 12-17.

[12] S. R. Sridhara and N. R. Shanbhag,“Coding for system-on-chip networks: a unified framework,”IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 13, pp. 655-667, June 2005.

[13] C. Duan, K. Gulati, and S. P. Khatri,“Memory-based crosstalk canceling CODECs for on-chip buses,”in Proceedings IEEE International Symposium on Circuits and Systems (ISCAS'06), Island of Kos, Greece, May 21-24, 2006, pp. 1119-1122.

[14] S. R. Sridhara and N. R. Shanbhag,“Coding for reliable on-chip buses: a class of fundamental bounds and practical codes,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, pp. 977-982, May 2007.

[15] C. Duan, C. Zhu, and S. P. Khatri,“Forbidden transition free crosstalk avoidance CODEC design,”in Proceedings 45th Annual Design Automation Conference (DAC'08), Anaheim, CA, USA, June 8-13, 2008, pp. 986-991.

[16] X.Wu, Z. Yan, and Y. Xie,“Two-dimensional crosstalk avoidance codes,”in Proceedings IEEE Workshop on Signal Processing Systems (SiPS'08), Washington, D. C., USA, October 8-10, 2008, pp. 106-111.

[17] C. Duan, V. H. C. Calle, and S. P. Khatri,“Efficient on-chip crosstalk avoidance CODEC design,”IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, pp. 551-560, April 2009.

[18] X. Wu and Z. Yan,“Efficient CODEC designs for crosstalk avoidance codes based on numeral systems,”IEEE Transactions on Very Large Scale Integration (VLSI) Systems, to appear.

[19] W.-A. Kuo, Y.-L. Chiang, T.-T. Hwang, and A. C.-H. Wu,“Performance-driven crosstalk elimination at postcompiler level—the case of low-crosstalk op-code assignment,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, pp. 564-573, March 2007.

[20] W.-W. Hsieh, P.-Y. Chen, C.-Y. Wang, and T.-T. Hwang,“A bus-encoding scheme for crosstalk elimination in high-performance processor design,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, pp. 2222-2227, December 2007.

[21] B. E. Moision, A. Orlitsky, and P. H. Siegel,“On codes that avoid specified differences,”IEEE Transactions on Information Theory, vol. 47, pp. 433-442, January 2001.

[22] L. L. Peterson and B. S. Davie, Computer Networks: A Systems Approach, 4th edition, San Francisco, CA: Morgan Kaufmann Publishers, 2007.

[23] S. Halevy, J. Chen, R. M. Roth, P. H. Siegel, and J. K. Wolf,“Improved bit-stuffing bounds on two-dimensional constraints,”IEEE Transactions on Information Theory, vol. 50, pp. 824-838, May 2004.

[24] C. E. Shannon,“A mathematical theory of communication,”Bell System Technical Journal , vol. 27, pp. 379-423 (Part I), 623-656 (Part II), July, October 1948.

[25] T. M. Cover and J. A. Thomas, Elements of Information Theory, New York, NY: John Wiley & Sons, 1991.

[26] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge, UK: Cambridge University Press, 1985.

[27] S. I. Resnick, Adventures in Stochastic Processes, Boston, MA: Birkha¨user, 1992.

[28] R. J. Fletcher,“Integrated circuit having outputs configured for reduced state changes,”U.S. Patent 4,667,337, May 1987.

[29] M. R. Stan and W. P. Burleson,“Bus-invert coding for low-power I/O,”IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 3, pp. 49-58, March 1995.

[30] R.-B. Lin and C.-M. Tsai,“Theoretical analysis of bus-invert coding,”IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 10, pp. 929-935, December
2002.

[31] T. M. Apostol, Mathematical Analysis, 2nd Edition, Addison-Wesley Publishing Company, 1974.

[32] M. Fekete,“Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten,”Mathematische Zeitschrift, vol. 17, pp. 228-249, 1923.