Re: Question to working group regarding LDPC Draft

Dear all,

Here is the new LDPC document that includes the modifications
suggested in a previous email:
http://planete.inrialpes.fr/~roca/doc/rfc5170_VR.txt

And the associated diff:
http://planete.inrialpes.fr/~roca/doc/rfc5170_VR-from-preliminary.diff.html

Note that these modifications have been made W.R.T. the document
edited by the RFC Editor, not version -08.

When reviewing the document once again, we also identified a non
critical error, section 5.7 (pmms_rand() return value can be equal
to 0).

Regards,


   Vincent, on behalf of the authors


Brian Adamson wrote:
> 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]>
> 
>