Methods and devices for rate adaptive forward error correction using a flexible irregular error correcting code

1. A method comprising:

receiving, at a forward error correction (FEC) encoder of a transmitter, a digital data signal comprising a plurality of data bits;

generating, at the FEC encoder, a FEC enabled data signal encoded as a staircase code,

the FEC enabled data signal comprising a sequence of data blocks alternating between row-wise data blocks and column-wise data blocks;

each row-wise data block comprising a plurality of rows, the plurality of rows defining a plurality of columns, each row comprising:

a data bit sequence comprising one or more of the data bits; and

a parity bit sequence comprising one or more parity bits, each parity bit sequence being based on its respective data bit sequence and a corresponding row of a prior column-wise data block;

each column-wise data block comprising a plurality of columns, the plurality of columns defining a plurality of rows, each column comprising:

a data bit sequence comprising one or more of the data bits; and

a parity bit sequence comprising one or more parity bits, each parity bit sequence being based on its respective data bit sequence and a corresponding column of a prior row-wise data block;

each data block including at least one parity bit sequence of a first encoding and at least parity bit sequence of a second encoding;

each parity bit sequence of the first encoding having a first predetermined number of parity bits;

each parity bit sequence of the second encoding having a second predetermined number of parity bits greater than the first predetermined number; and

transmitting the FEC enabled data signal.

2. The method of claim 1 , wherein at least one data block of the sequence of data blocks contains at least one parity bit sequence of a third encoding, each parity bit sequence of the third encoding having a third predetermined number of parity bits greater than the second predetermined number.

3. The method of claim 2 , wherein each data block of the sequence of data blocks includes:

a first number of parity bit sequences of the first encoding;

a second number of parity bit sequences of the second encoding; and

a third number of parity bit sequences of the third encoding,

the first number, second number, and third number being determined based on a target error correction overhead level,

the method further comprising:

receiving channel condition information;

updating the target error correction overhead level based on the channel condition information; and

changing the first number, second number, and third number based on the updated target error correction overhead level.

4. The method of claim 3 , wherein, for each data block, the parity bit sequences of each encoding are distributed among the rows or columns such that a number of adjacent parity bit sequences of the same encoding is minimized.

5. The method of claim 3 , wherein:

each row-wise data block has the same distribution of parity bit sequences of each encoding among its rows; and

each column-wise data block has the same distribution of parity bit sequences of each encoding among its columns.

6. The method of claim 2 , further comprising generating a parity bit sequence in a row-wise data block by:

identifying a binary vector comprising:

an unknown parity bit sequence;

the data bits of the row of the parity bit sequence in the row-wise data block; and

the bits of the corresponding row of the prior column-wise data block;

identifying a valid parity bit sequence such that, by setting the unknown parity bit sequence to the valid parity bit sequence and multiplying the binary vector by a transpose of a parity check matrix to generate a syndrome, the syndrome comprising a vector having a number of elements equal to a number of rows of the parity check matrix, each element of the syndrome is equal to zero; and

setting the parity bit sequence to the valid parity bit sequence.

7. The method of claim 6 , wherein:

the parity bit sequence is of the first encoding; and

the parity check matrix comprises a one row matrix defined by a primitive element a of a Galois field such that:

the first element of the parity check matrix is one; and

each subsequent element of the parity check matrix is a times the previous element.

8. The method of claim 6 , wherein:

the parity bit sequence is of the second encoding; and

the parity check matrix comprises a two row matrix defined by a primitive element a of a Galois field such that:

the first element of the first row of the parity check matrix is one;

each subsequent element of the first row of the parity check matrix is a times the previous element;

the first element of the second row of the parity check matrix is one; and

each subsequent element of the second row of the parity check matrix is a 3 times the previous element.

9. The method of claim 6 , wherein:

the parity bit sequence is of the third encoding; and

the parity check matrix comprises a three row matrix defined by a primitive element a of a Galois field such that:

the first element of the first row of the parity check matrix is one;

each subsequent element of the first row of the parity check matrix is a times the previous element;

the first element of the second row of the parity check matrix is one;

each subsequent element of the second row of the parity check matrix is a 3 times the previous element;

the first element of the third row of the parity check matrix is one; and

each subsequent element of the third row of the parity check matrix is a 5 times the previous element.

10. The method of claim 1 , further comprising:

receiving, at a forward error correction (FEC) decoder of a receiver, the FEC enabled data signal; and

for each row of each data row-wise block of the FEC enabled data signal, performing, at the FEC decoder, a parity check using the parity bit sequence of the row to detect at least one bit error in a prior data block of the FEC enabled data signal

for each column of each column-wise data block of the FEC enabled data signal, performing, at the FEC decoder, a parity check using the parity bit sequence of the column to detect at least one bit error in a prior data block of the FEC enabled data signal.

11. The method of claim 10 , wherein at least one data block of the sequence of data blocks contains at least one parity bit sequence of a third encoding, each parity bit sequence of the third encoding having a third predetermined number of parity bits greater than the second predetermined number.

12. The method of claim 11 , wherein:

each row-wise data block has the same distribution of parity bit sequences of each encoding among its rows; and

each column-wise data block has the same distribution of parity bit sequences of each encoding among its columns.

13. The method of claim 11 , wherein detecting a bit error in the corresponding row of the prior column-wise data block using a parity bit sequence comprises:

identifying a binary vector comprising:

the parity bit sequence;

the data bits of the row of the row-wise data block; and

the bits of the corresponding row of the prior column-wise data block;

