(en)A memory system according to the embodiment comprises a cell array including word lines and plural memory cells operative to store data in accordance with plural different physical levels when selected by the word lines; a register operative to hold first data input from external; and a data converter unit operative to convert the first data held in the register into second data and overwrite the second data in the area of the register for holding the first data, and further operative to convert the second data held in the register into third data to be recorded in the memory cells and overwrite the third data in the area of the register for holding the second data.

1.ApplicationNumber: US-201113232456-A
1.PublishNumber: US-8595592-B2
2.Date Publish: 20131126
3.Inventor: TODA HARUKI

4.Inventor Harmonized: TODA HARUKI(JP)

5.Country: US
6.Claims:
(en)A memory system according to the embodiment comprises a cell array including word lines and plural memory cells operative to store data in accordance with plural different physical levels when selected by the word lines; a register operative to hold first data input from external; and a data converter unit operative to convert the first data held in the register into second data and overwrite the second data in the area of the register for holding the first data, and further operative to convert the second data held in the register into third data to be recorded in the memory cells and overwrite the third data in the area of the register for holding the second data.

7.Description:
(en)CROSS-REFERENCE TO RELATED APPLICATION
This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2010-214357, filed on Sep. 24, 2010, the entire contents of which are incorporated herein by reference.
FIELD
The embodiment relates to a memory system.
BACKGROUND
In recent years, mass data is held in mobile devices, for example, in handheld smart terminals and electronic books for fast access. Such technologies have become important increasingly. Further, from the viewpoint of weight-reducing and energy-saving of information devices, integrated circuit memories having no moving parts such as a motor has proceeded rapidly. The importance in this case is how to use up memory cells in performance marginal parts on memory production. In accordance with this, lower prices and larger capacities due to improvements in productivity of memories can be realized. In addition, the reliability of data stored in such the mass-capacity memories becomes important.
Even with no large-scale technical innovation, mass-capacity memories can be realized. One such method is a multi-level technology, which can increase the storage capacity per memory cell. In addition, as the technology of insuring data for marginal memory cells, ECC is known. In particular, as for NAND flash memories, multi-levels of memory cells and ECC system technologies have been matured and almost completed.
Such the NAND flash memories have been used increasingly wider, for example, in mobile terminals and SSDs. Accordingly, it is required to achieve additional technical leaps for the NAND flash memories. For that purpose, it is required to add innovative modifications to the conventional multi-leveling technologies and ECC.
The multi-leveled NAND flash memories have been developed originally based on the specifications without consideration of multi-level. In addition, the ECC is applied to the NAND flash memories based on the technologies for the system of the overall memory. Therefore, the multi-leveling technologies and ECC have not been made optimal as the technology kept with multi-levels of memory cells.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a table showing relations among the numbers of levels of p-adic cells, the data storage efficiencies and so forth in a memory system according to a first embodiment.
FIG. 2 is a conceptual view of the memory system according to the present embodiment.
FIG. 3 is a diagram illustrative of the outline of a data interface in the memory system according to the present embodiment.
FIG. 4 is a diagram illustrative of the procedure of data transfer in the memory system according to the present embodiment.
FIG. 5 is a diagram illustrative of write processing at every sector in the memory system according to the present embodiment.
FIG. 6 is a diagram illustrative of read processing at every sector in the memory system according to the present embodiment.
FIG. 7 is a diagram illustrative of assigning numerals in a finite field Zp (p=17) to p-adic cells in the memory system according to the present embodiment.
FIG. 8 is a diagram illustrative of write/read methods in the memory system according to the present embodiment.
FIG. 9 is a diagram illustrative of word-line level conversion and data transfer timing at the time of write/read in the memory system according to the present embodiment.
FIG. 10 is a diagram illustrative of the configuration of a to-17-adic converter circuit in the memory system according to the present embodiment.
FIG. 11 is a block diagram of a to-17-adic converter circuit corresponding to 1 step (“X to p” circuit block) in the memory system according to the present embodiment.
FIG. 12 is a block diagram of the “X to p” circuit block in the memory system according to the present embodiment.
FIG. 13 is a diagram showing a circuit symbol of the “X to p” circuit block in the memory system according to the present embodiment.
FIG. 14 is a diagram showing a circuit symbol of an operating circuit element for deriving elements in Zp (“6 bit mod 17” circuit block) in the memory system according to the present embodiment.
FIG. 15 is a block diagram of the “6 bit mod 17” circuit block in the memory system according to the present embodiment.
FIG. 16 is a diagram showing a circuit symbol of a to-17-adic conversion core (“p-adic” circuit block) in the memory system according to the present embodiment.
FIG. 17 is a block diagram of the “p-adic” circuit block in the memory system according to the present embodiment.
FIG. 18 is a block diagram of the to-17-adic converter circuit in the memory system according to the present embodiment.
FIG. 19 is a circuit diagram of a “D-r” register in the memory system according to the present embodiment.
FIG. 20 is a timing chart of timing signals for use in control of the to-17-adic converter circuit in the memory system according to the present embodiment.
FIG. 21 is a diagram illustrative of the configuration of a to-2 5 -adic converter circuit in the memory system according to the present embodiment.
FIG. 22 is a block diagram of a to-2 5 -adic converter circuit corresponding to 1 step (“a to X” circuit block) in the memory system according to the present embodiment.
FIG. 23 is a block diagram of the “a to X” circuit block in the memory system according to the present embodiment.
FIG. 24 is a diagram showing a circuit symbol of the “a to X” circuit block in the memory system according to the present embodiment.
FIG. 25 is a diagram showing a circuit symbol of an operating circuit element for deriving a binary element (“6 bit add 17” circuit block) in the memory system according to the present embodiment.
FIG. 26 is a block diagram of the “6 bit add 17” circuit block in the memory system according to the present embodiment.
FIG. 27 is a block diagram of a to-2 5 -adic converter circuit block corresponding to 1 step (“p to X” circuit block) common to the memory system according to the present embodiment.
FIG. 28 is a diagram showing a circuit symbol of the “p to X” circuit block in the memory system according to the present embodiment.
FIG. 29 is a diagram showing a circuit symbol of a to-2 5 -adic converter circuit core (“binary” circuit block) in the memory system according to the present embodiment.
FIG. 30 is a block diagram of the “binary” circuit block in the memory system according to the present embodiment.
FIG. 31 is a block diagram of a to-2 5 -adic converter circuit in the memory system according to the present embodiment.
FIG. 32 is a circuit diagram of an “A-r” register in the memory system according to the present embodiment.
FIG. 33 is a block diagram of the memory system according to the present embodiment.
FIG. 34 is a flowchart of encoding in the memory system according to the present embodiment.
FIG. 35 is a flowchart of decoding in the memory system according to the present embodiment.
FIG. 36 is a flowchart of decoding in the memory system according to the present embodiment.
FIG. 37 is a diagram showing a circuit symbol of a multiplier circuit for deriving the product of elements in Zp (“X Zp” circuit block) in the memory system according to the present embodiment.
FIG. 38 is a block diagram of the “X Zp” circuit block in the memory system according to the present embodiment.
FIG. 39 is a diagram showing a circuit symbol of an operating circuit element for deriving the sum of elements in Zp (“5 bit AD mod 17” circuit block) in the memory system according to the present embodiment.
FIG. 40 is a block diagram of the “5 bit AD mod 17” circuit block in the memory system according to the present embodiment.
FIG. 41 is a block diagram of a circuit for deriving a code component to be stored in a memory in the memory system according to the present embodiment.
FIG. 42 is a diagram showing a circuit symbol of a circuit for deriving the cumulative sum of elements in Zp (“X k-times” circuit block) in the memory system according to the present embodiment.
FIG. 43 is a block diagram of the “X k-times” circuit block in the memory system according to the present embodiment.
FIG. 44 is a block diagram of a circuit for deriving a syndrome in the memory system according to the present embodiment.
FIG. 45 is a block diagram of a circuit for deriving a syndrome in the memory system according to the present embodiment.
FIG. 46 is a block diagram of a circuit for deriving a syndrome in the memory system according to the present embodiment.
FIG. 47 is a diagram showing a circuit symbol of a circuit for deriving the cumulative sum of elements in Zp (“(j) i (j=1 to 16)” circuit block) in the memory system according to the present embodiment.
FIG. 48 is a block diagram of the “(j) i (j=1 to 16)” circuit block in the memory system according to the present embodiment.
FIG. 49 is a block diagram of a circuit for deriving a solution searching polynomial in the memory system according to the present embodiment.
FIG. 50 is a block diagram of a circuit for deriving coefficients of a Hasse differential polynomial in the memory system according to the present embodiment.
FIG. 51 is a table of various operational results over elements in Zp in the memory system according to the present embodiment.
FIG. 52 is a circuit diagram of a decoder for deriving the correspondences among elements in Zp in the memory system according to the present embodiment.
FIG. 53 is a block diagram of a circuit for deriving a polynomial solution and the associated multiplicity in the memory system according to the present embodiment.
FIG. 54 is a block diagram of a circuit for deriving a true error from a root and multiplicity pair of the Hasse differential polynomial to execute code correction in the memory system according to the present embodiment.
FIG. 55 is a block diagram of an operating circuit for computing a Lee metric of the error code word in the memory system according to the present embodiment.
FIG. 56 is a diagram showing a circuit symbol of an operating circuit element for computing the Lee metric (“5 bit LM 17” circuit block) in the memory system according to the present embodiment.
FIG. 57 is a block diagram of the “5 bit LM 17” circuit block in the memory system according to the present embodiment.
FIG. 58 is a diagram showing a circuit symbol of a unit contained in a computing circuit for deriving A=CG −1 from C=AG (“c (m−1) j” circuit block) in the memory system according to the present embodiment.
FIG. 59 is a block diagram of the “c (m−1) j” circuit block in the memory system according to the present embodiment.
FIG. 60 is a diagram showing a circuit symbol of a unit contained in the computing circuit for deriving A=CG −1 from C=AG (“a m ” circuit block) in the memory system according to the present embodiment.
FIG. 61 is a block diagram of the “a m ” circuit block in the memory system according to the present embodiment.
FIG. 62 is a block diagram of the computing circuit for deriving C=CG −1 from C=AG in the memory system according to the present embodiment.
FIG. 63 is a block diagram of a memory system according to a second embodiment.
FIG. 64 is a block diagram of a circuit for deriving component elements of a syndrome in the memory system according to the present embodiment.
FIG. 65 is a diagram showing a circuit symbol of a circuit for use in a Euclidean iterative method (“kn” circuit block) in the memory system according to the present embodiment.
FIG. 66 is a block diagram of the “kn” circuit block in the memory system according to the present embodiment.
FIG. 67 is a diagram showing a circuit symbol of a circuit for use in a Euclidean iterative method (“fn” circuit block) in the memory system according to the present embodiment.
FIG. 68 is a block diagram of the “fn” circuit block in the memory system according to the present embodiment.
FIG. 69 is a diagram illustrative of a circuit symbol of a circuit for use in a Euclidean iterative method (“pn” circuit block) in the memory system according to the present embodiment.
FIG. 70 is a block diagram of the “pn” circuit block in the memory system according to the present embodiment.
FIG. 71 is a diagram showing a circuit symbol of a circuit for use in a Euclidean iterative method (“f n =k n f n+1 +f n+2 ” circuit block) in the memory system according to the present embodiment.
FIG. 72 is a block diagram of the “f n =k n f n+1 +f n+2 ” circuit block in the memory system according to the present embodiment.
FIG. 73 is a diagram showing a circuit symbol of a circuit for use in a Euclidean iterative method (“p n+1 =k n p n +p n−1 ” circuit block) in the memory system according to the present embodiment.
FIG. 74 is a block diagram of the “p n+1 =k n p n +p n−1 ” circuit block in the memory system according to the present embodiment.
FIG. 75 is a block diagram of a circuit for use in the Euclidean iterative method in the memory system according to the present embodiment.
FIG. 76 is a block diagram of a circuit for use in the Euclidean iterative method in the memory system according to the present embodiment.
FIG. 77 is a diagram showing a circuit symbol of a circuit for use in a Euclidean iterative method (“DEG” circuit block) in the memory system according to the present embodiment.
FIG. 78 is a block diagram of the “DEG” circuit block in the memory system according to the present embodiment.
FIG. 79 is a block diagram of a circuit for deciding the stop condition on the Euclidean iterative method in the memory system according to the present embodiment.
FIG. 80 is a block diagram of a circuit for deciding the success condition on the Euclidean iterative method in the memory system according to the present embodiment.



DETAILED DESCRIPTION
A memory system according to the embodiment comprises a cell array including word lines and plural memory cells operative to store data in accordance with plural different physical levels when selected by the word lines; a register operative to hold first data input from external; and a data converter unit operative to convert the first data held in the register into second data and overwrite the second data in the area of the register for holding the first data, and further operative to convert the second data held in the register into third data to be recorded in the memory cells and overwrite the third data in the area of the register for holding the second data.
With reference to the drawings, memory systems according to the embodiments will now be described below.
Overview of Embodiment
A memory system realizes a higher-density storage capacity by finely fabricating a cell array, forming the cell array and so forth in 3-dimensional structures, and thinking physical phenomena for use in memory cells. If the memory system is further required to have a higher density after completion of stable process steps, multi-leveling of memory cells is effective means.
In particular, as for NAND flash memories, multi-leveling proceeds promptly and 3-bit cells capable of storing 8 levels per cell become practical. Much higher multi-leveling of memory cells associates with a sudden deterioration of reliability, however, and suffers a 2-decimal places or more error rate per bit error rate increase at least. Thus, from the problem on the reliability and production yield, the progression of multi-leveling of memory cells has a difficult problem even though it is expected as means for realizing high-capacity file memories.
If the problem on multi-leveling of memory cells can be overcome to achieve effective use, NAND flash memories can be attained to have a higher-density storage capacity while utilizing stable process steps for NAND flash memories for longer terms.
Therefore, the first embodiment, under the following gist, proposes a memory system utilizing a Lee metric code.
(1) An error in a memory cell, in many cases, may be caused by writing an adjacent level in the memory cell and reading an adjacent level from the memory cell. Even in such the case, the assignment of binary bits to the conventional memory cell may cause a larger error quantity. Therefore, the memory system according to the embodiment described below utilizes multi-level storage cells with reliability improved by simplifying the assignment of levels to a memory cell.
(2) A multi-level of the memory cell can be grasped as a height from the base level. In a word, a multi-leveled memory cell is suitable for storing information not digitalized by a binary but digitalized by a prime. Therefore, the memory system according to the embodiment described below is configured with the use of memory cells having physical quantity levels assigned to elements in a finite field Zp of a prime p (hereinafter referred to as “p-adic cells”).
(3) An ECC (Error Correcting Code) effective in the case of the error caused by writing an adjacent level in the memory cell and reading an adjacent level from the memory cell is a Lee metric code in the finite field Zp. Therefore, the memory system according to the embodiment described below utilizes an ECC system that uses a Lee metric code thought to cause no error searching miss.
(4) The configuration of the NAND flash memory using p-adic cells is different from the configuration of the conventional NAND flash memory. Therefore, the embodiment described below proposes an essential idea of the specification about a specific memory system and describes the memory system configured based thereon.
(5) If it is desired to set a larger correctable error quantity, an error correcting method using a Euclidean iterative method may be effective if it is used as the error correcting method using the Lee metric code ECC. Therefore, the following description is given to specific circuits required to realize the memory system using the Euclidean iterative method for error correction.
First Embodiment
Lee Metric Code
First, an overview of the Lee metric code is described.
A symbol c representative of the code is an integer shown in Expression 1.

c j εGF ( p )= Zp, 0 ≦c<p [Expression 1]

When the metrics of these integers are represented by |c j | as Lee metrics and all Lee metrics |c j | are represented by integers of p/2 or below, the Lee metrics |c j | can be defined as in Expression 2.

0 ≦c<p/ 2 :|c j |=c j

p/ 2 <c<p:|c j |=p−c j [Expression 2]

As the code C can be considered a row of n (=p−1) symbols c j , it can be represented by C=(c 1 , c 2 , . . . , c n ), and a metric w(C) of the code C can be defined as the sum of Lee metrics of the symbols c j as in Expression 3.

w ( C )=| c 1 |+|c 2 |+ . . . +|c n | [Expression 3]

The distance between codes can be defined by the sum of Lee metrics of differences between the symbols corresponding to the code. Here, a difference between 2 symbols c and y (Lee distance) d L (c, y) is given as Expression 4.

d L ( c,y )= w ( c−y ) [Expression 4]

Further, the minimum Lee distance of the code C can be defined by the minimum metric of the metrics w(C) of the code C as shown in Expression 5.

d L ( C )=min w ( C ) [Expression 5]

In this case, the Lee metric code is such a code that has the minimum distance of 2γ between codes having a generator matrix G and a syndrome matrix H shown in Expression 6 and that can correct (γ−1) or lower Lee metric errors.
G = [ 1 2 ⋯ ( p - 1 ) 1 2 2 2 ⋯ ( p - 1 ) 2 ⋮ ⋮ ⋱ ⋮ 1 k 2 k ⋯ ( p - 1 ) k ] ,
⁢ H = [ 1 2 ⋯ ( p - 1 ) 1 1 2 1 ⋯ ( p - 1 ) 1 ⋮ ⋮ ⋱ ⋮ 1 γ - 1 2 γ - 1 ⋯ ( p - 1 ) γ - 1 ] [ Expression ⁢ ⁢ 6 ]
Here, when the word length of the code C is denoted with n and the word length of data is denoted with k, then γ=n−k where γ represents the redundant word length contained in the code C.

For the purpose of generating the Lee metric code thus configured, the input-converted data is presented by a k-digit, p-adic number. The numerals on the digits of the p-adic number are the elements in Zp and therefore can be used as a data word X of the Lee metric code to obtain a code expression through an operation C=XG based on the generator matrix G. The obtained code word is stored in the memory. Information about the error caused on the stored numeral in Zp is used as a data word Y of the Lee metric code read out of the memory to obtain a syndrome through an operation S=YH t (H t is a transpose of H) so that the position and quantity of the error can be computed to correct the error.
<Principle of Data Processing, Syndrome Converting Method>
The following description is given to the principle of a data processing method in the NAND flash memory using p-adic cells. Hereinafter, the principle is referred to as a “syndrome converting method”.
The components of the code C held in the p-adic cells are the numerals in Zp and they cause variations on receipt of various disturbances at every component and make a change to the code Y consisting of different components as shown in Expression 7.

Y =( y i ), y i =c i +e i ,i= 1 ˜p− 1 [Expression 7]

The operation to restore C from Y is decoding. Prior to decoding, a syndrome is derived.
After selecting 3-component vectors <m>=<m 1 , m 2 , m 3 > (m i =0 to p−2) from Zp and applying a matrix operation of these vectors and H matrix as in Expression 8, a syndrome <m> S can be derived as elements S <m>+0 , S <m>+1 , S <m>+ε where ε=γ−1.







⁢

[

Expression
⁢



⁢
8

]











〈
m
〉


⁢
S

=



Y
⁡

[




(

p
-

1

-
1



)



0


⋯


0




0



(

p
-

2

-
1



)



⋯


0




⋮


⋮


⋱


⋮




0


0


⋯



{

p
-


(

p
-
1

)


-
1



}




]



m
3


⁢







[




(

p
-
1

)



0


⋯


0




0



(

p
-
2

)



⋯


0




⋮


⋮


⋱


⋮




0


0


⋯



{

p
-

(

p
-
1

)


}




]


m
2


⁡

[



1


0


⋯


0




0


2


⋯


0




⋮


⋮


⋱


⋮




0


0


⋯



(

p
-
1

)




]



m
1


⁢

H
t








After setting <m> S=(S <m>+l ) (l=0 to ε), and deriving S 0 from <m>+1=0, if |S 0 |≦ε, then decoding starts.
This is because the generator matrix G and the syndrome matrix H are configured to satisfy GH t =0(mod p), for example. Therefore, the substitution of Y=C+E makes zero the part corresponding to C as shown in Expression 9 so that S can be represented by the components of E.









∑

j
=
1


p
-
1


⁢



⁢



(

p
-

j

-
1



)


m
3


⁢


(

p
-
j

)


m
2


⁢


(
j
)


m
1


⁢


(
j
)

1

⁢

c
j



=



∑

i
=
0


p
-
ɛ
-
3


⁢



⁢


a
i

⁢


∑

j
=
1

p

⁢



⁢



(
j
)


i
+
1
+
1
+

m
1



⁢


(

p
-
j

)


m
2


⁢


(

p
-

j

-
1



)


m
3






=


0
⇒

S


〈
m
〉

+
1



=



∑

j
=
1


p
-
1


⁢



⁢



(

p
-

j

-
1



)


m
3


⁢


(

p
-
j

)


m
2


⁢


(
j
)


m
1


⁢


(
j
)

1

⁢

y
j



=


∑

j
=
1


p
-
1


⁢



⁢



(

p
-

j

-
1



)


m
3


⁢


(

p
-
j

)


m
2


⁢


(
j
)



m
1

+
1


⁢

e
j










[

Expression
⁢



⁢
9

]







If <m>=<0>, l=0 and E=(e 1 , e 2 , . . . , e n ), the representation of S <0>+0 =S 0 =Σe j can be given so that S 0 indicates the total sum of errors as can be found.
If |S 0 |≦γ−1, an error can be found through the following syndrome converting method. Even if this condition is not satisfied, the value of the error on the code component can be obtained according to the computation. It is not possible to determine whether the error is an error on a true code or an error on an adjacent code. Therefore, it cannot be used in error correction. This is because the requirement for enabling error correction of the Lee metric code includes the minimum value of the Lee metric code between codes being equal to 2γ, and because in this case the Lee metric code of S 0 always becomes equal to ε or below, that is, the total sum of Lee metrics of error components becomes equal to ε or below.
If |S 0 |≦ε, the flow enters the error searching through the syndrome converting method and executes the syndrome conversion at the start. In this case, the flow seeks u=ε(S <m>+0 ) −1 that makes uS <m>+0 ≡ε over <m> that leads to S <m>+0 ≠0, from Expression 10, to obtain a new syndrome u <m> S=(uS <m>+0 , uS <m>+1 , . . . , uS <m>+ε ).








uS


〈
m
〉

+
0


=



∑

j
=
1


p
-
1


⁢

u
⁢



⁢


(

p
-

j

-
1



)


m
3


⁢


(

p
-
j

)


m
2


⁢


(
j
)


m
1


⁢

e
j



=

ɛ
≡

u
⁢


∑

j
=
1


p
-
1


⁢



(
j
)


〈
n
〉


⁢

e
j










[

Expression
⁢



⁢
10

]







Subsequently, the converted syndrome is used to decode the error. This method is described.
The code stored in the memory cell array contains the error E=(e 1 , e 2 , . . . , e n ) (n=p−1). Accordingly, a virtual error on the new syndrome includes {u(1) <m> e 1 , u(2) <m> e 2 , . . . , u(n) <m> e p−1 }. These n (=p−1) error components are converted and classified into 2 sets J + and J − as in Expression 11.

J + ={j ε(1,2 , . . . , n ); e j <p/ 2}

J − ={j ε(1,2 , . . . , n ); e j >p/ 2} [Expression 11]

Namely, it is classified into J + , which is an arrangement of the positions j of the symbols c j , if the error quantity of the symbol is u(j) <m> e j <p/2, and J − , which is an arrangement of the positions j of the symbols c j , if the error quantity of the symbol is u(j) <m> e j >p/2. Polynomials Λ(x), V(x) on Zp are configured on the basis of these sets as in Expression 12.

Λ ⁡ ( x ) = ∏ j ∈ J + ⁢ ⁢ ( 1 - jx ) u ⁡ ( j ) 〈 m 〉 e j ,
⁢ V ⁡ ( x ) = ∏ j ∈ J - ⁢ ⁢ ( 1 - jx ) p - u ⁡ ( j ) 〈 m 〉 e j [ Expression ⁢ ⁢ 12 ]
Thus, the polynomial Λ(x) is such a polynomial that has a reciprocal number of the error component position j in J + as a root, and that has a Lee metric u(j) <m> e j of that error component as the multiplicity of the root. On the other hand, the polynomial V(x) is such a polynomial that has a reciprocal number of the error component position j in J − as a root, and that has a Lee metric p−u(j) <m> e j of that error component as the multiplicity of the root. Decoding is a process of finally configuring these polynomials only from the information on the syndromes to solve them, thereby obtaining information on errors. In a word, it is required to seek a relation between these polynomials Λ(x), V(x) and the syndromes. When it is configured with a series polynomial having each syndrome u <m> S on a coefficient of the corresponding degree, it is represented with a rational polynomial having the position of the error composition and the value of the virtual error composition in factors thereof as in Expression 13.

S ⁡ ( x ) = ∑ l = 1 ∞ ⁢ uS 〈 m 〉 + 1 ⁢ x 1 = ∑ j = 1 p - 1 ⁢ u ⁡ ( j ) 〈 m 〉 ⁢ e j ⁢ ∑ l = 1 ∞ ⁢ ( jx ) 1 = ∑ j = 1 p - 1 ⁢ u ⁡ ( j ) 〈 m 〉 ⁢ e j ⁢ jx 1 - jx [ Expression ⁢ ⁢ 13 ]
From Expression 13, a relational equation shown in Expression 14 can be established among the polynomials Λ(x), V(x) and the syndrome S(x).










(


Λ
⁡

(
x
)



V
⁡

(
x
)



)

⁢

S
⁡

(
x
)



=

-


x
⁡

(


Λ
⁡

(
x
)



V
⁡

(
x
)



)


′






[

Expression
⁢



⁢
14

]







Subsequently, the relational equation shown in Expression 14 is used to seek the polynomials Λ(x), V(x) from the syndrome S(x).
From the syndrome S(x), a polynomial Ψ(x) with a degree of γ−1 or lower shown in Expression 15 is sought.










Ψ
⁡

(
x
)


⁢

S
⁡

(
x
)



≡


-
x

⁢



⁢


Ψ
′

⁡

(
x
)


⁢

(

mod
⁢



⁢

x
γ


)



⁢




⁢



Ψ
⁡

(
x
)


=

1
+


