Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes
RFC 5170

Network Working Group                                            V. Roca
Request for Comments: 5170                                         INRIA
Category: Standards Track                                     C. Neumann
                                                                 Thomson
                                                              D. Furodet
                                                      STMicroelectronics
                                                               June 2008

         Low Density Parity Check (LDPC) Staircase and Triangle
                 Forward Error Correction (FEC) Schemes

Status of This Memo

   This document specifies an Internet standards track protocol for the
   Internet community, and requests discussion and suggestions for
   improvements.  Please refer to the current edition of the "Internet
   Official Protocol Standards" (STD 1) for the standardization state
   and status of this protocol.  Distribution of this memo is unlimited.

Abstract

   This document describes two Fully-Specified Forward Error Correction
   (FEC) Schemes, Low Density Parity Check (LDPC) Staircase and LDPC
   Triangle, and their application to the reliable delivery of data
   objects on the packet erasure channel (i.e., a communication path
   where packets are either received without any corruption or discarded
   during transmission).  These systematic FEC codes belong to the well-
   known class of "Low Density Parity Check" codes, and are large block
   FEC codes in the sense of RFC 3453.

Roca, et al.                Standards Track                     [Page 1]
RFC 5170            LDPC Staircase and Triangle FEC            June 2008

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  3
   3.  Definitions, Notations, and Abbreviations  . . . . . . . . . .  3
     3.1.  Definitions  . . . . . . . . . . . . . . . . . . . . . . .  3
     3.2.  Notations  . . . . . . . . . . . . . . . . . . . . . . . .  4
     3.3.  Abbreviations  . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . . .  6
     4.1.  FEC Payload IDs  . . . . . . . . . . . . . . . . . . . . .  6
     4.2.  FEC Object Transmission Information  . . . . . . . . . . .  6
       4.2.1.  Mandatory Element  . . . . . . . . . . . . . . . . . .  6
       4.2.2.  Common Elements  . . . . . . . . . . . . . . . . . . .  6
       4.2.3.  Scheme-Specific Elements . . . . . . . . . . . . . . .  7
       4.2.4.  Encoding Format  . . . . . . . . . . . . . . . . . . .  8
   5.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . . .  9
     5.1.  General  . . . . . . . . . . . . . . . . . . . . . . . . .  9
     5.2.  Determining the Maximum Source Block Length (B)  . . . . . 11
     5.3.  Determining the Encoding Symbol Length (E) and Number
           of Encoding Symbols per Group (G)  . . . . . . . . . . . . 12
     5.4.  Determining the Maximum Number of Encoding Symbols
           Generated for Any Source Block (max_n) . . . . . . . . . . 13
     5.5.  Determining the Number of Encoding Symbols of a Block
           (n)  . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
     5.6.  Identifying the G Symbols of an Encoding Symbol Group  . . 14
     5.7.  Pseudo-Random Number Generator . . . . . . . . . . . . . . 17
   6.  Full Specification of the LDPC-Staircase Scheme  . . . . . . . 19
     6.1.  General  . . . . . . . . . . . . . . . . . . . . . . . . . 19
     6.2.  Parity Check Matrix Creation . . . . . . . . . . . . . . . 19
     6.3.  Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 21
     6.4.  Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 21
   7.  Full Specification of the LDPC-Triangle Scheme . . . . . . . . 22
     7.1.  General  . . . . . . . . . . . . . . . . . . . . . . . . . 22
     7.2.  Parity Check Matrix Creation . . . . . . . . . . . . . . . 22
     7.3.  Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 23
     7.4.  Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 24
     8.1.  Problem Statement  . . . . . . . . . . . . . . . . . . . . 24
     8.2.  Attacks Against the Data Flow  . . . . . . . . . . . . . . 24
       8.2.1.  Access to Confidential Objects . . . . . . . . . . . . 24
       8.2.2.  Content Corruption . . . . . . . . . . . . . . . . . . 25
     8.3.  Attacks Against the FEC Parameters . . . . . . . . . . . . 26
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 27
   10. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 27
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 27
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 27