draft-ietf-rmt-bb-fec-ldpc-02.txt | draft-ietf-rmt-bb-fec-ldpc-03.txt | |||
---|---|---|---|---|

RMT V. Roca | RMT V. Roca | |||

Internet-Draft INRIA | Internet-Draft INRIA | |||

Expires: December 23, 2006 C. Neumann | Expires: January 19, 2007 C. Neumann | |||

Thomson Research | Thomson Research | |||

D. Furodet | D. Furodet | |||

STMicroelectronics | STMicroelectronics | |||

June 21, 2006 | July 18, 2006 | |||

Low Density Parity Check (LDPC) Staircase and Triangle Forward Error | Low Density Parity Check (LDPC) Staircase and Triangle Forward Error | |||

Correction (FEC) Schemes | Correction (FEC) Schemes | |||

draft-ietf-rmt-bb-fec-ldpc-02.txt | draft-ietf-rmt-bb-fec-ldpc-03.txt | |||

Status of this Memo | Status of this Memo | |||

By submitting this Internet-Draft, each author represents that any | By submitting this Internet-Draft, each author represents that any | |||

applicable patent or other IPR claims of which he or she is aware | applicable patent or other IPR claims of which he or she is aware | |||

have been or will be disclosed, and any of which he or she becomes | have been or will be disclosed, and any of which he or she becomes | |||

aware will be disclosed, in accordance with Section 6 of BCP 79. | aware will be disclosed, in accordance with Section 6 of BCP 79. | |||

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF), its areas, and its working groups. Note that | Task Force (IETF), its areas, and its working groups. Note that | |||

skipping to change at page 1, line 38 | skipping to change at page 1, line 38 | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

The list of current Internet-Drafts can be accessed at | The list of current Internet-Drafts can be accessed at | |||

http://www.ietf.org/ietf/1id-abstracts.txt. | http://www.ietf.org/ietf/1id-abstracts.txt. | |||

The list of Internet-Draft Shadow Directories can be accessed at | The list of Internet-Draft Shadow Directories can be accessed at | |||

http://www.ietf.org/shadow.html. | http://www.ietf.org/shadow.html. | |||

This Internet-Draft will expire on December 23, 2006. | This Internet-Draft will expire on January 19, 2007. | |||

Copyright Notice | Copyright Notice | |||

Copyright (C) The Internet Society (2006). | Copyright (C) The Internet Society (2006). | |||

Abstract | Abstract | |||

This document describes two Fully-Specified FEC Schemes, LDPC- | This document describes two Fully-Specified FEC Schemes, LDPC- | |||

Staircase and LDPC-Triangle, and their application to the reliable | Staircase and LDPC-Triangle, and their application to the reliable | |||

delivery of objects on packet erasure channels. These systematic FEC | delivery of objects on packet erasure channels. These systematic FEC | |||

skipping to change at page 2, line 18 | skipping to change at page 2, line 18 | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 | |||

2. Requirements notation . . . . . . . . . . . . . . . . . . . . 4 | 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 4 | |||

3. Definitions, Notations and Abbreviations . . . . . . . . . . . 5 | 3. Definitions, Notations and Abbreviations . . . . . . . . . . . 5 | |||

3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 | 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 5 | 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 6 | 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 6 | |||

4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 7 | 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 7 | |||

4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 7 | 4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 7 | |||

4.2. FEC Object Transmission Information . . . . . . . . . . . 7 | 4.2. FEC Object Transmission Information . . . . . . . . . . . 7 | |||

4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 7 | 4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 7 | |||

4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 7 | 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 7 | |||

4.2.3. Scheme-Specific Element . . . . . . . . . . . . . . . 8 | 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 8 | |||

4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 8 | 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 8 | |||

5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 11 | 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 11 | |||

5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 11 | 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 11 | |||

5.2. Determining the Maximum Source Block Length (B) . . . . . 12 | 5.2. Determining the Maximum Source Block Length (B) . . . . . 12 | |||

5.3. Determining the Encoding Symbol Length (E) and Number | 5.3. Determining the Encoding Symbol Length (E) and Number | |||

of Encoding Symbols per Group (G) . . . . . . . . . . . . 12 | of Encoding Symbols per Group (G) . . . . . . . . . . . . 12 | |||

5.4. Determining the Number of Encoding Symbols of a Block . . 13 | 5.4. Determining the Number of Encoding Symbols of a Block . . 13 | |||

5.5. Identifying the Symbols of an Encoding Symbol Group . . . 15 | 5.5. Identifying the Symbols of an Encoding Symbol Group . . . 15 | |||

5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 18 | 5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 18 | |||

6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 20 | 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 20 | |||

skipping to change at page 3, line 12 | skipping to change at page 3, line 12 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 33 | Intellectual Property and Copyright Statements . . . . . . . . . . 33 | |||

1. Introduction | 1. Introduction | |||

RFC 3453 [3] introduces large block FEC codes as an alternative to | RFC 3453 [3] introduces large block FEC codes as an alternative to | |||

small block FEC codes like Reed-Solomon. The main advantage of such | small block FEC codes like Reed-Solomon. The main advantage of such | |||

large block codes is the possibility to operate efficiently on source | large block codes is the possibility to operate efficiently on source | |||

blocks of size several tens of thousands (or more) source symbols. | blocks of size several tens of thousands (or more) source symbols. | |||

The present document introduces the Fully-Specified FEC Encoding ID | The present document introduces the Fully-Specified FEC Encoding ID | |||

XX that is intended to be used with the "Low Density Parity Check" | XX that is intended to be used with the LDPC-Staircase FEC codes, and | |||

(LDPC) Staircase FEC codes, and the Fully-Specified FEC Encoding ID | the Fully-Specified FEC Encoding ID YY that is intended to be used | |||

YY that is intended to be used with the "Low Density Parity Check" | with the LDPC-Triangle FEC codes [4][7]. Both schemes belong to the | |||

(LDPC)-Triangle FEC codes [4][7]. Both schemes belong the broad | broad class of large block codes. | |||

class of large block codes. | ||||

-- editor's note: This document makes use of the FEC Encoding ID | -- editor's note: This document makes use of the FEC Encoding ID | |||

