AREA EFFICIENT IMPLEMENTATION OF A PRODUCT CODE ERROR CORRECTING CODE DECODER

• US 20190312600A1
• Filed: 04/10/2018
• Published: 10/10/2019
• Est. Priority Date: 04/10/2018
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Khayat, Patrick R., Parthasarathy, Sivagnanam, Doru, Shantilal, Richardson, Nicholas J.
• Granted Patent: US 10,439,648 B1
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence

Abstract

A method and system for implementing error correcting code using a product code decoder. The method and system receive a product code, wherein the product code is a matrix of row and column component codes, generate a plurality of row syndromes column syndromes from the received product code, store the plurality of row syndromes in a row syndrome queue, store the plurality of column syndromes in a column syndrome queue, the column and row syndrome queue to support the plurality of modes of operation corresponding to the plurality of phases of decoding the product code, correct the plurality of row syndromes and columns syndromes in the row and column syndrome queues based on errors detected in respective row and column syndromes and errors detecting in overlapping syndromes, and correct the product code in a codeword buffer at locations corresponding to corrections in the plurality of row syndromes and the plurality of column syndromes.

Claims

1. A method for implementing error correcting code (ECC) using a product code decoder, the method comprising:

receiving a product code, wherein the product code is a matrix of row and column component codes;

generating a plurality of row syndromes and a plurality of column syndromes from the received product code;

storing the plurality of row syndromes in a row syndrome queue, the row syndrome queue to support a plurality of modes of operation corresponding to a plurality of phases of decoding the product code;

storing the plurality of column syndromes in a column syndrome queue, the column syndrome queue to support the plurality of modes of operation corresponding to the plurality of phases of decoding the product code;

correcting the plurality of row syndromes in the row syndrome queue based on errors detected in respective row syndromes and errors detecting in overlapping column syndromes;

correcting the plurality of column syndromes in the column syndrome queue based on errors detected in respective column syndromes and errors detected in overlapping row syndromes; and

correcting the product code in a codeword buffer at locations corresponding to corrections in the plurality of row syndromes and the plurality of column syndromes.

2. The method of claim 1, wherein the row syndrome queue stores the plurality of row syndromes by storing each received row syndrome in a register of a plurality of registers in the row syndrome queue and shifting stored row syndromes in the plurality of registers to prepare to receive a next row syndrome.

3. The method of claim 1, further comprising:

decoding each column syndrome in the plurality of column syndromes to generate corrected column syndromes and row adjustments for row syndromes from the plurality of row syndromes in the row syndrome queue.

4. The method of claim 3, further comprising:

combining a plurality of the row adjustments with the plurality of row syndromes in the row syndrome queue by combination logic of the row syndrome queue on a single clock cycle.

5. The method of claim 1, further comprising:

decoding each row syndrome in the plurality of row syndromes to generate corrected row syndromes and adjustments for column syndromes from the plurality of column syndromes.

6. The method of claim 1, further comprising:

clearing a row syndrome from the plurality of row syndromes in the row syndrome queue in response to a correction of the row syndrome.

7. The method of claim 1, further comprising:

processing the plurality of row syndromes and the plurality column syndromes iteratively to correct errors in the product code with each row syndrome or column syndrome correction being corrected in a location in a row and column of the product code, the iterative processing rotating the plurality of row syndromes in the row syndrome queue and the plurality of column syndromes in the column syndrome queue into a component decoder and continuing until all rows and columns of the product code are corrected.

8. A product code decoder comprising:

a codeword buffer to store a received product code that is a matrix of row and column component codes;

a row syndrome generator to generate a plurality of row syndromes from the received product code;

a column syndrome generator to generate a plurality of column syndromes from the received product code;

a row syndrome queue having a plurality of registers to store the plurality of row syndromes, the row syndrome queue to support a plurality of modes of operation corresponding to a plurality of phases of decoding the product code;

a column syndrome queue having a plurality of register to store the plurality of column syndromes, the column syndrome queue to support the plurality of modes of operation corresponding to the plurality of phases of decoding the product code;

and

a component code decoder coupled to the codeword buffer, row syndrome generator, and column syndrome generator, the component code decoder to correct the plurality of row syndromes in the row syndrome queue based on errors detected in respective row syndromes and errors detecting in overlapping column syndromes, to correct the plurality of column syndromes in the column syndrome queue based on errors detected in respective column syndromes and errors detected in overlapping row syndromes, and

