A modified sum-product algorithm over graphs with isolated short cycles

Nithin Raveendran; Shayan Garani Srinivasa

doi:10.1109/ISIT.2014.6875308

A modified sum-product algorithm over graphs with isolated short cycles

Nithin Raveendran
, Shayan Garani Srinivasa

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

We investigate into the limitations of the sumproduct algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).

Original language	English (US)
Title of host publication	2014 IEEE International Symposium on Information Theory, ISIT 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2619-2623
Number of pages	5
ISBN (Print)	9781479951864, 9781479951864
DOIs	https://doi.org/10.1109/ISIT.2014.6875308
State	Published - 2014
Externally published	Yes
Event	2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States Duration: Jun 29 2014 → Jul 4 2014

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095
ISSN (Electronic)	2157-8117

Other

Other	2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/Territory	United States
City	Honolulu, HI
Period	6/29/14 → 7/4/14

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2014.6875308

Cite this

Raveendran, N., & Srinivasa, S. G. (2014). A modified sum-product algorithm over graphs with isolated short cycles. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 2619-2623). Article 6875308 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875308

A modified sum-product algorithm over graphs with isolated short cycles. / Raveendran, Nithin; Srinivasa, Shayan Garani.
2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 2619-2623 6875308 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Raveendran, N & Srinivasa, SG 2014, A modified sum-product algorithm over graphs with isolated short cycles. in 2014 IEEE International Symposium on Information Theory, ISIT 2014., 6875308, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 2619-2623, 2014 IEEE International Symposium on Information Theory, ISIT 2014, Honolulu, HI, United States, 6/29/14. https://doi.org/10.1109/ISIT.2014.6875308

@inproceedings{6ce9bc4d65384ffabcbaeec7dd5ae162,

title = "A modified sum-product algorithm over graphs with isolated short cycles",

abstract = "We investigate into the limitations of the sumproduct algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).",

author = "Nithin Raveendran and Srinivasa, \{Shayan Garani\}",

year = "2014",

doi = "10.1109/ISIT.2014.6875308",

language = "English (US)",

isbn = "9781479951864",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2619--2623",

booktitle = "2014 IEEE International Symposium on Information Theory, ISIT 2014",

note = "2014 IEEE International Symposium on Information Theory, ISIT 2014 ; Conference date: 29-06-2014 Through 04-07-2014",

}

TY - GEN

T1 - A modified sum-product algorithm over graphs with isolated short cycles

AU - Raveendran, Nithin

AU - Srinivasa, Shayan Garani

PY - 2014

Y1 - 2014

N2 - We investigate into the limitations of the sumproduct algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).

AB - We investigate into the limitations of the sumproduct algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).

UR - https://www.scopus.com/pages/publications/84906544524

UR - https://www.scopus.com/pages/publications/84906544524#tab=citedBy

U2 - 10.1109/ISIT.2014.6875308

DO - 10.1109/ISIT.2014.6875308

M3 - Conference contribution

AN - SCOPUS:84906544524

SN - 9781479951864

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2619

EP - 2623

BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014

Y2 - 29 June 2014 through 4 July 2014

ER -

A modified sum-product algorithm over graphs with isolated short cycles

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this