values XX and YY that will be specified after IANA assignment -- | values XX and YY that will be specified after IANA assignment -- | |||

LDPC codes rely on a dedicated matrix, called a "Parity Check | LDPC codes rely on a dedicated matrix, called a "Parity Check | |||

Matrix", at the encoding and decoding ends. The parity check matrix | Matrix", at the encoding and decoding ends. The parity check matrix | |||

defines relationships (or constraints) between the various encoding | defines relationships (or constraints) between the various encoding | |||

symbols (i.e. source symbols and repair symbols), that are later used | symbols (i.e. source symbols and repair symbols), that are later used | |||

by the decoder to reconstruct the original k source symbols if some | by the decoder to reconstruct the original k source symbols if some | |||

of them are missing. These codes are systematic, in the sense that | of them are missing. These codes are systematic, in the sense that | |||

the encoding symbols include the source symbols in addition to the | the encoding symbols include the source symbols in addition to the | |||

repair symbols. | repair symbols. | |||

Since the encoder and decoder must operate on the same parity check | Since the encoder and decoder must operate on the same parity check | |||

matrix, information must be communicated between them as part of the | matrix, information must be communicated between them as part of the | |||

FEC Object Transmission information. | FEC Object Transmission Information. | |||

A publicly available reference implementation of these codes is | A publicly available reference implementation of these codes is | |||

available and distributed under a GNU/LGPL license [6]. | available and distributed under a GNU/LGPL license [6]. | |||

2. Requirements notation | 2. Requirements notation | |||

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | |||

document are to be interpreted as described in [1]. | document are to be interpreted as described in [1]. | |||

skipping to change at page 5, line 48 | skipping to change at page 5, line 48 | |||

be partitioned | be partitioned | |||

G denotes the number of encoding symbols per group, i.e. the | G denotes the number of encoding symbols per group, i.e. the | |||

number of symbols sent in the same packet | number of symbols sent in the same packet | |||

rate denotes the "code rate", i.e. the k/n ratio | rate denotes the "code rate", i.e. the k/n ratio | |||

max_n denotes the maximum number of encoding symbols generated for | max_n denotes the maximum number of encoding symbols generated for | |||

any source block | any source block | |||

H denotes the parity check matrix | ||||

srand(s) denotes the initialization function of the pseudo-random | srand(s) denotes the initialization function of the pseudo-random | |||

number generator, where s is the seed (s > 0) | number generator, where s is the seed (s > 0) | |||

rand(m) denotes a pseudo-random number generator that returns a | ||||

rand(m) denotes a pseudo-random number generator, that returns a | ||||

new random integer in [0; m-1] each time it is called | new random integer in [0; m-1] each time it is called | |||

3.3. Abbreviations | 3.3. Abbreviations | |||

This document uses the following abbreviations: | This document uses the following abbreviations: | |||

ESI: Encoding Symbol ID | ESI: Encoding Symbol ID | |||

FEC OTI: FEC Object Transmission Information | FEC OTI: FEC Object Transmission Information | |||

FPI: FEC Payload ID | ||||

LDPC: Low Density Parity Check | ||||

PRNG: Pseudo Random Number Generator | ||||

4. Formats and Codes | 4. Formats and Codes | |||

4.1. FEC Payload IDs | 4.1. FEC Payload IDs | |||

The FEC Payload ID is composed of the Source Block Number and the | The FEC Payload ID is composed of the Source Block Number and the | |||

Encoding Symbol ID: | Encoding Symbol ID: | |||

The Source Block Number (12 bit field) identifies from which | The Source Block Number (12 bit field) identifies from which | |||

source block of the object the encoding symbol(s) in the payload | source block of the object the encoding symbol(s) in the packet | |||

is(are) generated. There are a maximum of 2^^12 blocks per | payload is(are) generated. There are a maximum of 2^^12 blocks | |||

object. | per object. | |||

The Encoding Symbol ID (20 bit field) identifies which encoding | The Encoding Symbol ID (20 bit field) identifies which encoding | |||

symbol(s) generated from the source block is(are) carried in the | symbol(s) generated from the source block is(are) carried in the | |||

packet payload. There are a maximum of 2^^20 encoding symbols per | packet payload. There are a maximum of 2^^20 encoding symbols per | |||

block. The first k values (0 to k-1) identify source symbols, the | block. The first k values (0 to k-1) identify source symbols, the | |||

remaining n-k values (k to n-k-1) identify repair symbols. | remaining n-k values (k to n-k-1) identify repair symbols. | |||

There MUST be exactly one FEC Payload ID per packet. In case of en | There MUST be exactly one FEC Payload ID per packet. In case of an | |||

Encoding Symbol Group, when multiple encoding symbols are sent in the | Encoding Symbol Group, when multiple encoding symbols are sent in the | |||

same packet, the FEC Payload ID refers to the first symbol of the | same packet, the FEC Payload ID refers to the first symbol of the | |||

packet. The other symbols can be deduced from the ESI of the first | packet. The other symbols can be deduced from the ESI of the first | |||

symbol thanks to a dedicated function, as explained in Section 5.5 | symbol thanks to a dedicated function, as explained in Section 5.5 | |||

0 1 2 3 | 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 | 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 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Source Block Number | Encoding Symbol ID (20 bits) | | | Source Block Number | Encoding Symbol ID (20 bits) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 1: FEC Payload ID encoding format for FEC Encoding ID XX and | Figure 1: FEC Payload ID encoding format for FEC Encoding ID XX and | |||

YY | YY | |||

4.2. FEC Object Transmission Information | 4.2. FEC Object Transmission Information | |||

4.2.1. Mandatory Elements | 4.2.1. Mandatory Element | |||

o FEC Encoding ID: the Fully-Specified FEC Schemes described in this | o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully- | |||

document use the FEC Encoding ID XX for LDPC-Staircase and FEC | Specified FEC Schemes use respectively the FEC Encoding ID XX | |||

Encoding ID YY for LDPC-Triangle. | (Staircase) and YY (Triangle). | |||

4.2.2. Common Elements | 4.2.2. Common Elements | |||

The following elements MUST be defined with the present FEC Scheme: | The following elements MUST be defined with the present FEC Scheme: | |||

