Bounds on the Asymptotic Rate for Capacitive Crosstalk Avoidance Codes for On-Chip Buses

Tadashi WADAYAMA  Taisuke IZUMI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.12   pp.2018-2025
Publication Date: 2018/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.2018
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding theory and techniques
crosstalk avoidance codes,  constraint coding,  domatic partition,  

Full Text: PDF>>
Buy this Article

Several types of capacitive crosstalk avoidance codes have been devised in order to prevent capacitive crosstalk in on-chip buses. These codes are designed to prohibit transition patterns prone to capacitive crosstalk from any two consecutive words transmitted to on-chip buses. The present paper provides a rigorous analysis of the asymptotic rate for (p,q)-transition free word sequences under the assumption that coding is based on a stateful encoder and a stateless decoder. Here, p and q represent k-bit transition patterns that should not appear in any two consecutive words at the same adjacent k-bit positions. The maximum rate for the sequences is proven to be equal to the subgraph domatic number of the (p,q)-transition free graph. Based on the theoretical results for the subgraph domatic partition problem, lower and upper bounds on the asymptotic rate are derived. We also show that the asymptotic rate 0.8325 is achievable for p=01 and q=10 transition free word sequences.