Semiconductor memory device

[0001] This application is based on and claims the benefit of prior Japanese Patent Application No. 2001-356571, filed on Nov. 21, 2001, the entire contents of which are incorporated herein by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to a semiconductor memory device such as a NAND-type flash memory, more particularly to a semiconductor memory device having an on-chip error correcting function.

[0004] 2. Description of the Related Art

[0005] The NAND-type flash memory is known to deteriorate its cell property through repeated operations of rewriting, and to vary data after it is left for a long time. In order to improve the reliability of the NAND-type flash memory, such a semiconductor memory that contains an ECC (Error Correcting Code) circuit mounted on-chip for error detection and correction has been proposed in the art (for example, Japanese Patent Application Laid-Open Nos. 2000-348497 and 2001-14888).

[0006] FIG. 21 is a block diagram briefly showing an arrangement of the conventional NAND-type flash memory with ECC circuits mounted thereon.

[0007] This memory comprises eight memory cell areas 1₀, 1₁, . . . , 1₇. Each of the memory cell areas 1₀, 1₁, . . . , 1₇ includes a plurality of memory cells, not depicted, arrayed in a matrix. Data of 528 bits (=one page) can be written in and read out from 528 memory cells connected to a common word line through 528 bit lines at a time. Page buffers 2₀–2₇ are connected to the memory cell areas 1₀–1₇, respectively. Each page buffer can hold 528-bit write data and read data. Between the page buffers 2₀–2₇ and I/O terminals 4₀–4₇ located corresponding to the memory cell areas 1₀–1₇, ECC circuits 3₀–3₇ are provided for the memory cell areas 1₀–1₇, respectively.

[0008] Each ECC circuit 3₀–3₇ has a coding function to add a certain number of check bits (ECC) to one page of information bits (528 bits) to be stored in each memory cell area 1₀–1₇, and a decoding function to detect and correct a certain number of errors in the information bits with the check bits added thereto. BCH (Bose-Chaudhuri-Hocquenghem) code is employed as an error correcting code that can correct a plurality of bit errors with a relatively small circuit scale. Data is read from and written to the memory on a basis of 8 bits, corresponding to the number of memory cells. Data is fed bit by bit into each ECC circuit 3₀–3₇, and is circulated through and output from an internal cyclic shift register bit by bit to execute coding and decoding. ECC circuit 3₀–3₇ using BCH code will be described next.

[0009] The number of check bits in BCH code for correcting 2-bit errors and detecting 3-bit errors is equal to 21 bits for 528 information bits. For convenience of description, a simple error detection and correction system is described, which employs BCH code capable of correcting 2-bit errors and detecting 3-bit errors for the number of information bits, k=7, a code length, n=15, and the number of check bits, n−k=8.

[0010] In this case, a generating polynomial required for coding and decoding is given below as it is generally known:

[0011] $\begin{array}{cc}\begin{array}{c}\mathrm{Fundamental}\mathrm{Polynomial}\text{:}F\left(X\right)=X^4+X+1\\ \alpha \mathrm{Minimal}\mathrm{Polynomial}\text{:}{M}_1\left(x\right)=X^4+X+1\\ {\alpha }^3\mathrm{Minimal}\mathrm{Polynomial}\text{:}{M}_3\left(x\right)=X^4+X^3+X^2+X^{+1}\\ \mathrm{Generating}\mathrm{Polynomial}\text{:}G\left(x\right)=M_1{M}_3\\ =X^8+X^7+X^6+X^4+1\end{array}& \left(1\right)\end{array}$
(1) Coder

[0012] FIG. 22 is a block diagram showing a coder 10 functionally configured inside the convention ECC circuit 3i (i=0, 1, . . . , or 7). The coder 10 comprises a shift register 11 consisting of registers D₇, D₆, D₅, D₄, D₃, D₂, D₁, D₀, XOR circuits 12₁, 12₂, 12₃, 12₄ for modulo-2 operations, and circuit changing switches SW1, SW2.

[0013] Clocking the shift register 11 once corresponds to multiplying each value in the shift register 11 by X. A value of data stored in the shift register 11 can be expressed by:
a₀X⁰+a₁X¹+a₂X²+a₃X³+a₄X⁴+a₅X⁵+a₆X⁶+a₇X⁷   (2)
where a_i denotes a value stored in a register D_i, and a_i'20 or 1 (i=0−7). When this content is shifted once (with SW2 OFF), the following is obtained:
a₀X¹+a₁X²+a₂X³+a₃X⁴+a₄X⁵+a₅X⁶+a₆X⁷+a₇X⁸   (3)
From the generating polynomial G(x) given by Expression (1), a relation of X⁸=X⁷+X⁶+X⁴+1 is derived. Therefore, Expression (3) can be represented by:
a₇X⁰+a₀X¹+a₁X²+a₂X³+(a₃+a₇)X⁴+a₄X⁵+(a₅+a₇)X⁶+(a₆+a₇)X⁷   (4)
This corresponds to shifting each bit; storing the value a₇ of the register D₇ into the register D₀; adding the values a₃, a₇ of the registers D₃, D₇ at the XOR circuit 12₁ and storing the sum into the register D₄; adding the values a₅+a₇ of the registers D₅, D₇ at the XOR circuit 12₂ and storing the sum into the register D₆; and adding the values a₆+a₇ of the registers D₆, D₇ at the XOR circuit 12₃ and storing the sum into the register D₇.

[0014] On coding, the switches SW1, SW2 are first connected to ON sides to enter input data (information bits) I₀, I₁, I₂, I₃, I₄, I₅, I₆ (I₀−I₆=0 or 1) bit by bit from external through the I/O terminal 4i. Every time one bit of the input data I₀−I₆ enters, the shift register 11 operates once. As the switch SW1 is kept ON during the input data I₀−I₆ entering, the data is output bit by bit to the page buffer 2i as it is. At the same time, the input data I₀−I₆ is added to the value a₇ of the register D₇ at the XOR circuit 12₁ and the sum is stored in turn into the shift register 11. After completion of the input data I₀−I₆ entered into the page buffer 2i, check bits I₇, I₈, I₉, I₁₀, I₁₁, I₁₂, I₁₃, I₁₄ are stored inside the registers D₇, D₆, D₅, D₄, D₃, D₂, D₁, D₀ of the shift register 11, respectively. The switches SW1, SW2 are then connected to OFF sides and, every time the shift register 11 operates, the check bits I₇−I₁₄ are output serially to the page buffer 2i through the switch SW1. The information bits and check bits stored in the page buffer 2i are written into the memory cell area 1i. At the same time, the value in the shift register 11 is reset.

(2) Decoder

[0015] A decoder is described next. The decoder comprises syndrome computational circuits and an error position detector. In the case of 2-bit error detection, two syndromes S₁, S₃ are required for decoding. These syndromes can be derived from the minimal polynomial M₁(x)=X⁴+X+1 as it is known. FIG. 23 specifically shows (A) a conventional S₁ syndrome computational circuit 20 and (B) a conventional S₃ syndrome computational circuit 30.

[0016] Based on the minimal polynomial M₁(x), the S₁ syndrome computational circuit 20 in FIG. 23A comprises a shift register 21 consisting of registers D₃, D₂, D₁, D₀, and XOR circuits 22₁, 22₂. Clocking the shift register 21 once corresponds to multiplying a value in the shift register 21 by X. The value stored in the shift register 21 can be expressed by:
a₀X⁰+a₁X¹+a₂X²+a₃X³   (5)
where a_i denotes a value stored in a register D_i, and a_i=0 or 1 (i=0−3). When this is shifted once, the following is obtained:
a₀X¹+a₁X²+a₂X³+a₃X⁴   (6)
From the α minimal polynomial M₁(x), a relation of X⁴=X+1 is derived. Accordingly:
a₃X⁰+(a₀+a₃)X¹+a₁X²+a₂X³   (7)
This corresponds to shifting each bit; storing the value a₃ of the register D₃ into the register D₀; and adding the values a₀, a₃ of the registers D₀, D₃ at the XOR circuit 12₂ and storing the sum into the register D₁. The information bits I₀−I₆ and check bits I₇−I₁₄ are fed in this order into the S₁ syndrome computational circuit 20 bit by bit. The shift register 21 operates once every time one bit enters. After all bits I₀−I₁₄ enter, the syndrome S₁ is generated in the shift register 21 (D₀−D₃).

[0017] Similar to the S₁ syndrome computational circuit 20, the S₃ syndrome computational circuit 30 in FIG. 23B comprises a shift register 31 consisting of registers D₃, D₂, D₁, D₀, and XOR circuits 32₁, 32₂, 32₃, 32₄. It is configured by the X³ circuit of the minimal polynomial M₁(x). In the S₃ syndrome computational circuit 30, an operation for moving the shift register 31 once corresponds to multiplying a value in the shift register 31 by X³. The value stored in the shift register 31 is expressed by Expression (5). When it is multiplied by X³, the following is given:
a₀X³+a₁X⁴+a₂X⁵+a₃X⁶   (8)
From the α minimal polynomial M₁(x), a relation of X⁴−X+1 is derived. Accordingly:
a₁X⁰+(a₁+a₂)X¹+(a₂+a₃)X²+(a₀+a₃)X³   (9)
This corresponds to shifting each bit; storing the value a₁ of the register D₁ into the register D₀; adding the values a₁, a₂ of the registers D₁, D₂ at the XOR circuit 32₂ and storing the sum into the register D₁; adding the values a₂, a₃ of the registers D₂, D₃ at the XOR circuit 32₃ and storing the sum into the register D₂; and adding the values a₀, a₃ of the registers D₀, D₃ at the XOR circuit 32₄ and storing the sum into the register D₃. The information bits I₀−I₆ and check bits I₇−I₁₄ stored in the memory cells are also fed in this order into the S₃ syndrome computational circuit 30 bit by bit. The shift register 31 operates once every time one bit enters. After all bits I₀−I₁₄ enter, the syndrome S₃ is generated in the shift register 31 (D₀−D₃).