o Transfer-Length (L): a non-negative integer indicating the length | o Transfer-Length (L): a non-negative integer indicating the length | |||

of the object in bytes. There are some restrictions on the | of the object in bytes. There are some restrictions on the | |||

maximum Transfer-Length that can be supported: | maximum Transfer-Length that can be supported: | |||

maximum transfer length = 2^^12 * B * E | maximum transfer length = 2^^12 * B * E | |||

skipping to change at page 8, line 26 | skipping to change at page 8, line 26 | |||

o Maximum-Source-Block-Length (B): a non-negative integer indicating | o Maximum-Source-Block-Length (B): a non-negative integer indicating | |||

the maximum number of source symbols in a source block. There are | the maximum number of source symbols in a source block. There are | |||

some restrictions on the maximum B value, as explained in | some restrictions on the maximum B value, as explained in | |||

Section 5.2. | Section 5.2. | |||

o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer | o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer | |||

indicating the maximum number of encoding symbols generated for | indicating the maximum number of encoding symbols generated for | |||

any source block. There are some restrictions on the maximum | any source block. There are some restrictions on the maximum | |||

max_n value. In particular max_n is at most equal to 2^^20. | max_n value. In particular max_n is at most equal to 2^^20. | |||

Section 5 explains how to derive the values of each of these | Section 5 explains how to define the values of each of these | |||

elements. | elements. | |||

4.2.3. Scheme-Specific Element | 4.2.3. Scheme-Specific Elements | |||

The following element MUST be defined with the present FEC Scheme. | The following elements MUST be defined with the present FEC Scheme: | |||

It contains two distinct pieces of information: | ||||

o G: a non-negative integer indicating the number of encoding | o G: a non-negative integer indicating the number of encoding | |||

symbols per group used for the object. The default value is 1, | symbols per group (i.e. per packet). The default value is 1, | |||

meaning that each packet contains exactly one symbol. Values | meaning that each packet contains exactly one symbol. Values | |||

greater than 1 can also be defined, as explained in Section 5.3. | greater than 1 can also be defined, as explained in Section 5.3. | |||

o PRNG seed: The seed is a 32 bit unsigned integer between 1 and | o PRNG seed: the seed is a 32 bit unsigned integer between 1 and | |||

0x7FFFFFFE (i.e. 2^^31-2) inclusive. This value is used to | 0x7FFFFFFE (i.e. 2^^31-2) inclusive. This value is used to | |||

initialize the Pseudo Random Number Generator (Section 5.6). This | initialize the Pseudo Random Number Generator (Section 5.6). This | |||

element is optional. Whether or not it is present in the FEC OTI | element is optional. Whether or not it is present in the FEC OTI | |||

is signaled in the associated encoding format through an | is signaled in the associated encoding format through an | |||

appropriate mechanism (see Section 4.2.4). When the PRNG seed is | appropriate mechanism (Section 4.2.4). When the PRNG seed is not | |||

not carried within the FEC OTI, it is assumed that encoder and | carried within the FEC OTI, it is assumed that encoder and | |||

decoders use another way to communicate the information, or use a | decoders use another way to communicate the information, or use a | |||

fixed, predefined value. | fixed, predefined value. | |||

4.2.4. Encoding Format | 4.2.4. Encoding Format | |||

This section shows two possible encoding formats of the above FEC | This section shows two possible encoding formats of the above FEC | |||

OTI. The present document does not specify when or how these | OTI. The present document does not specify when or how these | |||

encoding formats should be used. | encoding formats should be used. | |||

4.2.4.1. Using the General EXT_FTI Format | 4.2.4.1. Using the General EXT_FTI Format | |||

The FEC OTI binary format is the following, when the EXT_FTI | The FEC OTI binary format is the following, when the EXT_FTI | |||

mechanism is used. | mechanism is used (e.g. within the ALC [11] or NORM [13] protocols). | |||

0 1 2 3 | 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 | 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 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| HET = 64 | HEL (=4 or 5) | | | | HET = 64 | HEL (=4 or 5) | | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |||

| Transfer-Length (L) | | | Transfer-Length (L) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Encoding Symbol Length (E) | G | B (MSB) | | | Encoding Symbol Length (E) | G | B (MSB) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

skipping to change at page 9, line 42 | skipping to change at page 9, line 41 | |||

for field alignment purposes. | for field alignment purposes. | |||

o The Maximum-Source-Block-Length (B) field (20 bits) is split into | o The Maximum-Source-Block-Length (B) field (20 bits) is split into | |||

two parts: the 8 most significant bits (MSB) are in the third 32- | two parts: the 8 most significant bits (MSB) are in the third 32- | |||

bit word of the EXT_FTI, and the remaining 12 least significant | bit word of the EXT_FTI, and the remaining 12 least significant | |||

bits (LSB) are in fourth 32-bit word. | bits (LSB) are in fourth 32-bit word. | |||

4.2.4.2. Using the FDT Instance (FLUTE specific) | 4.2.4.2. Using the FDT Instance (FLUTE specific) | |||

When it is desired that the FEC OTI be carried in the FDT Instance of | When it is desired that the FEC OTI be carried in the FDT Instance of | |||

a FLUTE session, the following XML elements must be described for the | a FLUTE session [12], the following XML elements must be described | |||

associated object: | for the associated object: | |||

o FEC-OTI-Transfer-length | o FEC-OTI-Transfer-length | |||

o FEC-OTI-Encoding-Symbol-Length | o FEC-OTI-Encoding-Symbol-Length | |||

o FEC-OTI-Maximum-Source-Block-Length | o FEC-OTI-Maximum-Source-Block-Length | |||

o FEC-OTI-Max-Number-of-Encoding-Symbols | ||||

o FEC-OTI-Max-Number-of-Encoding-Symbols | ||||

o FEC-OTI-Number-Encoding-Symbols-per-Group | o FEC-OTI-Number-Encoding-Symbols-per-Group | |||

o FEC-OTI-PRNG-seed (optional) | o FEC-OTI-PRNG-seed (optional) | |||

When no PRNG seed is to be carried in the FEC OTI, the sender simply | When no PRNG seed is to be carried in the FEC OTI, the sender simply | |||