∑

j
=
1


⁢


ψ
j

⁢

x
j





,




⁢


ψ
j

=


-

1
j


⁢


∑

i
=
1

j

⁢


ψ

j
-
i


⁢

uS


〈
m
〉

+
i











[

Expression
⁢



⁢
15

]







In an expansive expression of the polynomial Ψ(x), a coefficient ψ j can be sought from a comparison between coefficients of the homogeneous degree on both sides of the expression shown in Expression 15 through an iterative method using the syndrome uS <m>+j and an already-determined coefficient ψ j−1 . Coefficients ψ 0 -ψ ε of the polynomial Ψ(x) are sought from syndromes uS <m>+0 to uS <m>+ε . The results are shown in Expression 16.









ψ
0

=
1

⁢




⁢


ψ
1

=



-

ψ
0


⁢

uS


〈
m
〉

+
1



=

-

uS


〈
m
〉

+
1





⁢




⁢





ψ
2

=


-

(



ψ
1

⁢

uS


〈
m
〉

+
1



+


ψ
0

⁢

uS


〈
m
〉

+
2




)


/
2







=


-

u
⁡

(



ψ
1

⁢

S


〈
m
〉

+
1



+


ψ
0

⁢

S


〈
m
〉

+
2




)



/
2





⁢




⁢
⋮
⁢




⁢





ψ

γ
-
1


=


-

(



ψ

ɛ
-
1


⁢

uS


〈
m
〉

+
1



+
…
+


ψ
0

⁢

uS


〈
m
〉

+
ɛ




)


/
ɛ







=


-

u
⁡

(



ψ

ɛ
-
1


⁢

S


〈
m
〉

+
1



+
…
+


ψ
0

⁢

S


〈
m
〉

+
ɛ




)



/
ɛ









[

Expression
⁢



⁢
16

]







The polynomial Ψ(x) is a polynomial equivalent to Λ(x)/V(x). In this case, the key conditions on mutual primes λ(x) and ν(x) are given as in Expression 17. Therefore, V(x)=1 can be established and Ψ(x) can be applied as Λ(x) itself.

v ( x )Ψ( x )≡λ( x )(mod x ε+1 )

deg λ( x )− deg v ( x )= =ε(mod p )

deg λ( x )− deg v ( x )≦ε [Expression 17]

The condition, deg λ(x)−deg ν(x)=ε and deg λ(x)+deg ν(x)≦ε, on the degree of the polynomial results in 0≦2 deg ν(x)≦0, which establishes deg ν(x)=0 as can be found. Namely, as V(x)=1 and Λ(x)=Ψ(x) can be established, so Ψ(x) can satisfy this condition. In this case, ε previously determined by Ψ(x) derived from the syndrome, and ε=deg Ψ(x)=deg Λ(x) should be established. If it is established, all key conditions can be satisfied and accordingly Ψ(x) can be used to obtain a solution. On the other hand, if it is not established, no error satisfies the key conditions, resulting in no solution.
This method corresponds to conversions, which collect the positions of all error code components into the set J + , applied to errors. Another viewpoint indicates the presence of the possibility of error correction if conversions are executed such that the total sum of the converted errors reaches ε.
The possibility referred above has two meanings. The first is associated with the requirement in which the positions of all error code components are collected in J + , and the degree of Ψ(x) derived from the syndrome is just equal to ε. The second is associated with the requirement in which the error quantity can be obtained according to the computation even though |S 0 |≦ε is not satisfied. This condition is added, though, to exclude failed corrections.
The method of solution searching comprises substituting Λ(x)=Ψ(x) and V(x)=1 to find a solution that satisfies the equation from the elements in Zp, and applying an inverse transformation to obtain a true error E from the obtained root and multiplicity.
Next, with respect to the syndrome converting method in accordance with the above principle, an effective condition on error searching is considered.
When a point in a true error code word actually indistinct is represented by E=(e 1 , e 2 , . . . , e p−1 ), in the syndrome converting method the process converts it to a point <m> E=(u(1) <m> e 1 , u(2) <m> e 2 , . . . , u(n) <m> e p−1 ) in a virtual error code word. Note that the component coordinates themselves are unchanged. In this case, the syndrome is represented as in Expression 18. In Expression 18, j i (i=1 to ξ) indicates the component coordinates of E different from zero where j 1 <j 2 < . . . <j ξ .








uS


〈
m
〉

+
0


=


u
⁢


∑

i
=
1

ξ

⁢



(

j
i

)


〈
m
〉


⁢

e

j
i





=
ɛ





[

Expression
⁢



⁢
18

]







If ξ≧2 and <m>≠<m′>, the conversions to the virtual errors are all independent. Because if there is an equal one, u(j) <m> =u′(j) <m′> is required to establish over ξ different j because j i is unchanged through the conversion. This means that Expression 19 shown below can establish over all j i and can establish only if ξ=1.













(

j
i

)


〈
m
〉


⁢

S


〈

m
′

〉

+
0



=

⁢




(

j
i

)


〈

m
′

〉


⁢

S


〈
m
〉

+
0



⇒








⁢



(

j
i

)


〈
m
〉


⁢


∑

i
=
1

ξ

⁢



(

j
i

)


〈

m
′

〉


⁢

e

j
i











=

⁢



(

j
i

)


〈
m
〉


⁢


∑

i
=
1

ξ

⁢



(

j
i

)


〈
m
〉


⁢

e

j
i












[

Expression
⁢



⁢
19

]







Thus, according to the syndrome converting method, scanning <m> can configure polynomials of virtual error points different at every different <m>. The case of ξ=1 corresponds to one in which only the conversion of the syndrome multiplied by u is required to ready for virtual errors.
In addition, when paying attention to one virtual error component, for example, u(j) <m> e j =(S <m>+0 ) −1 (j) <m> e j moves through all Zp components except zero under the following condition. In other words, when any one of <m> components fluctuates from 0 to p−2, then
{ ( j i ) 〈 m 〉 } - 1 ⁢ S 〈 m 〉 + 0 = ∑ k ≠ i ξ ⁢ { ( p - j i - 1 ) - 1 ⁢ ( p - j k - 1 ) } m 3 ⁢ { ( p - j i ) - 1 ⁢ ( p - j k ) } m 2 ⁢ { ( j i ) - 1 ⁢ ( j k ) } m 1 ⁢ e j k + e j i [ Expression ⁢ ⁢ 20 ]
it moves through Zp components 1 to p−1 except 0. Accordingly, the inverse element thereof (S <m>+0 ) −1 (j) <m> also takes all components except zero. In the end, as u(j) <m> e j takes all components except zero once at least, the sufficient condition is to scan any one of <m> components from 0 to p−2.

In the syndrome converting method, the process introduces syndromes, (p−1) diagonal matrixes, and uses 0-th to (p−2)-th powers of these individuals to cause a virtual error. Therefore, the following description is given to the error that can be covered by the conversion to such the virtual error, and to the condition on the syndrome converting method.
When a point in a true error code word is given by E=(e 1 , e 2 , . . . , e p−1 ), a point in a virtual error code word in accordance with the syndrome converting method is given <m> E={u(1) <m> e 1 , u(2) <m> e 2 , . . . , u(p−1) <m> e p−1 }.
There are ξ error component positions, which are represented by j i (i=1−ξ, j 1 <j 2 < . . . <j ξ ) and replaced as in Expression 21.
uS 〈 m 〉 + 0 = u ⁢ ∑ i = 1 ξ ⁢ ( j i ) 〈 m 〉 ⁢ e j i = ɛ , u ⁡ ( j i ) 〈 m 〉 ⁢ e j i = ɛ i [ Expression ⁢ ⁢ 21 ]
In Expression 21, ε i (i=1 to p−1) is considered a variable where the sum of ε i to ε p−1 is fixed to ε.

Therefore, the process computes the number in the case of ξ components that make the sum equal to ε.
As for (ξ−1) components, 1 to p−1 can be selected freely. The final ξ-th value can be selected for the sum of (ξ−1) such that the sum of ξ components is made congruent with ε. Accordingly, the number is equal to (p−1) ξ−1 in the case of selection of the variable.
This result, however, also contains the case where the final selection is required to take 0. Accordingly, this case is excluded. If the number is equal to n(ξ) when the sum is congruent with ε for ξ pieces of 1 to p−1, it is required to exclude the case where the sum reaches ε before the final selection. Therefore, n(ξ)=(p−1) ξ−1 −n(ξ−1) establishes, and thus n(ξ) can be obtained as in Expression 22.

ξ:even n (ξ)={( p− 1) ξ −1 }/p

ξ:odd n (ξ)={( p− 1) ξ +1 }/p

n (ξ)={( p− 1) ξ −(−1)}/ p [Expression 22]

When ε is divided into ξ pieces, there is one having components all present between 0 and 2/p, that is, components belong only in J + . If the number of conversions to different virtual errors is higher than the number in the case of n(ξ) pieces, it is possible to make J + virtual errors. In this case, if the resultant true error can satisfy the condition on error correction of the Lee metric code, it is possible to find solutions through the syndrome converting method without misses.

Subsequently, the flow finds the number of different virtual errors that can be caused from the true error through the syndrome converting method. In the case described above, the degree of the vector <m> is equal to 3. Therefore, <m>=<m 1 , m 2 , m 3 > establishes, and in order to allow the divided components of ε to move all from 1 to p−1, the components are independently scanned from 0 to p−2. In the case of the current specific example, the number of conversions in the case of <m>≠<m′> is equal to (p−1) 3 .
In comparison with the number n(ξ) when the sum of ξ free variables ε i reaches ε,

n (ξ)={( p− 1) ξ −(−1) ξ }/p ≦( p− 1) 3 [Expression 23]

is the scan condition without misses. Thus, ξ=4 can satisfy this condition, and the method using 3 diagonal matrixes is possible to execute searching up to ξ=4 without misses.

