System and method for optimizing Reed-Solomon decoder for errors and erasures

Patent metadata

Field	Value
Publication number	US-11146293-B2
Application number	US-202016813921-A
Country	US
Kind code	B2
Filing date	Mar 10, 2020
Priority date	Mar 10, 2020
Publication date	Oct 12, 2021
Grant date	Oct 12, 2021

Abstract

A memory system, Reed Solomon (“RS”) Decoder, and method for decoding Reed-Solomon codewords includes: a Syndrome Computation engine configured as a first stage of a pipeline for receiving the RS codeword and computing one or more Syndromes; an initialization unit for providing initialization values for a key equation solver engine that generates the errata locator polynomial and the errata magnitude polynomial configured as a second stage; and as a third stage a Chien Search engine for receiving the error locator polynomial and determining the one or more locations of the one or more erasures and random errors in the received RS codeword and an error-value evaluation (“EE”) engine for receiving the errata magnitude polynomial and determining the one or more magnitudes of the one or more erasures and random errors in the RS received codeword.

First claim

What is claimed is:

1. A Reed-Solomon decoder for decoding Reed-Solomon codewords, the Reed-Solomon decoder comprising:
one or more Syndrome Computation engines for receiving the Reed-Solomon (“RS”) codeword and computing one or more Syndromes;
a key equation solver engine for generating an errata locator polynomial and an errata magnitude polynomial;
one or more initialization units for providing initialization values for the key equation solver engine;
one or more Chien Search engines for receiving the error locator polynomial and determining the one or more locations of the one or more erasures and random errors in the received Reed-Solomon codeword; and
one or more error-value evaluation (“EE”) engines for receiving the errata magnitude polynomial and determining the one or more magnitudes of the one or more erasures and random errors in the RS received codeword,
wherein the Reed-Solomon decoder is configured as a three stage pipeline wherein the one or more Syndrome Computation engines are configured in a first stage, the key equation solver engine and the one or more initialization units are configured as a second stage, and the one or more Chien Search engines and the one or more EE engines are configured as a third stage.

2. The Reed-Solomon decoder of claim 1 , wherein the one or more initialization units are parallelized.

3. The Reed-Solomon decoder of claim 2 , wherein the one or more initialization units are parallelized to calculate the initialization values in a single clock cycle.

4. The Reed-Solomon decoder of claim 2 , wherein the one or more Syndrome Computation engines are parallelized.

5. The Reed-Solomon decoder of claim 3 , wherein the one or more Syndrome Computation engines are parallelized so that the parallelized group of the one or more Syndrome Computation engines computes the one or more Syndromes for the received RS codeword in 2t+1clock cycles, where t is the number of random errors that are correctable in the received RS codeword.

6. The Reed-Solomon decoder of claim 1 , wherein the one or more Chien Search engines are parallelized.

7. The Reed-Solomon decoder of claim 3 , wherein the one or more Chien Search engines are parallelized so that the parallelized group of the one or more Chien Search engines solves the errata locator polynomial in 2t+1 clock cycles, where t is the number of random errors that are correctable in the received RS codeword.

8. The Reed-Solomon decoder of claim 1 , wherein the one or more EE engines are parallelized.

9. The Reed-Solomon decoder of claim 7 , wherein the one or more EE engines are parallelized so that the parallelized group of one or more EE Search engines solves the errata magnitude polynomial in 2t+1 clock cycles, where t is the number of random errors that are correctable in the received RS codeword.

10. The Reed-Solomon decoder of claim 3 , wherein the one or more Chien Search engines and the one or more EE engines are combined in one or more CS/EE units where each combined CS/EE unit shares resources, and the one or more combined SC/EE units are parallelized to solve the errata locator polynomial and the errata magnitude polynomial in 2t+1 clock cycles, where t is the number of random errors that are correctable in the received RS codeword.

