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
fDate :
6/1/2007 12:00:00 AM
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;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2007.896864