omits the FEC-OTI-PRNG-seed element. | omits the FEC-OTI-PRNG-seed element. | |||

5. Procedures | 5. Procedures | |||

This section defines procedures that are common to FEC Encoding IDs | This section defines procedures that are common to FEC Encoding IDs | |||

skipping to change at page 11, line 30 | skipping to change at page 11, line 30 | |||

are numbered consecutively from 0 to N-1. The first I source blocks | are numbered consecutively from 0 to N-1. The first I source blocks | |||

consist of A_large source symbols, the remaining N-I source blocks | consist of A_large source symbols, the remaining N-I source blocks | |||

consist of A_small source symbols. Each source symbol is E bytes in | consist of A_small source symbols. Each source symbol is E bytes in | |||

length, except perhaps the last symbol which may be shorter. | length, except perhaps the last symbol which may be shorter. | |||

For each block the actual number of encoding symbols is determined, | For each block the actual number of encoding symbols is determined, | |||

as explained in the following section. | as explained in the following section. | |||

Then, FEC encoding and decoding can be done block per block, | Then, FEC encoding and decoding can be done block per block, | |||

independently. To that purpose, a parity check matrix is created, | independently. To that purpose, a parity check matrix is created, | |||

that forms a system of linear equations between the repair and source | that forms a system of linear equations between the source and repair | |||

symbols of a given block, where the basic operator is XOR. | symbols of a given block, where the basic operator is XOR. | |||

This parity check matrix is logically divided into two parts: the | This parity check matrix is logically divided into two parts: the | |||

left side (from column 0 to k-1) which describes the occurrence of | left side (from column 0 to k-1) which describes the occurrence of | |||

each source symbol in the equation system; and the right side (from | each source symbol in the equation system; and the right side (from | |||

column k to n-1) which describes the occurrence of each repair symbol | column k to n-1) which describes the occurrence of each repair symbol | |||

in the equation system. An entry (a "1") in the matrix at position | in the equation system. An entry (a "1") in the matrix at position | |||

(i,j) (i.e. at row i and column j) means that the symbol with ESI i | (i,j) (i.e. at row i and column j) means that the symbol with ESI i | |||

appears in equation j of the system. The only difference between the | appears in equation j of the system. The only difference between the | |||

LDPC-Staircase and LDPC-Triangle schemes is the construction of the | LDPC-Staircase and LDPC-Triangle schemes is the construction of the | |||

skipping to change at page 12, line 20 | skipping to change at page 12, line 20 | |||

field length of the FEC Payload ID (20 bits), as well as possible | field length of the FEC Payload ID (20 bits), as well as possible | |||

internal codec limitations. | internal codec limitations. | |||

The B parameter cannot be larger than the following values, derived | The B parameter cannot be larger than the following values, derived | |||

from the FEC Payload ID limitations, for a given code rate: | from the FEC Payload ID limitations, for a given code rate: | |||

max1_B = 2^^(20 - ceil(Log2(1/rate))) | max1_B = 2^^(20 - ceil(Log2(1/rate))) | |||

Some common max1_B values are: | Some common max1_B values are: | |||

o rate == 1 (no repair symbols): max_B = 2^^20 = 1,048,576 | o rate == 1 (no repair symbols): max1_B = 2^^20 = 1,048,576 | |||

o 1 > rate >= 1/2: max1_B = 2^^19 = 524,288 symbols | o 1/2 <= rate < 1: max1_B = 2^^19 = 524,288 symbols | |||

o 1/2 > rate >= 1/4: max1_B = 2^^18 = 262,144 symbols | o 1/4 <= rate < 1/2: max1_B = 2^^18 = 262,144 symbols | |||

o 1/4 > rate >= 1/8: max1_B = 2^^17 = 131,072 symbols | o 1/8 <= rate < 1/4: max1_B = 2^^17 = 131,072 symbols | |||

Additionally, a codec MAY impose other limitations on the maximum | Additionally, a codec MAY impose other limitations on the maximum | |||

block size. This is the case for instance when the codec uses | block size. This is the case for instance when the codec uses | |||

internally 16 bit integers to store the Encoding Symbol ID, since it | internally 16 bit unsigned integers to store the Encoding Symbol ID, | |||

does not enable to store all the possible values of a 20 bit field. | since it does not enable to store all the possible values of a 20 bit | |||

In that case, if for instance 1 > rate >= 1/2, then the maximum block | field. In that case, if for instance 1/2 <= rate < 1, then the | |||

size is 2^^15. Other limitations may also apply, for instance | maximum source block length is 2^^15. Other limitations may also | |||

because of a limited working memory size. This decision MUST be | apply, for instance because of a limited working memory size. This | |||

clarified at implementation time, when the target use case is known. | decision MUST be clarified at implementation time, when the target | |||

This results in a max2_B limitation. | use case is known. This results in a max2_B limitation. | |||

Then, B is given by: | Then, B is given by: | |||

B = min(max1_B, max2_B) | B = min(max1_B, max2_B) | |||

Note that this calculation is only required at the coder, since the B | Note that this calculation is only required at the coder, since the B | |||

parameter is communicated to the decoder through the FEC OTI. | parameter is communicated to the decoder through the FEC OTI. | |||

5.3. Determining the Encoding Symbol Length (E) and Number of Encoding | 5.3. Determining the Encoding Symbol Length (E) and Number of Encoding | |||

Symbols per Group (G) | Symbols per Group (G) | |||

skipping to change at page 13, line 17 | skipping to change at page 13, line 17 | |||

Yet other considerations can exist. For instance, the E parameter | Yet other considerations can exist. For instance, the E parameter | |||

can be made a function of the object transfer length. Indeed, LDPC | can be made a function of the object transfer length. Indeed, LDPC | |||

codes are known to offer better protection for large blocks. In case | codes are known to offer better protection for large blocks. In case | |||

of small objects, it can be a good practice to reduce the encoding | of small objects, it can be a good practice to reduce the encoding | |||

symbol length (E) in order to artificially increase the number of | symbol length (E) in order to artificially increase the number of | |||

symbols, and therefore the block size. | symbols, and therefore the block size. | |||

In order to minimize the protocol header overhead, several symbols | In order to minimize the protocol header overhead, several symbols | |||

