Systems and methods for error correction and decoding on multi-level physical media

• US 8,782,500 B2
• Filed: 01/21/2013
• Issued: 07/15/2014
• Est. Priority Date: 12/12/2007
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: DensBits Technologies Ltd. (Broadcom, Inc.)
• Inventors: Weingerten, Hanan
• Primary Examiner(s): Wilson, Yolanda L
• Application Number:
  US13/746,072
• Publication Number:
  US 20130139037A1
• Time in Patent Office: 540 Days
• Field of Search: 714/752, 714/763, 714/777
• US Class Current: 714/785
• CPC Class Codes: A61K 36/8962 Allium, e.g. garden onion, leek, garlic or chives
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/6566 Implementations concerning memory access contentions

Abstract

Apparatus and methods for operating a flash device characterized by use of Lee distance based codes in a flash device so as to increase the number of errors that can be corrected for a given number of redundancy cells, compared with Hamming distance based codes.

Claims

1. A method for operating a flash device, said method comprising:

reading, from flash memory cells the flash device, data symbols and redundancy symbols;

calculating syndrome symbols based on the redundancy symbols;

calculating estimated syndrome symbols based on at least the data symbols;

calculating differences between the syndrome symbols and corresponding estimated syndrome symbols to provide error syndromes; and

calculating corrected data symbols in response to the data symbols, the error syndromes;

wherein the calculating of the corrected data symbols involves calculating Lee distances.

2. The method according to claim 1, wherein the calculating of the estimated syndrome symbols is based only on the data symbols.

3. The method according to claim 2, wherein the calculating of the syndrome symbols comprises applying a sequence of operations that comprise de-mapping, Bose Chaudhuri Hocquengham (BCH) decoding and mapping;

and wherein the calculating of the estimated syndrome symbols comprises syndrome computation.

4. The method according to claim 3 wherein each flash memory cell of the flash memory cells stores up to L distinctive levels of charge;

wherein if L differs from a power of two the de-mapping comprises de-encapsulating the redundancy symbols.

5. The method according to claim 1, wherein the calculating of the estimated syndrome symbols is based on the data symbols and on redundancy bits stripped from the redundancy symbols.

6. The method according to claim 5, wherein the calculating of the syndrome symbols comprises applying a sequence of operations that comprises de-mapping, Bose Chaudhuri Hocquengham (BCH) decoding and mapping;

and

wherein the calculating of the estimated syndrome symbols comprises demapping and syndrome computation.

7. The method according to claim 1, wherein the calculating of the estimated syndrome symbols is based on the data symbols and on the redundancy symbols.

8. The method according to claim 7 wherein the calculating of the estimated syndrome symbols comprises syndrome computation;

and

wherein the calculating of the syndrome symbols comprises applying a sequence of operations that comprises de-mapping, Bose Chaudhuri Hocquengham (BCH) decoding, mapping and multiplication by a Galois matrix;

wherein elements of the Galois matrix are powers of alpha, alpha being a non-zero primitive element of a Galois field in which the data symbols and the redundency symbols are elements.

9. The method according to claim 8 wherein r is a row index r, c is a column index, t being a number of data symbols, w being a number of redundancy syndromes, wherein r and c range between zero and (w−

1), an element of the Galois matrix that belong to a r'"'"'th row and a c'"'"'th column of the Galois matrix equals alpha by a power of (t+c)*r.

10. The method according to claim 8 wherein r is a row index r, c is a column index, t being a number of data symbols, n′

is a number of data bits that are represented by the data symbols, being a number of redundancy syndromes, wherein r and c range between zero and (w−

1), an element of the Galois matrix that belong to a r'"'"'th row and a c'"'"'th column of the Galois matrix equals alpha by a power of (t+c+n′

)*r.

11. The method according to claim 7 wherein the calculating of the estimated syndrome symbols comprises demapping and syndrome computation;

and

