# Video over DSL with LDGM Codes for Interactive Applications
## 3 Methodology
### Packetization with LDGM  
Section 2 analyzed LDPC and its cousin channel code LDGM in terms of matrix operations. Instead advantage can be taken of the sparseness of the matrices to reduce the computational complexity. This is achievable by exploiting an alternative representation of the codes in a Tanner graph, a type of bi-partite graph. The same representation is the basis of the iterative belief propagation decoding algorithm mentioned in Section 1. A Tanner graph connects code nodes, \(c_{i}\), and check nodes, \(y_{i}\). The code nodes comprise the information data together with the parity or redundant data. The check nodes describe how the input data are XORed together but they are not output as part of the coded data stream. Figure 1 shows an example of a bi-partite Tanner graph by way of explanation. Lines connecting the information data code nodes to the check nodes indicate how the data are XORed together. (Notice that XORing corresponds to modulo 2 addition.) The summation forms the output to the \(n-k\) parity code nodes. Reiterating, in an LDGM code (unlike some other codes), the parity code nodes are each derived from just one check node. The Tanner graph only indicates how the data symbols are combined. For example, if each symbol is a fixed-size data block it is the data blocks that are bitwise XORed together according to the pattern given in Figure 1 and, in general, with whatever pattern is indicated by matrix \(H\) (as matrix \(H\) is used as a generator matrix in LDGM). It should also be remarked that for LDGM codes if random generation of the \"1s\" in \(H\), subject to the constraint of (7) results in a cycle of four, this cycle is removed by rearranging the matrix. Cycles of four occur when two data nodes are connected to the same two check nodes in the Tanner graph representation. The reason for this rearrangement is that cycles of four are known to result in weaker decoding performance.  
Thus, in LDGM codes, a recovery packet is generated for each row of \(H\), as the result of applying bitwise XOR operations to the data packets corresponding to the entries equal to \"1\" in \(H\), as described by Figure 1. The process to do this at the data-packet level is shown in Figure 2. Equally, each row of \(H\) indicates which data packets are combined to form a FEC packet. Each row provides recovery for just one packet. Thus, if any one packet indicated by the presence of a \"1\" in the row is lost it can be recovered by bitwise XORing with the remaining packets together with the corresponding FEC packet. If more than one packet in a row is lost in an error burst then it is no longer possible to recover a packet using that row alone. This property can also be deduced from the equations in Figure 1. However, if more than one packet in a row has been lost it is possible to replace one or more of those packets by first using the recovery properties of other rows. Nevertheless, the recovery becomes problematic if error bursts occur, because then more rows face the loss of more than one packet. The longer the error burst the more likely that a number of rows within sparse \(H\) could be affected. This issue is returned to in Section 3.2.  
To take advantage of the possibility of allowing the information data to by-pass decoding if no errors are detected, the information and parity data can be separated into two streams. The three main steps of the protection scheme are illustrated in Figure 3: (i) division of data into blocks of low \(k\), (ii) encoding of each block of \(k\) information data packets, and (iii) the outcome of the coding for each block of \(k\) data packets then forms a set of \(n-k\) packets.  
Figure 1: Example Low-Density Generator Matrix (LDGM) bipartite graph.  
Figure 2: Forward Error Correction (FEC) generation. Protection operation for a block of \(k\) information data packets.