can be grouped in the same Encoding Symbol Group (i.e. G > 1). | can be grouped in the same Encoding Symbol Group (i.e. G > 1). | |||

Depending on how many symbols are grouped (G) and on the packet loss | Depending on how many symbols are grouped (G) and on the packet loss | |||

rate (which leads to loosing G symbols at a time), this strategy | rate (G symbols are lost for each packet erasure), this strategy | |||

might or might not be appropriate. A balance must therefore be | might or might not be appropriate. A balance must therefore be | |||

found. | found. | |||

The current specification does not mandate any value for either E or | The current specification does not mandate any value for either E or | |||

G. The current specification only provides an example of possible | G. The current specification only provides an example of possible | |||

choices for E and G. Note that this choice is done by the sender. | choices for E and G. Note that this choice is done by the sender. | |||

Then the E and G parameters are communicated to the receivers thanks | Then the E and G parameters are communicated to the receivers thanks | |||

to the FEC OTI. | to the FEC OTI. | |||

Example: | Example: | |||

skipping to change at page 14, line 32 | skipping to change at page 14, line 32 | |||

max_n: Maximum number of encoding symbols generated for any source | max_n: Maximum number of encoding symbols generated for any source | |||

block | block | |||

n: Number of encoding symbols generated for this source block | n: Number of encoding symbols generated for this source block | |||

Algorithm: | Algorithm: | |||

max_n = floor(B / rate); | max_n = floor(B / rate); | |||

if (max_n >= 2^^20) then return an error ("invalid code rate"); | if (max_n > 2^^20) then return an error ("invalid code rate"); | |||

(NB: if max_n has been defined as explained in Section 5.2, this | (NB: if B has been defined as explained in Section 5.2, this error | |||

error should never happen) | should never happen) | |||

n = floor(k * max_n / B); | n = floor(k * max_n / B); | |||

AT A RECEIVER: | AT A RECEIVER: | |||

Input: | Input: | |||

B: Extracted from the received FEC OTI | B: Extracted from the received FEC OTI | |||

max_n: Extracted from the received FEC OTI | max_n: Extracted from the received FEC OTI | |||

k: Given by the source blocking algorithm | k: Given by the source blocking algorithm | |||

Output: | Output: | |||

n: | n: Number of encoding symbols generated for this source block | |||

Algorithm: | Algorithm: | |||

n = floor(k * max_n / B); | n = floor(k * max_n / B); | |||

5.5. Identifying the Symbols of an Encoding Symbol Group | 5.5. Identifying the Symbols of an Encoding Symbol Group | |||

When multiple encoding symbols are sent in the same packet, the FEC | When multiple encoding symbols are sent in the same packet, the FEC | |||

Payload ID information of the packet MUST refer to the first encoding | Payload ID information of the packet MUST refer to the first encoding | |||

symbol. It MUST then be possible to identify each symbol from this | symbol. It MUST then be possible to identify each symbol from this | |||

single FEC Payload ID. To that purpose, the symbols of an Encoding | single FEC Payload ID. To that purpose, the symbols of an Encoding | |||

skipping to change at page 15, line 35 | skipping to change at page 15, line 34 | |||

packet) that the application wants to create, | packet) that the application wants to create, | |||

* for a receiver, the ESI information contained in the FEC | * for a receiver, the ESI information contained in the FEC | |||

Payload ID. | Payload ID. | |||

and returns the list of G Encoding Symbol IDs that will be packed | and returns the list of G Encoding Symbol IDs that will be packed | |||

together. In case of a source packet, the G source symbols are | together. In case of a source packet, the G source symbols are | |||

taken consecutively. In case of a repair packet, the G repair | taken consecutively. In case of a repair packet, the G repair | |||

symbols are chosen randomly, as explained below. | symbols are chosen randomly, as explained below. | |||

o are stored in sequence in the packet, without any padding. In | ||||

other words, the last byte of the symbol with ESI i (where i is | ||||

the i-th ESI returned by the function ESIs_of_group()) is | ||||

immediately followed by the first byte of symbol i+1. | ||||

The system must first be initialized by creating a random permutation | The system must first be initialized by creating a random permutation | |||

of the n-k indexes. This initialization function MUST be called | of the n-k indexes. This initialization function MUST be called | |||

immediately after creating the parity check matrix. More precisely, | immediately after creating the parity check matrix. More precisely, | |||

since the PRNG seed is not re-initialized, no call to the PRNG | since the PRNG seed is not re-initialized, no call to the PRNG | |||

function must have happened between the time the parity check matrix | function must have happened between the time the parity check matrix | |||

has been initialized and the time the following initialization | has been initialized and the time the following initialization | |||

function is called. This is true both at a sender and at a receiver. | function is called. This is true both at a sender and at a receiver. | |||

int *txseqToID; | ||||

int *IDtoTxseq; | ||||

/* | /* | |||

* Initialization function. | * Initialization function. | |||

* Warning: use only when G > 1. | * Warning: use only when G > 1. | |||

*/ | */ | |||

void | ||||

initialize_tables () | initialize_tables () | |||

{ | { | |||

int i; | int i; | |||

int randInd; | int randInd; | |||

int backup; | int backup; | |||

txseqToID = malloc((n-k) * sizeof(int)); | ||||

IDtoTxseq = malloc((n-k) * sizeof(int)); | ||||

/* initialize the two tables that map ID | /* initialize the two tables that map ID | |||

* (i.e. ESI-k) to/from TxSequence. */ | * (i.e. ESI-k) to/from TxSequence. */ | |||

for (i = 0; i < n - k; i++) { | for (i = 0; i < n - k; i++) { | |||

IDtoTxseq[i] = i; | IDtoTxseq[i] = i; | |||

txseqToID[i] = i; | txseqToID[i] = i; | |||

} | } | |||

/* now randomize everything */ | /* now randomize everything */ | |||

for (i = 0; i < n - k; i++) { | for (i = 0; i < n - k; i++) { | |||

randInd = rand(n - k); | randInd = rand(n - k); | |||

backup = IDtoTxseq[i]; | backup = IDtoTxseq[i]; | |||

skipping to change at page 17, line 6 | skipping to change at page 17, line 6 | |||

txseqToID[IDtoTxseq[i]] = i; | txseqToID[IDtoTxseq[i]] = i; | |||

txseqToID[IDtoTxseq[randInd]] = randInd; | txseqToID[IDtoTxseq[randInd]] = randInd; | |||

} | } | |||

return; | return; | |||

} | } | |||

