US 11,146,293 B2Granted

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

AssigneeInternational Business Machines Corporation

InventorsMilos Stanisavljevic, Thomas Mittelholzer, Nikolaos Papandreou, Charalampos Pozidis

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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.

4 more elements

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.

5 more elements

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.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/813,921Filed 10 Mar 2020
Published: US 2021/0288669 A116 Sep 2021
Granted: 12 Oct 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

H03M 13/1515
Using error location or error correction polynomials: reed-Solomon codes
H03M 13/153
Determination and particular use of error location polynomials: using the Berlekamp-Massey algorithm
H03M 13/154
Using error location or error correction polynomials: error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
H03M 13/1545
Using error location or error correction polynomials: determination of error locations, e.g. Chien search or other methods or arrangements for the…