Bounds on asymptotic rate of capacitive crosstalk avoidance codes for on-chip buses

摘要

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