s, each encoding symbol can be generated from k information symbols in O(log k) Check nodes time on average, and one can recover all k information symbols from k + O(Vk10g2(k/8)) encoding symbols with Variable nodes probability 1 - in O(k log k) time, on average. By concatenating an LDPC code as an outer code and Figure 3.4-3 Tanner graph of a regular LDPC code of length 8. The degree of the variable nodes is du = 2, and the degree of the an LT code as an inner code, Shokrollahi [47] was able to check nodes is do = 4. construct rateless codes called Raptor codes whose era- sure correcting performance is similar to that of LT codes, but can be encoded and decoded in only O(k) time. where it is shown in particular that some of the best LDPC codes can be encoded in O(n) time with high probability. Because of the sparseness of their Tanner 3.4.3.1.7 Lattice codes graph, LDPC codes can be decoded in ((n) time with an Codes over finite fields can also be interpreted as codes iterative procedure known as probabilistic decoding [21], over real numbers by mapping each element of the finite message passing, sum-product algorithm [49], or belief field to a real number. For example, in the binary (3, 1) propagation [37]. These algorithms alternately pass repetition code, the binary digit 0 can be mapped to the information between adjacent variable nodes and check real value -a and the binary digit 1 can be mapped to the nodes to compute estimates of the a posteriori real value +a SO that the two codewords are (-a, -a, -a) probabilities of the codeword symbols. The decoded code- and (+a, +a, +a). Minimum distance decoding then word is based on the estimates obtained after convergence means decoding the received vector to the codeword that or if a maximum number of iterations is reached. Chung is closest in Euclidean distance. In this section, we will et al. [14] were able to design a rate-1 irregular LDPC consider a class of codes called lattice codes, which con- code of length 107 bits that is only 0.04 dB away from the tain