Forward error correction

• US 8,959,418 B1
• Filed: 11/30/2012
• Issued: 02/17/2015
• Est. Priority Date: 11/30/2012
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Mazahreh, Raied N., Rao, Raghavendar M., Pfister, Henry D., Narayanan, Krishna R.
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US13/691,501
• Time in Patent Office: 809 Days
• Field of Search: 714/785, 714/746, 714/782, 714/784
• US Class Current: 714/785
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence

Abstract

In one embodiment, a circuit for FEC decoding includes first and second syndrome calculation circuits, configured to calculate FEC syndromes for rows and columns of symbols in a de-interleaved format, respectively. A decoding circuit is configured to arrange the symbols into windows. Each window includes a plurality of sequential rows and sequential columns of the symbols in the de-interleaved format. The decoding circuit is configured to place N of the windows in a group and perform M decoding iterations of the windows in the group. In each decoding iteration, the decoding circuit performs FEC decoding of rows of each of the windows in the group followed by FEC decoding of columns of each of the windows in the group.

Claims

1. A circuit for forward error correction decoding, comprising:

a first syndrome calculation circuit, configured to calculate a first set of FEC syndromes for groups of symbols that are equal to respective rows of symbols in a de-interleaved format;

a second syndrome calculation circuit, configured to calculate a second set of FEC syndromes for groups of symbols that are equal to respective columns of the symbols in the de-interleaved format;

a decoding circuit configured to;

arrange the symbols into windows, each window including a plurality of sequential rows and a plurality of sequential columns of the symbols in the de-interleaved format;

place N of the windows in a group; and

perform M decoding iterations of the windows in the group, in each decoding iteration the decoding circuit is configured to;

perform FEC decoding of rows of each of the windows in the group using the first set of FEC syndromes; and

after the FEC decoding of rows of each of the windows in the group, perform FEC decoding of columns of each of the windows in the group using the second set of FEC syndromes.

2. The circuit of claim 1, further comprising:

a formatting circuit coupled to the first and second syndrome calculation circuits and configured to;

arrange a set of symbols from an interleaved format into a row-aligned format, wherein each row of the set of symbols in the row-aligned format includes data symbols in a respective one of the groups of symbols equal to respective rows of the symbols in the de-interleaved format; and

arrange the set of symbols from the interleaved format into a column-aligned format, wherein each row of the set of symbols in the column-aligned format includes symbols in a respective one of the groups of the symbols equal to respective columns of the symbols in the de-interleaved format.

3. The circuit of claim 1, wherein the decoding circuit is further configured to, after the M decoding iterations of the windows in the group and in response to receiving an additional window:

remove one of the windows from an end of the group;

add the additional window to a front of the group; and

perform the M decoding iterations of the windows in the group.

4. The circuit of claim 1, wherein the decoding circuit includes a syndrome update circuit configured to, in each decoding iteration:

in response to completing the FEC decoding of rows of each of the windows in the group and errors remaining in one of the rows;

update a syndrome in the first set of FEC syndromes corresponding to the row including the errors; and

update syndromes in the second set of FEC syndromes; and

in response to completing the FEC decoding of columns of each of windows in the group and errors remaining in one of the columns;

update a syndrome in the second set of FEC syndromes corresponding to the column including the errors; and

update syndromes in the first set of FEC syndromes.

5. The circuit of claim 1, wherein the decoding circuit includes a plurality of FEC decoding circuits that are configured to, in each of the M decoding iterations, perform FEC decoding on the windows in the group in parallel.

6. The circuit of claim 1, wherein the decoding circuit includes:

a first memory circuit configured to store locations of the rows determined to be in error; and

a second memory circuit configured to store locations of the columns determined to be in error.

7. The circuit of claim 6, further comprising a correction circuit coupled to the first and second memories and configured to:

in response to a window being removed from the group of windows, correcting symbols of the window determined to be in error using the locations of rows and columns determined to be in error that are stored in the first and second memories.

8. The circuit of claim 7, wherein the correction circuit includes:

a first error-to-bit mapping circuit configured to, in response to a window being removed from the group of windows, generate a first error matrix of the window in the row-aligned format using the locations of rows determined to be in error that are stored in the first memory; and

a second error-to-bit mapping circuit configured to, in response to the window being removed from the group of windows, generate a second error matrix of the window in the column-aligned format using the locations of rows determined to be in error that are stored in the first memory.

9. The circuit of claim 8, wherein the correction circuit further includes:

a formatting circuit coupled to the first and second error-to-bit mapping circuits and configured to reformat the first and second error matrices into the interleaved format;

a combining circuit coupled to the formatting circuit and configured to combine the first and second error matrices to produce a combined error matrix in the interleaved format; and

a XOR circuit configured to correct bits in each window using a combined error matrix corresponding to the window.

10. A method for forward error correction (FEC) decoding, comprising:

receiving a first plurality of symbols in an interleaved format;

determining, by a first syndrome calculation circuit, a first set of FEC syndromes for respective groups of the data symbols corresponding to respective rows of the symbols in a de-interleaved format;

determining, by a second syndrome calculation circuit, a second set of FEC syndromes for respective groups of the data symbols corresponding to respective columns of the symbols in the de-interleaved format;

