# Video over DSL with LDGM Codes for Interactive Applications
## 2 Channel Codes
### LDGM Codes  
A simplified version of LDPC codes is represented by LDGM codes, for which the parity-check matrix \(H\) corresponds to the generator matrix \(G\)[13], _i.e._, \(H\) is employed directly in encoding. In the LDGM approach, the parity-check matrix \(H\) has a size of \((n-k)\times k\), compared to the LDPC case in Section 2.1 of \((n-k)\times n\). An identity matrix of size \((n-k)\times(n-k)\) augments \(H\) in order to associate each parity symbol with a set of data symbols identified by \(H\). Thus, augmented \(H\), \(H^{\prime}\), has the form:  
\[H^{\prime}=[H|\ I_{n-k}] \tag{5}\]  
It is interesting to compare the LDGM codes with the Staircase codes of [20] for fast encoding. Though in [20] these are called LPDC codes, they are in fact also a type of LDGM code, as the first \(k\) data symbols are combined through \(H\). However, rather than augment \(H\) with an identity matrix, \(H\) is augmented with a diagonal matrix, \(P_{D}\), with just two \"1s\" in each row (except for just one \"1\" in the first row) and size \((n-k)\times(n-k)\). The form of \(P_{D}\), which is of a descending staircase of \"1s\" from the viewer's left to right, gives rise to the name \"Staircase\". The form of the Staircase code matrix \(H\)s is:  
\[H_{s}\,=[H|\,P_{D}] \tag{6}\]  
The Staircase code can be used in an iterative fashion to create the parity symbols. The author of [20] points out that this Staircase code has linear encoding complexity if account is taken of the sparseness of \(H\). Thus, it is that LDGM codes also have linear encoding complexity. A regular LDGM code, as used in this paper, is constrained by:  
\[k.w_{c}=(n-k).w_{r} \tag{7}\]  
When encoding with \(H\), only the first \(k\) symbols contribute to encoding, compared to the LDPC case, for which \(n\) symbols have to be processed. The disadvantage of this arrangement is that parity symbols are only protected by one subset of data symbols, implying that the error-correction capability is reduced. LDGM codes have several potential advantages despite the reduction in recovery performance: as the encoding complexity is lower than LDPC codes and decoding is similarly of low complexity, _i.e.,_ the decoding algorithms are the same, they are suited to encoding/decoding on a variety of battery-powered mobile devices; and low values of \(k\) imply that for real-time video applications such as telemedicine or video conferencing, the latency budget is considerably reduced.  
There is a downside: LDGM codes have high error floors that cannot necessarily be reduced by increasing the block size. (When, after application of FEC, the bit error rate ceases to reduce with decreased Signal-to-Noise Ratio (SNR), an error floor is said to exist.) However, at least for a binary symmetric channel (BSC) it is has been analytically demonstrated [21] that concatenating two LDGM codes (applying one LDGM code after another) overcomes the onset of an error floor, while retaining LDGM's computational complexity, provided a belief-propagation (message-passing) decoding algorithm is employed. Later work [22] confirmed the findings of [21] for a Rayleigh channel and provides analysis on how best to configure LDGM codes.  
In this paper, we simulate an erasure channel, which is not necessarily open to analysis in the way a BSC is but nevertheless occurs in practice after PHY-layer error recovery fails to recover a packet. An erasure channel is distinguished by the property that the positions of corrupted symbols are known in advance, sometimes because an upper-layer protocol records the packet sequence numbers. Though a concatenated LDGM code was not used in the experiments of Section 4, video quality was still found to be good. The LDGM improvement in Section 3.2 is not intended as a remedy to high error floors, though it does improve the coding efficiency. However, as with Raptor codes [12], which already use concatenated codes, the effect of introducing concatenation is expected to be simply a linear increase in coding complexity.