to identify locations in the product code in the codeword buffer corresponding to corrections in the plurality of row syndromes and the plurality of column syndromes.

9. The product code decoder of claim 8, wherein the row syndrome queue stores the plurality of row syndromes by storing each received row syndrome in a register of the plurality of registers and shifting stored row syndromes in the plurality of registers to prepare to receive a next row syndrome.

10. The product code decoder of claim 8, wherein the component code decoder is to decode each column syndrome in the plurality of column syndromes to generate corrected column syndromes and row adjustments for row syndromes from the plurality of row syndromes in the row syndrome queue.

11. The product code decoder of claim 10, wherein the row syndrome queue is coupled to the component code decoder to combine a plurality of the row adjustments with the plurality of row syndromes in the row syndrome queue by combination logic of the row syndrome queue on a single clock cycle.

12. The product code decoder of claim 8, wherein the component code decoder is to decode each row syndrome in the plurality of row syndromes to generate corrected row syndromes and adjustments for column syndromes from the plurality of column syndromes.

13. The product code decoder of claim 8, wherein the component code decoder is to clear a row syndrome from the plurality of row syndromes in a row syndrome queue in response to a correction of the row syndrome.

14. The product code decoder of claim 8, wherein the component code decoder is to process the plurality of row syndromes and the plurality column syndromes iteratively to correct errors in the product code with each row syndrome or column syndrome correction being corrected in a location in a row and column of the product code, the iterative processing rotating the plurality of row syndromes in the row syndrome queue and the plurality of column syndromes in the column syndrome queue into a component decoder and continuing until all rows and columns of the product code are corrected.

15. A memory system comprising:

a set of memory elements to store data;

a host interface to receive a request to store or access data in the set of memory elements; and

a memory controller including error code correction utilizing a product code decoder, the product code decoder including,

a codeword buffer to store a received product code that is a matrix of row and column component codes,

a row syndrome generator to generate a plurality of row syndromes from the received product code,

a column syndrome generator to generate a plurality of column syndromes from the received product code,

a row syndrome queue having a plurality of registers to store the plurality of row syndromes, the row syndrome queue to support a plurality of modes of operation corresponding to a plurality of phases of decoding the product code,

a column syndrome queue having a plurality of register to store the plurality of column syndromes, the column syndrome queue to support the plurality of modes of operation corresponding to the plurality of phases of decoding the product code, and

a component code decoder coupled to the codeword buffer, row syndrome generator, and column syndrome generator, the component code decoder to correct the plurality of row syndromes in the row syndrome queue based on errors detected in respective row syndromes and errors detecting in overlapping column syndromes, to correct the plurality of column syndromes in the column syndrome queue based on errors detected in respective column syndromes and errors detected in overlapping row syndromes, and to identify locations in the product code corresponding to corrections in the plurality of row syndromes and the plurality of column syndromes.

16. The memory system of claim 15, wherein the row syndrome queue stores the plurality of row syndromes by storing each received row syndrome in a register in the plurality of registers and shifting stored row syndromes in the plurality of registers to prepare to receive a next row syndrome.

17. The memory system of claim 15, wherein the component code decoder is to decode each column syndrome in the plurality of column syndromes to generate corrected column syndromes and row adjustments for row syndromes from the plurality of row syndromes in the row syndrome queue.

18. The memory system of claim 17, wherein the row syndrome queue is coupled to the component code decoder to combine a plurality of the row adjustments with the plurality of row syndromes in the row syndrome queue by combination logic of the row syndrome queue on a single clock cycle.

19. The memory system of claim 15, wherein the component code decoder is to decode each row syndrome in the plurality of row syndromes to generate corrected row syndromes and adjustments for column syndromes from the plurality of column syndromes.

20. The memory system of claim 15, wherein the component code decoder is to process the plurality of row syndromes and the plurality column syndromes iteratively to correct errors in the product code with each row syndrome or column syndrome correction being corrected in a location in a row and column of the product code, the iterative rotating the plurality of row syndromes in the row syndrome queue and the plurality of column syndromes in the column syndrome queue into a component decoder and processing continuing until all rows and columns of the product code are corrected.