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

Tadashi WADAYAMA; Taisuke IZUMI

doi:10.1587/transfun.E101.A.2018

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

Tadashi WADAYAMA, Taisuke IZUMI

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.12 pp.2018-2025

Publication Date: 2018/12/01

Publicized

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

Authors

Tadashi WADAYAMA
the Nagoya Institute of Technology
Taisuke IZUMI
the Nagoya Institute of Technology

Keyword

crosstalk avoidance codes, constraint coding, domatic partition

Cite this

Copy

Tadashi WADAYAMA, Taisuke IZUMI, "Bounds on the Asymptotic Rate for Capacitive Crosstalk Avoidance Codes for On-Chip Buses" in IEICE TRANSACTIONS on Fundamentals, vol. E101-A, no. 12, pp. 2018-2025, December 2018, doi: 10.1587/transfun.E101.A.2018.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.2018/_p

Copy

@ARTICLE{e101-a_12_2018,
author={Tadashi WADAYAMA, Taisuke IZUMI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Bounds on the Asymptotic Rate for Capacitive Crosstalk Avoidance Codes for On-Chip Buses},
year={2018},
volume={E101-A},
number={12},
pages={2018-2025},
abstract={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.},
keywords={},
doi={10.1587/transfun.E101.A.2018},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - Bounds on the Asymptotic Rate for Capacitive Crosstalk Avoidance Codes for On-Chip Buses
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2018
EP - 2025
AU - Tadashi WADAYAMA
AU - Taisuke IZUMI
PY - 2018
DO - 10.1587/transfun.E101.A.2018
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2018
AB - 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.
ER -