DocumentCode
890217
Title
Computing the Stopping Distance of a Tanner Graph Is NP-Hard
Author
Krishnan, Karunakaran Murali ; Shankar, Priti
Author_Institution
Indian Inst. of Sci., Bangalore
Volume
53
Issue
6
fYear
2007
fDate
6/1/2007 12:00:00 AM
Firstpage
2278
Lastpage
2280
Abstract
Two decision problems related to the computation f stopping sets in Tanner graphs are shown to be NP-complete. It follows as a consequence that there exists no polynomial time algorithm for computing the stopping distance of a Tanner graph unless P = NP.
Keywords
decoding; parity check codes; NP-hardness; Tanner graph; decision problems; decoding; low-density parity-check codes; polynomial time algorithm; stopping distance; Automation; Computer science; Iterative algorithms; Iterative decoding; Linear code; NP-complete problem; Parity check codes; Performance analysis; Polynomials; Research and development; Low-density parity-check (LDPC) codes; NP-hardness; Tanner graph; stopping distance;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.2007.896864
Filename
4215144
Link To Document