Electronic data flash card with bose, ray-chaudhuri, hocquenghem (BCH) error detection/correction

• US 7,962,836 B1
• Filed: 01/24/2007
• Issued: 06/14/2011
• Est. Priority Date: 01/06/2000
• Status: Expired due to Fees

• Current Assignee: Super Talent Technology, Corporation
• Original Assignee: Supertalent Electronics, Inc.
• Inventors: Shen, Ming-Shiang, Ma, Abraham C., Lee, Charles C., Yu, I-Kang
• Primary Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US11/657,243
• Time in Patent Office: 1,602 Days
• Field of Search: 714/781, 714/782
• US Class Current: 714/781
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/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 Class Codes: H03M 13/1575 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

Abstract

A Bose, Ray-Chaudhuri, Hocquenghem (BCH) decoder is employed in non-volatile memory applications for determining the number of errors and locating the errors in a page of information. The decoder includes a syndrome calculator responsive to a sector of information. The sector includes data and overhead, with the data being organized into data sections and the overhead being organized into overhead sections. The syndrome calculator generates a syndrome for each of the data sections. A root finder is coupled to receive the calculated syndrome and to generate at least two roots. A polynomial calculator responds to the two roots and generates at least two error addresses, each identifying a location in the data wherein the error lies.

Claims

1. A non-volatile memory device comprising:

a Bose, Ray-Chaudhuri, Hocquenghem (BCH) decoder including,

a syndrome calculator responsive to a page of information, the page including data and overhead, the data being organized into a plurality of data sections and the overhead being organized into a plurality of overhead sections, the syndrome calculator operative to generate a syndrome for each of the data sections;

a root finder coupled to receive the calculated syndrome and operative to generate at least two roots; and

a polynomial calculator responsive to the at least two roots and operative to generate at least two error addresses, each identifying a location in the data wherein the error lies,

wherein the plurality of data sections is four sections and the root finder generates the at least two roots, Z₁ and Z₂, based upon a Galois Field (GF) (2¹¹) calculation.

2. A non-volatile memory device, as recited in claim 1, wherein the root finder generates the at least two roots, Z₁ and Z₂, based upon the following equations:

Z₁²+Z₁+K=0

and

Z₂²+Z₂+K=0,

wherein ‘

K’

represents a syndrome.

3. A non-volatile memory device, as recited in claim 1, wherein the root finder includes comparison logic for generating the at least two roots.

4. A non-volatile memory device, as recited in claim 1, wherein the comparison logic is made of a plurality of XOR.

5. A non-volatile memory device, as recited in claim 1, wherein the syndrome calculator includes combinatorial shift and comparison logic for generating each syndrome.

6. A non-volatile memory system comprising:

a host system;

at least one flash memory system coupled to store information from the host system; and

an flash controller coupled between the host system and the at least one flash system for transferring information, organized into pages, between the host system and the flash system and including,

a Bose, Ray-Chaudhuri, Hocquenghem (BCH) decoder including,

a syndrome calculator responsive to a page of information, the page including data and overhead, the data being organized into a plurality of data sections and the overhead being organized into a plurality of overhead sections, the syndrome calculator operative to generate a syndrome for each of the data sections;

a root finder coupled to receive the calculated syndrome and operative to generate at least two roots; and

a polynomial calculator responsive to the at least two roots and operative to generate at least two error addresses, each identifying a location in the data wherein the error lies,

wherein the plurality of data sections is four sections and the root finder generates the at least two roots, Z₁ and Z₂, based upon a Galois Field (GF) (2¹¹) calculation.

7. A non-volatile memory system, as recited in claim 6, further including a bus for coupling the controller to the host system wherein the bus operates in conformance with MMC, SD, CF, MS, PCIE, IDE, or SATA standards.

8. A non-volatile memory system, as recited in claim 7, wherein the host system includes a controller for coupling to the bus, wherein the controller operates in conformance with MMC, SD, CF, MS, PCIE, IDE, or SATA standards.

9. A non-volatile memory system, as recited in claim 6, wherein the root finder generates Z₁ and Z₂, based upon the following equations:

Z₁²+Z₁+K=0

and

Z₂²+Z₂+K=0,

wherein ‘

K’

represents a syndrome.

10. A non-volatile memory system, as recited in claim 6, wherein the root finder includes comparison logic for generating the at least two roots.

11. A non-volatile memory system, as recited in claim 6, wherein the comparison logic is made of a plurality of XOR.

12. A non-volatile memory system, as recited in claim 6, wherein the syndrome calculator includes combinatorial shift and comparison logic for generating each syndrome.

13. A method of detecting errors in information stored in non-volatile memory comprising:

calculating a plurality of syndromes, each of the syndromes being calculated for a segment of a page of information stored in the non-volatile memory;

calculating A, B, C using the calculated syndromes, ‘

A’

, ‘

B’ and

‘

C’

collectively represent an error bit value at a particular error location;

determining if the calculated syndromes are equal to each other;

if the calculated syndromes are determined not to be equal to each other;

determining if A, B and C are equal to each other;

if A, B and C are determined to be equal to each other, detecting a single error; and

if A, B and C are determined not to be equal to each other, detecting two errors.

14. A method of detecting errors, as recited in claim 13, further including, if the calculated syndromes are determined to be equal to each other, detecting no errors.

15. A method of detecting errors in information stored in non-volatile memory comprising:

Receiving a page of information, the page including data and overhead, the data being organized into a plurality of data sections and the overhead being organized into a plurality of overhead sections;

generating a syndrome for each of the data sections;

calculating A, B, C using the generated syndromes, ‘

A’

, ‘

B’

, and ‘

C’

collectively represent an error bit value at a particular error location;

if the generated syndromes are determined not to be equal to each other, determining if A, B and C are equal to each other;

if A, B, and C are determined to be equal to each other, detecting a single error; and

if A, B, and C are determined not be equal to each other, detecting two errors.