On-the-fly syndrome and syndrome weight computation architecture for LDPC decoding

Patent metadata

Field	Value
Publication number	US-9768807-B2
Application number	US-201514840821-A
Country	US
Kind code	B2
Filing date	Aug 31, 2015
Priority date	Aug 31, 2015
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

A decoder includes syndrome storage and a first barrel shifter configured to bit-shift hard decision bit data to generate shifted data that is aligned with a set of syndromes from the syndrome storage. The decoder also includes a first syndrome update circuit coupled to the first barrel shifter and configured to process the set of syndromes based on the shifted data to generate an updated version of the set of syndromes. The decoder may also be configured to perform on-the-fly syndrome weight computation.

First claim

What is claimed is:

1. A data storage device comprising:
a non-volatile memory; and
a controller coupled to the non-volatile memory and including a decoder configured to perform a decoding operation using codeword data read from the non-volatile memory,
wherein the decoder includes:
syndrome storage;
multiple barrel shifters including a first barrel shifter configured to bit-shift hard decision bit data to generate shifted data that is aligned with a set of syndromes from the syndrome storage;
multiple syndrome update circuits including a first syndrome update circuit coupled to the first barrel shifter and configured to process the set of syndromes based on the shifted data to generate an updated version of the set of syndromes;
a first set of multiplexors configured to route sets of syndromes from the syndrome storage to the syndrome update circuits; and
a second set of multiplexors configured to route updated versions of the sets of syndromes from the syndrome update circuits to the syndrome storage.

2. The data storage device of claim 1 , wherein the decoder further includes a syndrome weight update circuit coupled to the first syndrome update circuit.

3. The data storage device of claim 2 , wherein the syndrome weight update circuit includes adding circuitry coupled to each of the syndrome update circuits, the adding circuitry configured to determine a number of the syndromes that change from an initial value in a clock cycle of the decoder.

4. The data storage device of claim 3 , wherein the adding circuitry includes:
multiple summers coupled to the syndrome update circuits; and
an adder tree coupled to outputs of the summers.

5. The data storage device of claim 3 , wherein the decoder further includes:
a computation circuit coupled to the adding circuitry; and
a syndrome weight register coupled to the computation circuit, the computation circuit configured to determine an updated syndrome weight value based on the number of the syndromes that change and based on a syndrome weight value at the beginning of the clock cycle.

6. The data storage device of claim 5 , wherein the computation circuit is further configured to determine the updated syndrome weight value further based on a count of hard decision bits that have changed values.

7. The data storage device of claim 2 , wherein the syndrome weight update circuit includes first circuitry coupled to an input of a pipeline register and second circuitry coupled to an output of the pipeline register.

8. The data storage device of claim 1 , wherein:
the decoder includes a first number of the barrel shifters,
the decoder includes a second number of the syndrome update circuits, and wherein
the second number equals the first number.

9. A data storage device comprising:
a non-volatile memory; and
a controller coupled to the non-volatile memory and including a decoder configured to perform a decoding operation using codeword data read from the non-volatile memory,
wherein the decoder includes:
syndrome storage;
multiple barrel shifters including a first barrel shifter configured to bit-shift hard decision bit data to generate shifted data that is aligned with a set of syndromes from the syndrome storage;
multiple syndrome update circuits including a first syndrome update circuit coupled to the first barrel shifter and configured to process the set of syndromes based on the shifted data to generate an updated version of the set of syndromes; and
a syndrome weight update circuit including adding circuitry coupled to each of the syndrome update circuits, the adding circuitry configured to determine, for a clock cycle of the decoder, a number of the syndromes that change value during the clock cycle.

10. The data storage device of claim 9 , wherein:
the decoder includes a first number of the barrel shifters,
the decoder includes a second number of the syndrome update circuits, and
the second number equals the first number.

11. The data storage device of claim 9 , wherein the adding circuitry includes:
multiple summers coupled to the syndrome update circuits; and
an adder tree coupled to outputs of the summers.

12. The data storage device of claim 9 , wherein:
the decoder further includes:
a computation circuit coupled to the adding circuitry; and
a syndrome weight register coupled to the computation circuit, and

the computation circuit is configured to determine an updated syndrome weight value based on the number and based on a syndrome weight value corresponding to the beginning of the clock cycle.

13. The data storage device of claim 12 , wherein the computation circuit is further configured to determine the updated syndrome weight value further based on a count of hard decision bits that change value during the clock cycle.

14. The data storage device of claim 9 , wherein the decoder further includes:
a first set of multiplexors configured to route sets of syndromes from the syndrome storage to the syndrome update circuits; and
a second set of multiplexors configured to route updated versions of the sets of syndromes from the syndrome update circuits to the syndrome storage.

15. The data storage device of claim 9 , wherein the syndrome weight update circuit further includes:
first circuitry coupled to an input of a pipeline register; and
second circuitry coupled to an output of the pipeline register.

16. An apparatus comprising:
means for non-volatile storage; and
means for controlling the means for non-volatile storage, the means for controlling including means for decoding using codeword data read from the means for non-volatile storage,
wherein the means for decoding includes:
means for syndrome storage;
multiple means for barrel shifting including a first means for barrel shifting configured to bit-shift hard decision bit data to generate shifted data that is aligned with a set of syndromes from the means for syndrome storage;
multiple means for syndrome updating including a first means for syndrome updating configured to process the set of syndromes based on the shifted data to generate an updated version of the set of syndromes, the first means for syndrome updating coupled to the first means for barrel shifting; and
means for updating a syndrome weight including means for adding coupled to each of the means for syndrome updating, the means for adding configured to determine, for a clock cycle of the means for decoding, a number of the syndromes that change value during the clock cycle.

17. The apparatus of claim 16 , wherein:
the means for decoding includes a first number of the means for barrel shifting,
the means for decoding includes a second number of the means for syndrome updating, and
the second number equals the first number.

18. The apparatus of claim 16 , wherein the means for adding includes:
multiple means for summing coupled to the multiple means for syndrome updating; and
means for adding using a tree structure, the means for adding coupled to outputs of the multiple means for summing.

19. The apparatus of claim 16 , wherein the means for decoding further includes means for determining an updated syndrome weight value based on the number of the syndromes that change and based on a syndrome weight value at the beginning of the clock cycle.

20. The apparatus of claim 16 , wherein the means for decoding further includes:
a first set of means for multiplexing configured to route sets of syndromes from the means for syndrome storage to the multiple means for syndrome upda

Assignees

• Sandisk Technologies Inc
• Sandisk Technologies Llc

Inventors

• Zhang Xinmiao
• Ryabinin Yuri
• Sharon Eran

Classifications

• H03M13/1128

  Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations · CPC title

• H03M13/1575 Primary

  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 title

• G06F11/1068

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

• H03M13/658 Primary

  Scaling by multiplication or division · CPC title

• G11C29/52

  Protection of memory contents; Detection of errors in memory contents · CPC title