Question to working group regarding LDPC Draft

During the publication process of the LDPC FEC Scheme document, one 
of the author's brought to attention a technique to dramatically 
improve the erasure decoding performance of the subject codes (the 
LDPC staircase and triangle codes).

For application of this technique to the LDPC Staircase code (that 
has lower encoding/decoding computational complexity), a modification 
to the parity check matrix is needed to realize its full benefits.

Therefore, the authors have proposed a modification to the document, 
including a change to the format of the FEC OTI for the LDPC codes, 
to support this.

The publication process of this document has been halted pending a 
decision based on Working Group concensus as to whether this change 
is acceptable.  The authors feel this is a worthwhile modification

So, the question to the RMT Working Group is a query as to whether 
there is objection to this change.  The change will slightly delay 
the publication process here, but we will work to make it continue as 
quickly as possible.


Below is the authors' description of the change and rationale 
including a link to a paper that describes the performance benefits:

>** Motivations:
>
>Any LDPC decoder needs to solve a system of linear equations.
>Several techniques are possible, among which the iterative algorithm sketched
>in the I-D, a Gaussian elimination, or anything else. Some of them favor the
>decoding time at the price of a certain sub-optimality in terms of erasure
>recovery capabilities (e.g., iterative decoding), and vice-versa (e.g.,
>Gaussian elimination).
>
>We recently implemented and carried out performance evaluation of a hybrid
>iterative decoding/Gaussian elimination scheme [1] and found that
>LDPC-triangle codes can be made almost ideal, while keeping a reasonable
>decoding time (it's significantly faster than Reed-Solomon codes) for
>medium-sized objects.
>
>We recently discovered that by increasing the density of "1s" in the left
>side of the parity check matrix, similar improvements can be achieved with
>LDPC-staircase codes [2] (e.g., they are less than 1% away than ideal codes).
>
>
>** Proposal:
>
>We'd like to carry an additional parameter in the Scheme-Specific Elements
>of the FEC Object Transmission Information: the target column density of the
>left submatrix:
>
>- the default recommended value remains 3 (value which is currently hard-coded
>   in the I-D). It is optimal for both LDPC variants when using an iterative
>   decoding, and it remains almost optimal with LDPC-triangle codes featuring
>   a Gaussian elimination.
>
>- for a specific use-case, when it is recommended to use LDPC-staircase and
>   a Gaussian elimination, a higher value could be used (current tests suggest
>   values between 4 to 8, depending on the code rate).
>
>For practical reasons (3 bits left only), we do not carry the target column
>density but this value minus 3.
>
>
>** Details of the modifications:
>
>3.2.  Notations
>     N1 denotes the target number of "1s" per column in the left side of
>     the parity check matrix (Section 6.2)
>
>     N1m3 denotes the value N1 - 3, where N1 is the target number of "1s"
>     per column in the left side of the parity check matrix
>
>4.2.3.  Scheme-Specific Elements
>    o  G: an integer between 1 (default) and 31 inclusive indicating the number
>       of encoding symbols per group (i.e., per packet). [...]
>
>==> we need to restrict the G value since it is now encoded in a 5-bit field.
>
>
>    o  N1m3: an integer between 0 (default) and 7, inclusive. The number
>       of "1s" per column, N1, is equal to N1m3 + 3. Using N1m3 equal to
>       0 is recommended when the sender has no information on the decoding
>       scheme used by the receivers. A value greater than 0 for N1m3 can
>       be a good choice in specific situations, e.g., when using
>       LDPC-staircase codes with a Gaussian elimination decoding scheme.
>       Nevertheless, the current document does not mandate any specific
>       value. This choice is left to the codec developer.
>
>
>4.2.4.1.  Using the General EXT_FTI Format
>
>==> New EXT_FTI:
>
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |   Encoding Symbol Length (E)  | N1m3|    G    |   B (MSB)     |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>
>
>4.2.4.2.  Using the FDT Instance (FLUTE-Specific)
>
>==> New Scheme-Specific Information:
>
>     0                   1                   2                   3
>     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |                        PRNG seed                              |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    | N1m3|    G    |
>    +-+-+-+-+-+-+-+-+
>
>
>6.2.  Parity Check Matrix Creation
>
>==> In this section we replace all references to "3 "1s" per column"
>by N1 "1s" per column, both in the comments and in left_matrix_init()
>and add the N1 parameter to this function prototype.
>
>
>
>NB: We need to cross-check the whole document carefully, but I believe that
>modifications are restricted to the above sections.
>
>
>** Practically speaking:
>
>This change does not impact the interoperability of LDPC decoders using
>different types of decoding algorithms.
>
>The current value of 3 remains the recommended, general purpose value.
>Detailed recommendations on when to use a value greater than 3 will be
>made in separate documents (we are working on it).
>
>This modification is only meaningful with LDPC-Staircase codes. The current
>situation is already adequate to LDPC-Triangle codes, no matter the type of
>decoding algorithm used.
>
>The current LDPC-staircase and triangle reference codec already features
>this parameter (called leftDegree in the InitSession prototype):
>         ldpc_error_status InitSession  (int     nbSourceSymbols,
>                                         int     nbParitySymbols,
>                                         int     symbolSize,
>                                         int     flags = FLAG_BOTH,
>                                         int     seed = 1,
>                                         SessionType     codecType = 
>TypeTRIANGLE,
>                                         int     leftDegree = 3);
>
>
>** References :
>
>[1] M. Cunche, V. Roca,
>``Improving the Decoding of LDPC Codes for the Packet Erasure Channel with
>a Hybrid Zyablov Iterative Decoding/Gaussian Eliminiation Scheme'',
>INRIA Research Report RR-6473, March 2008.
>http://planete.inrialpes.fr/people/roca/doc/RR-6473.pdf
>
>
>[2] M. Cunche, V. Roca,
>`Optimizing the error recovering capabilities of LDPC-Staircase codes
>featuring a Gaussian elimination decoding scheme'',
><document almost finalized, to be published very soon...>
>



-- 
Brian
__________________________________
Brian Adamson
<mailto:[email protected]>