LDPC decoders with missing connections

Linjia Chang, Avhishek Chatterjee, Lav R Varshney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible under miswiring, but we find suitably defined decoding thresholds for communication systems with binary erasure channels and peeling decoders, as well as binary symmetric channels and Gallager A decoders. We see that decoding is robust to missing connections, as decoding thresholds degrade smoothly.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1576-1580
Number of pages5
ISBN (Electronic)9781509018062
DOIs
StatePublished - Aug 10 2016
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2016-August
ISSN (Print)2157-8095

Other

Other2016 IEEE International Symposium on Information Theory, ISIT 2016
CountrySpain
CityBarcelona
Period7/10/167/15/16

Fingerprint

Decoding
Binary
Process Variation
Peeling
Message passing
Error Probability
Message Passing
Information Processing
Convergence Theorem
Communication Systems
Performance Analysis
Timing
Communication systems
Chip
Manufacturing
Hardware
Networks (circuits)
Communication
Error probability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this

Chang, L., Chatterjee, A., & Varshney, L. R. (2016). LDPC decoders with missing connections. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 1576-1580). [7541564] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541564

LDPC decoders with missing connections. / Chang, Linjia; Chatterjee, Avhishek; Varshney, Lav R.

Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 1576-1580 7541564 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chang, L, Chatterjee, A & Varshney, LR 2016, LDPC decoders with missing connections. in Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory., 7541564, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 1576-1580, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541564
Chang L, Chatterjee A, Varshney LR. LDPC decoders with missing connections. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc. 2016. p. 1576-1580. 7541564. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2016.7541564
Chang, Linjia ; Chatterjee, Avhishek ; Varshney, Lav R. / LDPC decoders with missing connections. Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 1576-1580 (IEEE International Symposium on Information Theory - Proceedings).
@inproceedings{5080606dc4f64f44a6240a1e6d3ec590,
title = "LDPC decoders with missing connections",
abstract = "Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible under miswiring, but we find suitably defined decoding thresholds for communication systems with binary erasure channels and peeling decoders, as well as binary symmetric channels and Gallager A decoders. We see that decoding is robust to missing connections, as decoding thresholds degrade smoothly.",
author = "Linjia Chang and Avhishek Chatterjee and Varshney, {Lav R}",
year = "2016",
month = "8",
day = "10",
doi = "10.1109/ISIT.2016.7541564",
language = "English (US)",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1576--1580",
booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",
address = "United States",

}

TY - GEN

T1 - LDPC decoders with missing connections

AU - Chang, Linjia

AU - Chatterjee, Avhishek

AU - Varshney, Lav R

PY - 2016/8/10

Y1 - 2016/8/10

N2 - Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible under miswiring, but we find suitably defined decoding thresholds for communication systems with binary erasure channels and peeling decoders, as well as binary symmetric channels and Gallager A decoders. We see that decoding is robust to missing connections, as decoding thresholds degrade smoothly.

AB - Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible under miswiring, but we find suitably defined decoding thresholds for communication systems with binary erasure channels and peeling decoders, as well as binary symmetric channels and Gallager A decoders. We see that decoding is robust to missing connections, as decoding thresholds degrade smoothly.

UR - http://www.scopus.com/inward/record.url?scp=84985945937&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985945937&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541564

DO - 10.1109/ISIT.2016.7541564

M3 - Conference contribution

AN - SCOPUS:84985945937

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1576

EP - 1580

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

ER -