Re: Question to working group regarding LDPC Draft

All,

There hasn't been any object to alteration of the LDPC document as 
described below ... but there hasn't been _any_ response!

If there are no objections by the end of this week (2 May 2008), we 
will honor the authors' request for this change and help accommodate 
as quick as publication process as possible.

best regards,



At 9:37 AM -0400 4/17/08, Brian Adamson wrote:
>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]>


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