[0018] FIG. 24 is a flowchart showing an algorithm for decoding. The S₁, S₃ first based on the information bits and check bits read out from the memory cell area 1i (step S1). If the syndromes S₁, S₃ are S1=S3=0, it is determined errorless, and the read-out information bits are output as they are (steps S2, S3, S4). If only one of the syndromes S₁, S₃ is equal to 0, it is determined uncorrectable, and the data is output as it is (steps S2, S3, S5, S6, S7). If S₁≠0 and S₃≠0, computations are executed to derive σ₁=S₁² and σ₂=S₁³+S₃ (steps S2, S6, S8). If σ₂=0 (step S9), it can be found that a 1-bit error is present, and 1-bit corrected data is output (step S10). If σ₂≠0 (step S9), it can be found that 2-bit errors are present, and 2-bit corrected data is output (step S11).

[0019] The position of the error bit can be found by assigning Z=α^I(I=1, 2, 3, 4, 5, 6) in turn to an error locator polynomial σ(Z) represented by Expression (10) as it is known generally. The position of the error can be indicated by I that holds σ(α^I)=0.
σ(Z)=S₁+σ₁×Z+σ₂×Z²   (10)

[0020] An arrangement of the error position detector is shown in FIGS. 25 and 26, which is configured based on such the point. FIG. 25 shows a first arithmetic section 40a that computes and stores S₁, σ₁ and σ₂. FIG. 26 shows a second arithmetic section 40b that executes the operation of Expression (10) based on the operated result from the first arithmetic section 40a and outputs a detection signal to indicate the error position in the data. As shown in FIG. 25, the first arithmetic section 40a comprises a shift register 41, and X arithmetic circuit 42, and an X² arithmetic circuit 43. A shift register 41a stores the syndrome S₁, and shift registers 42a and 43a store the operated results, σ₁=S₁² and σ₂=S₁³+S₃. It is assumed that the shift register 42a has a value of:
a₀X⁰+a₁X¹+a₂X²+a₃X³   (11)
where a_i denotes a value stored in a register D_i, and a₁=0 or 1 (i=0−3). As the X arithmetic circuit 42 multiplies it by X, the value of the shift register 42a comes to:
a₀X¹+a₁X²+a₂X³+a₃X⁴   (12)
From the α minimal polynomial M₁(x), a relation of X⁴=X+1 is present. Accordingly, Expression (12) yields:
a₃X⁰+(a₀+a₃)X¹+a₁X²+a₂X³   (13)
This corresponds to shifting each bit; storing the value a₃ of the register D₃ into the register D₀; and adding the values a₀, a₃ of the registers D₀, D₃ at the XOR circuit 42₂ and storing the sum into the register D₁.

[0021] The X² arithmetic circuit 43 multiplies the value of the shift register 43a by X². Therefore, when the value indicated by Expression (11) is stored in the shift register 43a, and it is multiplied by X², the value of the shift register 43a comes to:
a₀X²+a₁X³+a₂X⁴+a₃X⁵   (14)
From the α minimal polynomial M₁(x), a relation of X⁴=X+1 is present. Accordingly, Expression (14) yields:
a₂X⁰+(a₂+a₃)X¹+(a₀+a₃)X²+a₁X³   (15)
This corresponds to shifting each bit; storing the value a₂ of the register E₂ into the register E₀; storing the value a₁ of the register E₁ into the register E₃; adding the values a₂, a₃ of the registers E₂, E₃ at the XOR circuit 43b₁ and storing the sum into the register E₁; and adding the values a₀, a₃ of the registers E₀, E₃ at the XOR circuit 43b₂ and storing the sum into the register E₂.

[0022] When 1-bit data I₀=I₆ is output, one shift operation of the shift registers 41a, 42a, 43a multiplies the term of σ₁ by Z in the X arithmetic section 42 and the term of σ₂ by Z² in the X² arithmetic section 43. The NAND-type flash memory operates the shift registers 41a, 42a, 43a in synchronization with the toggle signal that is employed to output the information bits stored in the memory cell to outside the chip. In the second arithmetic circuit 40b, the result from the operation through an XOR circuit 44 and an NOR gate 45 exhibits “1” at the error position. This output is employed to invert the corresponding data Ii to detect and correct the error.

[0023] Thus, in the conventional ECC circuit that employs BCH code, one shift and computation per 1-bit input is the basic operation. The NAND-type flash memory receives externally-generated 8-bit-parallel (8-I/O) or 16-bit-parallel (16-I/O) data. Therefore, it is required to correct an error per I/O terminal or compute 8 or 16 times during the one input cycle. The 8 or 16-time computation during the one input cycle needs a fast operation, which can not be achieved practically because a special process is required, for example.

[0024] Therefore, an ECC circuit 3i is provided for each memory cell area 1i (each I/O) in the art to correct errors on a basis of each memory cell area 1i. The NAND-type flash memory reads and programs data per page (528 bytes). If it is to correct 2-bit errors and detect 3-bit errors per I/O terminal, it requires 21 check bits for 528 information bits, 21×8=168 extra check bits in total for the entire chip. This is an inhibiting factor for improving the chip integration density.

[0025] The present invention has been made in consideration of such the problem and accordingly has an object to provide a semiconductor memory device having a reduced number of check bits for the same number of information bits to improve a chip integration density.

[0026] According to an aspect of the invention, a semiconductor memory device comprises a plurality of memory cell areas, each of which includes a plurality of memory cells arrayed in a matrix and has a data I/O portion; a plurality of buffers, each of which is coupled to the data I/O portion at each memory cell area to temporarily store data to be written into the memory cell area and data read out from the memory cell area; a plurality of I/O terminals, each of which is configured to receive external data to be written into the memory cell area and externally read out from the memory; and an error correction circuit located between the plurality of I/O terminals and the plurality of buffers, the error correction circuit includes a coder configured to generate check bits for error correcting and to append the check bits to the data to be written into the memory cell area and a decoder configured for error correcting the data read out from the memory cell area with the generated check bits, the error correction circuit operates to allocate a set of check bits to an information unit of M×N bits (N denotes an integer of two or more) to execute at least one process of coding and decoding by parallel processing N-bit data, where M denotes the number of bits in a unit of data to be written into and read out from each memory cell area.

[0054] Embodiments of the present invention will be described below with reference to the drawings.

(1) First Embodiment

[0055] In order to provide an understanding of the present invention, 2-bit error correction is exemplified as a first embodiment with the number of information bits, k=7, a code length, n=15, and the number of correction bits, t=2.

(1-1) Coder

[0056] When input data I₀ enters the conventional coder 11 shown in FIG. 22, the input data I₀ is added at the XOR circuit 12₄ to the term of X⁷ in the coder, then multiplied by X. Each register 11 in the coder 10 in the initial state has a value of 0, which is referred to as (0). Accordingly:
(0+I₀X⁷)X   (17)
When next input data I₁ enters the coder 10, the input data I₁ is added to the term of X⁷ in the coder 10, then multiplied by X to yield:
((0+I₀X⁷)X+I₁X⁷)X   (18)

[0057] When next input data I₂ enters the coder 10, the input data I₂ is added to the term of X⁷ in the coder 10, then multiplied by X to yield:
(((0+I₀X⁷)X+I₁X⁷)X+I₂X⁷)X   (19)

[0058] Similarly, after input data, up to I₆, enters the coder 10, the following is given:
(((((((0+I₀X⁷)X+I₁X⁷)X+I₂X⁷)X+I₃X⁷)X+I₄X⁷)X²+I₅X⁶)X²+I₆X⁷)X   (21)

[0059] This means that the pieces of input data I₀, I₁ are added to the terms of X⁷, X⁶ in the coder 10, respectively, then multiplied by X². Thereafter, the pieces of input data I₂, I₃ are added to the terms of X⁷, X⁶ in the coder 10, respectively, then multiplied by X². Finally the pieces of input data I⁴, I⁵ are added to the terms of X⁷, X⁶ in the coder 10, respectively, then multiplied by X². In a word, one operation of the shift register 11 after two bits input can multiply the data by X². As for the last data I⁶, however, one bit input clock cycle multiplies it by X as is in the art.

[0060] When the value of the shift register 11 represented by Expression (2) is multiplied by X², it comes to:
a₀X²+a₁X³+a₂X⁴+a₃X⁵+a₄X⁶+a₅X⁷+a₆X⁹   (22)
From the generating polynomial G(x) given by Expression (1), a relation of X⁸=X⁷+X⁶+X⁴+1 is derived. Therefore, Expression (21) yields:
(a₆+a₇)X⁰+a₇X¹+a₀X²+a₁X³+(a₂+a₆+a₇)X⁴+(a₃+a₇)X⁵+(a₄+a₆+a₇)X⁶+(a₅+a₆)X⁷   (23)