wherein the calculating of the syndrome symbols comprises applying a sequence of operations that comprises de-mapping, Bose Chaudhuri Hocquengham (BCH) decoding, mapping and multiplication by a Galois matrix;

wherein elements of the Galois matrix are powers of alpha, alpha being a non-zero primitive element of a Galois field in which the data symbols and the redundency symbols are elements.

12. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps of:

reading, from flash memory cells the flash device, data symbols and redundancy symbols;

calculating syndrome symbols based on the redundancy symbols;

calculating estimated syndrome symbols based on at least the data symbols;

calculating differences between the syndrome symbols and corresponding estimated syndrome symbols provide error syndromes; and

calculating corrected data symbols in response to the data symbols, the error syndromes;

wherein the calculating of the corrected data symbols involves calculating Lee distances.

13. A decoder comprising:

a first circuit for calculating syndrome symbols based on redundancy symbols read from a flash memory array;

a second circuit for calculating estimated syndrome symbols based on at least data symbols read from the flash memory array;

a subtraction unit arranged to calculate differences between the syndrome symbols and corresponding estimated syndrome symbols to provide error syndromes; and

a recovery block that is arranged to calculate corrected data symbols in response to the data symbols, the error syndromes by calculating Lee distances.

14. The decoder according to claim 13, wherein the calculating of the estimated syndrome symbols is based only on the data symbols.

15. The decoder according to claim 13, wherein the first circuit comprises a de-mapper, a Bose Chaudhuri Hocquengham (BCH) decoder and a mapper;

and wherein the second circuit comprises a syndrome computation unit.

16. The decoder according to claim 15 wherein each flash memory cell of the flash memory cells stores up to L distinctive levels of charge;

wherein if L differs from a power of two then de-mapper is arranged to de-encapsulate the redundancy symbols.

17. The decoder according to claim 13, wherein the calculating of the estimated syndrome symbols is based on the data symbols and on redundancy bits stripped from the redundancy symbols.

18. The decoder according to claim 17, wherein the first circuit comprises a de-mapper, a Bose Chaudhuri Hocquengham (BCH) decoder and a mapper;

and wherein the second circuit comprises another de-mapper and a syndrome computation unit.

19. The decoder according to claim 13, wherein the calculating of the estimated syndrome symbols is based on the data symbols and on the redundancy symbols.

20. The decoder according to claim 19 wherein the second circuit comprises a syndrome computation unit;

and

wherein the first circuit comprises a de-mapper, a Bose Chaudhuri Hocquengham (BCH) decoder, a mapper and a matrix multiplier;

wherein the matrix multiplier is arranged to receive symbols from the mapper and to multiply the symbols by a Galois matrix;

wherein elements of the Galois matrix are powers of alpha, alpha being a non-zero primitive element of a Galois field in which the data symbols and the redundency symbols are elements.

21. The decoder according to claim 20 wherein r is a row index r, c is a column index, t being a number of data symbols, w being a number of redundancy syndromes, wherein r and c range between zero and (w−

1), an element of the Galois matrix that belong to a r'"'"'th row and a c'"'"'th column of the Galois matrix equals alpha by a power of (t+c)*r.

22. The decoder according to claim 19 wherein the first circuit comprises a de-mapper, a Bose Chaudhuri Hocquengham (BCH) decoder, a mapper and a matrix multiplier;

wherein the second circuit comprises another de-mapper and a syndrome computation unit;

wherein the matrix multiplier is arranged to receive symbols from the mapper and to multiply the symbols by a Galois matrix;

wherein elements of the Galois matrix are powers of alpha, alpha being a non-zero primitive element of a Galois field in which the data symbols and the redundancy symbols are elements.

23. The decoder according to claim 22 wherein r is a row index r, c is a column index, t being a number of data symbols, n′

is a number of data bits that are represented by the data symbols, being a number of redundancy syndromes, wherein r and c range between zero and (w−

1), and an element of the Galois matrix that belong to a r'"'"'th row and a c'"'"'th column of the Galois matrix equals alpha by a power of (t+c+n′

)*r.