When j moves from 1 to p−1, an additional m-th power of the matrix that includes a diagonal matrix, that is, a function that moves through all Zp components 1 to p−1 except zero allows the number of conversions to increase at every (p−1)-fold similar to the above.
When ζ matrixes are aligned, the number of conversions reaches (p−1) ζ , which makes the condition without misses always be ξ=ζ+1.
In addition to the above used j, p−j, p−j −1 , examples of these functions include a in Zp but a≠1, 2, and a j , p−a 3 of which a is the number other than a power of a certain number so that a sufficient number of conversions can be made. Therefore, an appropriate selection of a to make a diagonal matrix can extend the degree of <m> so that ξ can be set always larger by 1 than this degree. Therefore, even if the syndrome converting method is used over all the cases, where the correctable condition on the Lee metric code is satisfied, instead of using the Euclidean iterative method, it is possible to execute error searching without misses.
The number in the case of the conversion grows (p−1)-fold when ξ increases by 1, however, and accordingly the number of searches increases exponentially. Therefore, depending on the case, the use of the conventional Euclidean iterative method shortens the processing time than the syndrome converting method as can be considered. In this case, it is required to execute an optimal selection in accordance with the applied memory system. In particular, in the case of ε=1, 2 and so forth, the use of the syndrome converting method is more advantageous.
<Data Interface in p-adic NAND Flash Memory>
On the basis of the above, the following description is given to a specific example of the NAND flash memory that uses the syndrome converting method for error correction. Hereinafter, this NAND flash memory is referred to as the “p-adic NAND flash memory”. In addition, if no special notice is given, a “memory system” refers to the p-adic NAND flash memory.
First, a comparison/consideration is performed to determine what kind of p-adic cell should be selected.
FIG. 1 is a table showing relations among the data storage efficiencies and so forth at every number of levels of p-adic cells in a memory system according to a first embodiment. The first column in the table shows evaluated items. The evaluated items are as follows.
L: The number of threshold level divisions of the p-adic cell.
p: A prime to be used.
h: A minimum number of bits required for binary representation of Zp.
ε: An overall quantity of Lee metrics of error-correctable errors.
M: A value determined by M=h(p−ε−3), which is the number of bits, that is, the quantity of binary data in a “Binary World” subject to batch processing by ECC.
The “Binary World” refers to an environment outside the memory system according to the present embodiment, for example, an IT instrument that handles data in binary.
δ: The number of digits of M as a 2 h -adic number (δ=M/h).
M/(p−1): An index indicative of the number of binary bits that one p-adic cell can store.
Binary M bits are treated as a code word having (p−1) code components, which are stored in (p−1) p-adic cells.
p−1: The number of p-adic cells required for storing a code word of the Lee metric code.
log 2 L: The number of bits that can be stored in a p-adic cell when the p-adic cell is made as a binary storing multi-level cell.
ε/(p−1): A proportion of the maximum number of correctable cells when c is used. Or a proportion of the maximum error level length correctable in one p-adic cell.
log 2 L/{M/(p−1)}: A redundancy when a memory cell is used as a p-adic cell for storing ECC with the Lee metric code, and the memory cell is regarded as a binary multi-bit cell.
In the table dotted parts are ranges that can be considered practical from the viewpoint of the level of the p-adic cell and the redundancy to binary.
The following description is given to an example of the practical memory system in the case of L=17 and ε=4 shown in FIG. 1 with the star mark where 4 cells among 16 cells can be corrected.
This considers that the number of levels per cell in the practically used NAND flash memory is equal to 16 levels. When E increases by 1, the scale of processing through the syndrome converting method increases almost p-fold. Accordingly, if p=17 is used, the case of ε=2 shown in FIG. 1 with a double circle where 2 cells among 16 cells are correctable is considered practical for the present, though the case of ε=4 is picked up for convenience in understanding of the embodiment.
Subsequently, a NAND flash memory system is configured for the specific example in the case of L=17 and ε=4. Initially, the specification for the NAND flash memory system is shown. The specification herein shown provides a skeleton of the specification for the use of other p and ε. In this case, the values of the skeleton can be changed to the corresponding values in accordance with the values of p and ε.
The following is the specification for the p-adic NAND flash memory system.
(1) The configuration of the data interface is a ×8 1-byte configuration.
(2) It operates in sync with clocks.
(3) A sector contains 512 bytes as a data transfer unit.
(4) The unit of conversion processing from a binary to a p-adic number includes 50 bits. Hereinafter, the conversion processing from the 50-bit binary to the p-adic number is referred to as a “process”. For the purpose of distinguishing it from other general terms, “process”, it is expressed by “PROCESS”. Therefore, a binary corresponding to 1 sector is converted to a p-adic number through 82 PROCESS.
(5) A page size is determined by 4 sectors (2048 bytes). A block size is not determined particularly though it has a size of 64 pages, for example, which depends on the configuration of the cell array.
(6) Each sector contained in a page can be accessed at random.
(7) A variety of modes are prepared as access methods in a sector. The access modes are roughly divided into two: a “fast mode” and a “random mode”.
The fast mode: A mode in which accesses are made in order of addresses fixed in a sector. In writing, after a lapse of 10 cycles since the beginning of the sector access, a PROCESS starts for processing data in turn. In reading, after completion of 1 PROCESS, a sector access is allowed. In both writing and reading, a PROCESS to a sector and an access to the sector proceed at the same time.
The random mode: An access mode in which a burst length of access to a sector, the burst mode, and the top address of burst can be set.
For example, the burst length may include 4/8/16/32/256 bits and so forth, and the burst mode can be set in an interleave mode/wrap-around mode and so forth.
After completion of PROCESS to the data to be stored in a sector, an access to the sector is allowed.
At the time of writing, PROCESS starts after completion of data storage in the sector access.
In the random mode, an access and a process start after pieces of data to the sector are grouped. Therefore, the access and the PROCESS to the same sector cannot proceed at the same time.
The following description is given to an overview of the memory system capable of realizing the above specification skeleton. This system is a system that directly treats the numerals in Zp as data.
As describe above, the environment outside the memory system, for example, the IT instrument that handles data in binary is referred to as the “binary world”. In contrast, containing a part that handles data in binary such as operational processing, an environment inside the p-adic NAND flash memory system that handles data in Zp is referred to as a “p-adic Zp world”. In this case, the “binary world” can also be referred to as a “p-adic Z 2 world”.
FIG. 2 is a conceptual view of the memory system. This memory system mainly comprises a “p-adic NAND cell” part operative to store data (codes), and a “Lee metric code & ECC” part operative to execute error processing at the time of executing write/read to the “p-adic NAND cell” part. These “p-adic NAND cell” part and “Lee metric code & ECC” part are parts that belong to the “p-adic Zp world”.
The memory system further comprises, as interfaces between the “binary world” and the “p-adic Zp world”, a “binary to p-adic” converter unit operative to convert binary data to Zp data, and a “p-adic to binary” converter unit operative to convert Zp data to binary data.
As the outside of the memory system is the “binary world”, the “binary to p-adic” converter unit receives binary data from the “binary world” and processes it at every 50 bits. Thereafter, the data is stored in p-adic cells, and further provided to external at every 50 bits by the “p-adic to binary” converter unit.
ECC to the data stored in the “p-adic NAND cell” part can be executed easily by applying a Lee metric code to Zp. The present memory system is also possible to execute ECC processing because it comprises the “Lee metric code & ECC” part.
As the memory system comprises the “binary to p-adic” part and the “p-adic to binary” converter unit, users can handle the memory system just as the “binary world” without having consciousness about the “p-adic Zp world” inside the memory system.
Data write and read to the “p-adic NAND cell” part is handled directly with relating the threshold levels to the elements in Zp. There are two such relating methods.
The first is a method in which interfaces are used to deal data write and read to conventionally NAND-connected multi-level cells (hereinafter referred to as “NAND MLC”). It is required to once convert the Zp level (1 to p−1) stored in MLC to page information and so forth of NAND MLC. Therefore, a part, which mediates between the NAND MLC and a peripheral circuit “p-adic Zp world”, is required to have a logic part. In the case of this method, information on Zp stored in MLC spans over page information of plural NAND MLCs and accordingly data transfer needs a longer time.
The second is a method in which a Zp level is directly written as a physical level in a p-adic cell. This method can make data write/read processing faster than the first method.
The present embodiment applies the second method.
The following description is given to data transfer suitable for the above-described memory system specification, and to an interface circuit for making the match with internal p-adic cells.
In the case of the memory system according to the present embodiment, all the results on data processing show up on page registers contained in pages. The p-adic cells communicate data with the page registers. Therefore, how to configure the page registers is the key to the data transfer specification.
At the start, the data interface specification is confirmed once again.
(1) The I/O transfer rate of the memory system is 1 byte/cycle. In a word, the transfer unit is 1 byte.
(2) 50 bits of binary data are converted as a processing unit to a Lee metric code.
(3) 1 sector includes 512 bytes. Therefore, 512 cycles are required to transfer 1 sector of binary data.
(4) 82 PROCESS are required to convert 1 sector of binary data to a Lee metric code. Binary data that can be processed by 82 PROCESS includes 82×50=4100 bits. Therefore, it is required to process 1 sector plus 4 bits.
(5) When binary data is converted to p-adic data, there is an increase to 55 bits per 50 bits. Therefore, 1 sector requires registers corresponding to 82×55=4510 bits.
(6) If binary data is converted to a Lee metric code through the conversion to p-adic data, there is an increase to 80 bits per 50 bits. Therefore, 1 sector requires registers corresponding to 82×80=6560 bits (820 bytes).
In consideration of the above (2), the subsequent description is given to a register configuration that allows data processing at every 50 bits to be executed efficiently.
Data is transferred at a rate of 1 byte/cycle in accordance with the above (1). Therefore, transfer of 50-bit binary data requires 7 cycles at the minimum. When 50-bit binary data is converted to a Lee metric code, there is an increase in size to 80 bits in accordance with the above (6).
Here, 50 bits can be represented by 5×10 bits, and 80 bits by 8×10 bits. Therefore, the memory system according to the present embodiment configures (10×8) register blocks with plural byte-unit registers to execute data processing using the registers thus configured. Thus, it is possible to realize an optimal register configuration and data processing in the memory system. The (10×8) register blocks are described later.
Subsequently, a flow of data processing is described with reference to FIG. 3 .
The transfer of 50-bit binary data to 1 register block is executed in 10 cycles.
Therefore, if the address order of data transfer has been determined, processing of 1 PROCESS is made enable at every 10 cycles. In PROCESS, however, pieces of data are merged at every I/O and processed. Accordingly, if an I/O is masked and invalidated, the I/O is processed as it holds fixed data.
On the other hand, if the address order of data transfer is at random, it is not possible to determine which part of the registers contained in a sector the data is transferred. Accordingly, on receipt of a command indicative of completion of 1-sector data transfer, the flow decides that preparation of processing-target data is completed, and starts PROCESS.
The PROCESS is treated by regarding (10×8) register blocks as the later-described “D-r” register and utilizing overwrite to the “D-r” register.
At the start, processing-target data stored in the “D-r” register is regarded as h=5, δ=10 binary data (first data) and converted to a p-adic number (second data) (S 1 in FIG. 3 ). Subsequently, the data converted to the p-adic number is overwritten in the “D-r” register (S 2 in FIG. 3 ). Subsequently, the p-adic data stored in the “D-r” register is multiplied by a generator matrix G to convert it to a Lee metric code (third data) (S 3 in FIG. 3 ). Finally, the Lee metric code is overwritten in the “D-r” register (S 4 in FIG. 3 ).
Thus, binary data corresponding to 1 PROCESS stored in the registers in a (10×8) or 80-bit register block serving as the “D-r” register is converted to the Lee metric code, then overwritten in the same register block and stored therein.
The repetition of the above PROCESS sequence can treat 512 bytes of sector data in 82 PROCESS. The quantity of data that can be treated in 82 PROCESS is equal to 512 bytes plus 4 bits. Accordingly, 4 fixed dummy bits are added for processing.
The following description is given to the relation between the configuration of register blocks and the burst data transfer.
FIG. 4 is a diagram showing a first register block contained in a sector register.
One register block includes 80 bit registers, in which a (8×5) register group shown with a in FIG. 4 holds pieces of data transferred in No. 1-5 cycles.
Pieces of data transferred in No. 6-10 cycles are held in another register group shown with b in FIG. 4 , which is located beneath and in parallel with the (8×5) register group. A part of the data transferred in No. 6-10 cycles is contained in part of data corresponding to 1 PROCESS held in the first register block shown in FIG. 4 and the other is contained in part of data corresponding to 1 PROCESS held in the next register block.
Transfer scanning of input byte data advances wave-like as shown with the dashed line in FIG. 4 . In a word, the data transferred in first 10 cycles decides data in the first register block. Thereafter, data processing is allowed.
Pieces of byte data transferred over cycles are merged on processing. Accordingly, the number of cycles used at every bit of byte data differs from one another as can be found. In the case of FIG. 4 , the first 2 bits of byte data form 10-cycle data and the remaining 6 bits form 5-cycle data.
Next, the process of data processing in the sector register at the time of data write is described with reference to FIG. 5 .
FIG. 5 shows, sequentially from the left, the state of a sector register on burst transfer of binary data (S 1 in FIG. 5 ), the state of a sector register after the p-adic conversion (S 2 in FIG. 5 ), and the state of a sector register after the Lee metric code conversion (S 3 in FIG. 5 ). The dashed line in FIG. 5 indicates the boundary of a byte register at every 8 bits.
The sector register is configured to include 820 registers aligned in 8 columns and has a receiving portion of 820 rows for 102.5-byte data transfer. Of 8 columns, No. 1-5 columns are used in data transfer and the remaining No. 6-8 columns are used in holding the target data after data transfer.
At S 1 in FIG. 5 , binary data corresponding to 1 PROCESS is transferred to the register block in 512 cycles. At the start, of the binary data transferred in 512 cycles, pieces of binary data transferred in the first No. 1-510 cycles are stored in the byte registers on No. 1-5 columns in order at every 5 cycles. At the time of completion of storing binary data transferred in No. 510 cycle, registers on No. 1-816 rows of 820 rows are filled with data.
Pieces of data transferred in subsequent No. 511, 512 cycles are divided into 4 bits each and held in registers on No. 817-820 rows, No. 1-4 columns as shown in the S 1 lower figure of FIG. 5 . The registers on No. 817-820 rows, No. 5 column are used to store 4 bits of fixed dummy data.
Thus, the sector register can store 50-bit binary data corresponding to h=5, δ=10 of a 10-digit, 2 5 -adic number, by 82 PROCESS.
At S 2 in FIG. 5 , 50-bit binary data is converted to an 11-digit, p-adic number (p=17), that is, 55-bit data and overwritten in the sector register. This PROCESS is executed at every 10 register rows. The converted p-adic data is stored over 55 bits of each 10-row, 8-column register block. The sector register includes 820-row, 8-column registers such that data is overwritten at every 10 rows by 1 PROCESS. Therefore, all sector registers are filled with p-adic data in 82 PROCESS.
Thus, S 1 and S 2 in FIG. 5 complete the conversion of binary data to p-adic data in 1 sector.
At S 3 in FIG. 5 , p-adic data is converted to a Lee metric code.
The Lee metric code is data having components that are equal to (p−1) (=16) elements in Zp. A Lee metric code by 1 PROCESS is 80-bit data resulted from 5-bit, p-adic data multiplied by a G matrix. The Lee metric code by 1 PROCESS is overwritten and stored in one 10-row, 8-column register block. In this case, 1 sector register is entirely filled with the Lee metric code in 82 PROCESS. Thus, the sector register can hold pieces of data to be written in 164-byte pieces of p-adic cells.
Thus, processing in 3 stages shown at S 1 -S 3 in FIG. 5 sequentially advances at every 10-row, 8-column register block.
The data transfer to the sector register is executed in the fast mode and in the random mode as described earlier. In the case of the fast mode, pieces of transferred binary data are filled in the sector register in turn from the top. Therefore, in the fast mode, when pieces of binary data by 1 PROCESS are stored in the 10-row, 8-column register block, PROCESS can be executed sequentially in serial.
On the other hand, in the random mode, it is possible to designate the top address at every burst length to set a data storage location and also possible to select 2 addressing modes: interleave, and wrap-around. In this case, no-data stored areas exist at intervals in the register block. Therefore, in the random mode, it is required to wait a command indicative of completion of binary data storage to the sector register to exert control over starting PROCESS and so forth.
Thus, in the memory system according to the present embodiment, data is overwritten in the sector register twice at the time of conversion of binary data (first data) to p-adic data (second data) and at the time of conversion of the p-adic data (second data) to a Lee metric code (third data).
By the way, in the case of the conventional memory system, there is no processing corresponding to the conversion of binary data to p-adic data, and binary data is directly converted to a code using Reed-Solomon and so forth. Accordingly, overwrite to a register is executed once at the most.
Next, the process of data processing in the sector register at the time of data read is described with reference to FIG. 6 .
At S 1 in FIG. 6 , pieces of data stored in 164-byte pieces of p-adic cells in the p-adic cell array are read out to 820-byte pieces of sector registers corresponding to 82 PROCESS.
The pieces of data stored in the sector registers are subject to computation processing by ECC, at every data corresponding to 1 PROCESS stored in a 10-row, 8-column register block, beginning from the sector register end, then error-corrected if enable, and left as it is if unable. Then, 82 PROCESS can be applied to complete ECC processing over all data in 1 sector to restore the Lee metric code.
At S 2 in FIG. 6 , the Lee metric code restored at S 1 in FIG. 6 is converted to p-adic data sequentially. Here, the Lee metric code corresponding to 1 sector is subject to inverse transformation with a generator matrix G at every 80 bits corresponding to 1 PROCESS such that it is converted to a 5-bit, 11-digit, p-adic number and then overwritten in each register block.
At S 3 in FIG. 6 , the p-adic number generated at S 2 in FIG. 6 is converted to a 2 5 -adic number, that is, binary data. The “p-adic to binary” part converts p-adic data corresponding to 1 PROCESS to 5-bit, 10-digit, 50-bit binary data and then overwrite the binary data at every 10-row, 8-column register block.
Thereafter, the binary data is read out at every 8-row, 5-column register group in column order at a rate of 1 byte/cycle and provided as data corresponding to 1 sector. With respect to data read from the sector register at the last 2 cycles, 4-bit, 2-column binary data is read out as byte data in 1 cycle, similar to data write, as shown in the lower figure at S 3 in FIG. 6 .
In the fast access mode, data is read out from the top of the sector register. Accordingly, data in the sector register can be read out sequentially with the latency of 1-PROCESS processing. On the other hand, in the random mode, the top of burst in the sector has not been known previously. Accordingly, after completion of 82 PROCESS when binary data corresponding to 1 sector is reproduced in the sector register, a first access is allowed.
Thus, in the memory system according to the present embodiment, data is overwritten in the sector register twice at the time of conversion of a Lee metric code (third data) to p-adic data (second data) executed after ECC processing and at the time of conversion of the p-adic data (second data) to binary data (first data).
By the way, in the case of the conventional memory system, there is no processing corresponding to the conversion of the Lee metric code to p-adic data. Accordingly, overwrite to a register is executed once at the most.
<Assignment of Elements in Zp to p-adic Cell>
The following description is given to an assignment of elements in Zp to p-adic cell levels, which is optimal for storing each code c j of a Lee metric code C=(c 1 , c 2 , . . . , c 16 ) in a p-adic cell.
In the present embodiment, as shown in FIG. 7 , elements in Zp are assigned continuously, beginning from the lowermost level of the p-adic cell, as 0, 1, . . . , 16. In this case, the error quantity is proportional to the quantity of level variation.
In the case of p=17, the number of levels required for a p-adic cell is equal to 17, and the number of boundaries (thresholds) between these 17-stage levels is equal to 16.
In the case of c=4, if an error arises only in 1 cell, error correction is possible on failed identification of a level within a range shown with a bold arrow in FIG. 7 . The error, however, arises mainly due to failed identification within a range of adjacent levels.
In a word, the memory system according to the present embodiment is possible to have a strong error correcting ability to realize error correction of 4 cells among 16 cells substantially in accordance with the assignment way shown in FIG. 7 .
<Data Read/Write>
An example of a method of data write/read to the p-adic cell array is described next with reference to FIG. 8 . The herein-called “p-adic cell array” means a cell array including plural p-adic cells NAND-connected, using a floating gate transistor as each p-adic cell.
Previously, the meanings of symbols shown in FIG. 8 are described.
In the case of p=17, the Lee metric code has 16 code components. These codes are denoted with c 1 -c 16 . Each code c can be represented by a 5-bit binary h. The bits from the least significant bit through the most significant bit of the binary h are denoted with C j 0 -C j 4 .
At the time of data write/read, a write voltage/read voltage supplied from a row decoder/word-line driver (Row Dec/WLDriver) serving as part of a data write unit or a data read unit changes the level on a word line WL in 17 stages. At this time, the signals indicative of the levels on the word line WL are denoted with Δ 1 -Δ 17 . In addition, the inversion of a bit X is represented by ‘/X’ with additional ‘/’.
At the start, data write to the p-adic cell is described.
The threshold of a NAND cell serving as the p-adic cell is set in accordance with the quantity of electrons injected into the floating gate while a certain voltage is applied between the word line WL and the bit line BL.
At the time of data write, the potential on the word line WL elevates in 16 stages. On the other hand, the bit line BL is connected to a certain power supply Vss. When the p-adic cell changes to have a desired threshold, it shifts to the floating state isolated from the certain voltage Vss. Thus, no voltage is applied to the floating gate such that injection of extra electrons into the floating gate can be prevented.
The present embodiment uses this method to set thresholds in batch over p-adic cells corresponding to the components contained in the code. The code components c 1 -c 16 correspond to elements in Zp and accordingly they are expressed in binary. As for the thresholds serving as levels of the p-adic cell, the lowermost threshold is assigned with the element 0 in Zp, and then the elements in Zp are assigned in ascending order from lowest. The upper limit of a threshold division corresponding to each level L of Zp is denoted with L, the level on the word line WL for injecting electrons by the quantity corresponding to the threshold is denoted with WV L , and the signal for generating the word line level WV L is denoted with Δ L .
If the erased state of the p-adic cell is assumed to have a threshold in the lowermost state, it is not required to change the threshold of the p-adic cell targeted to write the component 0 in Zp therein though it is required to change the threshold of the p-adic cell targeted to write another component in Zp therein.
Therefore, in order to change the threshold of the p-adic cell, the present embodiment elevates the voltage on the word line WL sequentially from lowest to inject electrons into the floating gate. At that time, if the voltage on the word line WL exceeds the voltage corresponding to the threshold to be set in the p-adic cell, the bit line BL connected to that p-adic cell is brought into the floating state, as described above, to prevent extra electron injections. This control is executed in a program setting circuit shown with a in FIG. 8 .
The program setting circuit includes an NMOS transistor QN 1 for connecting the bit line BL to the voltage Vss. The gate of the transistor QN 1 is connected to a constant voltage Vcc via a PMOS transistor QP 1 controlled by the later-described control signal /p. The gate of the transistor QN 1 is also connected to the voltage Vss via 16 paths, aligned in parallel, corresponding to the elements in Zp. These 16 paths each include a circuit of 5 serially connected NMOS transistors. Each path can conduct if /C j 0 □/C j 1 □/C j 2 □/C j 3 □Δ 1 , /C j 0 □/C j 1 □/C j 2 □/C j 3 □Δ 2 , . . . , /C j 0 □/C j 1 □/C j 2 □/C j 3 □Δ 16 .
On data write, the word line level varies from WV 0 to WV 16 . At that time, the program setting circuit exerts control, in accordance with the word line level, so that the bit line BL can be connected to the voltage Vss or isolated from the voltage Vss and brought into the floating state.
Namely, when the word line level is at WV L , that is, when the signal Δ L is made activate, the circuit isolates the bit line BL connected to the p-adic cell to be set at L−1 from the voltage Vss. Thus, the threshold of that p-adic cell is set in the division of L−1. Isolation of the bit line BL from the voltage Vss is controlled by the transistor QN 1 . The node n 1 on the gate of the transistor QN 1 is initially precharged via the transistor QP 1 that is controlled by the signal /p. The result from decoding with bits of information C j 0 -C j 3 representative of the code components and the signals Δ 1 -Δ 16 indicative of the word line levels are used to discharge the node n 1 , thereby turning off the transistor QN 1 to bring the bit line BL in the floating state. As for the p-adic cell targeted to write the element 16 in Zp therein, it is not required to discharge the node n 1 but just required to decode the elements 0 - 15 in Zp using 4 bits of information C j 0 -C j 3 .
The program setting circuit may be provided at every bit line BL connected to p-adic cells belonging to the same word line WL and corresponding to components of different codes. In this case, the p-adic cell can be set at the threshold level corresponding to Zp of the code component by sequentially elevating the voltage on the word line WL.
For the purpose of setting an accurate threshold level to the p-adic cell, an operation of verify read may be introduced to verify the state of the threshold of the p-adic cell when the word line level varies.
Subsequently, data read from the p-adic cell is described.
At the time of data read, the level of a p-adic cell is sensed from the current Icell flowing in the p-adic cell. This operation is executed at a sense amp unit t-SA provided on the end of the bit line BL.
The sense amp unit t-SA includes a sense amp sa operative to compare the reference current Iref with the cell current Icell; a latch L 1 operative to hold the latest comparison result from the sense amp sa; a latch L 2 operative to hold the previous comparison result from the sense amp sa; an XOR gate G 1 operative to detect a variation in comparison result from the results held in the latches L 1 and L 2 ; and an XOR gate G 2 operative to detect if the p-adic cell changes to the threshold corresponding to 16 in Zp. The output from the XOR gate G 2 provides the output from the sense amp sa.
The reference current Iref is set to a current slightly larger than the cell current when the upper limit of the division of the threshold level and the voltage on the word line WL corresponding to the threshold level are applied to the p-adic cell.
In the sense amp unit t-SA the sense amp sa compares the reference current Iref with the cell current Icell and outputs ‘1’ to the latch L 1 if the cell current Icell is larger. The voltage on the word line WL is sequentially varied within a range of WV 1 -WV 16 and, only if the word line level is at ‘0’ on WV L and at ‘1’ on WV L+1 , the threshold level of the p-adic cell belongs to the division L. In this case, the p-adic cell holds the element L in Zp.
The comparison result from the sense amp sa is transferred to 2 latches L 1 and L 2 in turn. If the contents of these latches L 1 and L 2 are different from each other, the output from the sense amp unit t-SA provides Z=‘1’. This makes it possible to determine the state of the threshold written in the p-adic cell from the word line level WV L .
If Z=‘1’ has been established already when the word line level is at WV 1 , it is required to determine if the threshold of the p-adic cell belongs to the division 0 or lower. If Z=‘0’ when the word line level is at WV 16 , it is required to determine if the threshold of the p-adic cell belongs to the division 16 or higher. Therefore, for the purpose of enabling these decisions, the initial states of the latches L 1 , L 2 are set at ‘0”, and a signal Δ 17 is generated after the signal Δ 16 . Thus, it is possible to decide that the threshold level of the p-adic cell is at L−1 from the signal Δ L when the output from the sense amp unit t-SA provides Z=‘1’.
The following description is given to the 5-bit register hanging from each bit line BL and operative to hold C j 0 -C j 4 .
The register has a circuit as b in FIG. 8 at every bit. In a word, the register includes, at every bit, a flip-flop FF composed of 2 inverters; an inverter IV 1 having an input connected to a node n 2 on one end of the flip-flop FF; 2 serially connected NMOS transistors QN 2 , QN 3 for discharging the voltage on the node n 2 ; and a transistor QN 4 for discharging a node n 3 on the other end of the flip-flop FF. This configuration provides the node n 2 with /r j , and the output from the inverter IV 1 with r j . The node n 2 is connected to the voltage Vss if j□Z=‘1’, and the node n 3 is connected to the voltage Vss if RS=‘1’.
A “Zp→h dec” circuit block shown in FIG. 8 is a decoder operative to convert the signals Δ 1 -Δ 17 to 5-bit representations of 0-16.
The register shown with b in FIG. 8 is arranged on each point of intersection of lines of the binary signals C j 0 -C j 4 output from the “Zp→h dec” circuit block and lines of the outputs Z from the sense amp unit t-SA. Thus, the outputs Z from the sense amp unit t-SA can be held in 5 registers. In this case, the data held in these 5 registers can be utilized as binary representations of code components c.
These registers may also be utilized to exert control on data write/read. For example, if these registers are used, at the time of data write, to store binary representations of components of the code to be set, they can be utilized for control such that the program setting circuit executes verify and brings the bit line BL in the floating state.
The subsequent description is given to setting of the write voltage/read voltage supplied from the row decoder/word-line driver to the word line WL.
With respect to all p-adic cells to be accessed at the same time, the levels of the p-adic cells are assigned with the values of codes at the same time. Accordingly, it is required to scan all the voltages WV 0 -WV 16 over the word line WL.
FIG. 9 shows an example of sequential upward and downward scan of the voltage on the word line WL.
In data write (Write), there is no changing method other than one in which the flow elevates the threshold of the p-adic cell in order. Accordingly, the word line voltage is changed from the lower voltage side to the higher voltage side. On the other side, in data read (Read), it is sufficient to shift all levels within the scan as described above.
In the case of FIG. 9 , the word line level rises from WV 0 to WV 16 in scan 1 . Accordingly, the code data C is set in the register prior to the rise such that data write can be executed. In the case of data read, data read can be executed at the time of completion of scan 1 because the code data is decided.
If data write is executed after completion of scan 1 , it is required to return the word line voltage to WV 0 again and elevate it to WV 16 sequentially as shown with the dotted line in scan 2 . On the other hand, in the case of data read, the word line voltage may be elevated sequentially as shown with the dotted line in scan 2 or dropped sequentially subsequent to scan 1 as shown with the solid line. As the code data is decided at the time of completion of scan 2 , data read can be executed similarly to the time of completion of scan 1 .
If scan 1 and scan 2 are applied to access all p-adic cells belonging to the word lines WL, it is required to select different word lines WL in these scan 1 and scan 2 . If p-adic cells belonging to the same word line WL are subject to serial read, for example, if the sense amp unit t-SA is shared among plural bit lines BL, it is also possible to select the same word line WL in scan 1 and scan 2 .
<Conversion from Binary Data to 17-Adic Number>
The following description is given to a binary/p-adic number (17-adic number) converter circuit required at the entrance and the exit of the memory system according to the present embodiment.
FIG. 10 is a diagram schematically showing the configuration of the process of conversion computation from a δ-digit, 2 h -adic number D (d 0 , d 1 , . . . , d δ−1 ) in the “binary world” to a (δ+1)-digit, p-adic number D (a 0 , a 1 , . . . , a δ−1 , a δ ) in the “p-adic Zp mod p world” in the case of p=17.
A square shown with “5 res” in FIG. 10 indicates an operating circuit operative to derive a quotient and the residue from the input binary data divided by 17. The input to the operating circuit is 6-bit binary data and the output therefrom is the residue obtained by dividing the binary data by 17. If the input binary data is equal to or larger than 17, then the quotient is output as a carry C. Hereinafter, the operating circuit element is referred to as the “5 res” circuit block.
At the start, at the 0-th step (S 0 in FIG. 10 ), 10-digit, 2 5 -adic data D (d 0 , d 1 , . . . , d 9 ) is subject to numeration from d 9 on the rightmost side. Here, the flow directly generates the residue and a quotient or carry C 1 45 by substituting 0 for the most significant bit of 6-bit binary data input to the “5 res” circuit block and dividing d 9 by 17.
Subsequently, 6-bit binary data, of which No. 5-1 bits are the outputs from the previous “5 res” circuit block (the residue represented by 5 bits) and No. 0 bit (the least significant bit) is the most significant bit D 8 4 (=D 39 ) of d 8 , is input to the next “5 res” circuit block, which generates the residue and a quotient or carry C 1 44 derived from the input binary data divided by 17.
Thereafter, until No. 0 bit of 6-bit binary data input to the “5 res” circuit block reaches the least significant bit D 0 0 (=D 0 ) of d 0 , 46 “5 res” circuit blocks are used to generate carries C 1 0 -C 1 45 . Binary data expressed by these generated carries C 1 0 -C 1 45 indicates the number of 17s contained in the data D.
The output from the “5 res” circuit block having the input of d 0 has a binary representation a 0 of a 11-digit, 17-adic number D (a 0 , a 1 , . . . , a 10 ).
Subsequently, at the 1st step (S 1 in FIG. 10 ), over the number of 17s contained in the data D obtained at the 0-th step, a further computation is executed to determine how many 17s are contained to seek the number of 17 2 s, thereby obtaining a binary having a coefficient a 1 on a digit of a weight of 17 1 in the 17-adic number D.
At the 1st step, numeration of 17 is executed to the carries C 1 0 -C 1 45 from C 1 45 on the rightmost side. At the time of the numeration of 17 executed to the carries C 1 41 -C 1 45 , the flow directly generates the residue and a carry C 2 41 by substituting 0 for the most significant bit of 6-bit input binary data and dividing the input binary data by 17.
Subsequently, 6-bit binary data, of which No. 5-1 bits are the outputs from the previous “5 res” circuit block (the residue represented by 5 bits) and No. 0 bit (the least significant bit) is C 1 40 , is input to the next “5 res” circuit block, which generates the residue and a quotient or carry C 2 40 derived from the input binary data divided by 17.
Thereafter, until No. 0 bit of 6-bit binary data input to the “5 res” circuit block reaches the least significant bit C 1 0 of C 1 x , 41 “5 res” circuit blocks are used to generate carries C 2 0 -C 2 41 . Binary data expressed by these generated carries C 2 0 -C 2 41 indicates the number of primes 17 2 s contained in the data D.
The output from the “5 res” circuit block having the input of C 1 0 has a binary a 1 of a 11-digit, 17-adic number D (a 0 , a 1 , . . . , a 10 ).
At the subsequent 2nd step (S 2 in FIG. 10 ), over the number of 17 2 s contained in the data D obtained at the 1st step, a further computation is executed to determine how many primes p are contained to seek the number of 17 3 s, thereby obtaining a binary having a coefficient a 2 on a digit of a weight of 17 2 in the 17-adic number D.
Thereafter, the flow advances up to the 10th step (S 10 in FIG. 10 ) similarly to obtain a binary representation of a coefficient a 10 on a digit of a weight of 17 10 of the p-adic number.
The carries C 11 0 -C 11 5 at the 10th step are not used in computation.
A consideration is given next to the configuration of the “binary to p-adic” converter unit using a “6 bit mod p” circuit block. The “6 bit mod p” circuit block is a circuit that compares an input A or 6-bit binary data with a prime 17, then provides PF 0 =‘1’ if A is equal to or higher than 17 and provides the residue Q modulo the prime 17 of A. The details are described later.
FIG. 11 (A) shows a circuit at the k-th step in the “binary to p-adic” converter unit, which is configured with “6 bit mod 17” circuit blocks.
Here, the j-th digit is denoted with d j when data is subject to a 10-digit, 2 5 -adic expression. In this case, d j can be indicated in 5-bit binary though the coefficient D of the indication is expressed in common with the coefficient D of other d. For that purpose, sub-indexes are used as shown in Expression 24.

d j =D j 0 +D j 1 2 +D j 2 2 2 +D j 3 2 3 +D j 4 2 4

d j (2 5 ) j =D 5j 2 5j +D 5j+1 2 5j+1 +D 5j+2 2 5j+2 +D 5(j+1)−2 2 5(j+1)−2 +D 5(j+1)−1 2 5(j+1)−1 [Expression 24]

The input to the operation at the k-th step, that is, the carry at the previous step (the (k−1)-th step) is C k 0 -C k 5(10−k)+k−1 , which is the coefficient of a binary expression that has the sub-index as an exponential of 2, and the numeral expressed by this binary indicates the number of 17 k s contained in the data.
At the k-th step, the input includes 5 (10−k)+k pieces of binaries (carries C k 0 -C k 5(10−k)+k−1 ) as shown in FIG. 11(A) , which are received at 5(10−(k+1))+k+1 pieces of “6 bit mod 17” circuit blocks.
The 1st “6 bit mod 17” circuit block < 1 > receives C k 5(10−k)+k−5 to C k 5(10−k)+k−1 and 0 on the input binary A 0 -A 4 , A 5 , and provides R 5(10−(k+1))+k to R 5(10−(k+1))+k 4 and C k+1 5(10−(k+1))+k from the outputs Q 0 -Q 4 and the carry PF 0 , respectively.
The 2nd “6 bit mod 17” circuit block < 2 >, not shown, receives a carry C k 5(10−(k+1))+k−1 and the outputs R 5(10−(k+1))+k 0 to R 5(10−(k+1))+k 4 from the 1st “6 bit mod 17” circuit block < 1 > on the input binary A 0 , A 1 -A 5 , and provides R 5(10−(k+1))+k−1 0 to R 5(10−(k+1))+k−1 4 and C k+1 5(10−(k+1))+k−1 from the outputs Q 0 -Q 4 and the carry PF 0 , respectively.
Thereafter, as shown in FIG. 11(A) , “6 bit mod 17” circuit blocks having the same input/output are aligned 5(10−(k+1))+k+1 pieces in total, and the carries C k+1 0 to C k+1 5(10−(k+1))+k output from the “6 bit mod 17” circuit blocks turn to the inputs at the next step, that is, the (k+1)-th step.
Thus, the conversion of binary to p-adic number is executed sequentially from the most significant bit of the carry C as in the schematic diagram shown in FIG. 11 B.
FIG. 11(A) shows the circuitry related to the k-th step. The circuitry shown in FIG. 11(A) can be used over steps if the steps are processed in time division. In this case, for the purpose of using simple on/off for control of the inputs/outputs of the “6 bit mod 17” circuit blocks, the circuitry at the 0-th step having the maximum number of required “6 bit mod 17” circuit blocks is additionally provided with 10 “6 bit mod 17” circuit blocks.
A circuit including 56“6 bit mod 17” circuit blocks thus configured is shown in FIG. 12 . Hereinafter, this circuit is referred to as the “X to p” circuit block.
As shown in FIG. 13 , the inputs to the “X to p” circuit block include C 0 0 -C 0 59 , 60 pieces in total, 10 pieces more than that in the case of k=0 in FIG. 12(A) . The outputs therefrom include 11 5-bit binaries R 0 0 -R 0 4 , R 5 0 -R 5 4 , . . . , R 45 0 -R 45 4 , R 50 0 -R 50 4 output from every 5 “6 bit mod 17” circuit blocks, and 55 carries C 1 0 -C 1 55 to be used as the inputs at the next step.
Next, the “5 res” circuit block shown in FIG. 10 , that is, the “6 bit mod 17” circuit block is described specifically.
FIG. 14 is a diagram showing a circuit symbol of the “6 bit mod 17” circuit block. The “6 bit mod 17” circuit block receives a 6-bit binary A 0 -A 5 and provides a 5-bit binary Q 0 -Q 4 and a carry PF 0 .
The “6 bit mod 17” circuit block provides the residue Q modulo the prime 17 of the input binary A, and provides ‘1’ from PF 0 if the input binary A is equal to or more than 17 and ‘0’ from PF 0 if it is lower than 17.
In the case of h=5, p=17, relations shown in Expression 25 can establish among the binary A, the binary Q and the prime p.

a=A 0 +A 1 2 +A 2 2 2 +A 3 2 3 +A 4 2 4 +A 5 2 5

Q=a (mod p )( a=Q+PF 0× p )

Q=Q 0 +Q 1 2 +Q 2 2 2 +Q 3 2 3 +Q 4 2 4 [Expression 25]

