# Video over DSL with LDGM Codes for Interactive Applications
## 2 Channel Codes
### LDPC Codes  
LDPC codes are linear block codes [18] characterized by parameters \(k\), and \(n\), which correspond to the number of bits (assuming for the moment a bit-sized symbol) of an information and code vector respectively. Therefore, the number of redundant bits is \(n-k\). The rate of such a code is represented by \(r=k/n\), _i.e._, \(r\) is inversely proportional to the number of redundant symbols added. In order to output a code vector \(\mathbf{c}\) from an information vector \(u\) a generator matrix \(G\) is required:  
\[\mathbf{c}=\mathbf{u}G \tag{1}\]  
Notice that a code vector includes both input data symbols and additional parity symbols. In turn, \(G\) is created from a parity-check matrix \(H\), which is involved in decoding when a transmission error has occurred. As the code's name implies, matrix \(H\) is a sparse matrix with a low density of \"1s\" and all other entries set to zero. In general, the entries of \(H\) are filled randomly. \(H\) provides \(n-k\) parity check equations that create constraints between data symbols and parity symbols. These constraints indicate which data symbols are involved in Exclusive OR (XOR) operations to form the parity symbols. Notice that, in LDPC, data symbols contribute indirectly to the creation of the parity symbols because the constraints can be combined in an XOR operation to form a parity symbol. To create \(G\) from \(H\), \(H\) is first re-arranged in an appropriate form such that the output will be systematic. (A systematic code is one in which the information symbols are separated from the parity symbols, allowing the information symbols to be extracted without decoding if no errors are detected.) Thus, \(H\) is represented as:  
\[H=[P^{T}\mid I_{n-k}] \tag{2}\]  
where \(P\) is a matrix of dimensions \(k\times(n-k)\) and \(I_{n-k}\) is the identity matrix of dimensions \((n-k)\times(n-k)\). \(G\) is then created as:  
\[G=[I_{k}\left|P\right| \tag{3}\]  
Though the \"1s\" in the \(H\) matrix are randomly generated, the number of \"1s\" in each row and each column is principally kept constant to reduce legal complexity, as mentioned in Section 1. Such an LDPC (and its lower-complexity cousin LDGM) \(H\) matrix is called regular under that constraint. For example, in a regular \(H\) matrix with three \"1s\" in each column, each code symbol is involved in three constraint equations. Each row represents a constraint equation. Thus, with four \"1s\" in a row,three data symbols are combined with a parity symbol. The constraint is then that all four symbols when XORed together will give a value of zero, hence the name parity check for matrix \(H\). Thus, two parameters can be defined: \(w_{c}\), the number of \"1s\" in each column; and \(w_{r}\), the number of \"1s\" in each row. For \(H\) also to be sparse requires \(w_{c}\ll(n-k)\) and \(w_{r}\ll k\). Then for a regular LDPC matrix:  
\[n.w_{c}\,=(n-k).w_{r} \tag{4}\]  
Although LDPC codes are not a Maximum-Distance Separable (MDS) code, implying that they do not offer the optimal recovery capability for a block code, they have a lower decoding computational burden compared to RS codes, owing to: the use of XOR operations to generate the redundancy when encoding; and the low density of the parity-check matrix, which results in a low number of decoding operations. To put matrix \(H\) in the form given by equation (2) the Gauss-Jordan elimination algorithm can be used. That algorithm, in general, has complexity of order \((n-k)^{3}\). Depending on circumstances, the creation of matrix \(G\) from \(H\) can be performed offline. However, resulting matrix \(G\) in general is not sparse, owing to the Gauss-Jordan elimination process applied, resulting in an encoding complexity of order \((n-k)^{2}\), with \(n\) around 1000 in large block coding. It is possible to rearrange matrix \(H\) into an approximately lower-triangle form [19] so that it retains its sparseness, even after Gauss-Jordan elimination, because only some of the sub-matrices are affected.