using the first and second sets of FEC syndromes, performing FEC decoding of windows of the symbols by a decoding circuit, each window including a plurality of sequential rows of the symbols in the de-interleaved format and a plurality of sequential columns of the symbols in the de-interleaved format, the FEC decoding of the windows of the symbols including;

placing N of the windows in a group; and

performing M decoding iterations of the windows in the group, each decoding iteration including;

performing FEC decoding of rows of each window in the group; and

after the FEC decoding of rows of each window in the group, performing FEC decoding of columns of each window in the group.

11. The method of claim 10, wherein the FEC decoding of the windows of the symbols further includes, after the M decoding iterations of the windows in the group, in response to receiving an additional window:

removing one of the windows from an end of the group;

adding the additional window to the front of the group; and

performing the M decoding iterations of the windows in the group.

12. The method of claim 10, wherein the M decoding iterations of the windows in the group further includes:

in response to completing the FEC decoding of rows of each of the windows in the group and errors remaining in one of the rows;

updating a syndrome in the first set of FEC syndromes corresponding to the row including the errors; and

updating syndromes in the second set of FEC syndromes; and

in response to completing the FEC decoding of columns of each of the windows in the group and errors remaining in one of the columns;

updating a syndrome in the second set of FEC syndromes corresponding to the column including the errors; and

updating syndromes in the first set of FEC syndromes.

13. The method of claim 12, further comprising:

after performing one or more decoding iterations of a window in the group,

resetting one or more of the updated syndromes in the first and second set of FEC syndromes, corresponding to rows and columns of the window, to the syndromes of the determined first and second sets of EC syndromes.

14. The method of claim 10, wherein for each of the M decoding iterations of the windows in the group, FEC decoding is performed on the windows in the group in parallel.

15. The method of claim 10, wherein:

the performing FEC decoding of rows of each of the windows in the group includes storing locations of the rows determined to be in error in a first memory; and

the performing FEC decoding of columns of each of the windows in the group includes storing locations of the columns determined to be in error in a second memory.

16. The method of claim 15, further comprising:

in response to removing a window from the group of windows, correcting symbols of the window determined to be in error using the locations of rows and columns determined to be in error that are stored in the first and second memories.

17. The method of claim 10, wherein the determining of the first and second sets of FEC syndromes includes:

formatting the symbols from the interleaved format into a row-aligned format, wherein each row of the symbols in the row-aligned format includes symbols equal to symbols in a corresponding row in the de-interleaved format; and

formatting the symbols from the interleaved format into a column-aligned format, wherein each row of the symbols in the column-aligned format includes symbols equal to symbols in a corresponding row in the de-interleaved format.

18. The method of claim 10, wherein:

the determining the first set of FEC syndromes for respective groups of the symbols corresponding to respective rows of the symbols in the de-interleaved format includes;

formatting the symbols from the interleaved format into a row-aligned format, wherein each row of the symbols in the row-aligned format includes symbols equal to symbols in a corresponding row in the de-interleaved format; and

determining FEC syndromes for respective rows of the symbols in the row-aligned format; and

the determining the second set of FEC syndromes for respective groups of the symbols corresponding to respective columns of the symbols in the de-interleaved format includes;

formatting the symbols from the interleaved format into a column-aligned format, wherein each row of the symbols in the column-aligned format includes symbols equal to symbols in a corresponding row in the de-interleaved format; and

determining FEC syndromes for respective rows of the symbols in the column-aligned format.

19. A method for forward error correction (FEC) encoding, comprising:

receiving a data block of symbols in an interleaved format;

adjusting a rate of the data block of symbols;

adding a plurality of symbols including zero padding bits to the data block of symbols in the interleaved format;

determining, by a first syndrome calculation circuit, a first set of FEC syndromes for respective groups of the symbols in the data block corresponding to respective rows of the symbols in a de-interleaved format;

determining, by a second syndrome calculation circuit, a second set of FEC syndromes for respective groups of the symbols of the data block corresponding to respective columns of the symbols in the de-interleaved format;

using the first and second sets of FEC syndromes, performing FEC decoding of windows of the symbols by a decoding circuit, each window including a plurality of sequential rows of the symbols in the de-interleaved format and a plurality of sequential columns of the symbols in the de-interleaved format, the FEC decoding of the windows of the symbols including;

placing N of the windows in a group; and

performing M decoding iterations of the windows in the group, each decoding iteration including;

performing FEC decoding of rows of each window in the group; and

after the FEC decoding of rows of each window in the group, performing FEC decoding of columns of each window in the group.

20. The method of claim 19, wherein:

the FEC decoding of the windows of the symbols further includes, after the M decoding iterations of the windows in the group, in response to receiving an additional window;

removing one of the windows from an end of the group;

adding the additional window to a front of the group; and

performing the M decoding iterations of the windows in the group; and

the FEC decoding of rows and columns of each of the windows in the group includes;

storing locations of the rows and columns determined to be in error in a memory; and

in response to removing a window from the group of windows;

generating an error matrix for the window determined to be in error using the locations of rows and columns in error that are stored in the memory;

removing bits of the error matrix corresponding to the zero-padding bits to produce a modified error matrix;

adjusting the rate of the error matrix to match the rate at which the data block of symbols is received; and

correcting bits in error of the received data block of symbols using the error matrix.