FIG. 15 is a block diagram of the “6 bit mod 17” circuit block.
The “6 bit mod 17” circuit block comprises a PF 0 generator unit U 1 , 2 half adders HA 1 , HA 2 , and 3 full adders FA 1 -FA 3 .
The PF 0 generator unit U 1 includes serially connected PMOS transistors QP 1 -QP 5 and NMOS transistors QN 1 -QN 2 between the Vcc terminal supplied with a certain voltage and the Vss terminal supplied with the ground voltage. These transistors QP 1 , QP 2 , QP 3 , QP 4 , QP 5 , QN 1 and QN 2 are controlled by A 0 , A 1 , A 2 , A 3 , A 5 , A 0 and A 4 , respectively.
The PF 0 generator unit U 1 also includes a PMOS transistor QP 6 , 4 NMOS transistors QN 3 -QN 6 , and an inverter IV 1 .
The transistor QP 6 is connected between the source of the transistor QP 1 and the drain of the transistor QP 4 in parallel. The transistors QN 3 -N 5 are connected between the source and drain of the transistor QN 1 in parallel. The transistor QN 6 is connected between the source of the transistor QN 1 and the drain of the transistor QN 2 (Vss terminal) in parallel. These transistors QP 6 , QN 3 , QN 4 , QN 5 and QN 6 are controlled by A 4 , A 2 , A 3 and A 5 , respectively.
The inverter IV 1 has an input connected to the sources of transistors QN 1 , QN 3 -QN 6 . The output from the inverter IV 1 provides the carry PF 0 .
The half adder HA 1 has inputs A 0 and PF 0 , an output Q 0 , and a carry output C 0 . The full adder FA 1 has inputs C 0 and A 1 , a carry input PF 0 , an output Q 1 , and a carry output C 1 . The full adder FA 2 has inputs C 1 and A 2 , a carry input PF 0 , an output Q 2 , and a carry output C 2 . The full adder FA 3 has inputs C 2 and A 3 , a carry input PF 0 , an output Q 3 and a carry output C 3 . The half adder HA 2 has inputs C 3 and A 4 , and an output Q.
In accordance with the above configuration, the PF 0 generator unit U 1 decides if the binary A input to the “6 bit mod 17” circuit block is equal to or more than 17, and provides the result from PF 0 . If the binary A is equal to or more than 17, the half adders HA 1 , HA 2 and the full adders FA 1 -FA 3 are used to add 15, a complement of the 6-bit binary 17, to the binary A in order to subtract 17 from the binary A.
The following description is given to the core part of the “binary to p-adic” converter unit, that is, the p-adic” circuit block.
FIG. 16 is a diagram showing a circuit symbol of the “p-adic” circuit block.
The “p-adic” circuit block receives B 0 -B 11 , I 0 -I 59 , and provides r 0 -r 60 as shown in FIG. 16 .
FIG. 17 is a block diagram of the “p-adic” circuit block. The “p-adic” circuit block includes an “X to p” circuit block in the 1-step circuitry, and additional control switches SW for controlling the input/output of the “X to p” circuit block.
Specifically, the inputs I 0 -I 4 , I 5 -I 9 , . . . , I 54 -I 59 are fed via the control switches SW 1 to the “X to p” circuit block as C 0 0 -C 0 4 , C 0 5 -C 0 9 , . . . , C 0 54 -C 0 59 , respectively. These control switches SW 1 are controlled by the inputs B 1 -B 10 , respectively.
One control switch SW 1 includes a transfer transistor TQ operative to connect the input IN with the output OUT, and an NMOS transistor QN operative to pull down the output OUT to the ground voltage. The transfer transistor TQ turns on if the control signal is CNT=‘0’ while the transistor QN turns on if the control signal is CNT=‘1’.
In the case of the control switches SW 1 , the control signals CNT include /B 1 -/B 10 . Therefore, I 0 -I 59 are provided directly as C 0 0 -C 0 59 if B=‘1’, and the output turns to ‘0’ independent of the input if B=‘0’. This is effective to prevent the input to the “X to p” circuit block from becoming indefinite even if the inputs I 0 -I 59 to the “p-adic” circuit block are indefinite.
The “X to p” circuit block on receipt of C 0 0 -C 0 59 provides R 0 0 -R 50 4 , C 1 0 -C 1 55 as described above.
The outputs C 1 0 -C 1 55 from the “X to p” circuit block pass through the control switches SW 2 and turn to r 5 -r 60 , that is, the outputs from the “p-adic” circuit block. These control switches SW 2 are controlled by the inputs B 1 -B 10 . Therefore, these control switches SW 2 directly pass C 1 0 -C 1 55 as r 5 -r 60 if B=‘0’.
The outputs R 0 0 -R 50 4 from the “X to p” circuit block pass through the control switches SW 3 and turn to r 0 -r 54 , that is, the outputs from the “p-adic” circuit block. These control switches SW 3 are controlled by B 0 □/B 1 to B 10 □/B 11 , respectively. Therefore, the control switches SW 3 located between R 0 0 and r 0 , for example, directly provide R 0 0 as r 0 only if B 0 =‘1’ and B 1 =‘0’.
B 1 -B 11 for use in control of the control switches SW are timing signals, which are signals that rise sequentially. In sync with this, the paths for the inputs I open at every 5 bits from the lower bit side and the paths for the outputs r switch to the paths for the outputs R.
In order to provide the result at the present step until the flow enters the computation process at the next step, R corresponding to a coefficient A on each digit of a 17-adic number is provided to the later-described external “D-r” register via the control switches SW 3 on/off-controlled by the signals resulted from the logical operation with the adjacent timing signals B.
The following description is given to the “binary to p-adic” converter unit including the above-described circuits grouped together.
FIG. 18 is a block diagram of the “binary to p-adic” converter unit. The “binary to p-adic” converter unit includes the “p-adic” circuit block and the “D-r” register coupled thereto.
The “D-r” register is a register controlled by the timing signal B and the clock clk as shown in FIG. 18 . It has the inputs r 0 -r 60 , D 0 -D 60 and the outputs I 0 -I 59 .
FIG. 19 is a circuit diagram of the “D-r” register.
The “D-r” register includes a flip-flop FF composed of 2 inverters at every bit. The flip-flop FF receives D j (j=0-60) via the control switch SW 1 and receives r j via the control switch SW 2 . On the other hand, the flip-flop FF is connected to an inverter IV 1 on the output side via the control switch SW 3 . The output from the inverter IV 1 provides I j .
The control switches SW 1 -SW 3 are controlled by the timing signal B 0 and the clock clk. Specifically, the control switch SW 1 turns on if /clk□/B 0 =‘1’, the control switch SW 2 if /clk□B 0 =‘1’, and the control switch SW 3 if clk=‘1’, respectively.
D 50 -D 60 not contained in the data input to the “D-r” register are held at ‘0’.
In the initial state of the “D-r” register, a binary D 0 -D 49 is set, and the rest is filled with ‘0’. Thereafter, when B 0 rises, data r j is taken in sync with the fall of clk, and the taken r j is provided as I j in sync with the rise of clk.
The “D-r” register couples with the “p-adic” circuit block to advance the computation step at every timing signal B j . The state of variations in each clock is shown in FIG. 20 . The clock clk is used to generate a clock ck and further generate timing signals B j .
At each computation step, each digit A j of a 17-adic number is obtained as the output r from the lower side, and this is held at the same timing as that for taking I in the second half of the timing signal B j .
After completion of all the computation steps, the “D-r” register holds the coefficients A j m on respective digits when the coefficients a on respective digits of 17-adic data D are converted to binaries.
In the case of p=17, the number of computation steps is equal to 12, and the number of “6 bit mod 17” circuit blocks contained in the “p-adic” circuit block is equal to 56.
<Conversion of 17-Adic Number to 2 5 -Adic Number>
FIG. 21 is a diagram schematically showing the configuration of a circuit for converting a 11-digit, 17-adic number D (a 0 , a 1 , . . . , a 9 , a 10 ) in the “p-adic Zp world” to a 10-digit, 2 5 -adic number D (d 0 , d 1 , . . . , d 9 ) in the “binary world”.
A square shown with “5 add 17” in FIG. 21 indicates an operating circuit operative to add 17 to the input 5-bit data in accordance with the input carry C to provide a 6-bit binary. Hereinafter, this circuit is referred to as the “5 add 17” circuit block.
At the start, at the 0-th step (S 0 in FIG. 21 ), the above-described computation is executed to a binary representation of the digit at the 9th degree of the 17-adic number with a binary representation of the digit at the 10th degree used as a carry, that is, a binary representation of the number of 17 10 s, thereby obtaining 10 bits of a carry C 1 0 -C 1 9 as the number of 17 9 s. This carry C 1 0 -C 1 9 turns to the input at the next 1st step.
Subsequently, at the 1st step (S 1 in FIG. 21 ), the above-described computation is executed to a binary representation of the digit at the 8th degree of the 17-adic number with the carry C 1 0 -C 1 9 obtained at the 0-th step used as a binary representation of the number of 17 9 s, thereby obtaining 15 bits of a carry C 2 0 -C 2 14 as the number of 17 8 s. This carry C 2 0 -C 2 14 turns to the input at the next 2nd step (S 2 in FIG. 21 ).
Thereafter, the same steps as the 0-th step and the 1st step are repeated and, at the 9th step (S 9 in FIG. 21 ), the above-described computation is executed to a binary representation of the digit at the 0-th degree of the 17-adic representation with a carry C 9 0 -C 9 49 obtained at the previous 8th step (S 8 in FIG. 21 ) used as a binary representation of the number of p, thereby obtaining 55 bits of a carry C 10 0 -C 10 54 as the number of 17 0 s, that is, a binary representation of D. In this case, the upper 5 bits are held at zero in accordance with the setting of the 17-adic number and the 2 5 -adic number associated with D. When C 10 50 -C 10 54 are excluded from the carries C 10 0 -C 10 54 and the remaining C 10 0 -C 10 49 are grouped at every 5 bits, a binary representation of D, that is, D (d 0 , d 1 , . . . , d 9 ) can be obtained.
A consideration is given next to the configuration of the “p-adic to binary” converter unit.
FIG. 22 shows the circuitry at the k-th step in the “p-adic to binary” converter unit configured using “6 bit add 17” circuit blocks. The “6 bit add 17” circuit block is a circuit operative to add a prime 17 to 5-bit binary data, that is, the input B, and provides the result as binary data Q. The details are described later.
It is possible to express data, a coefficient a 3 on the digit at the j-th place of a 11-digit, 17-adic representation, in 5-bit binary. For the purpose of bringing the coefficient A of this binary representation into a representation in common with coefficients a on other digits, sub-indexes as shown in Expression 26 are used.

a j =A j 0 +A j 1 2 +A j 2 2 2 +A j 3 2 3 +A j 4 2 4

a j (2 5 ) j =A 5j 2 5j +A 5j+1 2 5j+1 +A 5j+2 2 5j+2 +A 5(j+1)−2 2 5(j+1)−2 +A 5(j+1)−1 2 5(j+1)−1 [Expression 26]

The input to the operation at the k-th step, that is, the carry at the previous step (the (k−1)-th step) includes C k 0 -C k 5(k+1)−1 , of which sub-index of a coefficient in the binary representation is an exponent of 2. The number expressed by this binary indicates the number of 17 10−k s contained in the data.
At the k-th step, 5 (k+1) pieces of “6 bit add 17” circuit blocks are used in processing as shown in FIG. 22(A) . Each “6 bit add 17” circuit block receives 1 carry, and 5 binaries indicative of a coefficient on 1 digit of a 17-adic representation.
The 1st “6 bit add 17” circuit block < 1 > receives C k 0 , Q −1 0 -Q −1 4 at the carry and the inputs B 0 -B 4 , and provides C k+1 0 , Q 0 0 -Q 0 4 from Q 0 , Q 1 -Q 5 , respectively.
The 2nd “6 bit add 17” circuit block < 2 >, not shown, receives C k 1 , Q 0 0 -Q 0 4 at the carry and the inputs B 0 -B 4 , and provides C k+1 1 , Q 1 0 -Q 1 4 from Q 0 , Q 1 -Q 5 , respectively.
Thereafter, the “6 bit add 17” circuit blocks having the similar inputs and outputs are aligned 5(k+1) pieces in total as shown in FIG. 22(A) , and a carry C k+1 0 -C k+1 5(k+1)−1 output from each “6 bit add 17” circuit block turns to the input at the next step, that is, the (k+1)-th step.
Thus, the conversion of a 17-adic number to a binary is executed sequentially from the least significant bit of a carry C as in a schematic diagram shown in FIG. 22(B) .
FIG. 22(A) shows the circuitry related to the k-th step as described above. The circuitry shown in FIG. 22(A) can be used over at each step if each step is processed in time division. In this case, for the purpose of making the input/output of each “6 bit add 17” circuit block controllable in accordance with simple on/off, 5 “6 bit add 17” circuit blocks in the case of k=0 are configured to form a circuit block with a minimum configuration as shown in FIG. 23 .
The circuit including the 5“6 bit add 17” circuit blocks thus configured is referred to as an “a to X” circuit block.
As shown in FIG. 24 , the “a to X” circuit block has the inputs of Q −1 0 -Q −1 4 and C 0 0 -C 0 4 , 10 in number, and the outputs of Q 4 0 -Q 4 4 and C 1 0 -C 1 4 , 10 in number.
The following specific description is given to the “5 add 17” circuit block shown in FIG. 21 , that is, the “6 bit add 17” circuit block.
FIG. 25 shows a circuit symbol of the “6 bit add 17” circuit block. The “6 bit add 17” circuit block receives a 5-bit binary B 0 -B 4 and a 1-bit carry (carry), and provides a 6-bit binary Q 0 -Q 5 . The “6 bit add 17” circuit block adds a prime 17 to the input B if the carry is ‘1’, and provides the result as Q.
In the case of h=5, p=17, the relation shown in Expression 27 can be established between the binary B and the binary Q.

b=B 0 +B 1 2 +B 2 2 2 +B 3 2 3 +B 4 2 4

Q=b +carry× p

Q=Q 0 +Q 1 2 +Q 2 2 2 +Q 3 2 3 +Q 4 2 4 +Q 5 2 5 [Expression 27]

FIG. 26 is a block diagram of the “6 bit add 17” circuit block.
The “6 bit add 17” circuit block includes 4 half adders HA 1 -HA 4 and a single full adder FA 1 .
The half adder HA 1 has inputs B 0 and carry, an output Q 0 , and a carry output C 0 . The half adder HA 2 has inputs C 0 and B 1 , an output Q 1 , and a carry output C 1 . The half adder HA 3 has inputs C 1 and B 2 , an output Q 2 , and a carry output C 2 . The half adder HA 4 has inputs C 2 and B 3 , an output Q 3 , and a carry output C 3 . The full adder FA 1 has inputs B 4 and carry, a carry input C 3 , an output Q 4 , and a carry output Q 5 .
In accordance with the above configuration, the “6 bit add 17” circuit block adds a prime 17 to the input binary B if carry=‘1’.
Next, the above-described “a to X” circuit blocks are used to configure a circuit for 1 step operative to lower the degree of the 17-adic number by 1. Hereinafter, the circuit is referred to as the “p to X” circuit block. The “p to X” circuit block can be used in all the computation steps in common.
FIG. 27 is a diagram showing a circuit symbol of the “p to X” circuit block. The “p to X” circuit block is controlled by the timing signals B 1 -B 9 to provide outputs C 10 0 -C 10 54 in response to inputs Q −1 0 -Q 44 4 , C 9 0 -C 9 49 .
FIG. 28 is a block diagram of the “p to X” circuit block.
The “p to X” circuit block comprises 10 “a to X” circuit blocks.
The 1st “a to X” circuit block < 1 > receives part of the inputs to the “p to X” circuit block, that is, Q −1 0 -Q −1 4 , and C 9 0 -C 9 4 , and provides Q′ 4 0 -Q′ 4 4 and part of the outputs from the “p to X” circuit block, that is, C 10 0 -C 10 4 .
The 2nd “a to X” circuit block < 2 > receives Q 4 0-Q 4 4 and part of the inputs to the “p to X” circuit block, that is, C 9 5 -C 9 9 , and provides Q′ 9 0 -Q′ 9 4 and part of the outputs from the “p to X” circuit block, that is, C 10 5 -C 10 9 . Among the inputs, Q 4 0 -Q 4 4 are signals fed via the control switches SW 1 , through which the outputs Q′ 4 0 -Q′ 4 4 from the 1st “a to X” circuit block < 1 > are controlled by the timing signal B 9 .
The 3rd “a to X” circuit block < 3 > receives Q 9 0 -Q 9 4 and part of the inputs to the “p to X” circuit block, that is, C 9 10 -C 9 14 , and provides Q′ 14 0 -Q′ 14 4 and part of the outputs from the “p to X” circuit block, that is, C 10 10 -C 10 14 . Among the inputs, Q 9 0 -Q 9 4 are signals fed via the control switches SW 2 , through which the outputs Q′ 9 0 -Q′ 9 4 from the 2nd “a to X” circuit block are controlled by the timing signal B 8 .
Thereafter, similar connections will be made up to the 10th “a to X” circuit block < 10 >.
The inputs and outputs of the “a to X” circuit block are connected via the control switches SW in this way, because the connection of the input is switched between the external input and the internal input at every computation step, and for the purpose of preventing the output from the internal circuit from interfering in the case of the external input.
In the case of the circuitry of FIG. 28 , all the control switches SW are turned off at the timing when only the timing signal B 0 is at ‘1’, thereby activating only the last “a to X” circuit block < 10 >. This corresponds to the 0-th step.
Subsequently, when the timing signal B 1 also turns to ‘1’, the 9th “a to X” circuit block < 9 > is activated additionally. This corresponds to the 1st step.
Thereafter, at every sequential rise of the timing signals B 2 -B 9 , the “a to X” circuit block required at each step is activated.
The following description is given to the core part of the “p-adic to binary” converter unit, that is, the “binary” circuit block.
FIG. 29 shows a circuit symbol of the “binary” circuit block.
As shown in FIG. 29 , the “binary” circuit block receives B 0 -B 10 , I 0 -I 54 , and provides r 0 -r 54 .
FIG. 30 is a block diagram of the “binary” circuit block. The “binary” circuit block includes the “p to X” circuit block in the circuitry for 1 step, and additionally the control switch SW for use in control of the input/output of the “p to X” circuit block.
Specifically, the inputs I 5 -I 54 are fed as C 9 0 -C 9 49 to the “p to X” circuit block via the control switches SW 1 . These control switches SW 1 are controlled by the timing signals B 1 -B 10 . Therefore, the control switches SW 1 pass I 5 -I 54 directly as C 9 0 -C 9 49 if B=‘1’ and keep the outputs at ‘0’ independent of the inputs if B=‘0’.
In addition, the input I 0 -I 49 are fed as Q −1 0 -Q 44 4 to the “p to X” circuit block via the control switches SW 2 , respectively. These control switches SW 2 are controlled in accordance with B 10 ^/B 9 to B 1 ^/B 0 , respectively. Therefore, the control switch SW 2 located between I 0 and Q −1 0 passes I 0 directly as Q −1 0 only if B 10 =‘1’, B 9 =‘0’.
The outputs C 10 0 -C 10 54 from the “p to X” circuit block turn to r 0 -r 54 , that is, the outputs from the “binary” circuit block via the control switches SW 3 . The control switches SW 3 are controlled by the timing signals B 9 -B 0 . Therefore, the control switches SW 3 pass C 10 0 -C 10 54 directly as r 0 -r 54 if B=‘1’.
In accordance with the above circuitry, the “p to X” circuit block responds to each computation step while increasing the bit widths of the input and output 5-bit by 5-bit sequentially. While taking the numerals A on the digits of the 17-adic number from the upper digit sequentially at each computation step, and when all the computation steps are completed, a binary representation of data can be obtained.
As describe earlier, the timing signals B 0 -B 10 are the signals that rise in order. In accordance therewith, the paths to the inputs I and outputs r conduct 5-bit by 5-bit from the upper bit.
The numeral A on each digit of the 17-adic number is initially set in the later-described external “A-r” register, and fed to the “A-r” register via the control switch SW 3 on/off-controlled by the adjacent timing signal B such that the path switches selectively until the flow enters the next computation step.
The following description is given to the “p-adic to binary” converter unit including the above-described circuits grouped together.
FIG. 31 is a block diagram of the “p-adic to binary” converter unit. The “p-adic to binary” converter unit includes the “binary” circuit block and the “A-r” register coupled thereto.
The “A-r” register is a register controlled by the timing signal B 0 and the clock clk and having the inputs r 0 -r 54 , A 0 -A 54 and the outputs I 0 -I 54 as shown in FIG. 31 .
FIG. 32 is a circuit diagram of the “A-r” register.
The “A-r” register includes, at every bit, a flip-flop FF composed of 2 inverters. The flip-flop FF receives A j (j=0-54) via the control switch SW 1 and receives r j via the control switch SW 2 . On the other hand, the output of the flip-flop FF is connected to an inverter IV 1 via the control switch SW 3 . The output from the inverter IV 1 provides I j .
The control switches SW 1 -SW 3 are controlled by the timing signal B 0 and the clock clk. Specifically, the control switch SW 1 turns on if /clk□/B 0 =‘1’, the control switch SW 2 if /clk□B 0 =‘1, and the control switch SW 3 if clk=‘1, respectively.
The initial state of the “A-r” register includes the digits A 0 -A 54 of the 17-adic number.
Thereafter, after the timing signal B 0 rises, r j taken in sync with the fall of the clock clk is provided as I j in sync with the rise of the clock clk.
The “A-r” register couples with the “binary” circuit block to advance the computation step at every timing signal B j . The state of variations in each clock is similar to FIG. 20 . The clock clk is used to generate ck and further generate the timing signal B j .
After completion of all the computation steps, the “A-r” register holds a binary representation D j of the input, that is, the p-adic number A.
Thus, preparations for configuring the p-adic NAND flash memory have been made.
Next, the configuration of the memory system according to the present embodiment is described along the flow of data processing.
Data processing in the memory system according to the present embodiment can be executed using a Lee metric code. The methods of data processing include the above-described syndrome converting method, and a Euclidean iterative method. A first embodiment describes a memory system using the syndrome converting method for data processing.
The general principle of the syndrome converting method is as described above. The following case is described with specific numerals such as p=17, ε=4, and δ=10 substituted based on the above-described specification.
FIG. 33 is a block diagram showing the configuration of a p-adic memory system.
Data D, that is, binary data to the “binary world” is converted to a 17-adic number at a 17-adic converter unit 101 serving as the entrance to the “p-adic Zp world”, and converted to a code in Zp, that is, data A.
The 17-adic converter unit 101 can be composed of the circuits described with reference to FIGS. 10-20 , such as the “X to p” circuit block.
Subsequently, an encoder unit 102 brings the data A output from the 17-adic converter unit 101 into action with a generator matrix G, thereby converting the data A to a Lee metric code, that is, a code C.
Subsequently, the code C output from the encoder unit 102 is stored in a p-adic cell flash memory 103 .
Subsequently, the code held in p-adic cells is read out of the p-adic cell flash memory 103 . The code read out of the p-adic cell flash memory 103 is a code Y (fourth data). The code Y corresponds to the code C, which has been deformed by errors caused when the code C is written in p-adic cells for storage, or while it is stored in the p-adic cells, or when it is read out of the p-adic cells.
The read-out code Y is fed to a syndrome generator unit 104 . The syndrome generator unit 104 computes a syndrome <m ′S in accordance with Expression 28 using a transpose syndrome matrix H t and the powers of 3 types of diagonal matrixes.











〈
m
〉


⁢
S

=



Y
⁡

[




(

17
-

1

-
1



)



0


…


0




0



(

17
-

2

-
1



)



…


0




⋮


⋮


⋱


⋮




0


0


⋯



(

17
-

16

-
1



)




]



m
3


⁢







[



16


0


…


0




0


15


…


0




⋮


⋮


⋱


⋮




0


0


…


1



]


m
2


⁡

[



1


0


…


0




0


2


…


0




⋮


⋮


⋱


⋮




0


0


…


16



]



m
1


⁢

H
t








[

Expression
⁢



⁢
28

]







If <m> S=0, no error arises. Then, for the purpose of achieving the final processing step in the “p-adic Zp world”, the code Y is fed to a decoder unit 109 . In the case of <m> S≠0, on the other hand, if the first component S 0 of <m> S in the case of <m>=(0, 0, 0) satisfies |S 0 |>5, reliable error correction is impossible. Accordingly, NG signal is provided and the error-containing code Y is fed to the decoder unit 109 . In other cases, the syndrome <m> S is fed to a solution searching polynomial generator unit 105 .
The solution searching polynomial generator unit 105 derives a solution searching polynomial Ψ(x) from the syndrome <m> S and, if the coefficient at the 4th degree is φ 4 ≠0, then it feeds the φ(x) to a Hasse differential polynomial generator unit 106 . In the case of φ 4 =0, on the other hand, the step of seeking a new syndrome <m> S with changed <m> is repeated to seek a polynomial Ψ(x) again. If the coefficient at the 4th degree of Ψ(x) is still φ 4 =0 even after repetitions up to <m>=(15, 15, 15), error correction is impossible. Accordingly, NG signal is provided and the error-containing code Y is fed to the decoder unit 109 .
The Hasse differential polynomial generator unit 106 derives a Hasse differential polynomial from the input Ψ(x), then computes a root r and the multiplicity n of the root, and feeds them as t=r −1 to an error quantity computing unit 107 .
The error quantity computing unit 107 derives the positional coordinates of the error-caused code word from t=r −1 and derives the error quantity e t (={u(t) <m> } −1 n) from n to obtain the total quantity, Σ|e t |, of Lee metrics of the error quantity. If Σ|e t |≦4, the flow shifts processing to a code restorer unit 108 in order to restore the code C of the Lee metric code. If Σ|e t |≧5, it is dealt as uncorrectable because there is the possibility of failed correction. In this case, the flow repeats processing on and after the syndrome generator unit 104 for the next <m>. In the case of <m>=(15, 15, 15), error correction is impossible. Accordingly, NG signal is provided and the error-containing code Y is fed to the decoder unit 109 .
The code restorer unit 108 restores the code C (c 1 , c 2 , . . . , c 3 ) in accordance with c t =y t −e t . The restored code C is fed to the decoder unit 109 .
The decoder unit 109 executes an inverse transformation of the generator matrix G to the code C to obtain a 17-adic code A. This code A is fed to a 2 5 -adic converter unit 110 .
The 2 5 -adic converter unit 110 converts the code A to a 2 5 -adic number represented in binary, which is provided as the restored binary data D.
The 2 5 -adic converter unit 110 can be composed of the circuits described with reference to FIGS. 21-32 , such as the “p to X” circuit block.
<Generation of Lee Metric Code, Error Correction, and Restoration of Lee Metric Code>
Next, the procedures of data processing described with reference to FIG. 33 are detailed.
Hereinafter, with respect to an ECC operation in the “p-adic Zp world”, the procedure of encoding data that is input as Zp data to the memory system, and the procedures of decoding the code read out of the memory system to finally obtain the data A are arranged.
The procedure of encoding is as follows.
At the start, the input data D is converted at the “binary to p-adic” converter unit to a 17-adic-represented, 11-digit data word D(h) shown in Expression 29 (S 1 in FIG. 34 ).

D ( h )=( a 0 ,a 1 , . . . , a 10 ) [Expression 29]

Subsequently, the data D is multiplied by the generator matrix G to obtain 16 code word components c 1 -c 16 of the code C (S 2 in FIG. 34 ). The value of each code word component is as shown in Expression 30.








c
j

=


∑

i
=
0

10

⁢



(
j
)


i
+
1


⁢

a
i







[

Expression
⁢



⁢
30

]







Finally, the code word component c j is stored in memory cells (S 3 in FIG. 34 ). Each code word component can be processed as a 5-bit binary representation. In this case, as threshold levels corresponding to the p-adic cells, levels are set as they are representations of numerals in Zp.
The procedure of decoding the code Y read out of the p-adic cell array is as follows.
At the start, the code Y read out of the p-adic cell array is read out (S 4 in FIG. 35 ). The code Y is configured as shown in Expression 31 where e j denotes an error on the code word symbol located at the position j in the code Y.

Y =( y 1 ,y 2 , . . . ,y 16 )

Y=C+E,E =( e 1 ,e 2 , . . . ,e 16 ) [Expression 31]