[0061] FIG. 1 is a block diagram showing a circuit arrangement of an encoder 50 with 2-bit-parallel processing according to the present embodiment that specifically configures Expression (23).

[0062] The coder 50 comprises a shift register 51 consisting of registers D₇, D₆, D₅, D₄, D₃, D₂, D₁, D₀, XOR circuits 52₁, 52₂, 52₃, 52₄, 52₅, 52₆, 52₇, and four switches SW11, SW12, SW21, SW22 for changing input data and output data. The shift register 51 includes four-stage transfer gates 51a and other necessary gate circuits 51b as shown in FIG. 2. In the transfer gates 51a, a reset signal RSTn is employed to reset the contents of data and a clock signal CLK to synchronously transfer 1-bit data from an input terminal IN to an output terminal OUT. An XOR circuit 52 applied a modulo-2 operation to data input from input terminals IN1, IN2, as shown in FIG. 3, and output the result from an output terminal OUT.

[0063] Based on Expression (23), the coder 50 through one shift operation performs: adding the values a₆, a₇ of the registers D₆, D₇ at the XOR gate 52₆ and storing the sum into the register D₀; storing the value a₇ of the register D₇ into the register D₁; storing the value a₀ of the register D₀ into the register D₂; storing the value a₁ of the register D₁ into the register D₃; adding the values a₂, a₆, a₇ of the registers D₂, D₆, D₇ at the XOR gates 52₁, 52₆ and storing the sum into the register D₄; adding the values a₃, a₇ of the registers D₃, D₇ at the XOR gate 52₂ and storing the sum into the register D₅; adding the values a₄, a₆, a₇ of the registers D₄, D₆, D₇ at the XOR gates 52₃, 52₆ and storing the sum into the register D₆; and adding the values a₅, a₆ of the registers D₅, D₆ at the XOR gate 52₅ and storing the sum into the register D₇.

[0064] The pieces of input data (information bits) I₀, I₁, I₂, I₃, I₄, I₅, I₆, given from external to be written into the memory, are divided into two: input data I₀, I₂, I₄ and input data I₁, I₃, I₅. The input data I₀, I₂, I₄ is fed to ON sides of the switches SW11, SW21. The input data I₁, I₃, I₅ is fed to ON sides of the switches SW12, SW22. The pieces of input data are fed by two bits in parallel in an order of (I₀, I₁), (I₂, I₃), (I₄, I₅). After the input, the shift register 51 operates once. As the shift register 51 is connected to every other one, one shift operation multiplies the data by X². While the pieces of data (I₀, I₁), (I₂, I₃), (I₄, I₅) enter, the switches SW11, SW12, SW21, SW22 are all kept ON to allow these pieces of data to output by two bits in parallel as they are. At the same time, the data I₀, I₂, I₄ is added to the value a₇ of the register D₇ at the XOR circuit 52₇ and sequentially stored in the shift register 51. The data I₁, I₃, I₅ is added to the value a₇ of the register D₇ at the XOR circuit 52₄ and sequentially stored in the shift register 51. As the last I₆ of the input data is 1-bit input, the connection is switched to the same as in the conventional coder 10 shown in FIG. 22. Such the switching is required because k=7 is selected as the number of information bits. After completion of input of the data I₀, I₁, I₂, I₃, I₄, I₅, I₆, check bits I₇, I₈, I₉, I₁₀, I₁₁, I₁₂, I₁₃, I₁₄ are stored inside the registers D₇, D₆, D₅, D₄, D₃, D₂, D₁, D₀ in the shift register 51, respectively. The switches SW11, SW12, SW21, SW22 are then all connected to OFF sides. Thus, every time the shift register 51 operates, the check bits I₇, I₉, I₁₁, I₁₃ are fed to the output of the switch SW11 and the check bits I₈, I₁₀, I₁₂, I₁₄ to the output of the switch SW12. At the same time, the value in the shift register 51 is reset. This allows check bits to be generated through 2-bit input parallel processing.

(1-2) Decoder

{circle around (1)} S₁ Syndrome Computational Circuit

[0065] In the conventional S₁ syndrome computational circuit 20 of FIG. 23A, the value in the S₁ syndrome computational circuit 20 is first multiplied by X, then the input data I₀ is added to the term of X⁰ at the XOR circuit 22₁. The shift register 21 in the S₁ syndrome computational circuit 20 in the initial state has a value of 0, which is referred to as (0). Accordingly:
0×X+I₀   (24)
After the value in the S₁ syndrome computational circuit 20 is multiplied by X, the input data I₁ is added to the term of X₀. Accordingly:
(0×X+I₀)X+I₁   (25)

[0066] Subsequently, after the value in the S₁ syndrome computational circuit 20 is multiplied by X, the input data I₂ is added to the term of X⁰. Accordingly:
((0×X+I₀)X+I₁)X+I₂   (26)
When the input data, up to I₁₄, enters the S₁ syndrome computational circuit 20, the following is given:
(((((((((((((0×X+I₀)X+I₁)X+I₂)X+I₃)X+I₄)X+I₅)X+I₆)X+I₇)X+I₈)X+I₉)X+I₁₀)X+I₁₁)X+I₁₂)X+I₁₃)X+I₁₄   (27)
The expression can be altered in:
(((((((0×X²+I₀X+I₁)X²+I₂X+I₃)X²+I₄X+I₅)X²+I₆X+I₇)X²+I₈X+I₉)X²+I₁₀X+I₁₁)X²+I₁₂X+I₁₃)X+I₁₄   (28)
This means that after the value in the S₁ syndrome computational circuit 20 is multiplied by X², the input data I₀ is added to the term of X¹, and the input data I₁ to the term of X⁰. Then, after the value in the S₁ syndrome computational circuit 20 is multiplied by X², the input data I₂ is added to the term of X¹, and the input data I₃ to the term of X⁰. Next, after the value in the S₁ syndrome computational circuit 20 is multiplied by X², the input data I₄ is added to the term of X¹, and the input data I₅ to the term of X⁰. In a word, one operation of the shift register multiplies the data by X², then 2-bit data enters. Finally, after the value in the S₁ syndrome computational circuit 20 is multiplied by X, the input data I₁₄ is added to the term of X₀ by 1-bit input.

[0067] When the value of the shift register 21, expressed by Expression (5), is multiplied by X², the following is given:
a₀X²+a₁X³+a₂X⁴+a₃X⁵   (29)
From the α minimal polynomial M₁(x), a relation of X⁴=X+1 is derived. Accordingly:
a₂X⁰+(a₂+a₃)X¹+(a₀+a₃)X²+a₁X³   (30)

[0068] FIG. 4A is a block diagram showing a circuit arrangement of an S₁ syndrome computational circuit 60 according to the present embodiment that specifically configures Expression (30).

[0069] The S₁ syndrome computational circuit 60 comprises a shift register 61 consisting of registers D₀, D₁, D₂, D₃, and XOR circuits 62₁, 62₂, 62₃, 62₄.

[0070] Based on Expression (30), the S₁ syndrome computational circuit 60 through one shift operation performs: storing the value a₂ of the register D₂ into the register D₀; adding the values a₂, a₃ of the registers D₂, D₃ at the XOR circuit 62₂ and storing the sum into the register D₁; adding the values a₀, a₃ of the registers D₀, D₃ at the XOR circuit 62₄ and storing the sum into the register D₂; and storing the value a₁ of the register D₁ into the register D₃.

[0071] The information bits I₀, I₁, I₂, I₃, I₄, I₅, I₆ and check bits I₇, I₈, I₉, I₁₀, I₁₁, I₁₂, I₁₃, I₁₄ read out from the memory cell area, not depicted, are divided into I₀, I₂, I₄, I₆, I₈, I₁₀, I₁₂, I₁₄ and I₁, I₃, I₅, I₇, I₉, I₁₁, I₁₃ and fed by two bits in parallel in an order of (I₀, I₁), (I₂, I₃), (I₄, I₅), . . . to the S₁ syndrome computational circuit 60. After the input, the shift register 61 operates once. As the shift register 61 is connected to every other one, one shift operation multiplies the data by X². The data I₀, I₂, I₄, . . . , I₁₄ is added at the XOR circuit 62₃ to the output, a₂+a₃, from the XOR circuit 62₂ and the sum is stored in the register D₁. The data I₁, I₃, I₅, . . . , I₁₃ is added at the XOR circuit 62₁ to the value a₂ of the register D₂ and the sum is stored in the register D₀. As the last I₆ of the information bits is 1-bit input, the connection is switched to the same as in the circuit of FIG. 23. Alternatively, it is possible to input I₁₅=0 to the S₁ syndrome computational circuit 60 and, after a shift operation, multiply the shift register by X⁻¹. This allows 2-bit input parallel processing to be performed.

{circle around (2)} S₃ Syndrome Computational Circuit

