Staircase forward error correction coding

Apparatus comprising:

• a mapper to receive a stream of data symbols and to map the stream of data symbols among data symbol positions in a sequence of two-dimensional symbol blocks Bi, i a positive integer, each of the symbol blocks comprising data symbol positions and coding symbol positions;
• and
• a Forward Error Correction (FEC) encoder, operatively coupled to the mapper, to compute coding symbols for the coding symbol positions in each symbol block in the sequence, the coding symbols being computed such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, comprises a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1, forms a codeword of the FEC component code,
• wherein each symbol block comprises an n row by m column array of symbols, m, n≧1, n>m,
• the FEC encoder computing the coding symbols for the coding symbol positions in each symbol block Bi based on Di−1 and Bi, where Di−1 is a matrix formed by adding (n−m) sets of n predetermined symbols along the one dimension of Bi−1.

A Forward Error Correction (FEC) decoding method of a FEC decoder, the method comprising:

• receiving a sequence of FEC encoded two-dimensional symbol blocks Bi, i a positive integer, each of the received symbol blocks comprising received versions of data symbols at data symbol positions and coding symbols at coding symbol positions, the coding symbols for the coding symbol positions in each symbol block Bi in the sequence having been computed at a transmitter of the received symbol blocks such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, forms a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1, forms a codeword of the FEC component code, wherein each symbol block comprises an n row by m column array of symbols, m, n≧1, n>m, the coding symbols having been computed at the transmitter for the coding symbol positions in each symbol block Bi based on Di−1 and Bi, where Di−1 is a matrix formed by adding (n−m) sets of n predetermined symbols along the one dimension of Bi−1;
• and
• decoding the received FEC encoded symbol blocks.

Apparatus comprising:

• an interface to receive a sequence of FEC encoded two-dimensional symbol blocks Bi, i a positive integer, each of the received symbol blocks comprising received versions of data symbols at data symbol positions and coding symbols at coding symbol positions, the coding symbols for the coding symbol positions in each symbol block Bi in the sequence having been computed at a transmitter of the received symbol blocks such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, forms a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1, forms a codeword of the FEC component code, wherein each symbol block comprises an n row by m column array of symbols, m, n≧1, n>m, the coding symbols having been computed at the transmitter for the coding symbol positions in each symbol block Bi based on Di−1 and Bi, where Di−1 is a matrix formed by adding (n−m) sets of n predetermined symbols along the one dimension of Bi−1;
• and
• a decoder, operatively coupled to the interface, to decode the received FEC encoded symbol blocks.

A Forward Error Correction (FEC) encoding method of an encoding apparatus comprising a mapper and a FEC encoder operatively coupled to the mapper, the method comprising:

• the mapper mapping a stream of data symbols to data symbol positions in a sequence of two-dimensional symbol blocks Bi, i a positive integer, each of the symbol blocks comprising data symbol positions and coding symbol positions;
• and
• the FEC encoder computing coding symbols for the coding symbol positions in each symbol block in the sequence, the coding symbols being computed such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, forms a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1, forms a codeword of the FEC component code,
• wherein each symbol block comprises an n row by m column array of symbols, m, n≧1, n>m, the computing comprising:
• computing the coding symbols for the coding symbol positions in each symbol block Bi based on Di−1 and Bi, where Di−1 is a matrix formed by adding (n−m) sets of n predetermined symbols along the one dimension of Bi−1.

An apparatus comprising:

• means for mapping a stream of data symbols to data symbol positions in a sequence of two-dimensional symbol blocks Bi, i a positive integer, each of the symbol blocks comprising data symbol positions and coding symbol positions;
• and
• means for computing coding symbols for the coding symbol positions in each symbol block in the sequence, the coding symbols being computed such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, forms a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1,forms a codeword of the FEC component code,
• wherein each symbol block comprises an n row by m column array of symbols, m, n≧1, n>m, the computing comprising:
• computing the coding symbols for the coding symbol positions in each symbol block Bi based on Di−1 and Bi, where Di−1 is a matrix formed by adding (n−m) sets of n predetermined symbols along the one dimension of Bi−1.

A Forward Error Correction (FEC) encoding method of an encoding apparatus comprising a mapper and a FEC encoder operatively coupled to the mapper, the method comprising:

• mapping a stream of data symbols to data symbol positions in a sequence of two-dimensional symbol blocks Bi, i a positive integer, each of the symbol blocks comprising data symbol positions and coding symbol positions;
• and
• computing coding symbols for the coding symbol positions in each symbol block in the sequence, the coding symbols being computed such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, forms a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1, forms a codeword of the FEC component code,
• wherein the FEC component code comprises an algebraic linear code in non-cyclic form.

Apparatus comprising:

• a mapper to receive a stream of data symbols and to map the stream of data symbols among data symbol positions in a sequence of two-dimensional symbol blocks Bi, i a positive integer, each of the symbol blocks comprising data symbol positions and coding symbol positions;
• and
• a Forward Error Correction (FEC) encoder, operatively coupled to the mapper, to compute coding symbols for the coding symbol positions in each symbol block in the sequence, the coding symbols being computed such that, for each symbol block Bi that has a preceding symbol block Bi−1 and a subsequent symbol block Bi+1 in the sequence, a two-block concatenation of symbols at symbol positions along one dimension of the preceding symbol block Bi−1, concatenated with the symbols along the other dimension in the symbol block Bi, comprises a codeword of a FEC component code, and a two-block concatenation of symbols at symbol positions along the one dimension of the symbol block Bi, concatenated with the symbols along the other dimension in the subsequent symbol block Bi+1, forms a codeword of the FEC component code,
• wherein the FEC component code comprises an algebraic linear code in non-cyclic form.