Subsequently, a syndrome is computed from the code Y (S 5 in FIG. 35 ). With a substitution of (j) <m> =(p−j −1 ) m3 (p−j) m2 j m1 and a substitution of <m>=(m1, m2, m3), a syndrome <m> S=(S <m>+0 , S <m>+1 , . . . , S <m>+4 ) is derived from <m> Y={(1) <m> y 1 , (2) <m> y 2 , (3) < m> y 3 , . . . , (15) <m> y n−1 , (16) <m> y n }, <m> S= <m> YH.
Subsequently, as S <0>+0 =S 0 in the case of <m>=0, the total quantity of Lee metrics of errors cannot reach 5 or higher if |S 0 |≦4 and accordingly the flow starts the following Procedures 2 and 3. In the case of |S 0 |>4, as the total quantity of Lee metrics of errors reaches 5 or higher, the flow determines that it is uncorrectable and terminates solution searching as no solution (S 6 , S 7 in FIG. 35 ).
(Procedure 1) For <m> of which components are changed in order, a syndrome <m> S=(S <m>+0 , S <m>+1 , . . . , S <m>+4 ) is derived from Expression 32 (S 8 in FIG. 35 ).








S


〈
m
〉

+
1


=



∑

j
=
1

16

⁢



(
j
)


〈
l
〉


⁢

y
j



=


∑

j
=
1

16

⁢



(
j
)


〈
l
〉


⁢

e
j








[

Expression
⁢



⁢
32

]







(Procedure 2) For ε=4, that is, the upper limit of the number of the correctable code word components, u=4 (S <m>+0 ) −1 is computed first, and then a syndrome u <m> S=(uS <m>+0 , uS <m>+1 , . . . , uS <m>+4 ) is derived from the syndrome obtained in Procedure 1 (S 9 in FIG. 35 ). The coefficients φ j of the solution searching polynomial Ψ(x) are computed from the syndrome u <m> S in turn using Expression 33 (S 10 in FIG. 35 ).









Ψ
⁡

(
x
)


=

1
+


∑

j
=
1

4

⁢


ψ
j

⁢

x
j





,


ψ
j

=


-

j

-
1



⁢


∑

i
=
1

j

⁢


ψ

j
-
1


⁢

uS


〈
m
〉

+
i










[

Expression
⁢



⁢
33

]







If the degree of Ψ(x) is equal to 4, that is, φ 4 ≠0, then the flow advances to Procedure 3 to obtain a solution (S 11 in FIG. 35 ). In the case of φ 4 =0, on the other hand, the flow puts <m> forward to repeat (Procedure 1) (S 12 in FIG. 35 ). In the case of φ 4 =0 and m ξ =15 (ξ=1-3), the flow abandons error correction as no solution (S 13 in FIG. 35 ).
(Procedure 3) If it is found in Procedure 2 that a solution can be obtained, processing on and after Procedure 3 is proceeded to obtain the solution.
The process seeks coefficients of the Hasse differential polynomial required for obtaining the multiplicity of the solution of the polynomial Ψ(x) sought in Procedure 2 (S 15 in FIG. 35 ). The coefficients φ j obtained in Procedure 2 can be multiplied by a series of binomial coefficients j C i to obtain vectors Ψ [i] =( i C i φ i , i+1 C i φ i+1 , . . . ) of the coefficients of the Hasse differential polynomial.









[

Ψ
⁡

(
x
)


]


[
i
]


=


∑

j
=
1


⁢


(



j




i



)

⁢

ψ
j

⁢

x

j
-
i








[

Expression
⁢



⁢
34

]







(Procedure 4) The Hasse differential polynomial obtained in Procedure 3 is given a substitution of the elements 1 - 16 in Zp to seek an element r that makes zero the 0-th degree differential polynomial (=Ψ(x)). Subsequently, as shown in Expression 35, such the degree n is sought that makes an (n−1)-th differential polynomial zero and an n-th differential polynomial non-zero, for each element r (S 16 in FIG. 35 ).
[ Ψ ⁡ ( r ) ] [ 0 ] = Ψ ⁡ ( r ) = 0 ,
⁢ [ Ψ ⁡ ( r ) ] [ n - 1 ] = ∑ j = n - 1 ⁢ ( j n - 1 ) ⁢ ψ j ⁢ r j - n + 1 = 0 ,
⁢ [ Ψ ⁡ ( r ) ] [ n ] = ∑ j = n ⁢ ( j n ) ⁢ ψ j ⁢ r j - n ≠ 0 [ Expression ⁢ ⁢ 35 ]
The obtained r is an inverse element of the position number t of the error-caused code component, and the corresponding n is the quantity converted from the caused error quantity e t . This process is executed over all the elements r.

(Procedure 5) In Procedure 5, the error quantity is obtained through conversion from the multiplicity n of the solution (S 17 in FIG. 35 ). The position number of the error-caused code word component is t=r −1 , and an inverse transformation of the conversion executed to obtain the polynomial for obtaining the solution is applied to n. As there is a relation of u(t) <m> e t =n, the original error quantity e t can be obtained from n if e t =(u(t) <m> ) −1 n. The possibility of failed correction of errors is confirmed here. In the case of Σ|e t |≦4, the flow subtracts the error quantity e t from the symbol value y t of the code Y read out of the memory cells to obtain a symbol value c t of the corrected code C, and shifts processing to Procedure 6 (S 18 , S 21 in FIG. 36 ). In the case of Σ|e t |>4, on the other hand, there is the possibility of failed correction. Accordingly, the flow changes the next m and repeats processing from Procedure 1 (S 19 in FIG. 36 ). Even in the case of m ξ =15 (ξ=1-3), however, if the flow fails to shift processing to Procedure 6, it abandons error correction as no solution (S 20 in FIG. 36 ).
Until now, the correct code C stored in the p-adic cell array has been obtained. Accordingly, binary data input to the p-adic memory system is sought in accordance with Procedure 6.
(Procedure 6) A pluralistic system of linear equations of a relation AG=C among the codes C and A and the generator matrix G is applied to obtain 11 elements a 0 -a 10 in Zp and A (=a 0 , a 1 , . . . , a 10 ). Thus, 11 elements a 0 -a 10 in Zp can be obtained. The obtained elements a 0 -a 10 are used to create data A (=a 0 , a 1 , . . . , a 10 ) therefrom (S 22 in FIG. 36 ).
Thus, data processing in the “p-adic Zp world” is finished. Subsequently, a conversion is made to restore the data A to binary data at the exit of the “p-adic Zp world”. The data A is converted from the 11-digit, 17-adic representation to a 10-digit, 2 5 -adic representation such that a numeral on each digit of 10 digits is represented in binary. This provides the binary data D input to the p-adic memory system.
Thus, restoration of data is completed.
Next, a computing circuit operative to seek the product of Zp is described. Hereinafter, the computing circuit is referred to as the “X Zp” circuit block.
FIG. 37 is a diagram showing a circuit symbol of the “X Zp” circuit block. FIG. 38(A) is a block diagram of the “X Zp” circuit block. FIGS. 38(B) and (C) are diagrams schematically showing operational processing in the “X Zp” circuit block.
The “X Zp” circuit block is roughly divided into a circuit for processing a computation step group in the first half, and a circuit for processing a computation step group in the second half.
The circuit for processing the computation step group in the first half includes an AND gate G 1 , and 4 “5 bit AD mod 17” circuit blocks.
The AND gate G 1 yields the logical product of the i-th bit (i=0-4) of the multiplied numeral a and the j-th bit (j=0-4) of the multiplying numeral b, and provides it as M ij .
The “5 bit AD mod 17” circuit block is a circuit operative to seek the sum of 2 numerals in Zp modulo 17. The “5 bit AD mod 17” circuit block has the inputs A 0 -A 4 and B 0 -B 4 and the outputs Q 0 -Q 4 . The details are described later.
The 1st “5 bit AD mod 17” circuit block < 1 > receives M 10 -M 40 , ‘0’, M 01 -M 41 at A 0 -A 3 , A 4 and B 0 -B 4 , and provides Q 0 0 -Q 0 4 from Q 0 -Q 4 , respectively.
The 2nd “5 bit AD mod 17” circuit block < 2 > receives Q 0 1 -Q 0 4 , that is, the output from the “5 bit AD mod 17” circuit block < 1 >, ‘0’, and M 02 -M 42 at A 0 -A 3 , A 4 and B 0 -B 4 , and provides Q 1 0 -Q 1 4 from Q 0 -Q 4 , respectively.
As described above, the circuit for processing the computation step group in the first half includes the “5 bit AD mod 17” circuit block < 1 > through the “5 bit AD mod 17” circuit block < 4 >, of which inputs and outputs are connected in order.
The circuit for processing the computation step group in the second half includes 4“6 bit mod 17” circuit blocks. The “6 bit mod 17” circuit block is the circuit shown in FIGS. 25 and 26 .
The 1st “6 bit mod 17” circuit block < 1 > receives Q 2 0 and Q 3 0 -Q 3 4 at A 0 and A 1 -A 5 , and provides Q 4 0 -Q 4 4 from Q 0 -Q 4 , respectively.
The 2nd “6 bit mod 17” circuit block < 2 > receives Q 1 0 and Q 4 0 -Q 4 4 at A 0 and A 1 -A 5 , and provides Q 5 0 -Q 5 4 from Q 0 -Q 4 , respectively.
As described above, the circuit for processing the computation step group in the second half includes the “6 bit mod 17” circuit block < 1 > through the “6 bit mod 17” circuit block < 4 >, of which inputs and outputs are connected in order.
All the circuits operate not in sync with clocks and decide the output Q when the input M ab is given.
Mention is made here of the circuit scale of the “X Zp” circuit block.
If p=17, h=5 as in the present example, the “X Zp” circuit block can be configured with 4“5 bit AD mod 17” circuit blocks and 4“6 bit mod 17” circuit blocks.
There is a requirement for such “X Zp” of 8 circuit blocks.
Next, the “5 bit AD mod 17” circuit block shown in FIG. 38 is described in detail.
FIG. 39 shows a circuit symbol of the “5 bit AD mod 17” circuit block.
The “5 bit AD mod 17” circuit block seeks the sum of numerals a and b input from A and B, and provides the residue modulo a prime p of the resultant sum, from Q.
In the case of h=5, p=17, the numerals a, b and the binary representation Q of the residue establish a relation shown in Expression 36.

a=A 0 +A 1 2 +A 2 2 2 +A 3 2 3 +A 4 2 4

b=B 0 +B 1 2 +B 2 2 2 +B 3 2 3 +B 4 2 4

p= 17=2 4 +1 ,/p= 2 5 −p= 2 3 +2 2 +2 1 +1=15

a+b≡Q (mod 17)( a+b=Q+PF 0×17)

Q=Q 0 +Q 1 2 +Q 2 2 2 +Q 3 2 3 +Q 4 2 4 [Expression 36]

FIG. 40 is a circuit diagram of the “5 bit AD mod 17” circuit block.
The “5 bit AD mod 17” circuit block comprises a PF 0 generator unit U 1 , 3 half adders HA 1 -HA 3 , and 7 full adders FA 1 -FA 7 .
The PF 0 generator unit U 1 includes serially connected PMOS transistors QP 1 -QP 4 and NMOS transistors QN 1 and QN 2 between a Vcc terminal supplied with a certain voltage and a Vss terminal. These transistors QP 1 , QP 2 , QP 3 , QP 4 , QN 1 and QN 2 are controlled by S 0 , S 1 , S 2 , S 3 , S 0 and S 4 , respectively.
The PF 0 generator unit U 1 additionally includes a PMOS transistor QP 5 , 3 NMOS transistors QN 3 -QN 5 , and an inverter IV 1 .
The transistor QP 5 is connected between the source of the transistor QP 1 and the drain of the transistor QP 4 in parallel. The transistors QN 3 -QN 5 are connected between the source and drain of the transistor QN 1 in parallel. These transistors QP 5 , PN 3 , QN 4 and QN 5 are controlled by S 4 , S 1 , S 2 and S 3 , respectively. The inverter IV 1 has an input connected to the sources of the transistors QN 1 , QN 3 -QN 5 . The output from the inverter IV 1 provides a carry PF 0 .
The half adder HA 1 has inputs A 0 and B 0 , an output S 0 , and a carry output C 0 ′. The full adder FA 1 has inputs A 1 and B 1 , a carry input C 0 ′, an output S 1 , and a carry output C 1 ′. The full adder FA 2 has inputs A 2 and B 2 , a carry input C 1 ′, an output S 2 , and a carry output C 2 ′. The full adder FA 3 has inputs A 3 and B 3 , a carry input C 2 ′, an output S 3 , and a carry output C 3 ′. The full adder FA 4 has inputs A 4 and B 4 , a carry input C 3 ′, an output S 4 , and a carry output C 4 ′. The half adder HA 2 has inputs S 0 and PF 0 , and an output Q 0 , and a carry output C 0 . The full adder FA 5 has inputs S 1 and PF 0 , a carry input C 0 , an output Q 1 , and a carry output C 1 . The full adder FA 6 has inputs S 2 and PF 0 , a carry input C 1 , an output Q 2 , and a carry output C 2 . The full adder FA 7 has inputs S 3 and PF 0 , a carry input C 2 , an output Q 3 , and a carry output C 3 . The half adder HA 3 has inputs C 3 and S 4 , and an output Q.
In accordance with the above configuration, the PF 0 generator unit U 1 determines if the sum of binaries A and B input to the “5 bit mod 17” circuit block is equal to or higher than 17. If the sum of binaries A and B is equal to or higher than 17, then the half adders HA 1 -HA 3 and the full adders FA 1 -FA 7 are used to add 15, a complement of 17 in 5-bit binary, to the sum of A and B in order to subtract 17 from the sum of A and B.
Hereinafter, the circuitry of the blocks in the “p-adic Zp world” is described with specific examples shown.
An example of circuitry of the encoder unit 102 is described below.
FIG. 41(A) is a block diagram of a circuit for converting a code word A in Zp to a Lee metric code C. FIG. 41(B) is a diagram showing double clocks ck and cl for use in control of the circuit shown in FIG. 41(A) .
As shown in FIG. 41(B) , the clocks cl are pulses that rise after the rise of ck with delays, and the clocks cl, 11 in total, cl 0 -cl 10 , rise sequentially at every clock ck. After cl 10 rises, the next clock ck rises with a delay. The same waveforms repeat from ck 0 to ck 17 .
Among these clocks ck and cl, ck is applied to control a “Counter (1 to 6)” circuit block and a “Ri (1-16)” register unit, and cl to control a “Ro (0-16)” register unit and a “Rgstr” register.
The “Counter (1 to 6)” circuit block is a circuit having an initial state of 0. It starts counting the number of clocks again at every rise of the clock ck and provides the number. Namely, of ck j (j=1-16), it provides j to an “X k-times” circuit block at the rise of ck j .
The “Ri (1-16)” register unit includes registers operative to store components c j of the code word C and capable of storing 16 numerals in total. The “Ri (1-16)” register unit stores numerals in the individual registers sequentially in sync with the timing of the rise of ck. Namely, data, that is, the element c j is taken into the register at the timing of the rise of ck j+1 . At the rise of ck 17 , 16 elements c j are taken in the registers. In a word, the code C can be thus stored.
The “X k-times” circuit block is circuit that multiplies the input by the output at every rise of the clock cl. The “X k-times” circuit block multiplies the output by the input j at every rise of cl, 11-times in total. Namely, the rises of cl i (i=0-10) bring the output from the “X k-times” circuit block to (j) i+1 . This output is fed to the “X Zp” circuit block.
The “Ro (0-10)” register unit includes registers, which can store 11 numerals and, in the initial state, store 11 components a 0 -a 10 of the code A. The “Ro (0-10)” register unit receives the clocks cl, and provides the components a 0 -a 10 of the code A in order at every rise of the clock cl. Namely, on receipt of cl i (i=0-10), it provides a i .
The “X Zp” circuit block is a circuit operative to execute a multiplication of the input in Zp. The “X Zp” circuit block receives the output (j) i+1 from the “X k-times” circuit block and the output a i from the “Ro (0-10)” register unit at every clock cl i , and provides (j) i+1 a i . The output numerals (j) i+1 a i are summed in a combination of the “5 bit AD mod 17” circuit block and the “Rgstr” register.
The “5 bit AD mod 17” circuit block is a circuit that seeks the sum of 2 input numerals modulo 17. On the other hand, the “Rgstr” register is a register having an initial state of 0. It blocks any input from the “5 bit AD mod 17” circuit block at every input of the clock cl and feeds the self-holding contents to the “5 bit AD mod 17” circuit block. The connection of the “5 bit AD mod 17” circuit block with the “Rgstr” register as shown in FIG. 41 allows the previous output numeral to be added to a numeral output from a new “X Zp” circuit block at every input of the clock cl. Namely, when the clock cl 0 -cl 10 rises, the component c j of C after the conversion of the code A to the Lee metric code is provided in the cycle of the clock ck j . This is held in the “Ri (1-16)” register unit at the top in the cycle of the next ck j+1 . Thus, the code C converted from the code A can be obtained.
The “X k-times” circuit block shown in FIG. 41 is described.
FIG. 42 is a diagram showing a circuit symbol of the “X k-times” circuit block. FIG. 43 is a block diagram of the “X k-times” circuit block.
The “X k-times” circuit block is a circuit operative to compute a power (X) j of the input X, which is controlled by the clock cl j (j=1-16) as shown in FIG. 42 .
The “X k-times” circuit block includes an “X Zp” circuit block, and a “Rgstr” register < 1 > and a “Rgstr” register < 2 > operable in sync with the clock cl as shown in FIG. 43 .
The “Rgstr” register < 1 > has an input connected to X, and an output connected to one output of the “X Zp” circuit block. The “Rgstr” register < 2 > has an input connected to the output of the “X k-times” circuit block X, and an output connected to one input of the “X k-times” circuit block. The “Rgstr” register < 2 > holds ‘1’ in the initial state.
In accordance with this circuitry, the “X k-times” circuit block takes its own output with a 1-cycle delay to obtain the product of the input X and the output (X) j .
The output (X) j is multiplied cumulatively by the input X at every input of the clock cl. The data X is set in the “Rgstr” register < 1 > before the clock cl i (j=1-k) rises, and the “Rgstr” register < 2 > having an initial state of ‘1’ is brought into sync therewith, thereby obtaining (X) j at the j-th cl j .
An example of circuitry of the syndrome generator unit 104 is described below.
First, a circuit for seeking component elements of the syndrome <m> S is described.
Scanning of <m>=(m1, m2, m3) is executed over the components from 1 to 15 each. When each <m> is given, the corresponding component of the syndrome is computed. An equation required for operational processing of the component of the syndrome is shown in Expression 37.











〈
m
〉


⁢
S

=



Y
⁡

[




(

17
-

1

-
1



)



0


…


0




0



(

17
-

2

-
1



)



…


0




⋮


⋮


⋱


⋮




0


0


⋯



(

17
-

16

-
1



)




]



m
3


⁢








[



16


0


…


0




0


15


…


0




⋮


⋮


⋱


⋮




0


0


…


1



]


m
2


⁡

[



1


0


…


0




0


2


…


0




⋮


⋮


⋱


⋮




0


0


…


16



]



m
1


⁢

H
t

⁢




⁢



⁢

S
0


=



∑

j
=
1

16

⁢

y
j


=



∑

j
=
1

16

⁢


e
j

⁢




⁢

S


〈
m
〉

+
1




=



∑

j
=
1

16

⁢



(

17
-

j

-
1



)


m
3


⁢


(

17
-
j

)


m
2


⁢


(
j
)


m
1


⁢


(
j
)

l

⁢

y
j



=


∑

j
=
1

16

⁢



(

17
-

j

-
1



)


m
3


⁢


(

17
-
j

)


m
2


⁢


(
j
)



m
1

+
1


⁢

e
j













[

Expression
⁢



⁢
37

]







At the start, all the <m>-associated powers of elements in Zp required for computation are sought. In a computing method using that powers in seeking the sum of syndromes, the process seeks the power of each element in Zp and, when the element j in Zp is selected, the process decodes 17-j or 17-j −1 to select the power of the corresponding element, thereby computing the product or the sum.
Therefore, a computing circuit operative to seek the powers of elements in Zp is described.
FIG. 44(A) is a block diagram of the computing circuit operative to seek the power j m of an element j in Zp, and FIG. 44(B) is a timing chart of the clocks ck, cl and the timing signals B 0 -B 15 for use in control of this circuit.
This computing circuit comprises a selecting circuit U 1 , a “(j) i (j=1 to 16)” circuit block, a “R 1 (0-15)” register unit, a “R 2 (0-15)” register unit, and a “R 3 (0-15)” register unit.
The selecting circuit U 1 includes 16 AND gates G 1 -G 16 . The AND gate G 1 receives B 0 and /B 1 , and provides a signal “m=0”. The AND gate G 2 receives B 1 and /B 2 , and provides a signal “m=1”. From then on, in accordance with similar input/output, the AND gates G 3 -G 16 provide signals “m=2” to “m=15”, respectively. These signals “m=0” to “m=15” turn via the control switches SW 1 -SW 16 to the outputs r ξ (ξ=1, 2, 3) from the selecting circuit U 1 . The signals “m=0” to “m=15” are decoded through the control switches SW 1 -SW 16 at every value of the component of <m>.
As shown in FIG. 44(B) , the clocks cl are generated in 16 cycles, 15-times repeatedly, subsequent to the clock ck such that the “(j) i (j=1 to 16)” circuit block provides (j) 1 in the cycles of the clocks ck i and cl j .
The output (j) i is latched as data in the “R 1 (0-15)” register unit, the “R 2 (0-15)” register unit, and the “R 3 (0-15)” register unit in appropriate cycles to obtain 3 powers of the elements in Zp.
Determination of the timing of taking data in the “R 1 (0-15)” register unit, the “R 2 (0-15)” register unit and the “R 3 (0-15)” register unit requires the generation and use of signals B 0 -B 16 shown in FIG. 44(B) that rise sequentially in sync with the clock ck. The signals B 0 -B 16 are used to generate signals m=0, m=1, . . . , m=15, which are activated between the rise of ck and the rise of the next ck.
The selecting circuit U 1 decodes and selects these signals m=0, m=1, . . . , m=15 at every value of the component m ξ of <m>, and provides it as a signal r ξ , which is effective only in the time of ck i of i=m ζ .
The “R 1 (0-15)” register unit, the “R 2 (0-15)” register unit and the “R 3 (0-15)” register unit each determine the time of taking data in accordance with the signal j, that is, the logical sum of the signal r ξ and the clock cl i , and latch data in sync with the clock cl. As a result, at the end of the clock cycle, the m ζ -th (ζ=1, 2, 3) powers of the elements in Zp are stored in the “R 1 (0-15)” register unit, the “R 2 (0-15)” register unit and the “R 3 (0-15)” register unit.
Thus, the <m>-associated powers of the elements in Zp are generated.
The subsequent description is given to a computing circuit, applied to each element j in Zp, for computing an error component ε <m>+l j (l=1, 2, 3, 4; j=1-16) converted through the syndrome converting method. The error component is defined as ε <m>+l j =(17-j −1 ) m3 (17-j) m2 (j) ml+1 y j .
FIG. 45 is a block diagram of the computing circuit for computing ε <m>+l j . Hereinafter, this computing circuit is referred to as the “error component generator circuit”.
The error component generator circuit comprises a decoder unit U 1 , and a product operating unit U 2 .
The decoder unit U 1 includes a “Counter (1 to 16)” circuit block, a “17-j dec” circuit block, a “17-j −1 dec” circuit block, a “j 2 dec” circuit block, a “j 3 dec” circuit block and a “j 4 dec” circuit block, and also includes the “R 1 (0-15)” register unit, the “R 2 (0-15)” register unit and the “R 3 (0-15)” register unit used to store the m ξ -th powers of the elements in Zp (ξ=1, 2, 3) shown in FIG. 44 .
The decoder unit U 1 , “Counter (1 to 16)” circuit block generates j in order at the timing of the clock cl j (j=1-16). The j output from the “Counter (1 to 16)” circuit block is fed to the “17-j dec” circuit block, to the “17-j −1 dec” circuit block, to the “j 2 dec” circuit block, to the “j 3 dec” circuit block and to the “j 4 dec” circuit block.
The “17-j dec” circuit block decodes the input j to provide 17-j. The “17-j −1 dec” circuit block decodes the input j to provide 17-j −1 . The j 2 dec” circuit block decodes the input j to provide j 2 . The“j 3 dec” circuit block decodes the input j to provide j 3 . The“j 4 dec” circuit block decodes the input j to provide j 4 .
The “R 1 (0-15)” register unit provides (j) m1 based on the input j. The “R 2 (0-15)” register unit provides (17-j) m2 based on 17-j output from the “17-j dec” circuit block. The “R 3 (0-15)” register unit provides (17-j −1 ) m3 based on 17-j −1 output from the “17-j −1 dec” circuit block.
Thus, the decoder unit U 1 can obtain the outputs (j) m1 , (17-j) m2 , (17-j −1 ) m3 .
The product operating unit U 2 comprises a “Ro (1-16)” register unit, and 7 “X Zp” circuit blocks < 1 >-< 7 >.
The “Ro (1-16)” register unit includes 16 latches. These 16 latches hold 16 components of the code Y read out of the p-adic cells, that is, the elements y 1 -y 16 in Zp, respectively. The “Ro(1-16)” register unit provides y j , held in the latches, in sync with the clock cl j (j=1-16).
The “X Zp” circuit block < 1 > computes the product in Zp of y j output from the Ro (1-16)” register unit and (j) m1 output from the “R 1 (0-15)” register unit, and provides the product.
The “X Zp” circuit block < 2 > computes the product in Zp of (17-j) m2 output from the “R 2 (0-15)” register unit and (17-j −1 ) m3 output from the “R 3 (0-15)” register unit, and provides the product.
The “X Zp” circuit block < 3 > computes the product in Zp of the output from the “X Zp” circuit block < 1 > and the output from the “X Zp” circuit block < 2 >, and provides the product ε <m>+0 j .
The “X Zp” circuit block < 4 > computes the product of <m>+0 j output from the “X Zp” circuit block < 3 > and j, and provides the product ε <m>+l j .
The “X Zp” circuit block < 5 > computes the product of ε <m>+0 j output from the “X Zp” circuit block < 3 > and j 2 output from the “j 2 dec” circuit block, and provides the product ε <m>+3 3 .
The “X Zp” circuit block < 6 > computes the product of ε <m>+0 j output from the “X Zp” circuit block < 3 > and j 3 output from the “j 3 dec” circuit block, and provides the product ε <m>+3 j .
The “X Zp” circuit block < 7 > computes the product of ε <m>+0 j output from the “X Zp” circuit block < 3 > and j 4 output from the “j 4 dec” circuit block, and provides the product ε <m>+4 j .
With the above-configured product operating unit U 2 , the selected read data Y can be obtained in sync with the clock cl j as ε <m>+0 j , ε <m>+l j , ε <m>+2 j , ε <m>+3 j , ε <m>+4 j corresponding to the elements j in Zp.
The subsequent description is given to a computing circuit operative to seek the sum of ε <m>+l j (l=1, 2, 3, 4) where j=1-16. Seeking the sum of ε <m>+l j (l=1, 2, 3, 4) where j=1-16 allows a syndrome S <m>+1 to be obtained. Hereinafter, this computing circuit is referred to as the “syndrome generating circuit”.
FIG. 46 is a block diagram of the syndrome generating circuit.
The syndrome generating circuit includes a “Rgstr” register and a “5 bit AD mod 17” circuit block.
The syndrome generating circuit yields the sum of ε <m>+l j in sync with the clock cl j (j=1-16) through a loop containing the “5 bit AD mod 17” circuit block and the “Rgstr” register to generate the syndrome component S <m>+l (l=0-4).
The following description is given to a circuit block for computing the i-th power of the element j in Zp used in the circuit for seeking j m shown in FIG. 44 . Hereinafter, this circuit block is referred to as the “(j) i (j=1 to 16)” circuit block.
FIG. 47 is a diagram showing a circuit symbol of the “(j) i (j=1 to 16)” circuit block.
The “(j) i (j=1 to 16)” circuit block is controlled by the clocks ck i (i=0-15) and cl j (j=1-16), and provides (j) i and (j) i+1 in sync with the rise of the clock cl 3 .
FIG. 48 is a block diagram of the “(j) 1 (j=1 to 16)” circuit block.
The “(j) i (j=1 to 16)” circuit block is a circuit that computes the 0-th to 15-th powers of all the elements 1 - 16 in Zp other than zero in order, and holds them in registers.
The “(j) i (j=1 to 16)” circuit block includes an “X Zp” circuit block, a “Counter (1 to 16)” circuit block, and a “R (1-16)” register unit as shown in FIG. 48 .
The index-decidable clock is cki, and an index i can be decided by the order of the clock cki. On the other hand, the elements in Zp are designated in order from 1 by the clock cl, and the order j of the clock cl indicates the number of elements.
The “Counter (1 to 16)” circuit block is connected to one input of the “X Zp” circuit block. It uses ck i as the start signal and counts up at the timing of the rise of cl j within a range of 1-16.
The “R (1-16)” register unit includes 16 registers, and it stores inputs i 1 -i 16 in No. 1-16 registers in order at the rise of the clock /cl j at in, and provides the contents i 1 -i 16 of No. 1-16 registers in order at the rise of the clock cl j at out.
As shown in FIG. 48 , the clocks ck and cl input to the “Counter (1 to 16)” circuit block and the “R (1-16)” register unit are synchronized with each other, and the output from the “R (1-16)” register unit is multiplied by the output from the “Counter (1 to 16)” circuit block at the “X Zp” circuit block. In this case, after the clock ck i rises, the “R (1-16)” register unit provides (j) i at every rise of cl j . In addition, the “X Zp” circuit block provides (j) i+1 . This (j) i+1 can be used in each computing circuit, if required.
As an example of circuitry of the solution searching polynomial generator unit 105 , an operating circuit for seeking a solution searching polynomial Ψ(x) is described below. This operating circuit is referred to as the “solution searching polynomial generating circuit”.
A processing equation is shown in Expression 38, which is required in operational processing for deriving a coefficient φ j at each degree j of x in the solution searching polynomial Ψ(x).