[0072] A S₃ syndrome computational circuit 70 in FIG. 4B is described next. In the conventional S₃ syndrome computational circuit 30 in FIG. 23A, the value in the S₃ syndrome computational circuit 30 is first multiplied by X³, then the input data I₀ is added to the term of X⁰ at the XOR circuit 32₁. The shift register 31 in the S₃ syndrome computational circuit 30 in the initial state has a value of 0, which is referred to as (0). Accordingly:
0×X³+I₀   (31)
After the value in the S₃ syndrome computational circuit 30 is multiplied by X³, the input data I₁ is added to the term of X₀. Accordingly:
(0×X³+I₀)X+I₁   (32)
Subsequently, after the value in the S₃ syndrome computational circuit 30 is multiplied by X³, the input data I₂ is added to the term of X₀. Accordingly:
((0×X³+I₀)X³+I₁)X³+I₂  (33)
When the input data, up to I₁₄, enters the S₃ syndrome computational circuit 30, the following is given:
(((((0×X³+I₀)X³+I₂)X³+I₃)X³+I₄)X³+I₅)X³+I₆)X³+I₇)X³+I₈)X³+I₉)X³+I₁₀)X³ +I₁₁)X³+I₁₂)X³+I₁₃)X³+I₁₄   (34)
The expression can be altered in:
(((((0×X⁶+I₀X³+I₁)X⁶+I₂X³+I₃)X⁶+I₄X³+I₅)X⁶+I₆X³+I₇)X⁶+I₈X³+I₉)X⁶+I₁₀X³+I₁₁)X⁶+I₁₂X³+I₁₃)X³+I₁₄   (35)
This means that after the value in the S₃ syndrome computational circuit 30 is multiplied by X⁶, the input data I₀ is added to the term of X³, and the input data I₁ to the term of X⁰. Then, after the value in the S₃ syndrome computational circuit 30 is multiplied by X⁶, the input data I₂ is added to the term of X³, and the input data I₃ to the term of X⁰. Next, after the value in the S₃ syndrome computational circuit 30 is multiplied by X⁶, the input data I₄ is added to the term of X³, and the input data I₅ to the term of X⁰. In a word, one operation of the shift register multiplies the data by X⁶, then 2-bit data is input. Finally, after the value in the S₃ syndrome computational circuit 30 is multiplied by X³, the input data I₁₄ is added to the term of X₀ by 1-bit input.

[0073] When the value of the shift register 31, expressed by Expression (5), is multiplied by X⁶, the following is given:
a₀X⁶+a₁X⁷+a₂X⁸+a₃X⁹   (36)
From the α minimal polynomial M₁(x), a relation of X⁴=X+1 is derived. Accordingly:
(a₁+a₂)X⁰+(a₁+a₃)X¹+(a₀+a₂)X²+(a₀+a₁+a₃)X³   (37)

[0074] FIG. 4B is a block diagram showing a circuit arrangement of the S₃ syndrome computational circuit 70 according to the present embodiment that specifically configures Expression (37).

[0075] The S₃ syndrome computational circuit 70 comprises a shift register 71 consisting of registers D₀, D₁, D₂, D₃, and XOR circuits 72₁, 72₂, 72₃, 72₄, 72₅, 72₆.

[0076] Based on Expression (37), the S₃ syndrome computational circuit 70 through one shift operation performs: adding the values a₁, a₂ of the registers D₁, D₂ at the XOR circuit 72₂ and storing the sum into the register D₀; adding the values a₁, a₃ of the registers D₁, D₃ at the XOR circuit 72₆ and storing the sum into the register D₁; adding the values a₀, a₂ of the registers D₀, D₂ at the XOR circuit 72₄ and storing the sum into the register D₂; and adding the values a₀, a₁, a₃ of the registers D₀, D₁, D₃ at the XOR circuits 72₅, 72₆ and storing the sum into the register D₃.

[0077] The information bits I₀, I₁, I₂, I₃, I₄, I₅, I₆ and check bits I₇, I₈, I₉, I₁₀, I₁₁, I₁₂, I₁₃, I₁₄ read out from the memory cell area, not depicted, are divided into I₀, I₂, I₄, I₆, I₈, I₁₀, I₁₂, I₁₄ and I₁, I₃, I₅, I₇, I₉, I₁₁, I₁₃ and fed by two bits in parallel in an order of (I₀, I₁), (I₂, I₃), (I₄, I₅), . . . to the S₃ syndrome computational circuit 70. After the input, the shift register 71 operates once. The data I₀, I₂, I₄, . . . , I₁₄ is added at the XOR circuit 72₃ to the output, a₁+a₃, from the XOR circuit 72₆ and the sum is stored in the register D₁. The data I₁, I₃, I₅, . . . , I₁₃ is added to the output, a₁+a₂, from the XOR circuit 72₁ at the XOR circuit 72₂ and the sum is stored in the register D₀. As the last I₆ of the information bits is 1-bit input, the connection is switched to the same as in the S₃ syndrome computational circuit 30 of FIG. 23. Alternatively, it is possible to input I₁₅=0 to the S₃ syndrome computational circuit 70 and, after a shift operation, multiply the shift register by X⁻³. This allows 2-bit input parallel processing to be performed.

{circle around (3)} Error Position Detector

[0078] An error position detector is described next. In the error position detector in the present embodiment, the S₁, S₃ syndrome computational circuits 60, 70 perform one shift operation corresponding to the conventional two shift operations. Therefore, the error position detector performs an arithmetic also corresponding to the conventional two shift operations. The error position polynomial (10) is also represented by:
σ(Z)=S₁+σ₁×Z²+σ₂×Z⁴   (38)

[0079] FIGS. 5 and 6 show an arrangement of the error position detector configured based on Expression (38).

[0080] The error position detector 80 comprises a first arithmetic section 80a (FIG. 5) that computes and stores S₁, σ₁ and σ₂, and a second arithmetic section 80b that detects a data error position based on Expression (38) and outputs a detection signal. As shown in FIG. 5, the first arithmetic section 80a comprises a shift register 81, an X² arithmetic circuit 82, and an X⁴ arithmetic circuit 83. A shift register 81a stores the syndrome S₁ as the initial state, and shift registers 82a, 83a store the operated results, σ₁=S₁² and σ₂=S₁³+S₃, as the initial states. The error position detector 80 executes error detection in synchronization with every other data I₀, I₂, I₄, I₆ among the output data I₀, I₁, I₂, I₃, I₄, I₅, I₆. It operates the shift registers 81a, 82a, 83a once to multiply the term of σ₁ by Z² in the X² arithmetic circuit 82, and the term of σ₂ by Z⁴ in the X⁴ arithmetic circuit 83. If any error is present, then σ=0.

[0081] The X² arithmetic circuit 82 has the same arrangement as the X² arithmetic circuit 43 in FIG. 25: the shift register 43a corresponds to the shift register 82a; and the XOR circuits 43b₁, 43b₂ to the XOR circuits 82b₁, 82b₂. Therefore, detailed arrangement descriptions for those parts are omitted.

[0082] The X⁴ arithmetic circuit 83 multiplies the value expressed by Expression (11) of the shift register 83a by X⁴. Therefore, the shift register 83a has a value expressed by:
a₀X⁴+a₁X⁵+a₂X⁶+a₃X⁷   (39)
From the α minimal polynomial M₁(x), a relation of X⁴=X+1 is derived. Accordingly:
(a₀+a₃)X⁰+(a₀+a₁+a₃)X¹+(a₁+a₂)X²+(a₂+a₃)X³   (40)
Based on Expression (40), the X⁴ arithmetic section 83 through one shift operation performs: adding the values a₀, a₃ of the registers E₀, E₃ at the XOR circuit 83b₁ and storing the sum into the register E₀; adding the values a₀, a₁, a₃ of the registers E₀, E₁, E₃ at the XOR circuit 83b₁, 83b₂ and storing the sum into the register E₁; adding the values a₁, a₂ of the registers E₁, E₂ at the XOR circuit 83b and storing the sum into the register E₂; and adding the values a₂, a₃ of the registers E₂, E₃ at the XOR circuit 83b₄ and storing the sum into the register E₃.

[0083] The second arithmetic section 80b in FIG. 6 includes a first detector 84 to detect error positions in the output data I₀, I₂, I₄, I₆; a second detector 85 to detect error positions in the output data I₁, I₃, I₅; an X-arithmetic circuit 86 to multiply the term of σ₁ by Z regarding the data I₁, I₃, I₅; and an X²-arithmetic circuit 87 to multiply the term of σ₂ by Z² regarding the data I₁, I₃, I₅. The output resulted from the operation at the XOR circuit 88 and the NOR gate 89 in each detector 84, 85 exhibits “1” at the error position. This output is employed to invert the corresponding data Ii to detect 2-bit error positions in parallel at the same time by one shift operation. The X arithmetic circuit 86 and the X² arithmetic circuit 87 have the same arrangements as the conventional circuits shown in FIGS. 25 and 26 though they are not required to have registers for storing data.

(2) Second Embodiment

[0084] FIG. 7 is a block diagram showing a NAND-type flash memory according to a second embodiment, which mounts an ECC circuit on a chip.

[0085] The memory comprises eight memory cell areas 101₀, 101₁, 101₂, . . . , 101₇. Eight page buffers 102₀, 102₁, 102₂, . . . , 102₇ are provided corresponding to the memory cell areas 101₀, 101₁, 101₂, . . . , 101₇ to temporarily store data to be written in and read out of the memory cell areas 101₀, 101₁, 101₂, . . . , 101₇. Between the page buffers 102₀–102₇ and I/0 terminals 104₀, 104₁, . . . , 104₇, an ECC circuit 103 is provided to generate check bits, ECC, for correcting errors in the write data and to correct errors in the read data using the check bits (ECC). Different from the conventional type, for error detection and correction, the ECC circuit 103 adds 40 check bits commonly to information bits consisting of 528 bits ×8 I/O=4224 bits data (M=528, N=8) that can be read out of and written into all memory cell areas 101₀–101₇ at a time.

