 cyclic binary codes used for the algorithm is O(n)5 if exactly [n - Vn(k - 1) - 1] error detection. Given a generator polynomial g(x) = errors occurred and only O(n³) otherwise. The algorithm -, gi E {0, 1} of degree r, the codeword for of Berlekamp [7] is a hard-decision decoding algorithm, a binary information sequence u = ,Uk) is the which does not exploit all available information at the receiver when the demodulator allows soft decisions. concatenation u * p of u and the word p of length r associated to the polynomial p(x) = x'u(x)mod g(x). Efficient soft-decision decoding algorithms for Reed- Here we use the unique correspondence between a word Solomon codes were proposed by Koetter and Vardy [28] W = (u1, um) of length m and the polynomial w(x) = and Jiang and Narayanan [26]. For example, the algo- WI + W2X + ... + wmxm-1 of degree at most m - 1. rithm of Jiang and Narayanan [26] outperforms Suppose that the codeword u * p is sent over a binary hard-decision decoding by up to 3.1 dB at decoding error symmetric channel and let u' * p' be the received word. probability 10-5 when decoding a (15, Reed-Solomon Here u' and p' are words having the same length as u and code over a binary-input AWGN channel. p, respectively. Then the decoder computes P"(x) = "u'(x) mod g(x) and declares an error if p"(x) is not 3.4.3.1.3 LDPC codes equal to p'(x). Some of the most popular generator polynomials are the CRC-12 polynomial 1 +x+x2++ LDPC codes were introduced by Gallager [21]. They +x 11 + x 12, the CRC-16 polynomial 1 have attracted increased interest since MacKay and Neal and the CRC-CCITT polynomial 1 + [34,35] reported their outstanding performance on CRC code with generator polynomial a binary-input AWGN channel. An (n, k) LDPC code is g(x) = can detect any burst a linear code with a sparse parity-check matrix H = (hij). error of length k Agarwal and Ivanov [2] provided an It can also be described with a bipartite graph, called O(nm2r-m) algorithm for computing the probability of Tanner graph, whose set of nodes 