Ψ
⁡

(
x
)


=

1
+


∑

j
=
1


⁢


ψ
j

⁢

x
j





,




⁢


ψ
j

=


-

u
j


⁢


∑

i
=
1

j

⁢


ψ

j
-
1


⁢

S


〈
m
〉

+
i






,




⁢

u
=

4

S


〈
m
〉

+
0








[

Expression
⁢



⁢
38

]







FIG. 49 is a block diagram of the solution searching polynomial generating circuit.
The solution searching polynomial generating circuit is a circuit for use in the step of error searching with the use of a syndrome u <m> S=(uS <m>+0 , uS <m>+1 , uS <m>+2 , uS <m>+3 , uS <m>+4 ).
The solution searching polynomial generating circuit allows a simple circulation circuit to generate the solution searching polynomial Ψ(x) without using a complicated Euclidean iterative method.
The solution searching polynomial generating circuit comprises a first part circuit U 1 for deriving Σφ j−l S <m>+i on the right side of the 2nd equation shown in Expression 38, and a second part circuit U 2 for deriving u(j) −1 on the right side of the 2nd equation shown in Expression 38 as well.
The first part circuit U 1 includes 4 serially connected “Rgstr” registers < 1 >-< 4 >, and 4 “X Zp” circuit blocks < 1 >-< 4 > connected to the outputs of the Rgstr” registers, respectively.
The “Rgstr” register < 1 > has an initial value of ‘1’ and other “Rgstr” registers < 2 >-< 4 > have an initial value of ‘0’.
The first part circuit U 1 is controlled by the clock ck fed to the “Rgstr” registers, and provides the coefficients φ j−1 , φ j−2 , φ j−3 , φ j−4 at the respective degrees from the nodes between the “Rgstr” registers at the rise of the j-th clock ck j . A node with no coefficient present is at ‘0’ and accordingly cannot contribute to the product operation with the syndrome components S <m>+1 -S <m>+4 executed by the “X Zp” circuit blocks < 1 >-< 4 >. The outputs from the X Zp” circuit blocks < 1 >-< 4 > are summed 2 by 2 at the “5 bit AD mod 17” circuit blocks, and a ladder of these “5 bit AD mod 17” circuit blocks is applied to finally obtains Σφ j−1 S <m>+i .
The second part circuit U 2 comprises a “Counter (1 to 4)” circuit block, “X Zp” circuit blocks <a>, <b>, and a “j −1 dec” circuit block.
The second part circuit U 2 generates (jS <m>+0 ) −1 from j generated at the “Counter (1 to 4)” circuit block and the syndrome component S <m>+0 , in accordance with the clock ck j , at the “X Zp” circuit block <a> and the “j −1 dec” circuit block. Then, the “X Zp” circuit block <b> derives u(j) −1 from the generated (jS <m>+0 ) −1 and the established ε=4.
An “X Zp” circuit block <c> is used to multiply Σφ j−1 S <m>+i generated at the first part circuit U 1 , by u(j) −1 , generated at the second part circuit U 2 , to yield the coefficient φ j .
The coefficient φ j is a h-bit binary, which is represented in complement to represent a negative number. Therefore, the output from the “X Zp” circuit block <c> is inverted through the inverter IV 1 , and ‘1’ is added thereto at the “5 bit AD mod 17” circuit block, thereby obtaining a complement representation of 5-bit binary.
The “j −1 dec” circuit block shown in FIG. 49 is a circuit operative to seek the inverse element j −1 of an element j in Zp. The details of the “j −1 dec” circuit block are described later.
The solution searching polynomial generating circuit described above is possible to provide the coefficients φ 4 -φ 0 where j=4 on the respective nodes on receipt of 4-times inputs of the clock ck.
An example of circuitry of the Hasse differential polynomial generator unit 106 is described below.
If the degree of Ψ(x) is coincident with 4, it is required to derive the root of this Ψ(x) and the associated multiplicity. Therefore, the following description is given to an operating circuit operative to compute a coefficient of the Hasse differential polynomial required in deriving the multiplicity of the root. Hereinafter, this operating circuit is referred to as the “Hasse differential polynomial coefficient generating circuit”.
A relation between the coefficient of the Hasse differential polynomial, the coefficient, and the coefficient of Ψ(x) is as shown in Expression 39.









[

Ψ
⁡

(
x
)


]


[
i
]


=



∑

j
=
0


4
-
i


⁢


(




j
+
i





i



)

⁢

ψ

j
+
i


⁢

x
j



=


∑

j
=
0


4
-
i


⁢


ψ

[
i
]


⁢

jx
j








[

Expression
⁢



⁢
39

]







In a word, as can be found from Expression 39, the Hasse differential polynomial coefficient generating circuit multiplies the coefficient of Ψ(x) by the binomial coefficient, generates the coefficient at each degree at every differential stage using the clocks ck and cl, and stores all the coefficients in the registers.
FIG. 50(A) is a block diagram of the Hasse differential polynomial coefficient generating circuit, and FIG. 50(B) is a timing chart of the clocks ck and cl for use in control of the Hasse differential polynomial coefficient generating circuit.
The Hasse differential polynomial coefficient generating circuit includes a “i!” table having a record of the factorial i! of each element i in Zp, a “(i!) −1 ” table having a record of the inverse element, and a “φ i ” table having a record of the coefficient φ i of the solution searching polynomial Ψ(x). As for the i!” table and “(i!) −1 ” table, they can be suppressed to sufficiently small scales in practice in the case of p=17 as in the present example.
As for the “φ i ” table, it is created in the Hasse differential polynomial coefficient generating circuit shown in FIG. 49 . Therefore, this is used.
The Hasse differential polynomial coefficient generating circuit includes, as shown in FIG. 50 , the “i!” table, the “(i!) −1 ” table, the “φ i ” table, an “X Zp” circuit block, and control switches SW for switching the connections among those. Non-selected nodes, the nodes on the output side of the control switches SW, are discharged to ‘0’ in the initial state, such that the result of the product operation executed by the “X Zp” circuit block indicates ‘0’.
The number of clocks of the clock ck corresponds to the number of differential stages, and i in ck i takes a value of 1-4. On the other hand, the clock cl corresponds to the degree, and a growth in number of differential stages increases undesired degrees. Therefore, it is not required to generate the clock cl every time by the same number as the clock ck though the circuit of FIG. 50 generates it just 4 times every time. Therefore, although there are 4 2 storage timings, the “R i(0-4)/j(0-3)” register unit is not required to include registers corresponding to all clocks but just required to include almost half registers.
For the purpose of storing the coefficients of Ψ(x), that is, the coefficients corresponding to Ψ [0] , previously in the registers, ck 0 is provided as a matter of convenience.
FIG. 51 is a table of fixed operations (such as inverse element, factorial, and power) executed to each element in Zp in the case of p=17 also available in the Hasse differential polynomial coefficient generating circuit.
The 5-bit binary representations of these numerals can be used to form a decoder. Examples of the functions, which can scan all elements in Zp without excess/shortage when j varies through all elements 1 - 16 in Zp, are as shown in the table, which may exclude even powers and factorials in many cases. For example, a i can scan all elements in Zp except zero when j varies if a can satisfy the condition. For example, the cases of a=3, 5, 6, 7, 10 are as shown in FIG. 51 .
These functions can be utilized to extend the searching range by virtual errors in the syndrome converting method.
As an example of the circuit that configures the decoder, a decoder operative to derive the inverse element j −1 of an element j in Zp is described. Hereinafter, this decoder is referred to as the “j −1 dec” circuit block.
The inverse element j −1 can be derived from the element j by seeking a relation of j×j −1 ≡1 (mod 17), then configuring j and j −1 , 5-bit binary representations as shown in Expression 40 to form a converting decoder thereof.

Input: I i =( j ) i

j =( j ) 0 +( j ) 1 2+( j ) 2 2 2 +( j ) 3 2 3 +( j ) 4 2 4

Output: O i =( j −1 ) i

jj −1 ≡1(mod p )

j −1 =( j −1 ) 0 +( j −1 ) 1 2+( j −1 ) 2 2 2 +( j −1) 3 2 3 +( j −1 ) 4 2 4 [Expression 40]

FIG. 52 is a block diagram of the “j −1 dec” circuit block.
The “j −1 dec” circuit block can be configured by a general circuit operative to decode 5-bit binary data I to other 5-bit binary data O, setting I=j, O=j −1 as shown in Expression 40 in this case.
The “j −1 dec” circuit block includes NAND gates G 1 and G 2 to decode bits I 0 -I 3 partially 2-bit by 2-bit to create signals /A 0 -/A 3 , /B 0 -/B 3 , and also includes a 3-input NOR gate G 3 to create O m (m=0-4) from /A m , /B m , I 4 (or /I 4 ). In the case of j=0, a setting of j −1 =0 is given.
The following description is given to an operating circuit operative to compute the root and the associated multiplicity of the solution searching polynomial Ψ(x). Hereinafter, this operating circuit is referred to as the “solution searching polynomial root/multiplicity operating circuit”.
The solution searching polynomial root/multiplicity operating circuit regards the 0-th stage differential in the Hasse differential polynomial as Ψ(x). Unless the Hasse differential polynomial is zero for each element in Zp, the circuit shifts the computation to the next element. The circuit increases the number of differential stages while the Hasse differential polynomial keeps zero. When registers are used to hold the number of the first Hasse differential stages where the Hasse differential polynomial is not zero, for each element in Zp, the element with the number of stages being not zero indicates the root, and the number of the remaining stages indicates the multiplicity of the root. In a word, when those with non-‘0’ contents are selected from the registers, the held value indicates the multiplicity of the root.
Specifically, when the root of the solution searching polynomial Ψ(x) is denoted with α, and a Hasse differential polynomial of Ψ(x) in the i-th stage with [Ψ(x)] [i] , a relational equation is given as Expression 41 where the multiplicity of α is denoted with n.










[

Ψ
⁡

(
α
)


]


[
0
]


=


Ψ
⁡

(
α
)


=


1
+


∑

j
=
1

4

⁢


ψ
j

⁢

α
j




=



0
⁢




[

Ψ
⁡

(
α
)


]


[

n
-
1

]


=



∑

j
=
0


5
-
n


⁢


ψ
j

[

n
-
1

]


⁢

α
j



=
0





,




⁢



[

Ψ
⁡

(
α
)


]


[
n
]


=



∑

j
=
0


4
-
n


⁢


ψ
j

[
n
]


⁢

α
j



≠
0






[

Expression
⁢



⁢
41

]







The solution searching polynomial root/multiplicity operating circuit seeks n as in Expression 41 for each element a in Zp regardless of whether it is the root of Ψ(x) or not. In the case of n=0, it means that α is not a root.
FIG. 53(A) is a block diagram of the solution searching polynomial root/multiplicity operating circuit, and FIG. 53(B) is a timing chart of the clocks ck, cl and clk for use in control of the solution searching polynomial root/multiplicity operating circuit.
The solution searching polynomial root/multiplicity operating circuit scans the elements 1 - 16 in Zp at the clock ck to seek the number of stages of the Hasse differential at the clock cl, and the value of the Hasse differential polynomial in that number of stages at the clock clk. The clock ck is generated when the computed value of the Hasse differential polynomial becomes non-zero such that the process enters the cycle for the next element in Zp.
The solution searching polynomial root/multiplicity operating circuit includes, as shown in FIG. 53(A) , a “(j) i (j=1 to 16)” circuit block, a “Ro i(0-4)/j(0-4)” register unit, an “X Zp” circuit block, a “Rgstr” register < 1 >, a “5 bit AD mod 17” circuit block, a “Rgstr” register < 2 >, a “clock cl gen.” circuit block, a “Counter (0 to 4)” circuit block, and a “Li (1-16)” register unit.
The “(j) i (j=1 to 16)” circuit block selects an element α on α-times receipt of the clock ck, and provides the j-th power of α on (j−1)-times receipt of the clock clk.
The “Ro i(0-4)/j(0-4)” register unit is a register operative to provide a coefficient φ [i] j of the Hasse differential polynomial on receipt of the clocks cl i and clk j .
The “X Zp” circuit block multiplies the output a from the “(j) i (j=1 to 16)” circuit block by the output φ [i] j from the “Ro i(0-4)/j(0-4)” register unit, and provides α j φ [i] j .
Thus, when the clock clk is applied 5-times to the “(j) i (j=1 to 16)” circuit block, the “Ro i(0-4)/j(0-4)” register unit, and the “X Zp” circuit block, the value of the Hasse differential polynomial can be obtained. For the purpose of simplifying the control of the clocks ck, cl and clk, the sum of the terms of the value 0 not present in this computation is computed as well. Therefore, the total sum of the clocks clk originally required is almost halved.
The value [Ψ(x)] [i] of the differential polynomial is taken in the “Rgstr” register < 1 > as ‘0’ in the case of zero and ‘1’ in other cases.
The value held in the “Rgstr” register < 1 > is output at the timing of the clock clk 0 as the clock ck α (α=1-16). The clock ck α is held until it is reset by the clock clk 4 .
The “Rgstr” register < 1 > has an initial value of 0 and accordingly the clock ck l rises at the first clk 0 . The clock ck 2 and so forth rise at clk 0 in any cycle of clk in accordance with the computation result.
The “clock cl gen.” circuit block generates the clock cl i in sync with the clock clk 0 and resets it to the clock cl 0 at every rise of the clock ck α .
The “Counter (0 to 4)” circuit block is reset to 0 by the clock ck α , and counts up at every input of the clock cl and outputs the order of the clock cl minus 1. This output is stored in the “Li (1-16)” register unit.
The “Li (1-16)” register unit has the inputs, which are switched by the clock ck α , and thus can store the associated multiplicity in the α-th register.
An example of circuitry of the error quantity computing unit 107 is described below.
The following description is given to a converting circuit operative to derive a true error from the root and multiplicity of the Hasse differential polynomial, an α and [n] pair, to execute error correction. This converting circuit is herein referred to as the “code correcting circuit”.
The solution sought through the syndrome converting method, the virtual error n, the error-caused position t, and the true error e t have a relation therebetween as in Expression 42.









uS


〈
m
〉

+
0


=



∑

j
=
1

16

⁢



u
⁡

(
j
)



〈
m
〉


⁢

e
j



=
4


,




⁢

t
=

α

-
1



,




⁢

n
=



u
⁡

(
t
)



〈
m
〉


⁢

e
t







[

Expression
⁢



⁢
42

]







The numeral (j) <m> =(17-j −1 ) m3 (17-j) m2 (j) m1 is utilized in the conversion. This numeral is equal to S <m>+0 when compared with the relational equation S <m>+1 of the syndrome component shown in Expression 43 if Y=(0, 0, . . . , y j =1, . . . , 0, 0) is used as the syndrome component at l=0. This is used to give a representation of T <m>+0 to the syndrome component replaced by l for the t component of Y and 0 for others, which is used as a circuit input in a circuit shown in a block diagram of FIG. 54 .











S


〈
m
〉

+
1


=

⁢


∑

j
=
1

16

⁢



(

17
-

j

-
1



)


m
3


⁢


(

17
-
j

)


m
2


⁢


(
j
)


m
1


⁢


(
j
)

1

⁢

y
j









=

⁢


∑

j
=
1

16

⁢



(
j
)


〈
m
〉


⁢


(
j
)

1

⁢

y
j










[

Expression
⁢



⁢
43

]







The code correcting circuit includes a first part unit U 1 operative to seek the error-caused position t, a second part unit U 2 operative to seek the true error e t , and a third part unit U 3 operative to execute code correction in accordance with the true error e t .
The first part unit U 1 includes a “j −1 dec” circuit block < 1 ≦.
The “j −1 dec” circuit block < 1 > receives the root α, and provides the error-caused position t.
The second part unit U 2 includes 3 “X Zp” circuit blocks < 1 >-< 3 >, and a “j −1 dec” circuit block < 2 >.
The “X Zp” circuit block < 1 > receives the syndrome component S <m>+0 and 4 −1 (=13), and provides u −1 , that is, the inverse element of the numeral u found in the conversion.
The “j −1 dec” circuit block < 2 > receives T <m>+0 , and provides {(t) <m> } −1 , that is, the inverse element of (t) <m> .
The “X Zp” circuit block < 2 > receives the multiplicity n and the output u −1 from the “X Zp” circuit block < 1 >, and provides the product thereof nu −1 .
The “X Zp” circuit block < 3 > receives the output nu −1 from the “X Zp” circuit block < 2 > and the output {(t) <m> } −1 from the “j −1 dec” circuit block < 2 >, and provides the true error e t .
The third part unit U 3 includes 2“5 bit AD mod 17” circuit blocks < 1 > and < 2 >.
The “5 bit AD mod 17” circuit block < 1 > receives /e t and ‘1’, and provides −e t , that is, the complement of e t .
The “5 bit AD mod 17” circuit block < 1 > receives the code y t read out of the p-adic cells and the output −e t from the “5 bit AD mod 17” circuit block < 1 >, and provides the error-corrected correct code c t .
The code correcting circuit thus configured is possible to restore the correct code c t .
The following description is given to an operating circuit for computing a Lee metric w(E)=Σ|e j | (j=1-16) of an error code word E. Hereinafter, this operating circuit is referred to as the “Lee metric operating circuit”.
FIG. 55 is a block diagram of the Lee metric operating circuit.
The Lee metric operating circuit includes a “Ro (0-16)” register unit, a “5 bit LM mod 17” circuit block, a “5 bit AD mod 17” circuit block, and a “Rgstr” register.
The error code word E derived from the polynomial Ψ(x) is stored as the initial value in the “Ro (0-16)” register unit. From the “Ro (0-16)” register unit, the components e j of E are taken out in order by the clock ck j .
The “5 bit LM mod 17” circuit block computes the associated Lee metrics |e j | from the taken-out components e j . The “5 bit LM mod 17” circuit block provides the Lee metrics |e j | of the components, computed at every clock ck j , to the “5 bit AD mod 17” circuit block.
The “Rgstr” register and the “5 bit AD mod 17” circuit block form a loop, which is used to sum these |e j |. The output from the “5 bit AD mod 17” circuit block when the 16th clock ck rises provides w(E)=Σ|e j |.
If w(E)≦4, a series of error searching are finished, and E can be used to execute correction.
The error E sought through operational processing can be corrected after it is ensured that the associated Lee metric is equal to or below and it can be found that failed correction does not occur.
Therefore, the following description is given to an operational circuit element operative to compute a Lee metric of the element in Zp. Hereinafter, this operational circuit element is referred to as the “5 bit LM 17” circuit block.
As for an element a in Zp represented in 5-bit binary, the associated Lee metric Q=|a| can be expressed by Q=/PF 0 ×a+PF 0 ×(17−a). Here, PF 0 becomes ‘1’ if a≧9 and ‘0’ if a<9. Therefore, if a≧9, a derivation of the Lee metric of a just requires a subtraction of a from 17, that is, an addition of the complement of a to 17.
A relation between A and Q in the case of h=5, p=17 is as in Expression 44.

a=A 0 +A 1 2+ A 2 2 2 +A 3 2 3 +A 4 2 4

Q=|a |( Q=/PF 0× a+PF 0×(17 −a ))

Q=Q 0 +Q 1 2 +Q 2 2 2 +Q 3 2 3 +Q 4 2 4 [Expression 44]

FIG. 56 shows a circuit symbol of the “5 bit LM 17” circuit block, and FIG. 57 is a block diagram of the “5 bit LM 17” circuit block.
The “5 bit LM 17” circuit block receives a 5-bit binary A 0 -A 4 , and provides a 5-bit binary Q 0 -Q 4 .
The “5 bit LM 17” circuit block comprises a PF 0 generator unit U 1 , an XOR gate G 1 , 3 half adders HA 1 -HA 3 , and 2 full adders FA 1 , FA 2 .
The PF 0 generator unit U 1 includes, between the Vcc terminal and the Vss terminal, serially connected PMOS transistors QP 1 -QP 4 and NMOS transistors QN 1 , QN 2 . These transistors QP 1 , QP 2 , QP 3 , QP 4 , QN 1 and QN 2 are controlled by A 4 , A 2 , A 1 , A 0 , A 0 , and A 3 , respectively.
The PF 0 generator unit U 1 also includes a PMOS transistor QP 5 , 3 NMOS transistors QN 3 -QN 5 , and an inverter IV 1 .
The transistor QP 5 is connected between the source of the transistor QP 2 and the drain of the transistor QP 4 . The transistors QN 3 and QN 4 are connected between the source and drain of the transistor QN 1 . The transistor QN 5 is connected between the source of the transistor QN 1 and the drain of the transistor QN 2 (Vss terminal). These transistors QP 5 , QN 3 , QN 4 and QN 5 are controlled by A 3 , A 1 , A 2 and A 4 , respectively. The inverter IV 1 has an input connected to the sources of the transistors QN 1 , QN 3 , QN 4 and QN 5 . The output from the inverter IV 1 provides the carry PF 0 .
The XOR gate G 1 receives A j (j=0-4) and PF 0 , and provides B j .
The full adder FA 1 has inputs B 0 and PF 0 , a carry input PF 0 , an output Q 0 , and a carry output C 0 . The half adder HA 1 has inputs C 0 and B 1 , an output Q 1 , and a carry output C 1 . The half adder HA 2 has inputs C 1 and B 2 , an output Q 2 , and a carry output C 2 . The half adder HA 3 has inputs C 2 and B 3 , an output Q 3 , and a carry output C 3 . The full adder FA 2 has inputs B 4 and PF 0 , a carry input C 3 , and an output Q 4 .
In this specific example, if the input reaches 9 or above, the complement of a is added to 17. In the case of PF 0 =1, the complement of a is created at the XOR gate G 1 by inverting A j , that is, each bit representation of a, to yield B j , and adding 1 thereto.
As p=17 is 17=(10001) 2 , this is represented by PF 0 , and further PF 0 is used as 1, then these are added to B j as the sum of binaries.
The “5 bit LM 17” circuit block operates not in sync with the clocks and, on receipt of inputs, provides the computed Lee metric.
An example of circuitry of the decoder unit 109 is described below.
After error searching is finished and a Lee metric code C corrected with the error code E is obtained, it is required to restore it to the data code A in Zp. This operation corresponds to an inverse operation of C=AG with a generator matrix G though an inversion of a matrix requires a large-scale operation. Therefore, the elements of A are sequentially derived from the elements of C. The computation process is shown in Expression 45.










⁢



c
j

=


∑

i
=
0

10

⁢



(
j
)


j
+
1


⁢

a
i




⁢




⁢