[0086] Addresses and control signals, input to an I/O terminal 105, are fed to a control signal operation circuit 106 and an address decoder 107, respectively. The control signal operation circuit 106 receives various control signals, ALE, CLE, CE, WE, RE, WP, generates control voltages supplied to various parts, and outputs a signal, READY/BUSY, to an external circuit. On receipt of an address from external through the I/O terminal 105, the address decoder 107 temporarily stores it and drives a column decoder 108 and a block selector 109. The column decoder 108 activates one column in each of the page buffers 102₀–102₇. The block selector 109 applies a voltage to a word line in the memory cell areas 101₀–101₇ required for reading, writing and erasing.

[0087] As shown in FIG. 8, each memory cell area 101j (where j=0−7) includes electrically rewritable, nonvolatile memory cells MC arrayed in a matrix. In this example, 16 memory cells MC are serially connected in a unit. A drain of the memory cell MC at one end is connected to a bit line BL via a selection gate transistor SG1. A source of the memory cell MC at the other end is connected to a common source line SL via a selection gate transistor SG2. Control gates of the memory cells MC in the row direction are connected to a common word line WL. Gate electrodes of the selection gate transistors SG1, SO2 in the row direction are connected to a common selection gate line SGL1, SGL2. In this embodiment, data of 528 bits, stored in the memory cells arranged at odd or even numbers among 1056 memory cells MC along a control gate line, is treated as a page to be written or read as a unit. In this example, data of 16 pages adjoining in the column direction is treated as a block or a unit to be erased together. In addition to 1056 (528×2) memory cells MC arranged along a word line WL to store information bits, the memory cell area 1017 is further provided with memory cells MC to store 80 (40×2) check bits for error correction.

[0088] As shown in FIG. 8, each page buffer 102j includes 528 data storage circuits 121. Each data storage circuit 121 is connected to two bit lines BLi, BLi+1. Data can be read out from a memory cell MC in the memory cell area 101j via either bit line BL selected by the address. A state of a memory cell MC in the memory cell area 101j can be detected via the bit line BL. Writing into a memory cell MC in the memory cell area 101j can be performed when a write control voltage is applied to the memory cell MC via the bit line BL. Among 528 data storage circuits 121, either one is selected at the column decoder 108 and only the selected data storage circuit 121 is connected to the ECC circuit 103.

[0089] Therefore, in the whole memory, the data storage circuits 121 of 8 bits (8-I/O) having the same column address are connected to the ECC circuit 103 by the column decoder 108. In a read operation, the memory cells MC of one page surrounded by a dashed line in FIG. B are selected, and data of 528×8 bits is stored in all data storage circuits 121 at a time. The column decoder 108 increments the column address by one in synchronization with the read enable (RE) signal input from external. As a result, one in each of the memory cell areas 101₀–101₇, eight data storage circuits 121 in total are selected in turn and 8-bit (8-I/O) data is sequentially output to the ECC circuit 103. In a write operation, 8-bit (8-I/O) data is sequentially input to the ECC circuit 103 from external via the I/O terminal 104₀–104₇, and the 8-bit data is sequentially output from the ECC circuit 103. The column decoder 108 increments the column address by one in synchronization with the externally-generated write enable (WE) signal input. As a result, one in each of the memory cell areas 101₀–101₇, eight data storage circuits 121 in total are selected in turn, and (8-I/O) parallel data from the ECC circuit 103 is sequentially input to the selected storage circuit 121.

[0090] An ECC circuit 103 is explained next.

[0091] FIG. 9 is a block diagram showing the ECC circuit 103 in detail. The ECC circuit 103 includes an arithmetic logic circuit 131 containing multiple stages of registers, XOR circuits and switches; a Galois arithmetic circuit 132 for use in a syndrome computation and so forth; and an error position detector 133 (mainly a second arithmetic section) and a data inverter 134 operative to decode. The arithmetic logic circuit 131 configures a check bit generator when the ECC circuit 103 serves as a coder, and configures mainly the syndrome arithmetic circuit and a first arithmetic section in the error position detector when the ECC circuit 103 serves as a decoder.

(2-1) Coder

[0092] In the ECC circuit 103, data is input by 8 bits (D₀–D₇) to perform error detection and correction on a basis of data of 528×8=4224 bits. In the case of BCH code capable of correcting 3-bit errors and detecting 4-bit errors, the following condition can be considered: the number of information bits, k=4224; a code length, n=4264; the number of correction bits, t=3; and m=13. Therefore, a generating polynomial required for coding and decoding is given below:

