For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2018/12/01
Online ISSN: 1745-1337
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>>
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.