It is then possible, at the sender, to determine the sequence of G | It is then possible, at the sender, to determine the sequence of G | |||

Encoding Symbol IDs that will be part of the group. | Encoding Symbol IDs that will be part of the group. | |||

/* | /* | |||

* Determine the sequence of ESIs of the packet under construction | * Determine the sequence of ESIs for the packet under construction | |||

* at a sender. | * at a sender. | |||

* Warning: use only when G > 1. | * Warning: use only when G > 1. | |||

* PktIdx (IN): index of the packet, in {0..ceil(n/G)} range | * PktIdx (IN): index of the packet, in | |||

* ESIs[] (OUT): list of ESI of the packet | * {0..ceil(k/G)+ceil((n-k)/G)} range | |||

* ESIs[] (OUT): list of ESIs for the packet | ||||

*/ | */ | |||

void | ||||

sender_find_ESIs_of_group (int PktIdx, | sender_find_ESIs_of_group (int PktIdx, | |||

ESI_t ESIs[]) | ESI_t ESIs[]) | |||

{ | { | |||

int i; | int i; | |||

if (is_source_packet(PktIdx) == true) { | if (PktIdx < nbSourcePkts) { | |||

/* this is a source packet */ | /* this is a source packet */ | |||

ESIs[0] = (PktIdx * G) % k; | ESIs[0] = PktIdx * G; | |||

for (i = 0; i < G; i++) { | for (i = 1; i < G; i++) { | |||

ESIs[i] = ESIs[0] + i; | ESIs[i] = (ESIs[0] + i) % k; | |||

} | } | |||

} else { | } else { | |||

/* this is a repair packet */ | /* this is a repair packet */ | |||

for (i = 0; i < G; i++) { | for (i = 0; i < G; i++) { | |||

ESIs[i] = | ESIs[i] = | |||

k + | k + | |||

txseqToID[(i + (PktIdx - nbSourcePkts) * G) | txseqToID[(i + (PktIdx - nbSourcePkts) * G) | |||

% (n - k)]; | % (n - k)]; | |||

} | } | |||

} | } | |||

return; | return; | |||

} | } | |||

Similarly, upon receiving an Encoding Symbol Group (i.e. packet), a | Similarly, upon receiving an Encoding Symbol Group (i.e. packet), a | |||

receiver can determine the sequence of G Encoding Symbol IDs from the | receiver can determine the sequence of G Encoding Symbol IDs from the | |||

first ESI, esi0, that is contained in the FEC Payload ID. | first ESI, esi0, that is contained in the FEC Payload ID. | |||

/* | /* | |||

* Determine the sequence of ESIs of a packet received. | * Determine the sequence of ESIs for the packet received. | |||

* Warning: use only when G > 1. | * Warning: use only when G > 1. | |||

* esi0 (IN): : ESI contained in the FEC Payload ID | * esi0 (IN): : ESI contained in the FEC Payload ID | |||

* ESIs[] (OUT): list of ESI of the packet | * ESIs[] (OUT): list of ESIs for the packet | |||

*/ | */ | |||

void | ||||

receiver_find_ESIs_of_group (ESI_t esi0, | receiver_find_ESIs_of_group (ESI_t esi0, | |||

ESI_t ESIs[]) | ESI_t ESIs[]) | |||