[0093] $\begin{array}{cc}\begin{array}{c}\mathrm{Fundamental}\mathrm{Polynomial}\text{:}F\left(X\right)=X^{13}+X^4+X^3+X+1\\ \mathrm{Parity}\mathrm{Polynomial}\text{:}{M}_0\left(x\right)=X+1\\ \alpha \mathrm{Minimal}\mathrm{Polynomial}\text{:}{M}_1\left(x\right)=X^{13}+X^4+X^3+X+1\\ {\alpha }^3\mathrm{Minimal}\mathrm{Polynomial}\text{:}{M}_3\left(x\right)=X^{13}+X^{10}+X^9+X^7+X^5+X^4+1\\ {\alpha }^5\mathrm{Minimal}\mathrm{Polynomial}\text{:}{M}_5\left(x\right)=X^{13}+X^{11}+X^8+X^7+X^4+X^1+1\\ \mathrm{Generating}\mathrm{Polynomial}\text{:}G\left(x\right)=M_0{M}_1{M}_3{M}_5\\ =\begin{array}{c}{X}^{40}+X^{39}+X^{38}+X^{35}+X^{34}+X^{33}+\\ X^{32}+X^{28}+X^{27}+X^{26}+X^{25}+X^{23}+\\ X^{22}+X^{20}+X^{18}+X^{17}+X^{16}+X^{15}+\\ X^{14}+X^{10}+X^9+X^5+X^4+X^2+X^1+1\end{array}\end{array}& \left(41\right)\end{array}$
Similar to the first embodiment, Expression (42) can be altered in Expression (43).
(((((0+I₀X³⁹)X+I₁X³⁹)X+I₂X³⁹)X+I₃³⁹) . . . )X+I₅₂₇X³⁹)X   (42)
(((((0+I₀X³⁹+I₁X³⁸+I₂X³⁷ . . . I₇X³²)X⁸+(I₈X³⁹ . . . I₁₅X³²))X⁸ . . . (I₅₂₀X³⁹+I₅₂₁X³⁸ . . . I₅₂₇X³²)X⁸   (43)

[0094] Expression (43) means the following. The data of 8 bits D₀–D₇=I₀, I₁, I₂, . . . , I₇, input by one clock of the WE signal, is multiplied on a bit basis by X³⁹, X³⁸, X³⁷, . . . , X³², respectively, and each product is added into an internal register value, which is then multiplied by X⁸. Subsequently, the data of 8 bits D₀–D₇=I₈, I₉, I₁₀, . . . , I₁₅, input by the next clock of the WE signal, is multiplied on a bit basis by X³⁹, X³⁸, X³⁷, . . . , X³², respectively, and each product is added into an internal register value, which is then multiplied by X⁸. The same operations are repeated 528 times to the data of last 8 bits D₀–D₇=I₄₂₁₆, I₄₂₁₇, I₄₂₁₈, . . . , I₄₂₂₃.

[0095] FIG. 10 shows 40-stage registers REG0, REG1, . . . , REG39 equipped in the arithmetic logic circuit 131. These registers configure a cyclic shift register in the coder. The registers REG0, REG1, . . . , REG39 have Inputs B0, B1, . . . , B39 and Outputs A0, A1, . . . , A39. Based on the above generating polynomial (41) and Expression (43), the arithmetic logic circuit 131 executes XOR operations represented by the following Expressions (45) and (46) for one data input. The XOR operations herein employed are represented by Expression (44). Prior to sending the Outputs A32–A39, the registers REG32–REG39 sends Outputs AA32–AA39, which are resulted from XOR operations as shown by Expression (45) to add 8-bit data D₀–D₇ fed from external to register values. Outputs A0–31 and AA32–AA39 are led to XOR circuits. The results from the XOR operations, B0–B39, represented by Expression (46), are led to Inputs of the registers REG0–REG39 and fetched in synchronization with the shift register clock. When this operation is repeated 528 times, 40 check bits I₄₂₂₄, I₄₂₂₅, I₄₂₂₆, . . . , I₄₂₆₄ are generated in the registers REG0–REG39 of the arithmetic logic circuit 131.
XOR3(IN1, IN2, IN3)=XOR2(XOR2(IN1, IN2), IN3)
XOR4(IN1, IN2, IN3, IN4)=XOR2(XOR3(IN1, IN2, IN3), IN4)
XOR5(IN1, IN2, IN3, IN4, IN5)=XOR2(XOR4(IN1, IN2, IN3, IN4), IN5)
XOR6(IN1, IN2, IN3, IN4, IN5, IN6)=XOR2(XOR5(IN1, IN2, IN3, IN4, IN5), IN6)
XOR3(IN1, IN2, IN3)=XOR2(XOR2(IN1, IN2, IN3)
XOR7(IN1, IN2, IN3, IN4, IN5, IN6, IN7=XOR2(XOR6(IN1, IN2, IN3, IN4, IN5, IN6), IN7)   (44)
AA39=XOR2(A39, D0)
AA38=XOR2(A38, D1)
AA37=XOR2(A37, D2)
AA36=XOR2(A36, D3)
AA35=XOR2(A35, D4)
AA34=XOR2(A34, D5)
AA33=XOR2(A33, D6)
AA32=XOR2(A32, D7)   (45)
B0=XOR6(A32, A33, A35, A36, A37, A39)
B1=XOR5(A32, A34, A35, A38, A39)
B2=XOR2(A32, A37)
B3=XOR2(A33, A38)
B4=XOR6(A32, A33, A34, A35, A36, A37)
B5=XOR4(A32, A34, A38, A39)
B6=XOR3(A33, A35, A39)
B7=XOR2(A34, A36)
B8=XOR3(A0, A35, A37)
B9=XOR7(A1, A32, A33, A35, A36, A37, A39)
B10=XOR6(A2, A32, A34, A35, A37, A38)
B11=XOR6(A3, A33, A35, A36, A38, A39)
B12=XOR5(A4, A34, A36, A37, A39)
B13=XOR4(A5, A35, A37, A38)
B14=XOR6(A6, A32, A33, A35, A37, A38)
B15=XOR6(A7, A32, A34, A35, A37, A38)
B16=XOR4(A8, A32, A37, A38)
B17=XOR6(A9, A32, A35, A36, A37, A38)
B18=XOR4(A10, A32, A35, A38)
B19=XOR6(A11, A33, A36, A39)
B20=XOR7(A12, A32, A33, A34, A35, A36, A39)
B21=XOR6(A16, A33, A34, A35, A36, A37)
B22=XOR6(A14, A32, A33, A34, A38, A39)
B23=XOR5(A15, A32, A34, A36, A37)
B24=XOR5(A16, A33, A35, A37, A38)
B25=XOR7(A17, A32, A33, A34, A35, A37, A38)
B26=XOR5(A18, A32, A34, A37, A38)
B27=XOR5(A19, A32, A36, A37, A38)
B28=XOR5(A20, A32, A35, A36, A38)
B29=XOR5(A21, A33, A36, A37, A39)
B30=XOR4(A22, A34, A37, A38)
B31=XOR4(A23, A35, A38, A39)
B32=XOR5(A24, A32, A33, A35, A37)
B33=XOR7(A25, A32, A34, A35, A37, A38, A39)
B34=XOR4(A26, A32, A37, A38)
B35=XOR6(A27, A32, A35, A36, A37, A38)
B36=XOR6(A28, A33, A36, A37, A38, A39)
B37=XOR5(A29, A34, A37, A38, A39)
B38=XOR6(A30, A32, A33, A36, A37, A38)
B39=XOR6(A31, A32, A34, A35, A36, A38)   (46)

[0096] FIG. 11 is a flowchart showing an operation of coding in the ECC circuit 103 and FIG. 12 is a timing chart on coding in the same.

[0097] When a data input command (80h) enters from external (S21), the registers REG0–40 in the arithmetic logic circuit 131 are reset (S22), then an address (Add) is given. Subsequently, a WE (Write Enable) signal enters from external and, in synchronization with this signal, data is loaded by 8 bits into the page buffer 102j (S23, S24, S25). At the same time, the data is sent to the arithmetic logic circuit 131 to compute check bits. When the column address reaches the last 528 (S25), the data loading is terminated. Subsequently, a program command (10h) enters from external, and an operation of voltage boosting by a charge pump, not depicted, is started to write data into the memory cell MC. At the same time, prior to writing, check bits are output, using the internal oscillator and so forth, not depicted, from 40 bits REGO–REG39 by 5 bytes sequentially, and stored in the data storage circuit 121 of the page buffer 102₇. The data stored in the data storage circuit 121 is then written into the memory cells MC in the page (surrounded by the dashed line in FIG. 8) selected by the external address Add.

(2-2) Decoder

{circle around (1)} Syndrome Computational Circuits

[0098] For 3-bit error correction and 4-bit error detection, four syndromes S₀, S₁, S₃, S₅ are required as it is known. The syndrome S₀ can be derived from the minimal polynomial M₁(X)=X⁴+X+1. When X¹⁰=X³+1, derived from the minimal polynomial M₁(x)=X¹⁰+X³+1, is referred to as an α operator, the syndrome S₁ can be derived from the α operator, the syndrome S₃ from an α³ operator, and the syndrome S₅ from an α⁵ operator. Only one bit can enter by one clock of the WE signal in the conventional decoder. In contrast, 8-bit data can be fetched by one clock of the WE signal in this embodiment by altering Expressions similar to the first embodiment that alters Expression from (27) to (28), and Expression from (34) to (35). Accordingly, the syndrome S₁ can be derived from an α⁸-operator, the syndrome S₃ from an α²⁴ operator, and the syndrome S₅ from an α⁴⁰ operator.

[0099] FIG. 13 shows 40-stage registers REG0, REG1, . . . , REG39 equipped in the arithmetic logic circuit 131. The register REG0 configures a cyclic shift register in the S₀ syndrome computational circuit. The registers REG1–13 configure a cyclic shift register in the S₁ syndrome computational circuit. The registers REG14–26 configure a cyclic shift register in the S₃ syndrome computational circuit. The registers REG27–39 configure a cyclic shift register in the S₅ syndrome computational circuit. The register REG0 has an Input PP0 and an Output P0. The registers REG1–13 have Inputs AA0, AA1, . . . , AA12 and Outputs A0, A1, . . . , A12. The registers REG14–26 have Inputs BB0, BB1, . . . , BB12 and Outputs B), B1, . . . , B12. The registers REG27–39 have Inputs CC0, CC1, . . . , CC12 and Outputs C0, C1, . . . , C12. The arithmetic logic circuit 131 executes operations shown in Expressions (47), (48), (49) and (50) based on one data input. The 8-bit data D0–D7 read out of the data storage circuit 121 is added to the Outputs P0, A0–13, B0–13, C0–13 from the registers REG0–REG39 at XOR circuits. The Outputs PP), AA0–13, BB0–13, CC0–13 from the XOR circuits are led to the inputs of the registers REG0–39 and fetched in synchronization with the shift register clock. The XOR circuits connected to the registers REG1–13 configure an α⁸ arithmetic circuit, which receives the data D0–D7 input. The XOR circuits connected to the registers REG14–26 configure an α²⁴ arithmetic circuit, which receives the data D0–D7 input. The XOR circuits connected to the registers REG27–39 configure an α⁴⁰ arithmetic circuit, which receives the data D0–D7 input. In stead of the α⁴⁰ arithmetic circuit, because it has a large circuit scale, α⁴⁰ may be fed into one of inputs of the Galois arithmetic circuit 132 shown in FIG. 9, and the output thereof and the data D0–D7 are appropriately operated at XOR circuits.

<Computation of Syndrome S₀>
PP0=XOR9 (PO, D7, D6, D5, D4, D3, D2, D1, D0)   (47)
<Computation of Syndrome S₁>
AA0=XOR2(A5, D7)
AA1=XOR3(A5, A6, D6)
AA2=XOR3(A6, A7, D5)
AA3=XOR2(A5, A7, A8, D4)
AA4=XOR5(A5, A6, A8, A9, D3)
AA5=XOR5(A6, A7, A9, A10, D2)
AA6=XOR5(A7, A8, A10, A11, D1)
AA7=XOR5(A8, A9, A11, A12, D0)
AA8=XOR4(A0, A9, A10, A12)
AA9=XOR3(A1, A10, A11)
AA10=XOR3(A2, A11, A12)
AA11=XOR2(A3, A12)
AA12=A4   (48)
<Computation of Syndrome S₃>
BB0=XOR5(B1, B2, B7, B9, D7)
BB1=XOR7(B0, B1, B3, B7, B8, B9, B10)
BB2=XOR8(B1, B2, B4, B8, B9, B10, B11, D2)
BB3=XOR10(B0, B1, B3, B5, B7, B10, B11, B12, D6, D2)
BB4=XOR8(B0, B4, B6, B7, B8, B9, B11, B12)
BB5=XOR9(B1, B5, B7, B8, B9, B10, B12, D2, D1)
BB6=XOR10(B0, B2, B6, B8, B9, B10, B11, D5, D2, D1)
BB7=XOR7(B1, B3, B7, B9, B10, B11, B12)
BB8=XOR8(B2, B4, B8, B10, B11, B12, D1, D0)
BB9=XOR8(B3, B5, B9, B11, B12, D4, D1, D0)
BB10=XOR4(B4, B6, B10, B12)
BB11=XOR5(B0, B5, B7, B11, D0)
BB12=XOR7(B0, B1, B6, B8, B12, D3, D0)   (49)
<Computation of Syndrome S₅>
CC0=XOR13(C0, C1, C2, C4, C5, C7, C8, C9, C10 C11, C12, D7, D2)
CC1=XOR5(C3, C4, C6, C7, D2)
CC2=XOR8(C0, C4, C5, C7, C8, D4, D2, D0)
CC3=XOR10(C2, C4, C6, C7, C10, C11, C12, D4, D1, D0)
CC4=XOR9(C0, C1, C2, C3, C4, C9, C10, D1, D0)
CC5=XOR11(C0, C1, C2, C3, C4, C5, C10, C11, D6, D4, D2)
CC6=XOR12(C0, C1, C2, C3, C4, C5, C6, C11, C12, D4, D1, D0)
CC7=XOR11(C1, C2, C3, C4, C5, C6, C7, C12, D3, D2, D0)
CC8=XOR10(C0, C2, C3, C4, C5, C6, C7, C8, D3, D0)
CC9=XOR10(C0, C1, C3, C4, C5, C6, C7, C8, C9, D0)
CC10=XOR12(C1, C2, C4, C5, C6, C7, C8, C9, C10, D5, D3, D1)
CC11=XOR12(C0, C2, C3, C5, C6, C7, C8, C9, C10, C11, D3, D0)
CC12=XOR13(C0, C1, C3, C4, C6, C7, C8, C9, C10, C11, C12, D2, D1)   (50)
{circle around (2)} Error Position Detector (First Arithmetic Section)

[0100] FIG. 14 is a flowchart showing an operation of decoding in the ECC circuit 103.

[0101] A data read command (00h) is input, then a read address (Add) from external to start reading (S31). The data of one page (528 bytes) selected by the address is read out from the memory cells MC into the page buffers 102₀–102₇ (S32). Thereafter, in synchronization with a signal oscillated from the internal oscillator, the data D0–D7 is input byte by byte to the ECC circuit 103 to compute the syndrome (S33). As shown in FIG. 27, after computations of the syndromes S₀, S₁, S₃, S₅, if S₁=S₃=S₅=0 (S34) and if S₀=0 (S35), it is determined errorless (Normal output: S36). If S₀≠0 (S35), it is determined uncorrectable (S37). Unless S₁=S₃=S₅=0 (S34), computations are made for σ₂=S₁²S₃+S₅ and σ₀=S₁³+S₃ (S38). If σ₀=0 (S39) and if σ₂32 0 and S₀=0 (S40), it is determined 1-bit error, and the control goes to an algorithm for 1-bit error correction (S41). Unless σ₂=0 and S₀=0 (S40), it is determined uncorrectable (S42). If σ₀≠0 (S39), computations are made for σ₁=S₁(S₁³+S₃) and σ₃=(S₁³+S₃)²+S₁(S₁²S₃+S₅) (S43). If σ₃=0 (S44) and if σ₂≠0 and S₀=0 (S45), it is determined 2-bit errors, and the control goes to an algorithm for 2-bit error correction (S46). Unless σ₂≠0 and S₀=0 (S45), it is determined uncorrectable (S47). If σ₃≠0 (S44) and if S₀=1 (S48), it is determined 3-bit errors, and the control goes to an algorithm for 3-bit error correction (S49). The algorithm for 2-bit error correction is same as that for 3-bit error correction. If S₀≠1 (S48), it is determined uncorrectable (S50).

[0102] FIG. 15 shows an error position detector that executes the above computations. This error position detector includes a first arithmetic section, consisting of four registers R, A, B, C of 13 buts each, and not-depicted XOR circuits, contained in the arithmetic logic circuit 131. The error position detector also includes a Galois arithmetic circuit 132, and a second arithmetic section 133 consisting of eight locators 141 and arithmetic circuits 142 interposed between the locators 141 to operate xα, xα², xα³, 13-bit buses BUSR, BUSA, BUSB, BUSC are provided to connect them. The output from the Galois arithmetic circuit 132 is connected to the register R.

[0103] FIG. 16 shows an algorithm to compute the terms of the error position polynomial, σ₀, σ₁, σ₂, σ₃. The registers A, B, C store the syndromes S₁, S₃, S₅, respectively. If these syndromes are all zero, it is determined errorless and no operation is executed (S61). If not, an operation is made for σ₂=S₁²S₃+S₅ and the operated result is sequentially stored in the register R. The operated result finally obtained is transferred from the register R to the register C (S62). Next, an operation is made for σ₀=S₁³+S₃ and the operated result is sequently stored in the register R. The operated result finally obtained is transferred from the register R to the register B (S63). If the operated results stored in the registers B, C are both zero, then it is determined 1-bit error (S64) and “1” is stored in the register R (S65). If not, computations are made for σ₁=S₁(S₁³+S₃) and σ₃=(S₁³+S₃)²+S₁(S₁²S₃+S₅) (S66, S67, S68).

[0104] In the present embodiment, of the code length of n=8191, the information bits of k=4224 (528×8 bits) are subjected to the error correction, while the information bits can have 8151 bits except for 41 check bits originally in a code having the code length of n=8191. As a result, the error position is shifted by 8151−4224+1=3928 bits. On reading from a column address of 0, computations are performed to multiply σ₁ by α³⁹²⁸, σ₂ by α^{7856(=3928×2)}, and σ₃ by α^{3593(=3928×3−8191)} (S69, S70, S71). Similarly, on reading from a column address of i, computations are performed to multiply σ₁ by α³⁹²⁸⁺ⁱ, σ₂ by α^{7858(=(3928+i)×2)}, and σ₃ by α^{3596(=(3928+i)×3−8191)}. Factors such as α³⁹²⁸⁺ⁱ are written into a ROM, for example. The factor is stored in the vicinity of the column data storage or in the memory cell area 101, selected by the column selector 108 of FIG. 7, because it depends on the column address of i. Alternatively, only the factor at the column address of 0 is stored and, when another address is accessed, a dummy operation of detecting an error position is performed to provide a matched factor.

[0105] FIG. 17 is a block diagram showing the Galois arithmetic circuit 132 in detail.

[0106] 13-bit inputs A and B shown in FIG. 17A are respectively represented by:
A=a₀X⁰+a₁X¹+a₂X²+. . . +a₁₂X¹² B=b₀X⁰+b₁X¹+b₂X²+. . . +b₁₂X¹²   (51)
In this case, A×B can be represented by:

[0107] $\begin{array}{cc}\begin{array}{c}A\times B=A\left(b_0{X}^0+b_1{X}^1+b_2{X}^2+...+b_{12}{X}^{12}\right)\\ =A{b}_0+X\left(A{b}_1+X\left(A{b}_2+X\left(A{b}_3+......+X\left(A{b}_{12}\right)\right)\right)\right)))))))))\end{array}& \left(52\right)\end{array}$