multiplying the binary vector by a transpose of a parity check matrix to generate a syndrome, the syndrome comprising a vector having a number of elements equal to a number of rows of the parity check matrix; and

based on the elements of the syndrome, determining that the binary vector contains at least one bit error.

14. The method of claim 13 , wherein:

the parity bit sequence is of the first encoding; and

the parity check matrix comprises a one row matrix defined by a primitive element a of a Galois field such that:

the first element of the parity check matrix is one; and

each subsequent element of the parity check matrix is a times the previous element,

the method further comprising, in response to determining that the first element of the syndrome is not zero, using a syndrome decoder module of the FEC decoder to correct the one or more detected errors, the syndrome decoder module being configured to:

provide the first element of the syndrome to a one-error decoder unit of the FEC decoder;

use the one-error decoder unit to locate a single bit error in the binary vector based on the first element of the syndrome; and

correct the single bit error.

15. The method of claim 13 , wherein:

the parity bit sequence is of the second encoding; and

the parity check matrix comprises a two row matrix defined by a primitive element a of a Galois field such that:

the first element of the first row of the parity check matrix is one;

each subsequent element of the first row of the parity check matrix is a times the previous element;

the first element of the second row of the parity check matrix is one; and

each subsequent element of the second row of the parity check matrix is a 3 times the previous element,

the method further comprising, in response to determining that the first element or second element of the syndrome is not zero, using a syndrome decoder module of the FEC decoder to correct the one or more detected errors, the syndrome decoder module being configured to:

calculate a value D 3 by adding the cube of the first element of the syndrome to the second element of the syndrome;

if D 3 is zero:

provide the first element of the syndrome to a one-error decoder unit of the FEC decoder;

use the one-error decoder unit to locate a single bit error in the binary vector based on the first element of the syndrome; and

correct the single bit error; and

if D 3 is not zero:

provide the first and second elements of the syndrome to a two-error decoder unit of the FEC decoder;

use the two-error decoder unit to locate two bit errors in the binary vector based on the first element of the syndrome; and

correct the two bit errors.

16. The method of claim 11 , wherein:

the parity bit sequence is of the third encoding; and

the parity check matrix comprises a three row matrix defined by a primitive element a of a Galois field such that:

the first element of the first row of the parity check matrix is one;

each subsequent element of the first row of the parity check matrix is a times the previous element;

the first element of the second row of the parity check matrix is one;

each subsequent element of the second row of the parity check matrix is a 3 times the previous element;

the first element of the third row of the parity check matrix is one; and

each subsequent element of the third row of the parity check matrix is a 5 times the previous element;

the method further comprising, in response to determining that any of the three elements of the syndrome is not zero, using a syndrome decoder module of the FE decoder to correct the one or more detected errors, the syndrome decoder module being configured to:

calculate a value D 3 by adding the cube of the first element of the syndrome to the second element of the syndrome;

if D 3 is zero:

provide the first element of the syndrome to a one-error decoder unit of the FEC decoder;

use the one-error decoder unit to locate a single bit error in the binary vector based on the first element of the syndrome; and

correct the single bit error; and

if D 3 is not zero:

calculate a value D 5 by adding the first element of the syndrome, raised to the fifth power, to the third element of the syndrome;

if the first element of the syndrome, multiplied by D 5 , is equal to the second element of the syndrome, multiplied by D 3 :

provide the first and second elements of the syndrome to a two-error decoder unit of the FEC decoder;

use the two-error decoder unit to locate two bit errors in the binary vector based on the first and second elements of the syndrome; and

correct the two bit errors; and

if:

the first element of the syndrome, multiplied by D 5 , is not equal to the second element of the syndrome, multiplied by D 3 ; or

the first element of the syndrome is equal to zero:

 provide the first, second, and third elements of the syndrome to a three-error decoder unit of the FEC decoder;

 use the three-error decoder unit to locate three bit errors in the binary vector based on the first, second, and third elements of the syndrome; and

 correct the three bit errors.

17. The method of claim 16 , wherein the syndrome decoder module is a gated syndrome decoder module further configured to detect and correct bit errors in the data bit sequence of a row of a row-wise data block or in the corresponding row of the prior column-wise data block using a parity bit sequence of the first encoding or second encoding.

18. A transmitter, comprising:

a forward error correction (FEC) encoder configured to:

receive, at a forward error correction (FEC) encoder of a transmitter, a digital data signal comprising a plurality of data bits;

generate, at the FEC encoder, a FEC enabled data signal encoded as a staircase code,

the FEC enabled data signal comprising a sequence of data blocks alternating between row-wise data blocks and column-wise data blocks;

each row-wise data block comprising a plurality of rows, the plurality of rows defining a plurality of columns, each row comprising:

a data bit sequence comprising one or more of the data bits; and

a parity bit sequence comprising one or more parity bits, each parity bit sequence being based on its respective data bit sequence and a corresponding row of a prior column-wise data block;

each column-wise data block comprising a plurality of columns, the plurality of columns defining a plurality of rows, each column comprising:

a data bit sequence comprising one or more of the data bits; and

a parity bit sequence comprising one or more parity bits, each parity bit sequence being based on its respective data bit sequence and a corresponding column of a prior row-wise data block;

each data block including at least one parity bit sequence of a first encoding and at least parity bit sequence of a second encoding;

each parity bit sequence of the first encoding having a first predetermined number of parity bits;

each parity bit sequence of the second encoding having a second predetermined number of parity bits greater than the first predetermined number; and

transmit the FEC enabled data signal.