Method and apparatus for encoding and decoding data in memory system

Patent metadata

Field	Value
Publication number	US-11115055-B2
Application number	US-201916244944-A
Country	US
Kind code	B2
Filing date	Jan 10, 2019
Priority date	Jan 10, 2019
Publication date	Sep 7, 2021
Grant date	Sep 7, 2021

Abstract

A decoding circuit includes a Bose-Chaudhuri-Hocquenghem (BCH) decoder. The BCH decoder includes a Syndrome stage for generating syndromes based on a BCH encoded word, a Berlekamp-Massey (BM) stage performing a Berlekamp-Massey algorithm on the syndromes to generate Error Location Polynomial (ELP) coefficients, a Chien stage that performs a Chien search on the ELP coefficients using a Fast Fourier Transform (FFT) to generate error bits and iteration information, and a Frame Fixer stage configured to reorder the error bits to be sequential based on the iteration information. The BCH decoder decodes the BCH encoded word using the reordered error bits.

First claim

What is claimed is:

1. A decoding circuit for performing an error correction in a memory system, the decoding circuit comprising:
a Bose-Chaudhuri-Hocquenghem (BCH) decoder comprising:
a Syndrome stage for generating syndromes based on a BCH encoded word stored in the memory system;

a Berlekamp-Massey (BM) stage performing a Berlekamp-Massey algorithm on the syndromes to generate Error Location Polynomial (ELP) coefficients;
a Chien stage that performs a Chien search on the ELP coefficients using a Fast Fourier Transform (FFT) circuit to generate error bits and iteration information, wherein the Chien stage includes a first FFT stage operating on the ELP coefficients and a counter, and
a Frame Fixer stage configured to reorder the error bits to be sequential based on the iteration information output from the counter incremented for each iteration of the first FFT stage,
wherein the BCH decoder performs the error correction on data of the BCH encoded word using the reordered error bits.

2. The decoding circuit of claim 1 , wherein the Chien Stage comprises:
a second FFT stage iteratively performing an FFT operation on an output of the first FFT stage; and
a logic circuit configured to generate the error bits from an output of the second FFT stage.

3. The decoding circuit of claim 1 , further comprising:
a hard decision buffer;
a soft decision buffer; and
an input control circuit configured to store the BCH encoded word as hard decision bits in the hard decision buffer for output to the BCH decoder and store soft decision bits in the soft decision buffer indicating reliability of bits of the BCH encoded word.

4. The decoding circuit of claim 3 , wherein the decoding circuit performs the error correction of the BCH encoded word additionally using the soft decision bits.

5. The decoding circuit of claim 3 , further comprising a delta syndrome memory storing delta-syndromes and the BCH decoder performs the error correction on the data the BCH encoded word additionally using the stored delta-syndromes.

6. The decoding circuit of claim 5 , further comprising a Delta-Syndrome calculator, where a result of decoding the BCH encoded word successfully by the BCH decoder is output to the Delta-Syndrome Calculator for calculating the delta-syndromes.

7. The decoding circuit of claim 5 , further comprising a Reed-Solomon decoder to correct at least one of the delta-syndromes stored in the delta syndrome memory.

8. The decoding circuit of claim 3 , wherein the BCH decoder reads the soft decision bits from the soft decision buffer, and the BCH decoder flips one or more bits of the hard decision bits corresponding to bits of the soft decision bits with low reliability based on a certain probability.

9. The decoding circuit of claim 8 , further comprising a pseudo random number generator generating a pseudo-random number and the certain probability is generated from the pseudo-random number.

10. The decoding circuit of claim 1 , further comprising an output buffer configured to store a certain amount of data output by the BCH decoder at a predetermined rate.

11. The decoding circuit of claim 10 , wherein the output buffer comprises:
an even memory comprising a plurality of first rows configured to each store three times the certain amount of data output; and
an odd memory comprising a plurality of second rows configured to each store three times the certain amount of data output,
wherein the BCH decoder continues to output additional first data to the even memory until the even memory is full and then begins outputting additional second data to the odd memory.

12. The decoding circuit of claim 11 , wherein the output buffer further comprises:
a plurality of 2 to 1 first multiplexers, where each first multiplexer receives one bit of the even memory and one bit of the odd memory to output three times the certain amount of data output; and
a FIFO configured to receive outputs of the first multiplexers.

13. The decoding circuit of claim 12 , the output buffer further comprising:
a plurality of 60 to 1 multiplexers receiving an output from the FIFO;
a buffer comprising a first part storing a first half of data output by the 60 to 1 multiplexers and a second part storing a second half of the data output by the 60 to 1 multiplexers; and
a plurality of 2 to 1 second multiplexers, where each second multiplexer receives one bit from the first part and one bit from the second part.

14. A method for preforming an error correction in a memory system, the method comprising:
generating syndromes based on a Bose-Chaudhuri-Hocquenghem (BCH) encoded word stored in the memory system;
performing a Berlekamp-Massey algorithm on the syndromes to generate Error Location Polynomial (ELP) coefficients;
performing a Chien search on the ELP coefficients using a Fast Fourier Transform (FFT) circuit to generate error bits and iteration information;
reordering the error bits to be sequential based on the iteration information; and
performing the error correction on data of the BCH encoded word using the reordered error bits,
wherein the FFT circuit includes a first FFT stage iteration operating on the ELP coefficients and the iteration information is generated from an output of a counter incremented for each iteration of the first FFT stage.

15. The method of claim 14 , wherein performing the Chien search comprises:
using a second FFT stage of the FFT circuit to iteratively perform an operation on an output of the first FFT stage; and
generating the error bits from an output of the second FFT stage.

16. A decoding circuit for performing an error correction in a memory system, the decoding circuit comprising:
a Bose-Chaudhuri-Hocquenghem (BCH) decoder comprising:
a Syndrome stage for generating syndromes based on a BCH encoded Word stored in the memory system;
a Berlekamp-Massey (BM) stage performing a Berlekamp-Massey algorithm on the syndromes to generate Error Location Polynomial (ELP) coefficients;
a first Fast Fourier Transform (FFT) stage iteratively performing a first FFT operation on the ELP coefficients to generate first results;

a second FFT stage iteratively performing a second FFT operation on the first results to generate second results; and
a logic circuit configured to generate error bits from the second results, generate iteration information from an output of a counter incremented for each iteration of the first FFT stage, and reorder the error bits based on the iteration information,
wherein the BCH decoder performs the error correction on data of the BCH encoded word using the reordered error bits.

17. The decoding circuit of claim 16 , further comprising:
a hard decision buffer;
a soft decision buffer; and
an input control circuit configured to store the BCH encoded word as hard decision bits in the hard decision buffer for output to the BCH decoder and soft decision bits in the soft decision buffer indicating reliability of bits of the BCH encoded word.

18. The decoding circuit of claim 17 , wherein the BCH decoder reads the soft decision bits from the soft decision buffer, and the BCH decoder flips one or more bits of the hard decision bits corresponding to bits of the soft decision bits with low reliability based on a certain probability.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Doubchak Ariel
• Shapiro Dikla
• Berman Amit

Classifications

• H03M13/153

  using the Berlekamp-Massey algorithm · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• H03M13/152 Primary

  Bose-Chaudhuri-Hocquenghem [BCH] codes · CPC title

• G06F11/1068 Primary

  in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence) · CPC title

• H03M13/2927

  Decoding strategies · CPC title