Cheng-Shang Chang
Abstract
One of the main problems in deep submicron designs of high-speed buses is propagation delay due to the crosstalk effect. To alleviate the crosstalk effect, there are several types of crosstalk avoidance codes proposed in the literature. In this article, we analyze the coding rates of forbidden overlap codes (FOCs) that avoid “010 → 101” transition and “101 → 010” transition on any three adjacent wires in a bus. We first compute the maximum achievable coding rate of FOCs and the maximum coding rate of memoryless FOCs. Our numerical results show that there is a significant gap between the maximum coding rate of memoryless FOCs and the maximum achievable rate. We then analyze the coding rates of FOCs generated from the bit-stuffing algorithm. Our worst-case analysis yields a tight lower bound of the coding rate of the bit-stuffing algorithm. Under the assumption of Bernoulli inputs, we use a Markov chain model to compute the coding rate of a bus with n wires under the bit-stuffing algorithm. The main difficulty of solving such a Markov chain model is that the number of states grows exponentially with respect to the number of wires n. To tackle the problem of the curse of dimensionality, we derive an approximate analysis that leads to a recursive closed-form formula for the coding rate over the nth wire. Our approximations match extremely well with the numerical results from solving the original Markov chain for n ⩽ 10 and the simulation results for n ⩽ 3000. Our analysis of coding rates of FOCs could be helpful in understanding the trade-off between propagation delay and coding rate among various crosstalk avoidance codes in the literature. In comparison with the forbidden transition codes (FTCs) that have shorter propagation delay than that of FOCs, our numerical results show that the coding rates of FOCs are much higher than those of FTCs.
- C. Alexopoulos and A. Seila. 1996. Implementing the batch means method in simulation experiments. Proceedings of the 28th Conference on Winter Simulation. IEEE Computer Society. Google Scholar
Digital Library
- C.-S. Chang, J. Cheng, T.-K. Huang, X.-C. Huang, D.-S. Lee, and C.-Y. Chen. 2015. Bit-stuffing algorithms for crosstalk avoidance in high speed switching. IEEE Transactions on Computers, 22, 9, 2030--2033. Google ScholarDigital Library
- C.-S. Chang, J. Cheng, T.-K. Huang, and D.-S. Lee. 2014. Explicit constructions of memoryless crosstalk avoidance codes via C-transform. IEEE Transactions on Very Large Scale Integration (VLSI’14) Systems, 64, 12, 3404--3416.Google Scholar
- J. Cheng, C.-S. Chang, T.-H. Chao, D.-S. Lee, and C.-M. Lien. 2008. On constructions of optical queues with a limited number of recirculations. In Proceedings of IEEE INFOCOM.Google ScholarCross Ref
- C.-C. Chou, C.-S. Chang, D.-S. Lee, and J. Cheng. 2006. A necessary and sufficient condition for the construction of 2-to-1 optical FIFO multiplexers by a single crossbar switch and fiber delay lines. IEEE Transactions on Information Theory 52, 4519--4531. Google ScholarDigital Library
- T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons, New York, NY. Google ScholarDigital Library
- C. Duan, C. Zhu, and S. P. Khatri. 2008. Forbidden transition free crosstalk avoidance CODEC design. In Proceedings of the 45th Annual Design Automation Conference (DAC’08), Anaheim, CA, June 8--13, 986--991. Google ScholarDigital Library
- S. Halevy, J. Chen, R. M. Roth, P. H. Siegel, and J. K. Wolf. 2004. Improved bit-stuffing bounds on two-dimensional constraints. IEEE Transactions on Information Theory 50, 824--838. Google ScholarDigital Library
- R. A. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- International Technology Roadmap for Semiconductors. 2003. Semiconductor Industry Association. Retrieved April 8, 2016 from http://www.itrs.net/Links/2003ITRS/Home2003.htm.Google Scholar
- International Technology Roadmap for Semiconductors. 2005. Semiconductor Industry Association. Retrieved April 8, 2016 from http://www.itrs.net/Links/2005ITRS/ExecSum2005.pdf.Google Scholar
- J. D. Z. Ma and L. He. 2001. Formulae and applications of interconnect estimation considering shield insertion and net ordering. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’01). San Jose, CA, November 4--8, 327--332. Google ScholarDigital Library
- B. E. Moision, A. Orlitsky, and P. H. Siegel. 2001. On codes that avoid specified differences. IEEE Transactions on Information Theory 47, 433--442. Google ScholarDigital Library
- M. Mutyam. 2004. Preventing crosstalk delay using Fibonacci representation. In Proceedings of the International Conference on VLSI Design (VLSID’04). Mumbai, India, January 5--9, 685--688. Google ScholarDigital Library
- M. Mutyam. 2012. Fibonacci codes for crosstalk avoidance. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 20, 1899--1903. Google ScholarDigital Library
- R. Nelson. 1995. Probability, stochastic processes, and queueing theory: The mathematics of computer performance modeling. Springer Science and Business Media. Google ScholarDigital Library
- E. K. Orcutt and W. M. Marcellin. 1993. Redundant multitrack (d, k) codes. IEEE Transactions on Information Theory 39, 1744--1750. Google ScholarDigital Library
- C. E. Shannon. 1948. A mathematical theory of communication. Bell System Technical Journal 27, 379--423 (Part I), 623--656 (Part II).Google ScholarCross Ref
- P. P. Sotiriadis. 2002. Interconnect modeling and optimization in deep submicron technologies. Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, MA. Google ScholarDigital Library
- S. R. Sridhara. 2006. Communication inspired design of on-chip buses. Ph.D. Dissertation, University of Illinois, Urbana, IL.Google Scholar
- M. Stan and W. Burleson. 1994. Limited-weight codes for low power I/O. In Proceedings of the IEEE/ACM International Workshop Low Power Design. 209--214.Google Scholar
- B. Victor. 2001. Bus encoding to prevent crosstalk delay. Master’s Thesis. University of California, Berkeley, CA.Google Scholar
- B. Victor and K. Keutzer. 2001. Bus encoding to prevent crosstalk delay. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’01). San Jose, CA, November 4--8, 57--63. Google ScholarDigital Library
- W. Weeks and R. E. Blahut. 1998. The capacity and coding gain of certain checkerboard codes. IEEE Transactions on Information Theory 44, 1193--1203. Google ScholarDigital Library
- X. Wu and Z. Yan. 2011. Efficient CODEC designs for crosstalk avoidance codes based on numeral systems. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 548--558. Google ScholarDigital Library
- X. Wu, Z. Yan, and Y. Xie. 2008. Two-dimensional crosstalk avoidance codes. In Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS’08). Washington, DC, October 8--10, 106--111.Google Scholar
Index Terms
- Coding Rate Analysis of Forbidden Overlap Codes in High-Speed Buses
Recommendations
Rate-adaptive codes for distributed source coding
Special section: Distributed source codingSource coding with correlated decoder side information is considered. We impose the practical constraint that the encoder be unaware of even the statistical dependencies between source and side information. Two classes of rate-adaptive distributed ...
Finite-length rate-compatible LDPC codes: a novel puncturing scheme
In this paper, we study rate-compatible puncturing of finite-length low-density parity-check (LDPC) codes. We present a novel rate-compatible puncturing scheme that is easy to implement. Our scheme uses the idea that the degradation in performance is ...
Symbol-by-symbol MAP decoding algorithm for high-rate convolutional codes that use reciprocal dual codes
A symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes applying reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number ...
Comments