11. The Reed-Solomon decoder of claim 5 , wherein the one or more Chien Search engines and the one or more EE engines are combined in one or more CS/EE units where each combined CS/EE unit shares resources, and the one or more combined SC/EE units are parallelized to solve the errata locator polynomial and the errata magnitude polynomial in 2t+1 clock cycles, where t is the number of random errors that are correctable in the received RS codeword.

12. The Reed-Solomon decoder of claim 1 , wherein the Reed-Solomon decoder is on a module containing the memory devices.

13. A memory system comprising:
A memory module comprising a plurality of memory devices, a Reed-Solomon encoder and a Reed Solomon decoder, the Reed Solomon (RS) decoder configured as a three stage pipeline comprising:
one or more Syndrome Computation engines arranged and configured in a first stage of the RS decoder pipeline for receiving the Reed-Solomon (“RS”) codeword and computing the Syndromes;
a key equation solver (KES) engine for generating an errata locator polynomial and an errata magnitude polynomial;
one or more initialization (INIT) units for providing initialization values for the KES engine; wherein the KES engine and one or more INIT units are configured in a second stage of the RS decoder pipeline;
one or more Chien Search (CS) engines for receiving the errata locator polynomial and determining the location of one or more erasures and random errors in the received RS codeword; and

one or more error-value evaluation (“EE”) engines for calculating the magnitude of the erasures and random errors in the received RS codeword, the one or more CS engines and the one or more EE engines are combined in one or more combined CS/EE units where each combined CS/EE unit shares resources, wherein the one or more combined CS/EE units are configured in a third stage of the RS decoder pipeline.

14. The memory system of claim 13 , wherein the one or more INIT units are parallelized to complete in one cycle.

15. The memory system of claim 13 , wherein the second stage of the RS decoder is configured to compute the errata locator polynomial and the errata magnitude polynomial in 2t+1 clock cycles, where t is the number of random errors that are correctable in the RS codeword.

16. The memory system of claim 13 , wherein,
the one or more SC engines are parallelized to complete in CC SC clock cycles where CC SC is the nearest whole integer that is equal to or not less than 2t+1; and
the one or more CS/EE units are parallelized to complete in CC CS/EE clock cycles, where CC SC is the nearest whole integer that is equal to or not less than 2t+1.

17. A method for decoding Reed-Solomon codes for errata including at least one of the group consisting of random errors, erasures, and combinations thereof, the method comprising:
receiving a RS codeword in a first stage of an RS decoder;
in response to receiving the RS codeword, computing one or more Syndromes in the first stage of the RS decoder;
receiving the one or more Syndromes in a second stage of the RS decoder;
in response to receiving the one or more Syndromes, computing an errata locator polynomial and an errata magnitude polynomial in the second stage of the RS decoder;
receiving the errata locator polynomial and the errata magnitude polynomial in a third stage of the RS decoder: and
in response to receiving the errata locator polynomial and the errata magnitude polynomial, computing the errata locations and errata magnitudes.

18. The method of claim 17 , further comprising subtracting the errata locations and errata magnitudes from the RS codeword.

19. The method of claim 17 , wherein the second stage comprises a key equation solver (KES) engine and an initialization (INIT) unit that is combined into a INIT/KES block that computes the errata locator polynomial and the errata magnitude polynomial, wherein the INIT unit is parallelized so that the INIT/KES block computes the errata locator polynomial and the errata magnitude polynomial in 2t+1 clock cycles where t is the number of random errors that are correctable in the RS codeword.

20. The method of claim 19 , wherein the first stage comprises one or more Syndrome Computation (SC) engines to compute the Syndromes, the third sta

Assignees

• IBM

Inventors

• Stanisavljevic Milos
• Mittelholzer Thomas
• Papandreou Nikolaos
• Pozidis Charalampos

Classifications

• H03M13/153

  using the Berlekamp-Massey algorithm · CPC title

• H03M13/1545

  Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial · CPC title

• H03M13/1515 Primary

  Reed-Solomon codes · CPC title

• H03M13/1555

  Pipelined decoder implementations · CPC title

• H03M13/154

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title