{ | { | |||

int i; | int i; | |||

if (is_source_packet(esi0) == true) { | if (esi0 < k) { | |||

/* this is a source packet */ | /* this is a source packet */ | |||

for (i = 0; i < G; i++) { | ESIs[0] = esi0; | |||

for (i = 1; i < G; i++) { | ||||

ESIs[i] = (esi0 + i) % k; | ESIs[i] = (esi0 + i) % k; | |||

} | } | |||

} else { | } else { | |||

/* this is a repair packet */ | /* this is a repair packet */ | |||

for (i = 0; i < G; i++) { | for (i = 0; i < G; i++) { | |||

ESIs[i] = | ESIs[i] = | |||

k + | k + | |||

txseqToID[(i + IDtoTxseq[esi0 - k]) | txseqToID[(i + IDtoTxseq[esi0 - k]) | |||

% (n - k)]; | % (n - k)]; | |||

} | } | |||

skipping to change at page 21, line 5 | skipping to change at page 21, line 5 | |||

6.2. Parity Check Matrix Creation | 6.2. Parity Check Matrix Creation | |||

The LDPC-Staircase matrix can be divided into two parts: the left | The LDPC-Staircase matrix can be divided into two parts: the left | |||

side of the matrix defines in which equations the source symbols are | side of the matrix defines in which equations the source symbols are | |||

involved; the right side of the matrix defines in which equations the | involved; the right side of the matrix defines in which equations the | |||

repair symbols are involved. | repair symbols are involved. | |||

The left side is generated with the following algorithm: | The left side is generated with the following algorithm: | |||

/* initialize a list of possible choices to | /* initialize a list of all possible choices in order to | |||

* guarantee a homogeneous "1" distribution */ | * guarantee a homogeneous "1" distribution */ | |||

for (h = 3*k-1; h >= 0; h--) { | for (h = 3*k-1; h >= 0; h--) { | |||

u[h] = h % (n-k); | u[h] = h % (n-k); | |||

} | } | |||

/* left limit within the list of possible choices, u[] */ | /* left limit within the list of possible choices, u[] */ | |||

t = 0; | t = 0; | |||

for (j = 0; j < k; j++) { /* for each source symbol column */ | for (j = 0; j < k; j++) { /* for each source symbol column */ | |||

for (h = 0; h < 3; h++) { /* add 3 "1s" */ | for (h = 0; h < 3; h++) { /* add 3 "1s" */ | |||

/* check that valid available choices remain */ | /* check that valid available choices remain */ | |||

skipping to change at page 21, line 39 | skipping to change at page 21, line 39 | |||

} else { | } else { | |||

/* no choice left, choose one randomly */ | /* no choice left, choose one randomly */ | |||

do { | do { | |||

i = rand(n-k); | i = rand(n-k); | |||

} while (matrix_has_entry(i, j)); | } while (matrix_has_entry(i, j)); | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

} | } | |||

} | } | |||

/* Add extra bits to avoid rows with less than two "1s" */ | /* Add extra bits to avoid rows with less than two "1s". | |||

* This is needed when the code rate is smaller than 2/5. */ | ||||

for (i = 0; i < n-k; i++) { /* for each row */ | for (i = 0; i < n-k; i++) { /* for each row */ | |||

if (degree_of_row(i) == 0) { | if (degree_of_row(i) == 0) { | |||

j = rand(k); | j = rand(k); | |||

e = matrix_insert_entry(i, j); | e = matrix_insert_entry(i, j); | |||

} | } | |||

if (degree_of_row(i) == 1) { | if (degree_of_row(i) == 1) { | |||

do { | do { | |||

j = rand(k); | j = rand(k); | |||

} while (matrix_has_entry(i, j)); | } while (matrix_has_entry(i, j)); | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

skipping to change at page 22, line 30 | skipping to change at page 22, line 30 | |||

Thanks to the staircase matrix, repair symbol creation is | Thanks to the staircase matrix, repair symbol creation is | |||

straightforward: each repair symbol is equal to the sum of all source | straightforward: each repair symbol is equal to the sum of all source | |||

symbols in the associated equation, plus the previous repair symbol | symbols in the associated equation, plus the previous repair symbol | |||

(except for the first repair symbol). Therefore encoding MUST follow | (except for the first repair symbol). Therefore encoding MUST follow | |||

the natural repair symbol order: start with the first repair symbol, | the natural repair symbol order: start with the first repair symbol, | |||

and generate repair symbol with ESI i before symbol ESI i+1. | and generate repair symbol with ESI i before symbol ESI i+1. | |||

6.4. Decoding | 6.4. Decoding | |||

Decoding basically consists in solving a system of n-k linear | Decoding basically consists in solving a system of n-k linear | |||

equations whose variables are the source an repair symbols. Of | equations whose variables are the n source and repair symbols. Of | |||

course, the final goal is to recover the value of source symbols | course, the final goal is to recover the value of the k source | |||

only. | symbols only. | |||

To that purpose, many techniques are possible. One of them is the | To that purpose, many techniques are possible. One of them is the | |||

following trivial algorithm [10]: given a set of linear equations, if | following trivial algorithm [10]: given a set of linear equations, if | |||

one of them has only one remaining unknown variable, then the value | one of them has only one remaining unknown variable, then the value | |||

of this variable is that of the constant term. So, replace this | of this variable is that of the constant term. So, replace this | |||

variable by its value in all the remaining linear equations and | variable by its value in all the remaining linear equations and | |||

reiterate. The value of several variables can therefore be found | reiterate. The value of several variables can therefore be found | |||

recursively. Applied to LDPC FEC codes working over an erasure | recursively. Applied to LDPC FEC codes working over an erasure | |||

packet, the parity check matrix defines a set of linear equations | channel, the parity check matrix defines a set of linear equations | |||

whose variables are the source symbols and repair symbols. Receiving | whose variables are the source symbols and repair symbols. Receiving | |||

or decoding a symbol is equivalent to having the value of a variable. | or decoding a symbol is equivalent to having the value of a variable. | |||

Appendix A sketches a possible implementation of this algorithm. | Appendix A sketches a possible implementation of this algorithm. | |||

The Gauss elimination technique (or any optimized derivative) is | The Gauss elimination technique (or any optimized derivative) is | |||

another possible decoding technique. Hybrid solutions that start by | another possible decoding technique. Hybrid solutions that start by | |||

using the trivial algorithm above and finish with a Gauss elimination | using the trivial algorithm above and finish with a Gauss elimination | |||

are also possible. | are also possible. | |||

Because interoperability does not depend on the decoding algorithm | Because interoperability does not depend on the decoding algorithm | |||

skipping to change at page 25, line 12 | skipping to change at page 25, line 12 | |||

Here also repair symbol creation is straightforward: each repair | Here also repair symbol creation is straightforward: each repair | |||

symbol is equal to the sum of all source symbols in the associated | symbol is equal to the sum of all source symbols in the associated | |||

equation, plus the repair symbols in the triangle. Therefore | equation, plus the repair symbols in the triangle. Therefore | |||

encoding MUST follow the natural repair symbol order: start with the | encoding MUST follow the natural repair symbol order: start with the | |||

first repair symbol, and generate repair symbol with ESI i before | first repair symbol, and generate repair symbol with ESI i before | |||

symbol ESI i+1. | symbol ESI i+1. | |||

7.4. Decoding | 7.4. Decoding | |||

Decoding basically consists in solving a system of n-k linear | Decoding basically consists in solving a system of n-k linear | |||

equations, whose variables are the source an repair symbols. Of | equations, whose variables are the n source and repair symbols. Of | |||

course, the final goal is to recover the value of source symbols | course, the final goal is to recover the value of the k source | |||

only. To that purpose, many techniques are possible, as explained in | symbols only. To that purpose, many techniques are possible, as | |||

Section 6.4. | explained in Section 6.4. | |||

Because interoperability does not depend on the decoding algorithm | Because interoperability does not depend on the decoding algorithm | |||

used, the current document does not recommend any particular | used, the current document does not recommend any particular | |||

technique. This choice is left to the codec implementer. | technique. This choice is left to the codec implementer. | |||

8. Security Considerations | 8. Security Considerations | |||

The security considerations for this document are the same as that of | The security considerations for this document are the same as that of | |||

[2]. | [2]. | |||

skipping to change at page 30, line 5 | skipping to change at page 29, line 6 | |||

[9] Carta, D., "Two Fast Implementations of the Minimal Standard | [9] Carta, D., "Two Fast Implementations of the Minimal Standard | |||

Random Number Generator", Communications of the ACM, Vol. 33, | Random Number Generator", Communications of the ACM, Vol. 33, | |||

No. 1, pp.87-88, January 1990. | No. 1, pp.87-88, January 1990. | |||

[10] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density | [10] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density | |||

Codes for Transmission in a Channel with Erasures", Translated | Codes for Transmission in a Channel with Erasures", Translated | |||

from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, | from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, | |||

January-March 1974. | January-March 1974. | |||

[11] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered | ||||

Coding (ALC) Protocol Instantiation", | ||||

draft-ietf-rmt-pi-alc-revised-03.txt (work in progress), | ||||

April 2006. | ||||

[12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | ||||

"FLUTE - File Delivery over Unidirectional Transport", | ||||

draft-ietf-rmt-flute-revised-01.txt (work in progress), | ||||

January 2006. | ||||

[13] Adamson, B., Bormann, C., Handley, M., and J. Macker, | ||||

"Negative-acknowledgment (NACK)-Oriented Reliable Multicast | ||||

(NORM) Protocol", draft-ietf-rmt-pi-norm-revised-02.txt (work | ||||

in progress), June 2006. | ||||

Appendix A. Trivial Decoding Algorithm (Informative Only) | Appendix A. Trivial Decoding Algorithm (Informative Only) | |||

A trivial decoding algorithm is sketched below (please see [6] for | A trivial decoding algorithm is sketched below (please see [6] for | |||

the details omitted here): | the details omitted here): | |||

Initialization: allocate a table of partial sum buffers: | Initialization: allocate a table partial_sum[n-k] of buffers, each | |||

partial_sum[n-k], one per equation; | buffer being of size the symbol size. There's one | |||

Reset all the buffers to 0; | entry per equation since the buffers are meant to | |||

store the partial sum of each equation; Reset all | ||||

the buffers to zero; | ||||

/* | /* | |||

* For each newly received or decoded symbol, try to make progress | * For each newly received or decoded symbol, try to make progress | |||

* in the decoding of the associated source block. | * in the decoding of the associated source block. | |||

* new_esi (IN): ESI of the new symbol, which is also the index | * NB: in case of a symbol group (G>1), this function is called for | |||

* in [0; n-1] | * each symbol of the received packet. | |||

* new_symb (IN): New symbol received or decoded | * new_esi (IN): ESI of the new symbol received or decoded | |||

* new_symb (IN): Buffer of the new symbol received or decoded | ||||

*/ | */ | |||

void | void | |||

decoding_step(ESI_t new_esi, | decoding_step(ESI_t new_esi, | |||

symbol_t *new_symb) | symbol_t *new_symb) | |||

{ | { | |||

If (new_symb is an already decoded or received symbol) { | If (new_symb is an already decoded or received symbol) { | |||

Return; /* don't waste time with this symbol */ | Return; /* don't waste time with this symbol */ | |||

} | } | |||

If (new_symb is the last missing source symbol) { | If (new_symb is the last missing source symbol) { | |||

Return; /* decoding is now finished */ | Remember that decoding is finished; | |||

Return; /* work is over now... */ | ||||

} | } | |||

Create an empty list of equations having symbols decoded during | Create an empty list of equations having symbols decoded | |||

this decoding step; | during this decoding step; | |||

/* | /* | |||

* First add this new symbol to all partial sums of the | * First add this new symbol to the partial sum of all the | |||

* associated equations. | * equations where the symbol appears. | |||

*/ | */ | |||

For (each equation eq in which new_symb is a variable and | For (each equation eq in which new_symb is a variable and | |||

having more than one unknown variable) { | having more than one unknown variable) { | |||

Add new_symb to partial_sum[eq]; | Add new_symb to partial_sum[eq]; | |||

Remove entry(eq, new_esi) from the H matrix; | Remove entry(eq, new_esi) from the H matrix; | |||

If (degree of equation eq == 1) { | If (the new degree of equation eq == 1) { | |||

/* new symbol can be decoded, remember the equation */ | /* a new symbol can be decoded, remember the | |||

* equation */ | ||||

Append eq to the list of equations having symbols | Append eq to the list of equations having symbols | |||

decoded during this decoding step; | decoded during this decoding step; | |||

} | } | |||

} | } | |||

/* | /* | |||

* Then finish with recursive calls to decoding_step() for each | * Then finish with recursive calls to decoding_step() for each | |||

* newly decoded symbols. | * newly decoded symbol. | |||

*/ | */ | |||

For (each equation eq in the list of equations having symbols | For (each equation eq in the list of equations having symbols | |||

decoded during this decoding step) { | decoded during this decoding step) { | |||

/* | /* | |||

* Because of the recursion below, we need to check that | * Because of the recursion below, we need to check that | |||

* decoding is not finished, and that the equation is | * decoding is not finished, and that the equation is | |||

* __still__ of degree 1 | * __still__ of degree 1 | |||

*/ | */ | |||

If (decoding is finished) { | If (decoding is finished) { | |||

break; /* exit from the loop */ | break; /* exit from the loop */ | |||

} | } | |||

If ((degree of equation eq == 1) { | If ((degree of equation eq == 1) { | |||

Let dec_esi be the ESI of the newly decoded symbol in | Let dec_esi be the ESI of the newly decoded symbol in | |||

equation eq; | equation eq; | |||

Remove entry(eq, dec_esi); | Remove entry(eq, dec_esi); | |||

Allocate a buffer, dec_symb, for this symbol, and | Allocate a buffer, dec_symb, for this symbol and | |||

copy partial_sum[eq] to dec_symb; | copy partial_sum[eq] to dec_symb; | |||

/* finally, call this function recursively */ | /* finally, call this function recursively */ | |||

decoding_step(dec_esi, dec_symb); | decoding_step(dec_esi, dec_symb); | |||

} | } | |||

} | } | |||

Free the list of equations having symbols decoded; | ||||

Return; | ||||

} | } | |||

Authors' Addresses | Authors' Addresses | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

655, av. de l'Europe | 655, av. de l'Europe | |||

Zirst; Montbonnot | Zirst; Montbonnot | |||

ST ISMIER cedex 38334 | ST ISMIER cedex 38334 | |||

France | France | |||

End of changes. 65 change blocks. | ||||

88 lines changed or deleted | | 132 lines changed or added | ||

This html diff was produced by rfcdiff 1.32. The latest version is available from http://www.levkowetz.com/ietf/tools/rfcdiff/ |