[0108] This circuit can be configured as shown in FIG. 17B, in which A and Bi are subjected to the AND operation at an AND circuit 151. The operated result is then multiplied by X at an X multiplier 152, and the product is subjected at an XOR circuit 153 to the XOR operation with the AND-operated result from the next A and bi+1. From the α Minimal Polynomial M₁(x) in Expression (41), a relation of X¹³=X⁴+X³+X+1 is present. Therefore, as shown in FIG. 17C, the X multiplier 152 operates shifting the term of X¹² into the term of X⁰; adding it into the terms of X³, X¹, X⁰ by the XOR circuit 154; and storing it in the terms of X⁴, X³, X¹.

[0109] As a result of the above operations, 13-bit registers A, B, C, D are given σ₁, σ₃, σ₂, σ₀ as initial values, respectively.

{circle around (2)} Error Position Detector (Second Arithmetic Section)

[0110] Error bit positions can be detected based on the following error position polynomial (53) in the cases of 3-bit correction and 4-bit correction as it is known.
σ(Z)=S₁+σ₁×Z+σ₂×Z²+σ₃×Z³   (53)
When Z=α¹(I=0, 1, 2, 3, . . . ) is assigned in turn to Expression (53), the position of the error can be indicated by i that holds σ(α¹)=0. In the present embodiment, as 8-bit data is output per WE clock, Expression (53) is altered to Expression (54), like Expression (10) is altered to Expression (38) in the first embodiment.
σ(Z)=σ₀+σ₁×Z⁸+σ₂×Z¹⁶+σ₃×Z²⁴   (54)

[0111] As a result, the error detection can be performed by 8 bits simultaneously in each clock cycle of the error detection logic. In a word, of the output data of 8 I/O, the error detection is performed to the I/O 0. If an error is present, then σ=0. As a result of the computations in FIG. 16, the 13-bit registers A, B, C, D are given σ₁, σ₃, σ₂, σ₀ as initial values, respectively. The XOR circuits connected to the register A in the arithmetic logic circuit 131 configure an α⁸ arithmetic circuit. The XOR circuits connected to the register B configure an α²⁴ arithmetic circuit. The XOR circuits connected to the register C configure an α¹⁶ arithmetic circuit. The register A has Inputs AA0, AA1, . . . , AA12 and Outputs A0, A1, . . . , A12. The register B has Inputs BB0, BB1, BB12 and Outputs B0, B1 . . . B12. The register C has Inputs CC0, CC1, . . . , CC12 and Outputs C0, C1, . . . , C12. In this case, the α⁸, α¹⁶, α²⁴ arithmetic circuits perform operations respectively represented by Expressions (55), (56) and (57):
AA0=A5
AA1=XOR2(A5, A6)
AA2=XOR2(A6, A7)
AA3=XOR3(A5, A7, A8)
AA4=XOR4(A5, A6, A8, A9)
AA5=XOR4(A6, A7, A9, A10)
AA6=XOR4(A7, A8, A10, A11)
AA7=XOR4(A8, A9, A11, A12)
AA8=XOR4(A0, A9, A10, A12)
AA9=XOR3(A1, A10, A11)
AA10=XOR3(A2, A11, A12)
AA11=XOR2(A3, A12)
AA12=A4   (55)
<α¹⁶ arithmetic circuit>
CC0=XOR4(C6, C7, C9, C10)
CC1=XOR4(C6, C8, C9, C11)
CC2=XOR4(C7, C9, C10, C12)
CC3=XOR6(C0, C6, C7, C8, C9, C11)
CC4=XOR5(C0, C1, C6, C8, C12)
CC5=XOR4(C1, C2, C7, C9)
CC6=XOR5(C0, C2, C3, C8, C10)
CC7=XOR6(C0, C1, C3, C4, C9, C11)
CC8=XOR6(C1, C2, C4, C5, C10, C12)
CC9=XOR5(C2, C3, C5, C6, C11)
CC10=XOR5(C3, C4, C6, C7, C12)
CC11=XOR4(C5, C6, C7, C8)
CC12=XOR4(C5, C6, C8, C9)   (56)
<α²⁴ arithmetic circuit>
BB0=XOR4(B1, B2, B7, B9)
BB1=XOR7(B0, B1, B3, B7, B8, B9, B10)
BB2=XOR7(B1, B2, B4, B8, B9, B10, B11)
BB3=XOR8(B0, B1, B3, B5, B7, B10, B11, B12)
BB4=XOR8(B0, B4, B6, B7, B8, B9, B11, B12)
BB5=XOR7(B1, B5, B7, B8, B9, B10, B12)
BB6=XOR7(B0, B2, B6, B8, B9, B10, B11)
BB7=XOR7(B1, B3, B7, B9, B10, B11, B12)
BB8=XOR6(B2, B4, B8, B10, B11, B12)
BB9=XOR5(B3, B5, B9, B11, B12)
BB10=XOR4(B4, B6, B10, B12)
BB11=XOR4(B0, B5, B7, B11)
BB12=XOR5(B0, B1, B6, B8, B12)   (57)