{



∑

j
=
1

16

⁢



(
j
)


-
1


⁢

c
j



=



∑

j
=
1

16

⁢



(
j
)


-
1


⁢


∑

i
=
0

10

⁢



(
j
)


i
+
1


⁢

a
i





=



∑

i
=
0

10

⁢


∑

j
=
1

16

⁢



(
j
)

i

⁢

a
i




=



∑

j
=
1

16

⁢



(
j
)

0

⁢

a
0



=

16
⁢

a
0






}

⁢




⁢



∴

a
0


=


16

-
1


⁢


∑

j
=
1

16

⁢



(
j
)


-
1


⁢

c
j





⁢




⁢



⁢


c
j

(
0
)


=



c
j

-

ja
0


=


∑

i
=
0

10

⁢



(
j
)


j
+
1


⁢

a
i





⁢




⁢



{



∑

j
=
1

16

⁢



(

j
2

)


-
1


⁢

c
j

(
0
)




=



∑

j
=
1

16

⁢



(

j
2

)


-
1


⁢


∑

i
=
0

10

⁢



(
j
)


i
+
1


⁢

a
i





=



∑

i
=
1

10

⁢


∑

j
=
1

16

⁢



(
j
)

i

⁢

a
i




=



∑

j
=
1

16

⁢



(
j
)

0

⁢

a
1



=

16
⁢

a
1






}

⁢




⁢



∴

a
1


=


16

-
1


⁢


∑

j
=
1

16

⁢



(

j
2

)


-
1


⁢

c
j

(
0
)






⁢




⁢



⁢


c
j

(
1
)


=



c
j

(
0
)


-


j
2

⁢

a
1



=


∑

i
=
2

10

⁢



(
j
)


j
+
1


⁢

a
i





⁢




⁢



⁢
⋮





[

Expression
⁢



⁢
45

]







As shown in Expression 45, the relation c j =Σ(j) i+1 a i is deformed in turn to sequentially derive a 1 from a 0 , subsequently a 2 from a 1 , . . . , then a m . This is the principle of computation.
Both sides are multiplied by the inverse element of the power of j to yield the terms on all elements in Zp, which are then summed. At this time, the deformation is executed based on the fact that the sum of all elements in Zp becomes zero.
Expression 46 shows a relational equation of the components of C and the components of A.









c
j

(

-
1

)


=

c
j


⁢




⁢


c
j

(

m
-
1

)


=



c
j

(

m
-
2

)


-



(
j
)

m

⁢

a

m
-
1




=




∑

i
=
m

10

⁢



(
j
)


i
+
1


⁢

a
1



⁢




∴

a
m


=


16

-
1


⁢


∑

j
=
1

16

⁢



(

j

m
+
1


)


-
1


⁢

c
j

(

m
-
1

)












[

Expression
⁢



⁢
46

]







