{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T05:55:06Z","timestamp":1759730106000,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T00:00:00Z","timestamp":1462838400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology (MOST), Taiwan","doi-asserted-by":"crossref","award":["102-2221-E-007-006-MY3, 103-2622-E-009-012, and 103-2218-E-007-022"],"award-info":[{"award-number":["102-2221-E-007-006-MY3, 103-2622-E-009-012, and 103-2218-E-007-022"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2016,6,7]]},"abstract":"<jats:p>\n            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 \u201c010 \u2192 101\u201d transition and \u201c101 \u2192 010\u201d 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\n            <jats:italic>memoryless<\/jats:italic>\n            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            <jats:italic>n<\/jats:italic>\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            <jats:italic>n<\/jats:italic>\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\n            <jats:italic>\n              n\n              <jats:sup>th<\/jats:sup>\n            <\/jats:italic>\n            wire. Our approximations match extremely well with the numerical results from solving the original Markov chain for\n            <jats:italic>n<\/jats:italic>\n            \u2a7d 10 and the simulation results for\n            <jats:italic>n<\/jats:italic>\n            \u2a7d 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.\n          <\/jats:p>","DOI":"10.1145\/2846091","type":"journal-article","created":{"date-parts":[[2016,5,21]],"date-time":"2016-05-21T22:27:38Z","timestamp":1463869658000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Coding Rate Analysis of Forbidden Overlap Codes in High-Speed Buses"],"prefix":"10.1145","volume":"1","author":[{"given":"Cheng-Shang","family":"Chang","sequence":"first","affiliation":[{"name":"National Tsing Hua University, Taiwan, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jay","family":"Cheng","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tien-Ke","family":"Huang","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Duan-Shin","family":"Lee","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng-Yu","family":"Chen","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/256562.256608"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2409862"},{"volume-title":"Explicit constructions of memoryless crosstalk avoidance codes via C-transform","author":"Chang C.-S.","key":"e_1_2_1_3_1","unstructured":"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\u201914) Systems , 64, 12, 3404--3416. 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\u201914) Systems, 64, 12, 3404--3416."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.116"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881712"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons New York NY.   T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons New York NY.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391717"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.826633"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press Cambridge UK.   R. A. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511810817"},{"volume-title":"Semiconductor Industry Association. Retrieved","year":"2016","key":"e_1_2_1_10_1","unstructured":"International Technology Roadmap for Semiconductors. 2003. Semiconductor Industry Association. Retrieved April 8, 2016 from http:\/\/www.itrs.net\/Links\/2003ITRS\/Home2003.htm. International Technology Roadmap for Semiconductors. 2003. Semiconductor Industry Association. Retrieved April 8, 2016 from http:\/\/www.itrs.net\/Links\/2003ITRS\/Home2003.htm."},{"volume-title":"Semiconductor Industry Association. Retrieved","year":"2016","key":"e_1_2_1_11_1","unstructured":"International Technology Roadmap for Semiconductors. 2005. Semiconductor Industry Association. Retrieved April 8, 2016 from http:\/\/www.itrs.net\/Links\/2005ITRS\/ExecSum2005.pdf. International Technology Roadmap for Semiconductors. 2005. Semiconductor Industry Association. Retrieved April 8, 2016 from http:\/\/www.itrs.net\/Links\/2005ITRS\/ExecSum2005.pdf."},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201901)","author":"Ma J. D. Z.","key":"e_1_2_1_12_1","unstructured":"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\u201901) . San Jose, CA, November 4--8, 327--332. 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\u201901). San Jose, CA, November 4--8, 327--332."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.904557"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/962758.963404"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2011.2162010"},{"volume-title":"Probability, stochastic processes, and queueing theory: The mathematics of computer performance modeling","author":"Nelson R.","key":"e_1_2_1_16_1","unstructured":"R. Nelson . 1995. Probability, stochastic processes, and queueing theory: The mathematics of computer performance modeling . Springer Science and Business Media . R. Nelson. 1995. Probability, stochastic processes, and queueing theory: The mathematics of computer performance modeling. Springer Science and Business Media."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.259669"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"volume-title":"Proceedings of the IEEE\/ACM International Workshop Low Power Design. 209--214","author":"Stan M.","key":"e_1_2_1_21_1","unstructured":"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 . 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."},{"volume-title":"Bus encoding to prevent crosstalk delay. Master\u2019s Thesis","author":"Victor B.","key":"e_1_2_1_22_1","unstructured":"B. Victor . 2001. Bus encoding to prevent crosstalk delay. Master\u2019s Thesis . University of California , Berkeley, CA . B. Victor. 2001. Bus encoding to prevent crosstalk delay. Master\u2019s Thesis. University of California, Berkeley, CA."},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201901)","author":"Victor B.","key":"e_1_2_1_23_1","unstructured":"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\u201901) . San Jose, CA, November 4--8, 57--63. 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\u201901). San Jose, CA, November 4--8, 57--63."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.669282"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2009.2038389"},{"volume-title":"Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS\u201908)","author":"Wu X.","key":"e_1_2_1_26_1","unstructured":"X. Wu , Z. Yan , and Y. Xie . 2008. Two-dimensional crosstalk avoidance codes . In Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS\u201908) . Washington, DC, October 8--10, 106--111. X. Wu, Z. Yan, and Y. Xie. 2008. Two-dimensional crosstalk avoidance codes. In Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS\u201908). Washington, DC, October 8--10, 106--111."}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2846091","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2846091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:25Z","timestamp":1750225705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2846091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6,7]]}},"alternative-id":["10.1145\/2846091"],"URL":"https:\/\/doi.org\/10.1145\/2846091","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2016,5,10]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}