[0112] FIG. 18 is a circuit diagram showing a specific arrangement of the locator 141. The locator 141 includes XOR circuits 161 and NOR circuits 162 to compute σ(Z) and outputs “H” if an error is present (σ=0) at the I/O 0 (j=1−7). As a result, the data inverter 134 of FIG. 9 inverts the data from the data storage circuit 121 in the page buffer 102₀ and outputs the inverted data. Alternatively, as indicated by a dashed arrow 135 in FIG. 9, error correction can be directly performed to the data at the error position in the page buffer 102.

[0113] On the other hand, the data at the I/O 1 has values in σ(Z) with the term of σ₁ multiplied by Z, the term of σ₂ multiplied by Z², and the term of σ₃ multiplied by Z³. Accordingly, as shown in FIG. 15, an arithmetic circuit 142₁ is mounted to operate the term of σ₁×X, the term of σ₂×X², and the term of σ₂×X³, and supplies the output to the locator 141₁ to solve the error position polynomial. If an error is detected (σ=0), the output comes to “H”. When these X, X², X³ arithmetic circuits are assumed to have Inputs X0–X12 and Outputs Y0–Y12, the arithmetic circuits execute the following operations. The arithmetic circuits are not required to have registers to store data.

<X arithmetic circuit>
Y0=X12
Y1=XOR2(X0, X12)
Y2=X1
Y3=XOR2(X2, X12)
Y4=XOR2(X3, X12)
Y5=X4
Y6=X5
Y7=X6
Y8=X7
Y9=X8
Y10=X9
Y11=X10
Y12=X11   (58)
<X² arithmetic circuit>
Y0=X11
Y1=XOR2(X11, X12)
Y2=XOR2(X0, X12)
Y3=XOR2(X1, X11)
Y4=XOR3(X2, X11, X12)
Y5=XOR2(X3, X12)
Y6=X4
Y7=X5
Y8=X6
Y9=X7
Y10=X8
Y11=X9
Y12=X10   (59)
<X³ arithmetic circuit>
Y0=X10
Y1=XOR2(X10, X11)
Y2=XOR2(X11, X12)
Y3=XOR3(X0, X10, X11)
Y4=XOR3(X1, X10, X11)
Y5=XOR3(X2, X11, X12)
Y6=XOR2(X3, X12)
Y7=X4
Y8=X5
Y9=X6
Y10=X7
Y11=X8
Y12=X9   (60)

[0114] The data at the I/0 2 has values in σ(Z) with the term of σ₁ multiplied by Z², the term of σ₂ multiplied by Z⁴, and the term of σ₃ multiplied by Z⁶. If arithmetic circuits are mounted to operate the term of σ₁×X², the term of σ₂×X⁴, and the term of σ₂×X⁶ on the basis of I/O 0, the arithmetic circuit for a large multiplication such as X⁶ increases the circuit scale. Therefore, in this embodiment, an arithmetic circuit 141₁ is provided to multiply the output from the arithmetic circuit 141₂ by ×X, ×X², ×X³ again. Similarly, arithmetic circuits are provided up to 141₇ corresponding to the I/0 7.

[0115] If there is a problem on a signal transmission time delay, the eight locators 141 configuring the error position detector (second arithmetic section) 133 may be divided in two groups of four locators, as shown in FIG. 19, which are arranged on both sides of the arithmetic logic circuit 131. This arrangement is effective to halve the signal transmission path to the locator 141.

[0116] FIG. 20 is a timing chart on decoding in the ECC circuit 103. FIG. 20A shows data reading and error correcting after computations of all terms in the error position polynomial.

[0117] When a data read command (00h) is input from external, followed by a read address (Add), a READY/BUSY signal is activated to start reading. First, the data of one page (528 bytes) selected by the address is read out from the memory cells MC into the page buffers 102₀–102₇. Then, in synchronization with a signal oscillated from the internal oscillator, the data D0–D7 is input byte by byte to the ECC circuit 103 to compute the syndromes and operate the terms of the error position polynomial using the computed syndromes S₀, S₁, S₃, S₅. Thereafter, the data is read out in synchronization with the write enable (RE) signal and the error correction is executed at the same time. In this case, compared to the absence of the ECC circuit 103, an additional busy time is derived from a computation time for syndromes plus a computation time for error correction operators in total. For example, if one syndrome computation requires 50 ns and an arithmetic time for an operator is equal to 3.6 μs, then 528×50 ns+3.6 μs=30 μs.

[0118] FIG. 20B shows an example of computing the syndromes S₀, S₁, S₃, S₅ at the same time of data reading. After the reading is started similarly, the data of one page (528 bytes) is read out from the memory cells MC into the page buffers 102₀–102₇. Then, the data is output from the page buffers 102₀–102₇ byte by byte in synchronization with the RE signal and the ECC circuit 103 computes the syndromes. As a result of the syndrome computation, if an error is detected, a status fail command (70h) is activated. Accordingly, an operator for error correction is computed and the data is output again to correct the error. In this case, if no error is present, an additional busy time in total is equal to zero.

[0119] As for 2-bit error correction and 3-bit error detection, the number of permissible random failures (the number of random failures at a device failure probability of 1 ppm) is naturally better in the case of 528 information bits than in the case of 4224 information bits. Table 1 shows an application to a 256 Mb NAND-type flash memory.

[0120] From Table 1, the number of permissible random failures is 100 bits at 2-bit correction BCH code for 528 information bits, and only 30 bits for 4224 information bits. To the contrary, at 3-bit correction BCH code for 4224 information bits, the random failures can be permitted up to 300 bits with a necessary code as short as 40 bits. Further, at 4-bit correction BCH code for 4224 information bits, the random failures can be permitted up to 1000 bits with a necessary code as short as 53 bits effectively.

[0121]

TABLE 1
Number of random failures in 256 Mb at
Device failure probability of 1 ppm
	Code length per	Number of
	Page (528 B)	Failures
	2-bit correction BCH code	21 × 8 = 168 bits	100 bits
	(528 information bits)
	2-bit correction BCH code	27 bits	30 bits
	(4224 information bits)
	3-bit correction BCH code	40 bits	300 bits
	(4224 information bits)
	4-bit correction BCH code	53 bits	1000 bits
	(4224 information bits)

[0122] Table 2 shows chip sizes of NAND-type flash memories of 128 M-bits and 512 M-bits when no ECC circuit is mounted, compared with those when the conventional 2-bit correction ECC circuit is mounted, and those when the 2-bit correction ECC circuit of the present embodiment is mounted.

[0123]

	TABLE 2
	128M (0.16 μm)	512M (0.16 μm)
No ECC circuit	41.88 mm2 (100.0%)	136.99 mm2 (100.0%)
ECC circuit mounted	44.72 mm2 (106.8%)	143.96 mm2 (105.1%)
(Conventional)
ECC circuit mounted	43.21 mm2 (103.2%)	140.42 mm2 (102.5%)
(Embodiment)

[0124] Thus, the flash memory with the conventional ECC circuit mounted thereon has an increase in chip size of 6.8% (128 M) and 5.1% (512 M). To the contrary, the flash memory with the ECC circuit of the present embodiment mounted thereon has an increase in chip size of 3.2% (128 M) and 2.5% (512 M), which is half the conventional one.

[0125] As obvious from the forgoing, the information bits are generated per M-bit that is a unit for accessing each memory area in the art. To the contrary, according to the embodiments of the invention, N bits can be processed in parallel. Therefore, it is possible to allocate a set of check bits to M×N bits and reduce the number of check bits in total relative to the number of information bits. This is effective to improve a chip integration density while mounting an on-chip error correction circuit.

[0126] Having described the embodiments consistent with the invention, other embodiments and variations consistent with the invention will be apparent to those skilled in the art. Therefore, the invention should not be viewed as limited to the disclosed embodiments but rather should be viewed as limited only by the spirit and scope of the appended claims.