The following description is given to a specific operating circuit realized using the relational equation shown in Expression 46.
When seeking a m after a m−1 is obtained, parallel utilization of clocks is executed by computing the sum of j at a m in order while seeking c (m−1) j .
At the start, a circuit for converting the component of the Lee metric code C every time is described based on c (m−1) j =c (m−2) j −(j) m a m−1 shown in Expression 46. Hereinafter, this circuit is referred to as the “c (m−1) j ” circuit block.
FIG. 58 is a diagram showing a circuit symbol of the “c (m−1) j ” circuit block, and FIG. 59 is a block diagram of the “c (m−1) j ” circuit block.
The “c (m−1) j ” circuit block is a circuit operable in sync with the clocks cl j , /cl j . It receives (j) m , a m−1 and the code components c 1 -c 16 , and provides c (m−1) j .
The “c (m−1) j ” circuit block includes an “X Zp” circuit block, 2“5 bit AD mod 17” circuit blocks < 1 >, < 2 >, and a “R (1-16)” register unit.
The “X Zp” circuit block yields the product of (j) m and a m−1 , and provides it to the “5 bit AD mod 17” circuit block < 1 > via the inverter IV 1 .
The “5 bit AD mod 17” circuit block < 1 > seeks the complement of (j) m a m−1 output through the inverter IV 1 to yield −j m a m−1 , and provides it to the “5 bit AD mod 17” circuit block < 2 >.
The “5 bit AD mod 17” circuit block < 2 > yields the sum of −j m a m−1 output from the “5 bit AD mod 17” circuit block < 1 > and c j (=c (m−2) j ) output from the “R (1-16)” register unit in sync with the clock cl. This sum turns to c (m−1) j , that is, the output from the “c (m−1) j ” circuit block. The output c (m−1 ) j from the “5 bit AD mod 17” circuit block < 2 > is recorded in the j-th register in the “R (1-16)” register unit in sync with the fall of the clock cl.
The subsequent description is given to a circuit for creating a m based on a m =16 −1 Σ(j m+1 ) −1 c (m−1) j (j=1-16) shown in Expression 46. Hereinafter, this circuit is referred to as the “a m ” circuit block.
FIG. 60 is a diagram showing a circuit symbol of the “a m ” circuit block, and FIG. 61 is a block diagram of the “a m ” circuit block.
The “a m ” circuit block is operable in sync with the clock cl j . It receives (j) m+1 and c (m−1) j , and provides a m .
The “a m ” circuit block includes a “j −1 dec” circuit block, 2 “X Zp” circuit blocks < 1 >, < 2 >, a “5 bit AD mod 17” circuit block, and a “Rgstr” register.
The “j −1 dec” circuit block converts (j) m+1 to the inverse element thereof, (j) −m+1 , and provides it to the “X Zp” circuit block < 1 >.
The “X Zp” circuit block < 1 > operates the product of (j) −(m+1) fed from the “j −1 dec” circuit block and c j (=c (m−1) j ) output from the “c (m−1) j ” circuit block, and provides the product to the “5 bit AD mod 17” circuit block.
The products output from the “5 bit AD mod 17” circuit block are summed through a loop including the “Rgstr” register having an initial value of ‘0’ and the “5 bit AD mod 17” circuit block. The result is fed from the “5 bit AD mod 17” circuit block to the “X Zp” circuit block < 2 >.
The “X Zp” circuit block < 2 > operates the product of the sum output from the “5 bit AD mod 17” circuit block and 16 −1 =16 to obtain a m , that is, the output from the “a m ” circuit block.
Finally, a computing circuit is described, which includes the above-described “c (m−1) j ” circuit block and “a m ” circuit block to obtain the data code A. Hereinafter, this computing circuit is referred to as the “inverse transforming circuit”.
FIG. 62(A) is a block diagram of the inverse transforming circuit, and FIG. 62(B) is a timing chart of the clocks ck and cl for use in control of the inverse transforming circuit.
As shown in FIG. 62(B) , the clocks ck and cl have such a relation therebetween that the clock cl rises 16 times between the rise of a certain clock ck and the rise of the next clock ck.
The inverse transforming circuit comprises a first part circuit U 1 for converting the component of the Lee metric code C required for inverse transformation every time, and a second part circuit U 2 for seeking the elements of the data code A one by one.
The first part circuit U 1 includes a “(j i (j=1 to 16)” circuit block, a “Rgstr” register, and a “c (m−1) j ” circuit block.
The second part circuit U 2 includes a “(j) i (j=1 to 16)” circuit block, an “a m ” circuit block, and a “Li (0-10)” register unit.
Among those, the “(j) i (j=1 to 16)” circuit block is shared with the first part circuit U 1 . The “(j) i (j=1 to 16)” circuit block is a circuit operative to generate the (m+1)-th and m-th powers of the element j in Zp for use in the “a m ” circuit block and the “c (m−1) j ” circuit block. This circuit block applies m+1, the number of cycles of the clock ck and, m, a 1-cycle lower number than this number of cycles, as indexes, and provides (j) m+1 and (j) m .
The “(j) i (j=1 to 16)” circuit block provides the element in Zp itself to the “a m ” circuit block and ‘1’ to the “c (m−1) j ” circuit block in the 1st cycle of ck. The ‘1’ fed to the “c (m−1 ) j ” circuit block is originally not utilized in computation. Accordingly, it is required to put a thought in preventing the ‘1’ from exerting an influence on the operation result. Therefore, for the purpose of removing the influence of the ‘1’, the product operation in the first part circuit U 1 turns the other input to ‘0’ at the first cycle of the clock ck such that the result of the product operation becomes zero.
The “Rgstr” register in the first part circuit U 1 is given a setting of a m . The setting of a m is provided from the “Rgstr” register at the timing of the clock ck after the clock ck 1 . Namely, the output a m−1 from the “Rgstr” register is provided at the timing of the clock ck m .
In the first clock cycle ck 0 of the clock ck, the initial value of the output node in the “Rgstr” register is set at ‘0’ to exert no influence on the computation result as described above.
In sync with the clock ck m , the “c (m−1) j ” circuit block receives a m−1 and (j) m output from the “Rgstr” register and the “(j) i (j=1 to 16)” circuit block, respectively. The “c (m−1) j ” circuit block derives c (m−1) j , that is, the output from the first part circuit U 1 , from these inputs a m−1 and (j) m .
The initial value of the “c (m−1) j ” circuit block is the restored code data C, and the setting in the “Rgstr” register at the clock ck 0 provides c (−1) j =init C.
The “a m ” circuit block in the second part circuit U 2 obtains a m at every 16 cycles of the clock cl in accordance with the computing equation shown in Expression 46. The a m created at the “a m ” circuit block is stored in the m-th register in the “Li (0-10)” register unit at the clock ck m+1 that indicates the start timing of the cycles of the next 16 clocks cl.
After completion of all the clock cycles, the code data A is set and stored in the “Li (0-10)” register unit.
<Conclusion>
Thus, the first embodiment is described on the p-adic NAND flash memory using the syndrome converting method in error correction with the specific configurations exemplified.
The first embodiment makes it possible to ensure the reliability of data by a strong error correcting ability even if the level setting is insufficient in data write to p-adic cells and data read from p-adic cells.
Second Embodiment
The first embodiment describes the memory system that applies the syndrome converting method in data (code) processing in the “p-adci Zp world”. In this case, the circuitry used in the memory system can be simplified. An increase in the correctable error quantity, however, results in an increased number of searching repetitions for searching with no miss in error correction, which leads to an increase in processing time.
If the syndrome converting method is used in error correction as in the first embodiment, the number of repetitions of the computation required for error searching is, for example, in the case of p=17, equal to 16×16=256 times at the maximum if the correctable Lee metrics ε=3, and 16 times at the maximum if ε=2. On the other hand, if the correctable Lee metrics ε=4 as described in the first embodiment, it is required to repeat computation processing 16×16×16=4096 times at the maximum on error searching.
From the above point, the syndrome converting method is effective to an error correcting system mounted on a memory system with a smaller error quantity. In contrast, if the error-correctable quantity is larger (such as p=17, ε=4), the use of the conventional Euclidean iterative method rather than the syndrome converting method may reduce the processing time and the circuit scale depending on the case.
Therefore, the second embodiment describes a p-adic NAND flash memory using the Euclidean iterative method in error correction.
FIG. 63 is a block diagram of a memory system using the Euclidean iterative method in an error correction. This memory system is configured in the case of p=17 and the maximum error-correctable quantity of ε=4.
The p-adic memory system comprises a 17-adic converter unit 201 , an encoder unit 202 , a p-adic cell memory unit 203 , a syndrome generator unit 204 , a solution searching polynomial generator unit 205 , a Euclidean iteration processing unit 206 , a first Hasse differential polynomial generator unit 207 , a second Hasse differential polynomial generator unit 208 , a code restorer unit 209 , a decoder unit 210 , and a 2 5 -adic converter unit 211 .
Among those, the processes of processing in the 17-adic converter unit 201 , the encoder unit 202 , and the p-adic cell memory unit 203 are same as those in the 17-adic converter unit 101 , the encoder unit 102 , and the p-adic cell flash memory 103 in the p-adic memory system shown in FIG. 33 . Therefore, the following description is given to the processes of processing after the code Y is read out of the p-adic cell flash memory 103 .
The code C, Lee-metric-coded at the encoder unit 202 , is read out as the error-containing code Y from the p-adic cell flash memory 203 . The code Y is fed to the syndrome generator unit 204 .
The syndrome generator unit 204 uses the syndrome matrix H and each code word component of the code Y to compute the syndrome S in accordance with S=YH t . In the case of S=0, the code Y contains no error. Accordingly, the code Y is fed to the decoder unit 210 for final processing. On the other hand, if S≠0 and the first component S 0 of S is |S 0 |>5, the error in the code Y cannot be corrected surely. Accordingly, NG signal is provided and the error-containing code Y is directly fed to the decoder unit 210 for first processing. In other cases, the syndrome S is fed to the solution searching polynomial generator unit 205 .
The solution searching polynomial generator unit 205 derives a polynomial Ψ(x) from the syndrome S in accordance with the computation equation shown in Expression 47. This polynomial Ψ(x) is fed to the Euclidean iteration processing unit 206 .

S =( S 0 ,S 1 ,S 3 ,S 4 )→Ψ( x )

ψ 0 =1

ψ 1 =−S 1

ψ 2 =−(ψ 1 S 1 +ψ 0 S 2 )/2

ψ 3 =−(ψ 2 S 1 +ψ 1 S 2 +ψ 0 S 3 )/3

ψ 4 =−(ψ 3 S 1 +ψ 2 S 2 +ψ 1 S 3 +ψ 0 S 4 )/4 [Expression 47]

The Euclidean iteration processing unit 206 tries creation of λ=f n , ν=p n−1 through the Euclidean iterative method. If succeeded to create λ and ν, it provides these polynomials λ(x) and ν(x) to the first and second Hasse differential polynomial generator units 207 and 208 . On the other hand, if failed to create λ and ν, it provides NG signal, and feeds the error-containing code Y directly to the encoder unit 210 for first processing. The circuitry of the Euclidean iteration processing unit 206 is detailed later.
The first and second Hasse differential polynomial generator units 207 and 208 derive respective Hasse differential polynomials from the polynomials λ(x) and ν(x), and seek the roots r thereof and the multiplicities n of the roots. The first and second Hasse differential polynomial generator units 207 and 208 provide t=r −1 to the code restorer unit 210 in accordance with the established roots r and multiplicities n.
The code restorer unit 210 derives an error quantity e t from the positional coordinates of the error-caused code word and the multiplicities n. It restores the code C=(c 1 , c 2 , . . . , c 16 ) of the Lee metric code from c t =y t −e t .
Processing on and after the decoder unit 210 and the 2 5 -adic converter unit 211 is same as that in the decoder unit 109 and the 2 5 -adic converter unit 110 shown in FIG. 33 and accordingly omitted from the following description.
Thus, in the case of the memory system according to the present embodiment, the iteration and complication of processing can be all pushed in the Euclidean iterative method and the entire processing flow can be simplified.
The entire system configuration is roughly divided in 2: a system configuration surrounded by the dashed line shown with a in FIG. 63 ; and a system configuration surrounded by the chain line shown with b in FIG. 63 as can be considered.
The system surrounded by the dashed line includes a p-adic cell flash memory mounted thereon, which can serve as one memory system by itself. Therefore, in the case of this memory system, it is required to develop the p-adic cell flash memory also described in the first embodiment. In accordance therewith, it is also required to modify the level setting method applied to p-adic cells from that in the case of the memory system using the conventional NAND MLC.
The system surrounded by the chain line serves as a memory controller that uses the conventional NAND MLC directly as the memory device. Therefore, this system can be realized only by providing I/O operative to decode the elements in Zp so as to correspond to the levels of MLC at the time of data write. Thus, the conventional NAND MLC can be utilized to construct the memory system that uses the Lee metric code. The memory system that uses the memory controller, however, requires a longer time for mapping of MLC and Zp, and thus cannot provide a faster data processing system. It is still possible, though, to execute data management with increased reliability of data.
Mapping of MLC and Zp has different pages at every group of levels of MLC. Accordingly, unless pieces of data between different pages are managed collectively, the levels of 1 memory cell cannot be continuously associated as the elements in Zp. Therefore, it is required to provide registers corresponding to all pieces of page data for mapping of the elements in Zp and binary representations, and execute a series of data transfers between all pages in the register group and individual pages in the NAND MLC memory device. Therefore, the mapping requires a plurality of logic circuits. This mapping can be regarded as a large register-and-decoder set and accordingly the details are not described. The number of levels in NAND MLC is equal to a power of 2 and the number of elements in Zp is a prime. Therefore, available primes are below p=7 in the case of an 8-level cell, and below p=13 in the case of a 16-level cell. Thus, from the viewpoint of the efficiency of memory cells, it cannot be regarded as an optimal memory system.
Market demands determine which one of the systems should be constructed. In accordance with the description in the first embodiment and a second embodiment shown below, it is possible to realize either of the systems.
<Euclidean Method>
First, as the premise of the memory system using the Euclidean iterative method, general relational equations in the case of the use of the Euclidean method are described collectively where γ=ε+1.
The binary data of the code C recorded in p-adic cells includes h-bit code word symbols, a collection of (p−1) pieces, which may cause variations bit by bit when suffer various disturbances. Thus, the operation required to restore the code C from the code Y is decoding. Prior to decoding, the syndrome is sought at the start.
The syndrome S can be sought as elements S 0 , S 1 , . . . , S γ−1 shown in Expression 48 through an operation S=YH t using a syndrome matrix H.
∑ j = 1 p - 1 ⁢ ( j ) 1 ⁢ c j = ∑ i = 0 k ⁢ x i ⁢ ∑ j = 0 p - 1 ⁢ ( j ) 1 + i = 0 ⁢ ⁢
∴ S 1 = ∑ j = 1 p - 1 ⁢ ( j ) t ⁢ e j , S 0 = ∑ e j [ Expression ⁢ ⁢ 48 ]
Here, H t is a transpose of H. The generator matrix G and the syndrome matrix H are configured to satisfy GH t =0 (mod p). Accordingly, a representation of Y=C+E yields S=EH t . With E=(e 1 , e 2 , . . . , e p−1 ), a syndrome S 0 corresponds to the total sum of errors in the code word symbols as can be found. These syndromes S provide the only information on errors and, on the basis of these syndromes S, the correct code C is restored as follows.

Subsequently, the principle of decoding is described. Here, n(=p −1) error symbols are classified into 2 sets J + and J − as in Expression 49.

J + ={j ε(1,2 , . . . n ); e j <p/ 2}

J − ={j ε(1,2 , . . . n ); e j >p/ 2} [Expression 49]

Namely, it is classified into J + that is an arrangement of the positions j of the code symbols c j if the error quantity in the symbol is e j <p/2, and J − that is an arrangement of the positions j of the code symbols c j if the error quantity in the symbol is e j >p/2. Polynomials Λ(x), V(x) in the Galois field GF(p) are configured on the basis of these sets as in Expression 50.










Λ
⁡

(
x
)


=


∏

j
∈

J
+



⁢


(

1
-
jx

)


e
j




,


V
⁡

(
x
)


=


∏

j
∈

J
-



⁢


(

1
-
jx

)


p
-

e
j









[

Expression
⁢



⁢
50

]







Thus, the polynomial Λ(x) is a polynomial that has a reciprocal number of the position j of an error code word symbol in J + as a root and that has a Lee metric e j of that code word symbol as the multiplicity of the root. On the other hand, the polynomial V(x) is a polynomial that has a reciprocal number of the position j of an error code word symbol in J − as a root and that has a Lee metric p−e j of that code word symbol as the multiplicity of the root. Decoding is a process of finally configuring these polynomials only from the information on the syndrome S 1 to solve them, thereby obtaining information on errors. In a word, it is required to seek a relation between these polynomials Λ(x), V(x) and the syndrome S 1 .
Subsequently, as shown in Expression 51, when it is configured with a series polynomial having each syndrome S 1 on a coefficient of the corresponding degree, it is represented with a rational polynomial having the error quantity e j of the symbol, the position j and the value thereof.
S ⁡ ( x ) = ∑ l = 1 ∞ ⁢ S 1 ⁢ x 1 = ∑ j = 1 p - 1 ⁢ e j ⁢ ∑ l = 1 ∞ ⁢ ( jx ) 1 = ∑ j = 1 p - 1 ⁢ e j ⁢ jx 1 - jx [ Expression ⁢ ⁢ 51 ]
From Expression 51, a relational expression shown in Expression 52 can be established among the polynomials Λ(x), V(x) and the syndrome S(x).










(


Λ
⁡

(
x
)



V
⁡

(
x
)



)

⁢

S
⁡

(
x
)



=

-


x
⁡

(


Λ
⁡

(
x
)



V
⁡

(
x
)



)


′






[

Expression
⁢



⁢
52

]







Subsequently, the relational expression shown in Expression 52 is used to seek the polynomials Λ(x), V(x) from the syndrome S(x).
From the syndrome S(x), a polynomial Ψ(x) with a degree of γ−1 or lower shown in Expression 53 is sought.
Ψ ⁡ ( x ) ⁢ S ⁡ ( x ) ≡ - x ⁢ ⁢ Ψ ′ ⁡ ( x ) ⁢ ( mod ⁢ ⁢ x γ ) ⁢
⁢ Ψ ⁡ ( x ) = 1 + ∑ l = 1 ⁢ ψ 1 ⁢ x 1 ,
⁢ ψ j = - 1 j ⁢ ∑ i = 1 j ⁢ ψ j - i ⁢ S i [ Expression ⁢ ⁢ 53 ]
In an expansive expression of the polynomial Ψ(x), a coefficient ψ 3 can be sought from a comparison between the coefficients at the homogeneous degree on both sides of the expression shown in Expression 53 through an iterative method using the syndrome S i and an already-determined coefficient ψ j−1 . The coefficients ψ 0 to ψ γ−1 of the polynomial Ψ(x) are sought from the syndromes S 1 to S γ−1 . The results are shown in Expression 54.

ψ 0 = 1 ψ 1 = - ψ 0 ⁢ S 1 = - S 1 ψ 2 = - ( ψ 1 ⁢ S 1 + ψ 0 ⁢ S 2 ) / 2 ⋮ ψ γ - 1 = - ( ψ γ - 2 ⁢ S 1 + … + ψ 0 ⁢ S γ - 1 ) / ( γ - 1 ) [ Expression ⁢ ⁢ 54 ]
The polynomial Ψ(x) is a polynomial equivalent to Λ(x)/V(x) while the polynomials Λ(x), V(x) are given key conditions shown in Expression 55. Therefore, it can be sought through a Euclid iterative method applied to x γ and the polynomial Ψ(x) to eliminate constant multiples.

V ( x )Ψ( x )≡Λ( x )(mod x γ )

deg Λ( x )+ deg V ( x )<γ

Λ( x ) and V ( x ) are coprimes

deg Λ( x )− deg V ( x )≡ S 0 (mod p ) [Expression 55]

Therefore, if the polynomial Ψ(x) can be configured from the syndromes S 1 to S γ−1 , the syndrome S 0 can be used as the stop condition on the iterative method to seek the polynomials Λ(x), V(x). Namely, the polynomials Λ(x), V(x) sought from the set of (S 0 , Ψ(x)) through the iterative method can represent the position j and the error quantity e j of an error code word symbol.
<Error Correction through Euclidean Iterative Method>
Next, the Euclidean iterative method is described. The following description is given to an iterative method of seeking a congruence equation, v(x)Ψ(x)≡λ(x)(mod x γ ), with the stop condition, deg λ(x)−deg v(x)≡S 0 (mod p).
The Euclid iterative method is a method of sequentially seeking functions f 0 , f 1 , . . . , f n using divisions of polynomials. These quantities have relations shown in Expression 56.
f 0 = k 0 ⁢ f 1 + f 2 , f 1 = k 1 ⁢ f 2 + f 3 , … ⁢ , f n = k n ⁢ f n + 1 + f n + 2 ⁢
⁢ ⁢ p - 1 = 0 , p 0 = 1 , p n = k n - 1 ⁢ p n - 1 + p n - 2 ⁢
⁢ ⁢ q 0 = 0 , q 1 = 1 , q n = k n - 1 ⁢ q n - 1 + q n - 2 ⁢
⁢ p n ⁢ f n + p n - 1 ⁢ f n + 1 = ⁢ ( k n - 1 ⁢ p n - 1 + p n - 2 ) ⁢ f n + p n - 1 ⁢ f n + 1 = ⁢ p n - 1 ⁡ ( k n - 1 ⁢ f n + f n + 1 ) + p n - 2 ⁢ f n = ⁢ p n - 1 ⁢ f n - 1 + p n - 2 ⁢ f n ⁢ ⋮ = ⁢ p 0 ⁢ f 0 + p - 1 ⁢ f 1 = f 0 ⁢
⁢ q n ⁢ f n + q n - 1 ⁢ f n + 1 = ⁢ ( k n - 1 ⁢ q n - 1 + q n - 2 ) ⁢ f n + q n - 1 ⁢ f n + 1 = ⁢ q n - 1 ⁡ ( k n - 1 ⁢ f n + f n + 1 ) + q n - 2 ⁢ f n = ⁢ q n - 1 ⁢ f n - 1 + q n - 2 ⁢ f n ⁢ ⋮ = ⁢ q 1 ⁢ f 1 + q 0 ⁢ f 2 = f 1 ⁢
⁢ ⁢ f 0 = p n ⁢ f n + p n - 1 ⁢ f n + 1 , f 1 = q n ⁢ f n + q n - 1 ⁢ f n + 1 ⁢
⁢  p n p n - 1 q n q n - 1  = ⁢  k n - 1 ⁢ p n - 1 p n - 1 k n - 1 ⁢ q n - 1 q n - 1  = ⁢ -  p n - 1 p n - 2 q n - 1 q n - 2  -> p n ⁢ q n - 1 - p n - 1 ⁢ q n = ⁢ ( - 1 ) n - 1 ⁢ ( p 1 ⁢ q 0 - p 0 ⁢ q 1 ) = ⁢ ( - 1 ) n , ⁢
⁢ ⁢ f n = ( - 1 ) n ⁢ ( q n - 1 ⁢ f 0 - p n - 1 ⁢ f 1 ) ⁢
⁢ ∴ f n ≡ ( - 1 ) n + 1 ⁢ p n - 1 ⁢ Ψ ⁡ ( mod ⁢ ⁢ x γ ) , f 0 = x γ , f 1 = Ψ [ Expression ⁢ ⁢ 56 ]
Here, as shown in Expression 57, when p n or q n can be sequentially introduced from a quotient polynomial k n particularly obtained through the process of division, these polynomials can satisfy a simple relation. Accordingly, f n can be represented by f 0 , f 1 , p n−1 and q n−1 . Then, when f 0 =x γ , f 1 =Ψ(x) are established to create a congruence equation at x γ , the stop condition on iteration turns to deg f n −deg p n−1 ≡S 0 (mod p). With regard to n that satisfies the stop condition, if deg f n +deg p n−1 <γ, then λ(x)=f n , V(x)=p n−1 can be established.

As γ=ε+1, a computation for error 4 requires around 4 times of iterations, for example. With this regard, the use of the Euclidean iterative method increases the scale of the operating circuit though it can reduce the number of computations particularly lower than the syndrome converting method.
The following description is given to specific circuitry on points greatly different from the syndrome converting method.
<Circuitry of Syndrome Generator Unit>
Next, as an example of circuitry of the syndrome generator unit 204 , an operating circuit operative to seek component elements of the syndrome S in batch is described. Hereinafter, this operating circuit is referred to as the “syndrome component element generating circuit”.
The syndrome component element generating circuit is configured based on the equations shown in Expression 57.









S
0

=



∑

j
=
1


p
-
1


⁢

y
j


=


∑

j
=
1


p
-
1


⁢

e
j




⁢




⁢


S
1

=



∑

j
=
1


p
-
1


⁢



(
j
)

1

⁢

y
j



=


∑

j
=
1


p
-
1


⁢



(
j
)

1

⁢

e
j









[

Expression
⁢



⁢
57

]







FIG. 64(A) is a block diagram of the syndrome component element generating circuit, and FIG. 64(B) is a timing chart of the clocks ck i (i=0 to ε+1), cl j (j=1 to p−1) for use in control of the syndrome component element generating circuit.
The syndrome component element generating circuit includes, as shown in FIG. 64(A) , a “Ro (1 to p−1)” register unit, a “(j) i (j=1 to p−1)” circuit block, an “X Zp” circuit block, a “h bit AD mod p” circuit block, a “Rgstr” register, and a “Ri (0-ε)” register unit.
Data Y read out of the p-adic cell array is stored in the “Ro (1 to p−1)” register as an initial value. The “(j) i (j=1 to p−1)” circuit block generates (j) i . These “Ro (1 to p−1)” register and “(j) i (j=1 to p−1)” circuit block are synchronized with each other by the clock cl i and controlled such that (j) i is provided at the same time as the output of the component y j of Y. The “X Zp” circuit block yields the product thereof, (j) i y j , which is summed, in sync with the clock cl j (j=1 to p−1), through the loop including the “h bit AD mod p” circuit block and the “Rgstr” register, to create a syndrome component S i . The resultant S i is stored in the i-th register in the Ri (0-ε)” register at the clock ck i+1 . This process is treated at the clock ck i for i=0-ε to obtain all syndrome components, which are then stored in the “Ri (0-ε)” register unit.
An example of circuitry of the Euclidean iteration processing unit 206 is described below.
The first description is given to a circuit operative to derive k n in computation of f n =k n f n+1 +f n+2 . Hereinafter, this circuit is referred to as the “kn” circuit block.
The “kn” circuit block is configured based on the relational equations shown in Expression 58.

f n =k n f n+1 +f n+2

f n =a (n) 0 +a (n) 1 x+ . . . +a (n) j−1 x j−1 +a (n) j x j

k n =b (n) 0 +b (n) 1 x

b (n) 1 =a (n) j /b (n+1) j−1 ,b (n) 0 =( a (n) j−1 −b (n) 1 a (n+1) j−2 )/ a (n+1) j−1 [Expression 58]

The “kn” circuit block applies the relations between coefficients shown in Expression 58 to derive an unknown coefficient from the known coefficients. On the assumption that the polynomial of k n is at the 1st degree, and that the coefficient is turned to 0 in the process of computation if the coefficient at the highest degree becomes 0 as well, the process advances the procedure of computation sequentially. At this time, the inverse element of 0 is determined 0 to allow the relations between coefficients to establish always.
FIG. 65 is a diagram showing a circuit symbol of the “kn” circuit block. FIG. 66 is a block diagram of the “kn” circuit block.
The “kn” circuit block receives a (n) m−1 and a (n) m , and provides a (n+1) m−1 , a (n+1) m−2 , b (n) 1 , and b (n) 0 as shown in FIG. 65 .
The “kn” circuit block includes 3 “X Zp” circuit blocks < 1 >, < 2 >, < 3 >, 2 “h bit AD mod p” circuit blocks < 1 >, < 2 >, a “j −1 dec” circuit block, an XNOR gate G 1 , and an OR gate G 2 .
The “X Zp” circuit block < 1 > computes the product of a (n+1) m−2 and b (n) 1 . The result b (n) 1 a (n+1) m−2 is fed to the “h bit AD mod p” circuit block < 1 > via the inverter IV 1 .
The “h bit AD mod p” circuit block < 1 > receives the output from the inverter IV 1 and ‘1’, and obtains the complement of b (n) 1 a (n+1) m−2 .
The “h bit AD mod p” circuit block < 2 > receives the output from the “h bit AD mod p” circuit block < 1 > and a (n) m−1 , and provides the result, a (n) m−1 −b (n) 1 a (n+1) m−2 , to the “X Zp” circuit block < 2 >.
The “j −1 dec” circuit block receives a (n+1 ) m−1 , and provides the inverse element thereof, (a (n+1) m−1 ) −1 , to the “X Zp” circuit blocks < 2 > and < 3 >.
The “X Zp” circuit block < 2 > computes the product of the output, a (n) m−1 −b (n) 1 a (n+1) m−2 , from the “h bit AD mod p” circuit block < 2 > and the output, (a (n+1) m−1 ) −1 , from the “j −1 dec” circuit block, to obtain the result b′ (n) 0 .
The “X Zp” circuit block < 3 > computes the product of a (n) m and the output, (a (n+1) m−1 ) −1 , from the “j −1 dec” circuit block, to obtain the result b (n) 1 , that is, the output from the “kn” circuit block.
The XNOR gate G 1 receives the output, b′ (n) 0 , from the “X Zp” circuit block < 2 > and the output, b (n)1 0 , from the “X Zp” circuit block < 3 >. The OR gate G 2 receives the output from the “X Zp” circuit block < 3 > and b′ (n) 0 . In this case, the output from the OR gate G 2 turns to the output, b (n) 0 , from the “kn” circuit block.
The following description is given to a circuit operative to derive f n+2 in computation of f n =k n f n+1 +f n+2 . Hereinafter, this circuit is referred to as the “fn” circuit block.
The “fn” circuit block is configured based on the relational equations shown in Expression 59.

f n =k n f n+1 +f n+2

f n+2 =f n −k n f n+1 ,k n =b (n) 0 +b (n) 1 x

f n+2 =f n −( b (n) 0 f n+1 +b (n) 1 xf n+1 )

a (n+2) m =a (n) m −( b (n) 0 a (n+1) m +b (n) 1 a (n+1) n−1 ) [Expression 59]

The “fn” circuit block applies the relations between coefficients shown in Expression 59 to derive an unknown coefficient from the known coefficients. It utilizes the already-obtained coefficients of the polynomial of k n .
FIG. 67 is a diagram showing a circuit symbol of the “fn” circuit block. FIG. 68 is a block diagram of the “fn” circuit block.
The “fn” circuit block receives a (n+1) m−1 , a (n+1) m , a (n) m , b (n) 1 and b (n) 0 , and provides a (n+2) m as shown in FIG. 67 .
The “fn” circuit block includes 2 “X Zp” circuit blocks < 1 >, < 2 >, and 3 “h bit AD mod p” circuit blocks < 1 >, < 2 > and < 3 >.
The “X Zp” circuit block < 1 > computes the product of a (n+1) m−1 and b (n) 1 , and provides the result, b (n) 1 a (n+1) m−1 , to the “h bit AD mod p” circuit block < 1 >.
The “X Zp” circuit block < 2 > computes the product of a (n+1) m and b (n) 0 , and provides the result, b (n) 0 a (n+1) m , t 0 the “h bit AD mod p” circuit block < 1 >.
The “h bit AD mod p” circuit block < 1 > receives the output, b (n) 1 a (n+1) m−1 , from the X Zp” circuit block < 1 > and the output, b (n) 0 a (n+1) m , from the X Zp” circuit block < 2 >. The output from the “h bit AD mod p” circuit block < 1 > is fed to the “h bit AD mod p” circuit block < 2 > via the inverter IV 1 .
The “h bit AD mod p” circuit block < 2 > receives the output from the inverter IV 1 and ‘1’, and obtains the complement of (b (n) 0 a (n+1 ) m +b (n) 1 a (n+1) m−1 ).
The “h bit AD mod p” circuit block < 3 > receives a (n) m and the output from the “h bit AD mod p” circuit block < 2 >, and obtains a (n+2) m , that is, the output from this “fn” circuit block.
The following description is given to a circuit operative to derive p n−2 in computation of p n =k n−1 p n−1 +p n−2 . Hereinafter, this circuit is referred to as the “pn” circuit block.
The “pn” circuit block is configured based on the relational equations shown in Expression 60.

p n =k n−1 p n−1 +p n−2

p n =a (n) 0 +a (n) 1 x+ . . . +a (0) j−1 x j−1 +a (n) j x j

k n =b (n) 0 +b (n) 1 x

p n+1 =( b (n) 0 p n +b (n) 1 xp n )+ p n−1

a (n+1) m =( b (n) 0 a (n) m +b (n) 1 a (n) m−1 )+ a (n−1) m [Expression 60]

The “pn” circuit block applies the relations between coefficients shown in Expression 60 to derive an unknown coefficient from the known coefficients. It utilizes the already-obtained coefficients of the polynomial of k n .
FIG. 69 is a diagram showing a circuit symbol of the “pn” circuit block. FIG. 70 is a block diagram of the “pn” circuit block.
The “pn” circuit block receives a (n) m−1 , a (n) m and a (n−1 ) m , and provides a (n+1) m as shown in FIG. 69 .
The “pn” circuit block includes 2 “X Zp” circuit blocks < 1 >, < 2 >, and 2 “h bit AD mod p” circuit blocks < 1 > and < 2 > as shown in FIG. 70 .
The “X Zp” circuit block < 1 > computes the product of a (n) m−1 and b (n) 1 , and provides the result, b (n) 1 a (n) m−1 , to the “h bit AD mod p” circuit block < 1 >.
The “X Zp” circuit block < 2 > computes the product of a (n) m and b (n) 0 , and provides the result, b (n) 0 a (n) m , to the “h bit AD mod p” circuit block < 1 >.
The “h bit AD mod p” circuit block < 1 > receives the output, b (n) 1 a (n) m−1 , from the X Zp” circuit block < 1 > and the output, b (n) 0 a (n) m , from the X Zp” circuit block < 2 >, and provides b (n) 0 a (n) m +b (n) 1 a (n) m−1 to the “h bit AD mod p” circuit block < 1 >.
The “h bit AD mod p” circuit block < 2 > receives a (n−1) m and the output, b (n) 0 a (n) m +b (n) 1 a (n) m−1 , from the “h bit AD mod p” circuit block < 1 >, and obtains a (n+1) m , that is, the output from the “pn” circuit block.
Subsequently, a circuit for computing f n =k n f n+1 +f n+2 is described. Hereinafter, this circuit is referred to as the “f n =k n f n+1 +f n+2 ” circuit block.
FIG. 71 is a diagram showing a circuit symbol of the “f n =k n f n+1 +f n+2 ” circuit block. FIG. 72 is a block diagram of the “f n =k n f n+1 +f n+2 ” circuit block.
The “f n =k n f n+1 +f n+2 ” circuit block receives a 0 -a γ , the coefficients of f n ; and b 0 -b γ , the coefficients of f n+1 , and provides c 0 -c γ , the coefficients of f n+2 ; and β 0 -β γ , the coefficients of k n as shown in FIG. 71 .
As computations are started with substitutions of f 0 =x γ , f 1 =Ψ(x), the maximum degree of f n is γ, and the maximum degree of f n+2 is also γ because k n may be 1. Therefore, the “f n =k n f n+1 +f n+2 ” circuit block includes (γ+1) “kn” circuit blocks < 1 >-<γ+1>, and (γ+1) “fn” circuit blocks < 1 >-<γ+1> as shown in FIG. 72 .
The “kn” circuit block < 1 > associates ‘0’, a 0 , b 0 and a 1 with a (n+1) m−2 , a (n) m−1 , a (n+1) m−1 and a (n) m , and associates β (1) 0 and β (1) 1 with b (n) 0 and b (n) 1 , respectively.
The “kn” circuit block < 2 > associates b 0 , a 1 , b 1 and a 2 with a (n+1) m−2 , a (n) m−1 , a (n+1) m−1 and a (n) m , and associates β (1) 0 and β (1) 1 with b (n) 0 and b (n) 1 , respectively.
The subsequent “kn” circuit blocks < 3 >-<γ+1> have the similar inputs/outputs to the “kn” circuit blocks < 1 > and < 2 >. The outputs, β (m) 0 and β (m) 1 (m=0−γ), from the “kn” circuit blocks < 1 >-<γ+1> are provided as β 0 and β 1 from the “f n =k n f n+1 +f n+2 ” circuit block via the control switches SW controlled by deg(b 1 , b 2 , . . . , b γ )=m. The β 0 and β 1 can be utilized also as the inputs to the “fn” circuit blocks < 1 >-<γ+1>. Here, deg( ) represents the output from the degree decision circuit associated with f n+1 .
The “fn” circuit block < 1 > receives ‘0’, b 0 , a 0 , β 0 and β 1 as a (n+1) m−1 , a (n+1) m , a (n) m , b (n) 0 and b (n) 1 , and provides c 0 as a (n+2) m .
The “fn” circuit block < 2 > receives b 0 , b 1 , a 1 , β 0 and β 1 as a (n+1) m−1, a (n+1) m , a (n) m , b (n) 0 and b (n) 1 , and provides c 1 as a (n+2) m .
The subsequent “fn” circuit blocks < 3 >-<γ+1> have the similar inputs/outputs to the “fn” circuit blocks < 1 > and < 2 >.
The outputs from the “fn” circuit blocks < 1 >-<γ+1> turn to c 0 -c γ , that is, the output from the “f n =k n f n+1 +f n+2 ” circuit block.
Subsequently, a circuit for computing p n+1 =k n p n +p n−1 is described. Hereinafter, this circuit is referred to as the “p n+1 =k n p n +p n−1 ” circuit block.
FIG. 73 is a diagram showing a circuit symbol of the “p n+1 =k n p n +p n−1 ” circuit block. FIG. 74 is a block diagram of the “p n+1 =k n p n +p n−1 ” circuit block.
The “p n+1 =k n p n +p n−1 ” circuit block receives β 0 , β 1 , the coefficients of k n ; a 0 -a γ−1 , the coefficients of p n−1 ; and b 0 -b γy−1 , the coefficients of p n , and provides c 0 -c γy−1 , the coefficients of p n+1 as shown in FIG. 73 .
As computations are started with substitutions of p −1 =0, p 0 =1, the maximum degree of p n+1 is γ−1, for the purpose of utilizing p n+1 mod x γ . Therefore, the “p n+1 =k n p n +p n−1 ” circuit block includes γ “kn” circuit blocks < 1 >-<γ>.
The “pn” circuit block < 1 > receives ‘0’, b 0 , a 0 , β 0 and β 1 as a (n) m−1 , a (n) m , a (n−1) m , b (n) 0 and b (n) 1, and provides c 0 as a (n+1) m , respectively.
The “pn” circuit block < 2 > receives b 0 , b 1 , a 1 , β 0 and β 1 as a (n) m−1 , a (n) m , a (n−1) m , b (n) 0 and b (n) 1, and provides c 1 as a (n+1) m , respectively.
The subsequent “pn” circuit blocks < 3 >-<γ> have the similar inputs/outputs to the “pn” circuit blocks < 1 > and < 2 >.
The outputs from the “pn” circuit blocks < 1 >-<γ> are provided as c 0 -c γ−1 , that is, the output from the “p n+1 =k n p n +p n−1 ” circuit block.
Subsequently, a description is given to computing circuits operative to derive f n and p n−1 through iterative computations from 0 to n.
FIG. 75 shows the computing circuit operative to derive f n , and FIG. 76 shows the computing circuit operative to derive p n−1 .
The computing circuit operative to derive f n includes 3 “h(γ+1)” register units < 1 >-< 3 >, as shown in FIG. 75 , in addition to the “f n =k n f n+1 +f n+2 ” circuit block. The “h(γ+1)” register units < 1 >-< 3 > include (γ+1) pieces of h-bit latches each. The “h(γ+1)” register units < 1 >-< 3 > are given a setting of ‘0’ if there is no corresponding input. The computation of f n is advanced at the “f n =k n f n+1 +f n+2 ” circuit block and 3 “h(γ+1)” register units < 1 >-< 3 > provided in the periphery thereof, which circularly transfer data.
The computing circuit operative to derive p n+1 includes “hγ” register units < 1 >-< 3 >, as shown in FIG. 76 , in addition to the “p n+1 =k n p n +p n−1 ” circuit block. The “hγ” register units < 1 >-< 3 > include γ pieces of h-bit latches each. The “hγ” register units < 1 >-< 3 > are given a setting of ‘0’ if there is no corresponding input. The computation of p n+1 is advanced at the “p n+1 =k n p n +p n−1 ” circuit block and 3 “hγ” register units < 1 >-< 3 > provided in the periphery thereof, which circularly transfer data.
The computations of f n and p n−1 advance at every cycle of the clock cl and the number of cycles of the clock cl counted from 0 corresponds to n of the Euclidean iteration. Finally, the “h(γ+1)” register unit < 1 > holds f n , and the “hγ” register unit < 1 > holds p n−1 .
In the first clock cycle cl 0 , the “h(γ+1)” register units < 1 >-< 3 > and the “hγ” register units < 1 >-< 3 > are given settings of initial values as shown in FIGS. 75 and 76 , respectively.
In the computing circuit operative to derive f n , the coefficient of f 0 =x γ is set in the “h(γ+1)” register unit < 1 > and the coefficient of f 1 =Ψ(x) in the “h(γ+1)” register unit < 3 >. In the computing circuit operative to derive p n−1 , p −1 =‘0’ is set in the “hγ” register unit < 1 > and p −1 =‘1’ in the “hγ” register unit < 3 >. Thereafter, as the clock cycle advances, f n and p n−1 are set in the corresponding register units at the start of the cl n cycle.
The “h(γ+1)” register unit < 1 > and the “hγ” register unit < 1 > are prevented from receiving the inputs by a signal /ISTOP. Accordingly, data in the “h(γ+1)” register unit < 1 > and the “hγ” register unit < 1 > can be determined at that moment. The signal /ISTOP is a signal that is activated if the later-described stop condition on the Euclidean iterative method is satisfied.
Thus, the “h(γ+ 1 )” register unit < 1 > and the “hγ” register unit < 1 > can obtain the desired resultant coefficients of the polynomials therein.
These coefficients can be fed to the first Hasse differential polynomial generator unit 207 and the second Hasse differential polynomial generator unit 208 to seek the root and the multiplicity of the Hasse differential polynomial.
For the purpose of seeking the signal /ISTOP shown in FIGS. 75 and 76 , that is, the stop condition on the Euclidean iterative method, it is required to determine the degree of the computed polynomial. Therefore, the following description is given to a circuit operative to represent the degree in binary based on the obtained coefficients, a j (j=0−γ), of f n or p n−1 . Hereinafter, this circuit is referred to as the “DEG” circuit block.
FIG. 77 is a diagram showing a circuit symbol of the “DEG” circuit block. FIG. 78 is a block diagram of the “DEG” circuit block.
The “DEG” circuit block receives a 1 -a γ , and provides that is, a binary representation of the degree as shown in FIG. 77 .
The “DEG” circuit block includes “h bit reg” registers < 1 >-<γ>, OR gates G 0 < 1 >-<γ>, G 1 < 1 >-<γ>, and an “A to deg DEC.” circuit block as shown in FIG. 78 .
The “h bit” registers each hold h-bit binary data indicative of the coefficients, a 1 -a γ , of the γ-th degree polynomial. The h-bit binary data indicative of the coefficients a 1 -aγ are fed to the OR gates G 0 < 1 >-<γ>.
The OR gate G 0 <n> (n=1-γ) receives h-bit binary data indicative of a n . The OR gate G 0 < 1 > provides ‘0’ if a n =0 and ‘1’ if a n ≠0. In a word, the OR gate G 0 <n> determines whether a n is equal to 0 or other than 0.
The OR gate G 1 <m> (m=1 to γ−1) receives the outputs from the OR gates G 0 <m>-<γ>. The outputs from the OR gates G 1 < 1 >-<γ−1> turn to A 1 -A γ−1 , respectively. In addition, the output from the OR gate G 0 <γ> directly turns to A γ . These A 1 -A γ are fed to the “A to deg DEC.” circuit block.
The “A to deg DEC.” circuit block is a decoder circuit capable of realizing the associated relations between A 1 -A γ and binary representations of the degrees as shown with T 1 in FIG. 78 . The total sum of ‘1’s in A j (j=1−γ) corresponds to a binary representation of the degree.
The “A to deg DEC.” circuit block derives b 0 -b h−1 , that is, the output from the “DEC” circuit block, from A 1 -A γ based on the association table shown with T 1 in FIG. 78 . The degree γ is equal to or lower than p and accordingly can be represented by h bits.
The final description is given to a circuit operative to decide if the key condition on the Lee metric code is satisfied to stop the iterations, and if the error correctable condition is satisfied, based on fn and pn−1 obtained through the Euclidean iterative method.
FIG. 79 is a block diagram of a circuit operative to decide the stop condition on the Euclidean iterative method, that is, to create the signal /ISTOP.
This circuit includes 2 “DEG” circuit blocks < 1 >, < 2 >, 2 “h bit AD mod p” circuit blocks < 1 >, < 2 >, and a part circuit U 1 composed of plural logic gates.
The “DEG” circuit block < 1 > receives f n as a 1 -a γ , and provides deg f n , that is, a binary representation of f n as b 0 -b n−1 . This deg f n is fed to the “h bit AD mod p” circuit block < 2 >.
The “DEG” circuit block < 2 > receives p n−1 as a 1 -a γ , and provides deg p n−1 , that is, a binary representation of p n−1 as b 0 -b h−1 . This deg p n−1 is fed to the “h bit AD mod p” circuit block < 1 > via the inverter IV 1 .
The “h bit AD mod p” circuit block < 1 > derives the complement of deg p n−1 from the input, deg p n−1 , fed via the inverter IV 1 and ‘1’. The complement of deg p n−1 is fed to the “h bit AD mod p” circuit block < 2 >.
The stop condition on the Euclidean iterative method is deg f n −deg p n−1 ≡S 0 (mod p). Therefore, the “h bit AD mod p” circuit block < 2 > receives deg f n and the complement of deg p n−1 to obtain deg f n −deg p n−1 as a numeral in Zp. This result is fed to the part circuit U 1 for comparison with S 0 at every bit of the binary representation.
For the purpose of comparing deg f n −deg p n−1 with S 0 at every bit, the part circuit U 1 seeks an exclusive logical sum at every bit. If all bits (deg f n −deg p n−1 ) j (j=0 to h−1) match (S 0 ) j , the part circuit U 1 provides ‘0’ as the signal /ISTOP. In a word, the signal /ISTOP is (deg f n −deg p n−1 ) 0 (+) (S 0 ) 0 □ . . . □(deg f n −deg p n−1 ) m (+) (S 0 ) m □ . . . □(deg f n −deg p n−1 ) h−1 (+) (S 0 ) h−1 . Thus, the part circuit U 1 can realize if deg f n −deg p n−1 matches S 0 or not.
FIG. 80 is a block diagram of a circuit for deciding the success condition on the Euclidean iterative method.
This circuit includes a NAND gate G 1 , a “h bit AD mod p” circuit block, a “h bit γ≦” circuit block later-described, and an NOR gate G 2 .
The NAND gate G 1 is arranged to provide for the case where the Euclidean iterative method fails to satisfy the stop condition to stop. If the degree of f n is equal to 1, the degree of f n+1 is equal to 0, and the signal /ISTOPn in reverse logic of the signal /ISTOP is at 1, that is, under the condition of (deg f n =1)□(deg f n+1 =0)□(/ISTOPn=1), the NAND gate G 1 provides ‘1’ as a signal Ifail.
It is determined based on deg f n +deg p n−1 <γ if the error is correctable when the Euclidean iterative method stops.
Therefore, the “h bit AD mod p” circuit block is given deg f n and deg p n−1 to derive the sum thereof, deg f n +deg p n−1 . This sum, deg f n +deg p n−1 , is fed to the “h bit γ≦” circuit block.
The “h bit γ≦” circuit block is a circuit operative to determine if the input is equal to or higher than γ or not. The “h bit γ≦” circuit block provides ‘1’ as a signal gtγ if the input, deg f n +deg p n−1 , supplied from the “h bit AD mod p” circuit block is equal to or higher than γ.
The details of the “h bit γ≦” circuit block are omitted from the following description though they can be configured similar to the PF 0 generator unit U 1 in the “h bit AD mod p” circuit block shown in FIG. 40 .
The OR gate G 2 receives the output, Ifail, from the NAND gate G 1 and the output, gtγ, from the “h bit γ≦” circuit block and, if Ifail□gtγ, it provides NG signal indicative of the impossibility of error correction through the Euclidean iterative method.
<Conclusion>
Thus, the second embodiment is described on the p-adic NAND flash memory using the Euclidean iterative method in error correction with the specific configurations exemplified.
The second embodiment makes it possible to ensure the reliability of data by a strong error correcting ability even if the level setting is insufficient in data write to p-adic cells and data read from p-adic cells. It is possible to realize faster error correction processing than the first embodiment.
[Others]
While certain embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the inventions. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms: furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the spirit of the inventions. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the inventions.