# Patent

## Title
Memory system

## Abstract

A memory system according to the embodiment comprises a cell array of plural cells having three or more settable physical quantity levels and operative to store a code composed of symbols expressed by elements in a finite field Zp (p is a prime), wherein a set of two cells is defined as a pair cell and a combination of physical quantity levels of the two cells contained in the pair cell is defined as a pair cell level, wherein the pair cell uses a pair cell level of plural pair cell levels, which maximizes or minimizes a physical quantity level of one cell contained in the pair cell, to assign elements in the Zp to the pair cell levels, thereby storing symbols of the code.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is a divisional of U.S. application Ser. No. 14/203,889, filed Mar. 11, 2014, and is based upon and claims the benefit of priority from prior U.S. Provisional Application No. 61/933,107, filed on Jan. 29, 2014, the entire contents of each of which are incorporated herein by reference.


BACKGROUND
Field
The embodiment of the present invention relates to a memory system.
Description of the Related Art
As memory systems capable of storing mass data for use, variable resistance memories including cell arrays easily formable in three dimensions, such as a ReRAM (Resistance RAM) and an ion memory, have received attention.
In these memory systems, as one of methods for raising the density of information storage, there is a method of fine pattering a cell array. The use of this method, however, requires higher technologies and causes a problem about cost rises. Another method includes multi-valuing a cell. This method is an effective method because it causes almost no cost rise. In the case of this method, however, physical quantity levels of a cell become unstable. Therefore, unprecedented different ideas are required for writing data to a cell, storing data by a cell and reading data from a cell.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram illustrative of an outline of a pair cell in a memory system according to the embodiment.
FIG. 2 is a diagram illustrative of assignments of information values to states of the pair cell in the memory system according to the embodiment.
FIG. 3 is a diagram illustrative of assignments of information values to states of the pair cell in the memory system according to the embodiment.
FIG. 4 is a diagram illustrative of assignments of information values to states of the pair cell in the memory system according to the embodiment.
FIG. 5 is a diagram illustrative of assignments of information values to states of the pair cell in the memory system according to the embodiment.
FIG. 6 is a diagram showing state variations of a cell in the memory system according to the embodiment.
FIG. 7 is a diagram showing a relation between relative inter-ionic distances and activation energy in the cell in the memory system according to the embodiment.
FIG. 8 is a diagram showing state variations of a cell in the memory system according to the embodiment.
FIG. 9 is a diagram showing a relation between relative inter-CNT distances and activation energy in the cell in the memory system according to the embodiment.
FIG. 10 is a graph showing relations among phonon energy within a NT stack, resistances of the NT stack, and potentials of the electric field within the NT stack in the memory system according to the embodiment.
FIG. 11 is a graph showing a relation between phonon energy and voltages across electrodes of a NT stack cell when the NT stack resistance is made higher in the memory system according to the embodiment.
FIG. 12 is a graph showing a relation between phonon energy and cell current in the NT stack when the NT stack resistance is made lower in the memory system according to the embodiment.
FIG. 13 is a diagram showing a bias state of a cell array at the initial step in a write sequence in the memory system according to the embodiment.
FIG. 14 is a diagram showing a bias state of a cell array at the all ‘0’ write step in the write sequence in the memory system according to the embodiment.
FIG. 15 is a diagram showing a bias state of a cell array at the ‘L’ write step in the write sequence in the memory system according to the embodiment.
FIG. 16 is a diagram showing potential variations on bit lines at the time of the write sequence in the memory system according to the embodiment.
FIG. 17 is a diagram showing potential variations on word lines at the time of the write sequence in the memory system according to the embodiment.
FIG. 18 is a schematic diagram of a configuration of reference bit lines in the memory system according to the embodiment.
FIG. 19 is a circuit diagram of a current source for reference bit lines in the memory system according to the embodiment.
FIG. 20 is a diagram illustrative of relations among comparison currents at access operations in the memory system according to the embodiment.
FIG. 21 is a circuit diagram of a sense amp in the memory system according to the embodiment.
FIG. 22 is a diagram of operating waveforms in the sense amp in the memory system according to the embodiment.
FIG. 23 is a circuit diagram showing a circuit on the reference input side of the sense amp in the memory system according to the embodiment.
FIG. 24 is a diagram showing a configuration of a current sensing system in the memory system according to the embodiment.
FIG. 25 is a diagram showing a layout of arrangement regions of vertical lines in a cell array seen from the stacking direction in the memory system according to the embodiment.
FIG. 26 is a cross-sectional view of a transistor in the stacking direction in the memory system according to the embodiment.
FIG. 27 is a diagram showing a layout of the cell array in the memory system according to the embodiment.
FIG. 28 is a diagram showing a layout of the cell array in the memory system according to the embodiment.
FIG. 29 is a diagram showing a layout of the cell array in the memory system according to the embodiment.
FIG. 30 is an equivalent circuit diagram of a VBL-structured cell array in the memory system according to the embodiment.
FIG. 31 is a functional block diagram of the memory system according to the embodiment.
FIG. 32 is a flow chart of data processing in the memory system according to the embodiment.
FIG. 33 is a flow chart of decoding in the memory system according to the embodiment.
FIG. 34 is a block diagram of ECC processing in the memory system according to the embodiment.
FIG. 35 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 36 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 37 is a diagram showing a block symbol of a circuit block in the memory system according to the embodiment.
FIG. 38 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 39 is a power correspondence table of elements in Zp in the memory system according to the embodiment.
FIG. 40 is a power correspondence table of elements in Zp in the memory system according to the embodiment.
FIG. 41 is a power correspondence table of elements in Zp in the memory system according to the embodiment.
FIG. 42 is a power correspondence table of elements in Zp in the memory system according to the embodiment.
FIG. 43 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 44 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 45 is a table showing divergences and syndromes of a searching equation of Zp in the memory system according to the embodiment.
FIG. 46 is a correspondence table of elements in Zp, and inverse elements, squares and square roots thereof in the memory system according to the embodiment.
FIG. 47 is a correspondence table of elements in Zp, and inverse elements, squares and square roots thereof in the memory system according to the embodiment.
FIG. 48 is a correspondence table of elements in Zp, and inverse elements, squares and square roots thereof in the memory system according to the embodiment.
FIG. 49 is a correspondence table of elements in Zp, and inverse elements, squares and square roots thereof in the memory system according to the embodiment.
FIG. 50 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 51 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 52 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 53 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 54 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 55 is a circuit diagram of a computation block in the memory system according to the embodiment.
FIG. 56 is a circuit diagram of a computation block in the memory system according to the embodiment.



DETAILED DESCRIPTION
A memory system according to the embodiment comprises a cell array of plural cells having three or more settable physical quantity levels and operative to store a code composed of symbols expressed by elements in a finite field Zp (p is a prime), wherein a set of two cells is defined as a pair cell and a combination of physical quantity levels of the two cells contained in the pair cell is defined as a pair cell level, wherein the pair cell uses a pair cell level of plural pair cell levels, which maximizes or minimizes a physical quantity level of one cell contained in the pair cell, to assign elements in the Zp to the pair cell levels, thereby storing symbols of the code.
A memory system according to the embodiment is described below with reference to the drawings.
In multi-valuing a cell in a resistance variable memory, a problem arises because it is difficult to definitely write multi-values to a cell. This is because physical quantity levels or resistance values of the cell and voltage/current conditions are determined by indefinite statistical relations. In the case of a phase change memory of variable resistance memories, as a resistance value drift is large, a relative code is used in data reading for multi-valuing. In the case of a cell, in which the presence/absence of a metal filament is assigned to a storage state, the filament is unstable. Accordingly, the filament or retention is stabilized, thereby stabilizing the resistance value for multi-valuing. In the case of a memory, in which nanotubes (hereinafter also referred to as “NT”s) such as carbon nanotubes (hereinafter also referred to as “CNT”s) are stacked in a cell (hereinafter also referred to as a “NT stack cell”), the set resistance is maintained stable by the work of inter-molecular forces. Even in the case of the NT stack memory, however, it is difficult to set a definite resistance value as described above. Therefore, making practical a resistance variable memory including multi-valued cells requires studies of methods for ensuring the reliability of data. Hereinafter, the stacked NTs may also be referred to as a “NT stack”, and a memory including NT stack cells as an “NT stack memory”.
Then, in the embodiment, the NT stack memory is used as an example to handle methods of multi-value writing, which are effective in the overall memories including cells having indefinite resistance values and voltage/current conditions. In compensation for the indefiniteness of multi-value writing, this example applies a method of writing a Lee metric code (hereinafter also referred to as an “LMC”), which is a fast ECC (Error Correction Code), to a pair of cells (hereinafter referred to as a “pair cell”). This makes it possible to simplify verification and so forth at the time of resistance value setting and additionally suppress the number λ of cells per information bit. If λ<1 can be achieved, it is possible to exert an effect corresponding to a shrink equal to λ-times a memory chip size. This is not a shrink through processes and accordingly it can be realized without any increase in process step costs.
The memory system according to the embodiment will now be described below specifically.
First, an outline of a multi-valued pair cell is described.
FIG. 1 is a diagram illustrative of an outline of a pair cell in a memory system according to the embodiment.
For relatively stable setting of resistance values other than on/off to a cell in a resistance variable memory, the maximum number of levels assigned to resistance values can be considered equal to around eight. If more levels are assigned, statistical variations in cells allow no error in resistance values to be suppressed within one level. On the other hand, for increasing the quantity of information stored in a cell, it is desired to assign as many levels as possible to resistance values. Thus, it is required to assign eight levels or more at least. Then, in consideration of the magnitude of the burden on setting multi-levels to a cell alone, the embodiment uses a pair cell to reduce the burden. A method of setting resistance values is described, which increases the number of resistance value levels settable in a pair cell as a unit to increase the storage capacity of a memory while compensates for the increase in cell share caused by the use of the pair cell to raise the information density. In this method, resistance value levels are assigned to information values so that failed resistance value setting causes the minimum variation in information value, thereby utilizing the LMC efficiently. Specifically, a prime p is assigned to resistance value levels of a pair cell so that an error-caused variation in resistance value level of a pair cell falls within space between successive values of information.
The following description is given to assignments of information values to combinations of resistance value levels of a pair cell composed of 4-level/cell cells (hereinafter also simply referred to as “states of a pair cell” (pair cell levels)).
FIG. 2 is a diagram illustrative of assignments of information values to states of a pair cell in the memory system according to the embodiment. A numeral in ( ) of FIG. 2 indicates the corresponding information value. A bar graph in FIG. 2 schematically indicates cell current flowing when a certain voltage is applied across a cell so that a larger hatched part indicates a larger flow of cell current. It is assumed that a high resistance state with the lowest cell current and a low resistance state with the highest cell current can be set without causing failed setting. On the precondition of this assumption, it is desired that failed setting is not caused simultaneously in resistance values of two cells contained in the pair cell. Therefore, one cell in the pair cell is always set to a high resistance state or a low resistance state that allows cell current to become the lowest or the highest.
In the case of 4-level/cell, states of a pair cell vary in 12 ways. As an LMC utilizes a residue field of a prime p, information values are assigned to states of the pair cell where p=11. At this time, the assignment is executed in such a manner that one level error in resistance value of a cell caused by failed setting of a state of the pair cell becomes an error falling within a range of an information value ±1. As shown in FIG. 2, an information value 5 is assigned to two states of the pair cell so that a residue field of p=11 is assigned to 12 states of the pair cell. In this case, the precondition prevents failed setting from arising in two cells of the pair cell simultaneously. Therefore, as shown with the arrows in FIG. 2, failed writing is only allowed to occur between successive information values.
The efficiency of assignments of information values in FIG. 2 is described here in relation to the LMC.
As an error in information value falls within a range of +1, error correction is sufficient if it is ready for ε=1 where s is the maximum value of error correctable Lee metrics. In this example, however, error correction is made ready for ε=2. This enables error correction when errors within a range of ±1 occur in two code symbols of a code having a length of p−1, and when an error within a range of ±2 occurs in one code symbol of the code.
An LMC ECC of p=11 and ε=2 has a code length n=p−1=10 code symbols of which symbols usable as data are equal to k=n−(ε+1)=7 in number. In addition, the number of information bits storable in two cells is equal to log2 11. Therefore, the number of cells/bit becomes λ=(2n)/(k log2 p)=0.826.
In a word, according to the example of assignments of information values in FIG. 2, even if the reliability of data is maintained by ECC while using the pair cell, the cell occupation area can be shrunk by 0.826 times.
The following description is given to assignments of information values to states of a pair cell composed of 5-level/cell cells.
FIG. 3 is a diagram illustrative of assignments of information values to states of a pair cell in the memory system according to the embodiment. The viewpoint, precondition and so forth in FIG. 3 are similar to those of FIG. 2.
In the case of 5-level/cell, states of a pair cell vary in 16 ways. As an LMC utilizes a residue field of a prime p, information values are assigned to states of the pair cell where p=13. At this time, the assignment is executed in such a manner that one level error in resistance value of a cell caused by failed setting of a state of the pair cell becomes an error falling within a range of an information value ±1. As shown in FIG. 3, information values 2, 6 and 11 are each assigned to two states of the pair cell so that a residue field of p=13 is assigned to 16 states of the pair cell. In this case, the precondition prevents failed setting from arising in two cells of the pair cell simultaneously. Therefore, as shown with the arrows in FIG. 3, failed writing is only allowed to occur between successive information values.
The efficiency of assignments of information values in FIG. 3 is described here in relation to the LMC.
As an error in information value falls within a range of ±1, error correction is sufficient if it is ready for F=1. In this example, however, error correction is made ready for ε=2. This enables error correction when errors within a range of ±1 occur in two code symbols of a code having a length of p−1, and when an error within a range of ±2 occurs in one code symbol of the code.
An LMC ECC of p=13 and ε=2 has a code length n=p−1=12 code symbols of which symbols usable as data are equal to k=n−(ε+1)=9 in number. In addition, the number of information bits storable in two cells is equal to log2 13. Therefore, the number of cells/bit becomes λ=(2n)/(k log2 p)=0.721.
In a word, according to the example of assignments of information values in FIG. 3, even if the reliability of data is maintained by ECC while using the pair cell, the cell occupation area can be shrunk by 0.721 times.
The following description is given to assignments of information values to states of a pair cell composed of 6-level/cell cells.
FIG. 4 is a diagram illustrative of assignments of information values to states of the pair cell in the memory system according to the embodiment. The viewpoint, precondition and so forth in FIG. 4 are similar to those of FIG. 2.
In the case of 6-level/cell, states of a pair cell vary in 20 ways. As an LMC utilizes a residue field of a prime p, information values are assigned to states of the pair cell where p=17. At this time, the assignment is executed in such a manner that one level error in resistance value of a cell caused by failed setting of a state of the pair cell becomes an error falling within a range of an information value ±1. As shown in FIG. 4, information values 3, 8 and 14 are each assigned to two states of the pair cell so that a residue field of p=17 is assigned to 20 states of the pair cell. In this case, the precondition prevents failed setting from arising in two cells of the pair cell simultaneously. Therefore, as shown with the arrows in FIG. 4, failed writing is only allowed to occur between successive information values.
The efficiency of assignments of information values in FIG. 4 is described here in relation to the LMC.
As an error in information value falls within a range of ±1, error correction is sufficient if it is ready for ε=1. In this example, however, error correction is made ready for ε=2. In this case, error correction is possible when errors within a range of ±1 occur in two code symbols of a code having a length of p−1, and when an error within a range of ±2 occurs in one code symbol of the code.
An LMC ECC of p=17 and ε=2 has a code length n=p−1=16 code symbols of which symbols usable as data are equal to k=n−(ε+1)=13 in number. In addition, the number of information bits expressible by symbols composed of two cells is equal to log2 13. Therefore, the number of cells/bit becomes λ=(2n)/(k log2 p)=0.602.
In a word, according to the example of assignments of information values in FIG. 4, even if the reliability of data is maintained by ECC while using the pair cell, the cell occupation area can be shrunk by 0.602 times.
The following description is given to other assignments of information values to states of a pair cell composed of 6-level/cell cells.
FIG. 5 is a diagram illustrative of assignments of information values to states of the pair cell in the memory system according to the embodiment. FIG. 5 shows an instance of a prime p=19. The viewpoint, precondition and so forth in FIG. 5 are similar to those of FIG. 2.
In the case of 6-level/cell, states of a pair cell vary in 20 ways. As an LMC utilizes a residue field of a prime p, information values are assigned to states of the pair cell where p=19. At this time, the assignment is executed in such a manner that one level error in resistance value of a cell caused by failed setting of a state of the pair cell becomes an error falling within a range of an information value ±1. As shown in FIG. 5, an information value 9 is assigned to two states of the pair cell so that a residue field of p=19 is assigned to 20 states of the pair cell. In this case, the precondition prevents failed setting from arising in two cells of the pair cell simultaneously. Therefore, as shown with the arrows in FIG. 5, failed writing is only allowed to occur between successive information values.
The effect of assignments of information values in FIG. 5 is described here in relation to the LMC.
As an error in information value falls within a range of ±1, error correction is sufficient if it is ready for ε=1. In this example, however, error correction is made ready for ε=2. This enables error correction when errors within a range of ±1 occur in two code symbols of a code having a length of p−1, and when an error within a range of ±2 occurs in one code symbol of the code.
An LMC ECC of p=19 and ε=2 has a code length n=p−1=18 code symbols of which symbols usable as data are equal to k=n−(ε+1)=15 in number. In addition, the number of information bits storable in two cells is equal to log2 19. Therefore, the number of cells/bit becomes λ=(2n)/(k log2 p)=0.565.
In a word, according to the example of assignments of information values in FIG. 5, even if the reliability of data is maintained by ECC while using the pair cell, the cell occupation area can be shrunk by 0.565 times.
The following description is given to multi-value writing to a cell in a variable resistance memory.
There are several types of variable resistance memory cells. They are though roughly divided into the type that causes a variation in resistance value in accordance with formation of a filament by metal ions and the type that causes a variation in resistance value in accordance with contacts between molecules such as CNTs. The latter type of those can be considered as an aggregation of micro-switches in a sense. Therefore, the latter type is such that the cell resistance value is stable, the retention property is excellent, and cell multi-valuing is relatively easy. On the other hand, the former type (hereinafter also referred to as the “filament type”) is such that the filament itself is unstable and therefore the retention property is poor, and cell multi-valuing is relatively difficult.
Even a cell of the filament type, multi-valuing can be realized by thinking filament formation processes. Then, filament formation processes for realizing multi-valuing a cell are described with reference to FIG. 6.
FIG. 6 is a diagram showing state variations of a cell in the memory system according to the embodiment. The cell in FIG. 6 is of the filament type. It is a cell in an ion memory. FIG. 7 is a diagram showing a relation between relative inter-ionic distances and activation energy in the cell in the memory system according to the embodiment.
A filament can be formed in two stages. The first stage is a process of creating several clusters in an ion migrating medium while the second stage is a process of coupling these clusters by the filament. For realizing these filament formation processes, the solid medium is set so that a barrier potential Ec in the first stage becomes higher than a barrier potential Ef in the second stage. In the case of FIG. 7, the potential for cluster formation is Ec≈1 eV and the potential for filament formation between clusters is Ef≈0.8 eV. In a word, the difference between the potentials for cluster formation and filament formation is Eδ≈0.2 eV.
A variation in resistance value of the cell and a voltage V applied across the cell relate as follows. The medium in the reset cell contains isolated clusters remaining as shown with black circles in A of FIG. 6. Here, “reset” means turning the cell to a high resistance state. In this state, when the voltage V is applied between electrodes of the cell, Ag ions start to diffuse inside the medium as shown with white circles in B of FIG. 6. Then, when the potential on the center of the Ag ion exceeds the cluster formation potential Ec, clusters are formed between electrodes of the cell. The average number of clusters, <n>, formed at this time and the voltage V between electrodes establish a relation V=<n>Ec therebetween. Here, <n> is a value on the assumption that clusters are formed at equal intervals between electrodes. When the voltage V between electrodes is further maintained continuously, as the potential between electrodes has already become equal to or higher than the filament formation potential Ef, formation of a filament starts as shown in C of FIG. 6. Then, formation of a conductive filament between electrodes sets the cell. Here, “set” means turning the cell to a low resistance state by formation of the conductive filament between electrodes. The average number of clusters, <n>, is determined by an initial voltage applied between electrodes, the number of application times and so forth. A multi-value level of the cell can be determined in accordance with <n>.
For ensuring the retention property at the average number of clusters, <n>, the medium of the cell may be designed appropriately to set the potential. This is because such the design prevents application of a large voltage between electrodes of the cell and avoids an occurrence of disturbance. As a result, cluster sites remain after the filament almost disappears. When a voltage is applied between electrodes so that a voltage exceeding the potential Ef is applied to each cluster site again, the cell is set and turned to a low resistance state. The voltage V applied between electrodes of the cell is considered almost inversely proportional to <n>. Accordingly, the voltage V can be used to discriminate multi-value levels while lowering the cell resistance. Namely, the voltage V at the time of setting again has a proportional relation with the cell current at that time. Therefore, the voltage V can be used to discriminate which one of the levels it has.
Raising the cell resistance requires activation energy exceeding the cluster formation potential Ec again so as to diffuse metal ions to the electrode. Therefore, such a reverse bias voltage V is applied between electrodes of the cell that allows every potential on <n> clusters to exceed Ec. Thus, metal ions passing beyond the potential barrier for cluster formation are collected to the electrode.
The cell having a resistance value variable in accordance with filament formation operates on the basis of diffusion and collection of metal ions. Therefore, it is required to invert the voltage V applied between electrodes, resulting in bipolar operation.
In FIG. 6, a high resistance state is represented as ‘0’ data, and a low resistance state is represented as ‘1’ data. In addition, data corresponding to plural levels in a weak high resistance state, which is an intermediate state between the high resistance state and the low resistance state, is represented as ‘L’.
Subsequently, as an example of the unipolar operable cell, a NT stack cell using CNT contact/noncontact is described. In the following description of the memory system according to the embodiment, the case of the use of a unipolar operating cell is exemplified. This point should be noted.
FIG. 8 is a diagram showing state variations of a cell in the memory system according to the embodiment. The cell shown in FIG. 8 is a NT stack cell using CNTs. FIG. 9 is a diagram showing a relation between relative inter-CNT distances and activation energy in the cell in the memory system according to the embodiment.
A CNT has a nanoscale molecular structure excellent in electrical and physical properties, and applications thereof to resistance variable memories have been studied in the past.
The characteristics of the NT stack cell are described here.
If the CNT is compared to a straw, the NT stack is like a bed containing straws stacked disorderly. It has a structure of straws partly contacted and separated with/from each other. The contact between CNTs can be maintained by the Van der Waals force. The structure of the NT stack can be maintained by the stiffness of CNTs contacting by the Van der Waals force. When the NT stack is formed between electrodes to observe the electric resistance of the NT stack, the resistance value varies in accordance with the situation of contact between CNTs. NT stacks formed under similar conditions exhibit almost similar resistance variations. As shown in A of FIG. 8, a NT stack cell in a high resistance state has not only contact parts between CNTs (black circles in A of FIG. 8) but also many noncontact parts inside the NT stack. The contact/noncontact between CNTs can be maintained by the stiffness of CNTs and the Van der Waals force as described above. When a voltage is applied between electrodes of a NT stack cell in a high resistance state, an attractive electrostatic force acts between noncontact CNTs. When this attractive electrostatic force overcomes the stiffness held by CNTs, a relative distance between CNTs reduces. When the relative distance between CNTs reaches a certain distance, the Van der Waals force acts to make a contact between CNTs as shown in B of FIG. 8. A white circle in B of FIG. 8 is a new contact part between CNTs. As a result, the resistance value of the NT stack lowers.
The number of contact parts between CNTs varies along with the application time of the voltage between electrodes. The state of contact between CNTs can be maintained even after removing the voltage between electrodes. A difference in the number of contact parts between CNTs corresponds to the difference in level of the NT stack cell.
A return of the NT stack cell in a low resistance state to a high resistance state requires injection of phonons, that is, thermal oscillations into the NT stack. This makes it possible to oscillate CNTs intensively to separate contacted CNTs and return shapes of CNTs by the stiffness originally held by CNTs. For this purpose, a voltage for causing Joule heat easily in the NT stack cell is applied between electrodes of the NT stack to concentrate phonons on contact parts between CNTs.
In this connection, the potential of the Van der Waals force of the CNT is E0≈5 eV as shown in FIG. 9. Therefore, overcoming the stiffness to bend CNTs and make a contact between non-contacted CNTs requires a voltage having a larger potential than 5 eV to be applied between electrodes.
Hereinafter, the high resistance state of the NT stack cell may also be related to ‘0’ data, and the low resistance state to ‘L’ data. In the case of a multi-valued NT stack cell, one or more natural numbers are related to ‘L’.
The following description is given to a method of reversibly changing resistance states of a NT stack cell.
FIG. 10 is a graph showing relations among phonon energy within a NT stack, resistances of the NT stack, and potentials of the electric field within the NT stack in the memory system according to the embodiment. The lateral axis in FIG. 10 indicates average phonon energy e that allows a CNT end to freely execute an oscillating motion. It is considered that the energy e is proportional to Joule heat caused by electric energy added to the NT stack. When the voltage between electrodes of the NT stack cell is defined as v, the current flowing in the NT stack as i, and the resistance of the NT stack as r, then the energy e is represented by v2/r or i2r. On the lateral axis, e=E0 indicates the phonon energy corresponding to the Van der Waals force caused between CNTs. At this point, the contacted CNTs separate from each other, thereby increasing the resistance r of the NT stack. This variation is further affected by the situation of the electric field, or the voltage potential, placed between CNTs. FIG. 10 shows an instance of v<V0 with the solid line and an instance of v>V0 with the dashed line because the graph varies the situation greatly in accordance with the voltage v. The voltage V0 is an average voltage when the oscillating motion of a CNT end bends the CNT against the stiffness held by the CNT so as to make contact with another CNT. Namely, as shown by the arrow a1 in FIG. 10, in the case of v<V0, the phonon energy e rises even if the NT stack has any resistance r and, when e>E0 is reached, the contact between CNTs can be eliminated. As a result, the NT stack resistance rises up to r=R0. In addition, as shown by the arrow a2 in FIG. 10, even if the NT stack has any resistance r in the case of v>V0, it is bent until the CNT end makes contact with another adjacent CNT when e is small. As a result, the NT stack resistance r falls down to the minimum value. Then, this NT stack resistance r is fixed by the Van der Waals force. When the phonon energy e is elevated, the oscillating motion eliminates the contact between CNTs. Then, when e>E0 is reached, almost all contacts between CNTs can be eliminated. As a result, the NT stack resistance r becomes higher as shown by the arrow a3 in FIG. 10. As the bias of the electric field is large, however, the probability of contacts newly made between CNTs is also large. As a result, the NT stack resistance r has a value of around Rf larger than the minimum value. In a state of high phonon energy e, the magnitude relation between the voltage v and the voltage V0 makes the NT stack resistance r come and go between Rf and R0 as shown by the arrows a4 and a5 in FIG. 10. On the other hand, in a state of low phonon energy e, the NT stack makes only a change to a low resistance in the case of v>V0 and no change to a high resistance as shown by the arrow a6 in FIG. 10.
In the state of high phonon energy e, even if e≦E0 is reached in the case of v<V0, the NT stack maintains the same resistance Rf as that in the case of e>E0 as shown by the arrow a7 in FIG. 10.
In consideration of the above-described variations in the NT stack resistance r, a method of changing the NT stack resistance r is described next.
Initially, a description is given to raising the NT stack resistance.
FIG. 11 is a graph showing a relation between phonon energy and voltages across electrodes of a NT stack cell when the NT stack resistance is made higher in the memory system according to the embodiment. FIG. 11 shows V2/r relative to the phonon energy e at every resistance.
In the case of v<V0, the NT stack resistance becomes r=R0 in a state of high energy e. When the energy e lowers, the NT stack resistance is maintained almost at r=R0. This is utilized to raise the NT stack resistance.
With respect to the maximum resistance r=R0 of the NT stack, the voltage v is made sufficiently smaller than the voltage V0 so that v2/r becomes around E0 or below. In addition, with respect to the minimum resistance r of the NT stack, the voltage between electrodes of the NT stack cell is set to v=U0 so that it becomes larger than E0. In this case, until the NT stack resistance r becomes the minimum resistance, the phonon energy keeps e>E0. Thereafter, the voltage v between electrodes of the NT stack cell is gradually made larger so as to prevent the cell current i from increasing and make the voltage stay back from the voltage V0. Further, even if the resistance r is high, the energy e can be controlled to exceed E0. In this case, the NT stack resistance r can be made higher while the cell current i is maintained small. This corresponds to the instance in which the higher the resistance r, the larger the voltage v becomes in the case of constant energy e in FIG. 11. In this case, the state varies as the arrow a1 in FIG. 11.
In this connection, in read operation, the voltage v applied between electrodes of the NT stack cell is made equal to or lower than the voltage U0/3 to achieve 1/10 or below the energy required for making a transition to the high resistance state. This is required to prevent the NT stack resistance from rising. Therefore, in read operation, the current sense is desirable because it can expect a larger cell current flowing at the time of a lower resistance compared to the voltage sense.
Subsequently, a description is given to lowering the NT stack resistance.
FIG. 12 is a graph showing a relation between phonon energy and cell current in the NT stack when the NT stack resistance is made lower in the memory system according to the embodiment. FIG. 12 shows i2r relative to phonon energy e at every resistance.
Lowering the NT stack resistance utilizes the fact that the NT stack resistance r lowers one-sidedly if the voltage applied between electrodes of the NT stack cell satisfies v>V0. In particular, it utilizes the fact that the NT stack resistance r becomes lowermost if the energy satisfies e≦E0. When a voltage v=V0 is applied between electrodes of the NT stack cell having the maximum resistance r=R0, a current i=I0 flows. A constant voltage v>V0 is applied across the NT stack by limiting the current to a current i≦J0 (>I0). At this time, in the case of J02R0<E0, as the voltage v>V0 is applied between electrodes of the NT stack cell, the NT stack resistance r lowers. In addition, as the current is limited by i≦J0, the voltage v sharply falls and the NT stack stabilizes at a low resistance. In addition, in the case of J02R0>E0, the NT stack resistance lowers to r=Rf. At this time, if J02Rf<E0 and J0Rf>V0, then the phonon energy e is small and accordingly the resistance r lowers further. In other cases, the NT stack resistance stops at r=Rf and does not become lowermost. In any case, the resistance lowers.
These variations in the resistance r correspond to the arrows a1 and a2 in FIG. 12. If resistance lowering stays at the resistance r=Rf, however, it is the case that the arrow a3 in FIG. 12 indicative of the voltage v=V0 would locate rightward from the dashed line indicative of the energy E0, different from the case shown in FIG. 12. This case corresponds to the case where it cannot be changed from the curve indicative of the resistance r=Rf.
When the NT stack resistance is made lower, in practice, it is not required to always maintain a constant current. It is sufficient to satisfy the conditions about the voltage v>V0 and iV0<E0. Therefore, it is not required to thoughtlessly elevate the voltage v applied to the high-resistance NT stack for maintaining the constant current. If the lowered resistance increases the cell current i, the voltage v applied across the NT stack is lowered.
A method of accessing NT stack cells is described next.
The use of NT stack cells makes it possible to configure a cell array of the cross point type. In a word, the cell array of the cross point type is structured to include plural bit lines BL, plural word lines WL intersecting these plural bit lines BL, and NT stack cells provided at intersections of plural bit lines BL and plural word lines WL. Hereinafter, a cell provided in the cell array of the cross point type may also be referred to as a “CP cell” in particular. In addition, the cell array is divided in accordance with the size thereof into unit cell arrays each called a “MAT”.
In the case of the cell array of the cross point type, normally, accessing plural CP cells can be realized by selecting plural bit lines BL and one word line WL. Accordingly, the burden on the word line WL becomes heavy. Therefore, the size of a MAT is determined in consideration of the magnitude of an allowable burden on a word line WL, that is, the length of the word line WL. If plural short-fault CP cells locate on the same word line WL in a cell array, disturbances caused by current sneaking and so forth may prevent normal data write. Then, the following description is given to a write sequence according to the embodiment for solving these problems. Hereinafter, the short-fault cell may also be simply referred to as a “fault cell”.
The write sequence according to the embodiment includes an initial step, an all ‘0’ write step, and an ‘L’ write step. This write sequence may also be referred to as a “2-step write sequence” because writing data to an actual cell is achieved at two steps including the all ‘0’ write step and the ‘L’ write step.
At the start, the initial step in the write sequence is described.
FIG. 13 is a diagram showing a bias state of a cell array at the initial step in the write sequence in the memory system according to the embodiment. In FIG. 13, a cell MC shown by a black circle is a fault cell, an ‘L’-added cell MC is a cell MC in a low resistance state, and an ‘H’-added cell MC is a cell in a high resistance state. In addition, a selection line shown by a chain line is a non-access selection line, and a word line WL shown by a dashed line is a fault word line WL. These expressions are similarly applied in FIGS. 14 and 15.
In the following description, a voltage for generating larger energy than phonon energy capable of eliminating the Van der Waals force in a NT stack cell is denoted with U0, and a voltage slightly smaller than the voltage U0 is denoted with U0−d. In addition, a voltage for making a contact between NT stack cells against the stiffness of the NT stack cell is denoted with V0, and a voltage slightly smaller than the voltage V0 is denoted with V0−d.
In the following description, word lines WL and bit lines BL may also be called “selection lines”, the generic term thereof.
At the initial step, all bit lines BL are provided with the potential U0−d and all word lines WL with the potential U0. A current is detected in a selection line connected to a fault cell. The current is larger than expected when a normal cell MC is reverse-biased. This can be used to specify a fault selection line. The specified fault word line WL is handled at the subsequent all ‘0’ write step as a word line WL provided with the same fixed potential Vs as that on the access word line WL.
Subsequently, the all ‘0’ write step in the write sequence is described.
FIG. 14 is a diagram showing a bias state of a cell array at the all ‘0’ write step in the write sequence in the memory system according to the embodiment.
At the all ‘0’ write step, the fault word line WL is provided with the potential Vs while non-access bit lines BL are brought into the floating state and non-access word lines WL other than the fault word line WL are also brought into the floating state.
On the other hand, all access bit lines BL targeted to simultaneous access are provided with the potential U0. When a lower stationary voltage U0 is applied to cells MC, phonons are injected into cells MC in a low resistance state as described before. Thus, the corresponding cells MC change to a high resistance state by the access word line WL and the fault word line WL. At this time, even if there are many cells MC in a low resistance state, the voltage U0 is lower, and the cell current becomes smaller once the cells MC change to a high resistance state. Therefore, the electrical load on the word line WL provided with the potential Vs is light. To that extent, the number of access bit lines BL targeted to simultaneous access can be increased. In the cells connected to the fault word line WL except fault cells having faults in both a NT stack and a diode and fault cells including a NT stack of which resistance cannot be raised, resistances of cells MC are raised in order at every access. Therefore, current passing through these cells MC are reduced in order. As a result, at the subsequent ‘1’ write step, a high voltage via the fault cell is not applied to non-access cells MC via cells MC in a low resistance state. Accordingly, the influence of disturbance exerted on normal cells MC can be reduced greatly. This effect becomes effective when a MAT is upsized.
At the all ‘0’ write step, the current flowing in the access word line WL cannot be reduced. If all access cells MC cannot make a transition to a high resistance state, this access word line WL is regarded as connected to a fault cell that includes a normal diode but has a fault only in a NT stack. Then, this access word line WL is not accessed and the all ‘0’ write step is interrupted. Thereafter, this access word line WL is excluded from access targets at the subsequent steps.
Subsequently, the ‘L’ write step in the write sequence is described.
FIG. 15 is a diagram showing a bias state of a cell array at the ‘L’ write step in the write sequence in the memory system according to the embodiment.
At the ‘L’ write step, an access cell MC targeted to ‘L’ write is provided with the voltage V0+d, and all other non-access cells MC are brought into the floating state. In addition, only an access word line WL is provided with the potential Vs and other selection lines are brought into the floating state. As a result, the cell MC having electrodes provided with the voltage V0 or above is only the access cell MC. Therefore, only the access cell MC changes to a low resistance state. Multi-values can be discriminated by controlling the time of applying the voltage to the access cell MC.
In the initial stage of setting the potential V0+d on bit lines BL, the access cell MC is in a high resistance state. Accordingly, no large current flows therein and no load is imposed on the word line WL. When the access cell MC starts to change to a low resistance state, current starts to flow in the access cell MC. In individual bit lines BL, current is limited because the later-described circuit executes high-impedance control. Therefore, the load on the word line WL is prevented from becoming extremely heavier.
The following description is given to potential variations on selection lines at the time of the write sequence.
FIGS. 16 and 17 are diagrams showing potential variations on selection lines at the time of the write sequence in the memory system according to the embodiment. FIG. 16 shows those on bit lines BL while FIG. 17 shows those on word lines WL. In FIGS. 16 and 17, a chain line shows a non-access selection line, and a dashed line shows a fault word line WL and a non-access bit line BL connected to a fault cell. The time on the lateral axis indicates the initial step, the all ‘0’ write step and the ‘L’ write step dividedly. These three steps are not required to be continuous. A pause period may interpose between the steps, for example, at the time of accessing a cell MC. It is sufficient if the order of steps is kept. Namely, at the all ‘0’ write step, it is possible to configure a sequence as an independent process at every word line WL.
At the start, at the initial step, all bit lines BL are provided with the potential U0-d and all word lines WL with the potential U0 in a MAT. At this step, a fault word line WL is specified.
Subsequently, at the all ‘0’ write step, both the access word line WL and the fault word line WL are provided with the potential Vs. Access bit lines BL are provided with the potential U0, which is then pulled up little by little from the potential U0 as the resistance of the access cell MC rises. FIG. 16 shows the situation of the potential on the access bit line BL, which is pulled up in two stages. The potential on the access bit line BL may vary continuously or in stages more than two. Non-access bit lines BL are set in the floating state and accordingly vary to the potential Vs* little by little. Non-access word lines WL are also set in the floating state and accordingly reach the potential U0*.
Subsequently, at the ‘L’ write step, among the access bit lines BL, the access bit line BL connected to the access cell MC targeted to ‘L’ write is provided with the potential V0+d. Thereafter, the impedance of the power supply is raised so as to lower the potential on these access bit lines BL along with increases in cell current. Other access bit lines BL are set in the floating state and accordingly vary to the potential Vs* along with the lapse of time. The floating-state bit line BL connected to the fault cell varies to the potential Vs** as the access bit line BL is provided with the potential V0+d as described before. The access word line WL maintains at the setting of the potential Vs. In contrast, all non-access word lines WL including the fault word line WL are floating-set and accordingly vary to the potential V0*. They further vary to the potential Vs* along with the reduction in potential on the access bit line BL.
Setting of multi-value levels includes simultaneously activating individual multi-bit sense amps at every certain time and executing a comparison at every sense amp with a reference value set at every multi-value data to confirm the completion of write in the access cell MC individually. Then, connections with bit lines BL are closed in order beginning from the write-completed access cell MC.
Hereinafter, a memory system using 5-level/cell cells is described as an example of the memory system according to the embodiment using multi-level/cell.
In MAT access, multi-bit simultaneous access is effective. Then, as the precondition for multi-bit simultaneous access using reference cells, the following description is given to reference bit lines for generating multi-value reference values.
FIG. 18 is a schematic diagram of a configuration of reference bit lines in the memory system according to the embodiment. FIG. 19 is a circuit diagram of a current source for reference bit lines in the memory system according to the embodiment.
The memory system according to the embodiment uses a group of at least M bit lines BL as reference bit lines RBL<m> (m=1 to M) at every MAT to set a high resistance state in cells MC on all reference bit lines RBL (hereinafter also referred to as “reference cells”). Hereinafter, a group of M reference bit lines RBL may also be referred to as a “reference bit line group”. These M reference bit lines RBL are connected via switch elements to one bus, that is, a reference local bus. Selection of the value of M and selection of the number of reference bit lines RBL simultaneously connected to the reference local bus are determined by the situation of reference bit lines RBL and the interval between resistances set at every multi-value. Selection of a large M for simultaneous selection of many bit lines BL corresponds to extension of intervals between the corresponding resistance distributions at multi-values.
A MAT of the cross point type is characterized in that reference bit lines RBL and access bit lines BL are always selected by a common word line WL. Therefore, a reference bit line group is provided on several parts of a long word line WL to arrange reference bit lines RBL and access bit lines BL in near environments desirably. In addition, a high resistance state is set in reference cells RC for the purpose of reducing current flowing in the access word line WL as low as possible and because a variable resistance memory cell is generally more stable in the high resistance state that in a low resistance state.
With reference to current in the reference local bus (standard current), a multi-value is written in an access cell. Comparison currents for deciding multi-value levels are generated in a circuit shown in FIG. 19 (hereinafter also referred to as a “comparison current generator circuit”).
The comparison current generator circuit is a current source for supplying currents having 1:1, 1:3⁄4, 1:1⁄2 and 1:1⁄4 relations with the current drawn into the reference local bus, which are defined as comparison currents rf4, rf3, rf2 and rf1.
Individual circuit parts shown in FIGS. 18 and 19 are described below.
FIG. 18 shows only WL<1> and <2> as word lines for simple description.
The word line WL side of the reference bit line group is provided on a MAT end. An access word line WL is connected to the ground potential Vss via a WL switch controlled by a control signal, from rdec. On the other hand, on the bit line BL side of the reference bit line group, the reference bit lines RBL are connected to the reference local bus via a RBL switch controlled by a control signal, set/read.
The circuit serving as the current source for the reference local bus comprises a circuit indicated with A for supplying a power supply Vpp, and a circuit indicated with B for generating rf1-rf4 from the power supply Vpp fed from the former circuit. The circuit indicated with A includes an NMOS transistor controlled by a control signal Vr and utilizes operation of this transistor in the saturation region to feed the power supply Vpp to the circuit indicated with B. The circuit indicated with B includes a current mirror circuit composed of PMOS transistors controlled by the reference local bus. This current mirror circuit receives the power via a PMOS transistor controlled by a control signal, /accREAD, so that the current mirror circuit only operates as required.
The following description is given to the relation between the access bit lines BL and the comparison currents generated at M reference bit lines RBL.
The condition of a voltage applied to a cell at the time of read operation differs from that at the time of write operation. At the time of read operation, as low a voltage as possible is applied so as to cause no variation in cell state. At the time of write operation, a considerably high voltage is applied so as to cause a variation in cell state. Therefore, the comparison current is set to a value capable of discriminating the multi-value level of a cell in read operation using a low voltage. The comparison currents rf1-rf4 for 5-level/cell described above are converted at access bit lines BL into voltages in accordance with access operations.
FIG. 20 is a diagram illustrative of relations among comparison currents at access operations in the memory system according to the embodiment. A of FIG. 20 shows a comparison current at the time of write operation, B of FIG. 20 shows a comparison current at the time of read operation, and C of FIG. 20 shows a comparison current for the reference cell.
The group of reference cells is applied with such a voltage that does not change the high resistance state of a cell. Therefore, the comparison current to be generated becomes a reference level used at the time of read operation. The values shown in C of FIG. 20 are reference values corresponding to reference levels. These reference values are reference values that allow current to flow out at first from M simultaneously selected cells in high resistance states. This reference value is a value equal to M-times the value of current in the cell set in the high resistance state. The way for selecting M depends on the cell characteristics as described before. It should be noted that M is selected so as to cause no overlapped resistance distributions.
The values of reference levels are equal to M-times, M×3⁄4-times, M×1⁄2-times and M×1⁄4-times the average cell current of cells in high resistance states. Read operation decides the multi-value level of a cell by comparing the cell current with these comparison currents. In accordance with a cell current Iread when a read voltage Vread is applied, multi-value levels of a cell can be decided by 5 levels L0, L1, L2, L3 and L4 from the lower current value as shown in B of FIG. 20. The resistance value of the cell is the highest at the time of L0 and the lowest at the time of L4.
So as to obtain the cell current Iread corresponding to these read currents, the resistance of the cell is set in write operation. At the time of the all ‘0’ write, a voltage is applied to change a cell from a high resistance state to a low resistance state. This voltage is defined as a program voltage Vpro. Based on a cell current Ipro flowing at the time of application of the program voltage Vpro, a comparison current is generated.
In the case of Vpro=α·Vread, the reference current at the time of programming also becomes Ipro=α·Iread. Here, Iread is a comparison current at the time of read operation. Reference values are converted at individual sense amps for bit lines BL and related to write of any multi-value levels. The circuit used here is described later.
Hereinafter, a sense amp SA is described.
Next, the circuitry of the sense amp SA is described.
The embodiment uses a sense amp of the current comparison type so that fine current comparison can be applied at the time of read operation or write operation to monitor the state of a cell at a high speed. In the embodiment, however, for the purpose of further elevating the sensitivity of the sense amp SA, the quantity of current flowing into a current mirror circuit on the cell current input side is made equal to that on the reference current side so that the resistance value of the cell can be reflected more. The following description is given to the sense amp SA operative to compare the cell current flowing in a bit line BL with the reference current flowing in a reference bit line RBL.
FIG. 21 is a circuit diagram of a sense amp in the memory system according to the embodiment.
The sense amp SA includes PMOS transistors M0-M3, M8, M9, M12-M17 and NMOS transistors M4-M7, M10, M11 and M18. The transistors M0, M8, M10, M2 and M4 are serially connected between a certain supply potential Vdd and the ground potential Vss. The transistor M6 has a source connected to the gates of the transistors M0, M2 and M4, and a drain connected to the ground potential Vss. The transistors M1, M9, M11, M3 and M5 are serially connected between the supply potential Vdd and the ground potential Vss. The transistor M7 has a source connected to the gates of the transistors M1, M3 and M5, and a drain connected to the ground potential Vss. The transistors M8 and M9 have gates, which receive a control signal, /act. The transistors M10 and M11 have gates, which receive a control signal, vLTC. The transistors M6 and M7 have gates, which receive a control signal, /se, for controlling the start of sensing at the sense amp SA. An output node N2 between the transistors M2 and M4 is connected to the gates of the transistors M1, M3 and M5 and the source of the transistor M7. The output node N2 provides an output signal ‘out’. An output node N3 between the transistors M3 and M5 is connected to the gates of the transistors M0, M2 and M4 and the source of the transistor M6. The output node N3 provides an output signal ‘/out’.
The transistor M12 has a source connected to the drain of the transistor M16, a drain connected to an input node N0 between the transistors M10 and M2, and a gate connected to the drain of the transistor M14. The transistor M16 has a source connected to a certain potential V1, and a drain connected to the sources of the transistors M12 and M14. The gate of the transistor M12 and the drain of the transistor M14 receive an input signal ‘in’. The gate of the transistor M14 receives an input signal ‘/in’.
The transistor M13 has a source connected to the drain of the transistor M17, a drain connected to an input node N1 between the transistors M11 and M3, and a gate connected to the drain of the transistor M15. The transistor M17 has a source connected to the potential V1, and a drain connected to the sources of the transistors M13 and M15. The gate of the transistor M13 and the drain and gate of the transistor M15 receive the input signal ‘in’ The gates of the transistors M16 and M17 receive a control signal, /accREAD.
The transistor M18 has a source connected to the potential Vpp, and a drain connected to the potential V1. The gate of the transistor M18 is provided with a potential Vw at the time of write operation and a potential Vr at the time of read operation.
This sense amp SA decides the resistance state of a cell by comparing a cell current with a reference current. It is possible to execute fast reliable sensing even in a current comparison of several 10 nA or below.
The input stage of the sense amp SA includes a current mirror circuit composed of the transistors M12, M14 and M16, and a current mirror circuit composed of the transistors M13, M15 and M17. The input signal ‘/in’ and the input signal ‘in’ contain currents configured equal. Thus, the sense amp SA allows the inflow of cell current while reflecting the variation quantity relative to the reference cell current, and executes a current comparison at the time of the inflow of this cell current. One input, in, is supplied with a flow of cell current and the other input, /in, with a flow of reference current.
The above two current mirror circuits operate on the potential V1. This potential V1 is generated by limiting the potential Vpp and the current at the transistor M18. The transistor M18 is provided with the potential Vw at the time of write operation and the potential Vr at the time of read operation. This makes it possible to switch between the potentials on bit lines BL at access operations.
Basic operation of the sense amp SA is described next.
FIG. 22 is a diagram of operating waveforms in the sense amp in the memory system according to the embodiment.
At the start, when the control signal, /act, is lowered from “H” to “L” in a state of a control signal, /se=“H” (step S0 in FIG. 22), a pair of transistors M8 and M9 turns on. As a result, current flows in the sense amp SA.
Subsequently, the control signal, /accREAD, is lowered from “H” to “L” (step S1 in FIG. 22) to supply current into the access bit line BL and the reference bit line RBL through the inputs of input signals ‘in’ and ‘/in’. A difference between the cell current and the reference current flowing at this time is amplified as the drain voltage difference and latched by a pair of transistors M6 and M7, which are cut off after passing through the saturation region from the linear region.
Amplification of the current difference between the cell current and the reference current requires the control signal, /se, to be lowered from ‘H’ to ‘L’ (step S2 in FIG. 22). As a result, the paired transistors M6 and M7 both pass through the saturation region from the linear region and turn off. At that time, a slight difference between the cell current and the reference current causes a timing difference in transition to the saturation region, which is converted into the drain voltage. If the source potential on the transistor M6 is higher, the gate potentials on the transistors M0 and M2 become higher and accordingly the transistors M0 and M2 turn off. If the source potential on the transistor M7 is higher, on the other hand, the gate potentials on the transistors M1 and M3 become higher and accordingly the transistors M1 and M3 turn off. Thus, the drain voltage difference in the pair of transistors M6 and M7 is amplified.
A pair of transistors M10 and M11 is provided with a lowered gate potential in the initial stage of sensing to suppress the conductance, thereby reducing the sense amp current supplied from the supply potential Vdd. As a result, it reflects a cell current difference supplied via a pair of transistors M12 and M13 more strongly in accordance with the state of the sense amp SA.
In the initial stage of sensing, when the balance of the sense amp SA collapses in accordance with the current difference between the cell current and the reference current and then becomes stable, the control signal vLTC is raised from the potential Vrr to the potential Vpp higher than the supply potential Vdd (step S3 in FIG. 22). As a result, the sense amp SA is supplied with the supply voltage to fully swing the output signal ‘out’ to the supply potential Vdd (S4 in FIG. 22). At this time, the control signal /accREAD is raised to break the supply of the cell current and reference current to the sense amp SA.
The pairs of fine-patterned transistors contained in the sense amp SA have variations caused by fluctuations in production steps. Therefore, the variations can be cancelled if current paths are configured by serially connecting as many elements as possible. Then, the sense amp SA uses three pairs of transistors including the pair of transistors M0 and M1, the pair of transistors M8 and M9 and the pair of transistors M10 and M11 to configure the parts between the supply potential Vdd and the input nodes N0 and N1. In particular, the pair of NMOS transistors M10 and M11 suppresses the influence of variations in the pair of PMOS transistors M0 and M1 and the pair of PMOS transistors M8 and M9 contained in a feedback loop in operation of the sense amp SA. Namely, the conductance of NMOS transistors M10 and M11 is suppressed to raise the potentials on the drains and sources of PMOS transistors M0, M1, M8 and M9 located closer to the supply potential Vdd than these transistors M10 and M11, thereby raising the conductance of PMOS transistors M0, M1, M8 and M9. In a word, the conductance of PMOS transistors and NMOS transistors provides an action directing suppression of the influence of variations in respective characteristics. The gates of the pair of NMOS transistors M10 and M11 are supplied with the control signal vLTC. Accordingly, only when the control signal vLTC is amplified, this action becomes larger. Therefore, in the initial stage of sensing, the control signal vLTC is kept low. In the latter half of sensing in which data is settled, the data should be latched fast by elevating the control signal vLTC to raise the conductance of transistors. In the case of FIG. 22, the control signal vLTC is set to the potential Vrr different from the supply potential Vdd until the time immediately before latching after sensing and set to the higher potential Vpp at the time of latching.
The time difference between the fall of the control signal /accREAD (step S1 in FIG. 22) and the fall of the control signal /se (step S2 in FIG. 22) is adjusted so that the sense amp SA starts sensing after the control signal /accREAD falls and the cell current and reference current injected into the sense amp SA are sufficiently reflected on the input current.
The sense amp SA creates a control signal, fin, indicating its own activation period to external. This control signal, fin, is a signal that turns to ‘H’ in the case of /out=‘L’ and /se=‘L’. It is utilized, for example, to separate the bit line BL from the sense amp SA.
The reference input side of the sense amp SA for discriminating multi-value levels is detailed next.
FIG. 23 is a circuit diagram showing a circuit on the reference input side of the sense amp in the memory system according to the embodiment. In the case of FIG. 23, the sense amp SA is ready for 5-level/cell.
The reference input side requires comparison currents corresponding to multi-value levels (5 levels in the case of FIG. 23) as reference currents, which are appropriately switched for use at the time of monitoring the cell state. In addition, the voltage level at the time of write operation differs from that at the time of read operation. Accordingly, it is required to switch between the states of the reference input in accordance with these levels.
All the comparison currents rf1-rf4 fed into the side /in are currents flowing into the sense amp SA, which are generated at the reference bit lines RBL as described above. These comparison currents are not allowed to directly flow into the sense amp SA. The reason is as follows. The way of viewing comparison currents in the case of the sense amp SA used in write operation can be changed from that in the case of read operation. This makes it possible to prevent a cell from making a failed transition when a large voltage or current is given at the time of cell read operation. The comparison currents rf1-rf4 are selected by control signals L1-L4 and the selected current is fed to current mirrors. Current mirrors on the side /in are prepared two having different magnifications. A control signal /WRITE falls at the time of write operation and the reference current is magnified by a and fed into the sense amp SA for comparison with the cell current. A control signal /READ falls at the time of read operation and the reference current is fed at the same magnification into the sense amp SA. The meanings of magnifications at the time of write operation and at the time of read operation are as described above.
When the cell current on the side, in, becomes larger than the comparison current, that is, the cell resistance is made lower, the output signal becomes /out=‘L’.
An access system for selecting one word line WL and simultaneously selecting plural bit lines BL in one MAT is described next using a simple example.
FIG. 24 is a diagram showing a configuration of a current sensing system in the memory system according to the embodiment. FIG. 24 shows two word lines WL<1> and <2> and three bit lines RBL and BL<1> and <2>. Reference bit lines RBL are collectively represented by one.
A word line WL is selected when it is connected to the ground potential Vss via a WL switch controlled by the control signal, from rdec.
A bit line BL is selected by a BL switch. On/off control of the BL switch requires switching in accordance with the sense state and so forth. Therefore, a signal input to the gate of a transistor contained in the BL switch is generated through logic operation. A method of controlling the BL switch is as follows. Namely, a BL switch is always kept off by a control signal, /from cdec<m>, at ‘H’ when the corresponding bit line BL is to be selected. Once the bit line BL is selected as the control signal, /from cdec<m>, turns to ‘L’, the BL switch turns on/off in accordance with logic.
It is assumed here that the bit lines BL<1> and <2> belong to local buses <1> and <2>, respectively. The local buses <1> and <2> are connected to plural bit lines BL, and BL switches select BL<1> and <2> from those bit lines BL. The gates of transistors contained in the BL switches receive the control signals, from cdec<1> and <2>, from a column decoder via inverters, respectively. The power supplies for these inverters are connected to the inverse signals, /out<1> and <2>, of output signals, out<1> and <2>, from the sense amps SA. A circuit of the inverter is shown in A of FIG. 24.
The bit lines BL are connected to the local buses via the BL switches, which are turned on when selected by a control signal, pr. The BL switches are turned off on respective conditions in accordance with control signals, fin<m>, from the sense amps SA.
The reference bit line RBL is connected to a reference local bus via a transistor contained in a RBL switch, which is controlled by a control signal, set/read, so as to turn on at the time of cell set operation and at the time of read operation. A comparison current generated at the reference bit line RBL is converted into a comparison current for multi-values at a reference current conversion unit and fed to several sense amps SA commonly.
A sense amp SA is provided on each local bus. When the BL switch is cut off by the output signal, out, from the sense amp SA, it can stop writing to the bit line BL that has reached a certain current value.
The following description is given to a structure of a memory system including a three-dimensionally structured cell array capable of effectively utilizing the memory system described above.
BL switches, WL switches, sense amps SA and so forth are provided on a semiconductor substrate beneath a MAT (cell array).
Selection lines in a MAT of the cross-point type are led out alternately from the opposite sides of the MAT to relieve the pitch of MAT peripheral circuits. When transistors are formed in the vicinity of the surface of the semiconductor substrate, however, an increase in the number of stacked MATs proportionally increases the formation area of peripheral circuits. The reason is as follows. If the pitch of MAT selection lines cannot be relieved and the peripheral circuits are laid out elongated in the extending direction of selection lines, the peripheral circuits are required by the number of stacked MATs to be accessed individually.
Then, the following description is given to one of methods of solving the problem about the layout of the peripheral circuits.
FIG. 25 is a diagram showing a layout of arrangement regions of vertical lines in a cell array seen from the stacking direction in the memory system according to the embodiment.
The layout described here utilizes no transistors formed on the surface of the semiconductor substrate but utilizes transistors formed three-dimensionally instead. This transistor is a SGT (Surrounding Gate Transistor) having a gate surrounding a conduction channel, or a TFT (Thin Film Transistor) having a conduction channel sandwiched between gates. Poly-Si or an oxide semiconductor such as InGaZn-Oxide formed on the surface of the semiconductor substrate is configured as the conduction channel. The transistors stand in pillar shapes around MATs in large numbers.
FIG. 26 is a diagram showing a cross-section of a transistor in the stacking direction in the memory system according to the embodiment.
The lowermost part of the structure shown in FIG. 26 is a layer of conductor running parallel to the surface of the semiconductor substrate, which is turned to local word lines LWL/local bit lines LBL. A plug is raised on the local word line LWL/local bit line LBL, and a gate-controlled, short pillar-shaped conduction channel is further formed thereon. Around the conduction channel, a conduction layer turned to a gate is formed with an insulator layer sandwiched therebetween. The conduction layer is formed by linking plural gates as a bus of gate lines around MATs along the sides of MATs as shown in FIG. 25. Plural conduction layers are formed and plural conduction layers extend in parallel. On the pillar-shaped conduction channel, a plug is formed. This plug is connected to a pillar-shaped conduction layer serving as a vertical line arranged around the upper MAT. This vertical line is connected to a selection line in a specific MAT of plural stacked MATs.
FIG. 25 shows an example of SGT/TFT conduction channels arranged as even as possible. Plural MATs are stacked from MAT<0> in the lowermost layer in order of MAT<1>, <2>, <3>. Selection lines in each MAT are connected to vertical lines closer to the MAT in order from selection lines in the lower MAT so as not to collide with vertical lines. In the layout of FIG. 25, four selection lines in each MAT are connected to one local word line/local bit line LWL/LBL selectively. The local word line/local bit line LWL/LBL corresponds to the local bus <m> shown in FIG. 24 and so forth. If it is assumed here that plural MATs are not selected simultaneously, the local word line/local bit line LWL/LBL is a common line to all MATs. It is connected to an individual bit line BL or word line WL in a MAT in accordance with a signal level supplied to gate lines around the MAT. The same local word line/local bit line LWL/LBL is connected to four selection lines. As described above, selection lines are led out alternately from the opposite sides in each MAT. Accordingly, eight selection lines on a MAT are narrowed down to one selection line by the layout shown in FIG. 25 and connected to the local word line/local bit line LWL/LBL immediately beneath the MAT. This makes it possible to relieve the pitch of local buses immediately beneath the MAT, thereby facilitating the layout of peripheral circuits such as sense amps SA.
The above description has been given to the cell array that has a structure of stacked cell array layers (MATs) in which intersecting word lines WL and bit lines WL are arranged in parallel with the principal plane of the semiconductor substrate. The following description is given to an example of a MAT (cell array) having a structure of bit lines BL extending vertically relative to the semiconductor substrate. Hereinafter, sometimes, a structure of memory cell layers stacked is referred to as a “stacked structure”, a bit line extending in the vertical direction relative to the semiconductor substrate is represented by a “VBL”, and a structure of a cell array having bit lines VBL is called a “VBL structure”.
FIGS. 27-29 are diagrams showing layouts of the cell array in the memory system according to the embodiment. FIG. 27 shows a layout seen from the stacking direction, and FIGS. 28 and 29 are cross-sectional views in the vertical direction. In addition, a word line (second line) indicated with a thick frame in FIGS. 28 and 29 is a driven word line.
The VBL-structured MAT allows an arrangement of selection-line driver circuits immediately beneath the MAT. Therefore, it is possible to solve the increase in driver circuits around the MAT in accordance with the number of stacked cell array layers, which becomes a problem in a stacked structure. Namely, an arrangement of bit lines VBL (first line) in the vertical direction (third direction) relative to the semiconductor substrate can form driver circuits in a certain layout independent of the number of stacked cell array layers. In the case of the VBL structure, bit lines VBL are arranged vertically relative to the semiconductor substrate. Therefore, the cell structure greatly differs from that in the case of a stacked structure including bit lines BL arranged in parallel with a semiconductor substrate.
In the case of the VBL structure, TFT layers are provided in two layers on the semiconductor substrate immediately beneath the stacked MATs, and conduction paths composed of AND-structured transistors are formed in the vertical direction at bit lines VBL. In the VBL structure, bit lines VBL extending in the vertical direction are formed in pillar shapes and, as orthogonally intersecting therewith, word lines WL are stacked in the direction (first direction) running parallel with the principal plane of the semiconductor substrate. For one bit line VBL, one word line WL is selected at each memory cell layer. Further, even-numbered word lines WL and odd-numbered word lines WL aligned in each memory cell layer are arranged so that they can be selected alternately from the opposite sides of the cell array layer. In each memory cell layer, word lines WL are not selected individually. Accordingly, the area of word-line driver circuits can be reduced to that extent in comparison with the cell array having the stacked structure. Therefore, the area of selection-line driver units can be reduced greatly in comparison with the cell array having the stacked structure. A cell MC is formed at an intersection of a bit line VBL and a word line WL and driven by a voltage/current applied between the bit line VBL and the word line WL. A MAT includes plural TFT layers (transistor layers) stacked between the semiconductor substrate and the formation region of bit lines BL. In each TFT layer, plural TFTs are formed. A bit line VBL is selected by an AND circuit (logic circuit) composed of these TFTs. The selected bit line VBL is connected to a global bit line GBL (third line) extending in the direction (second direction) running parallel with the principal plane of the semiconductor substrate and orthogonally intersecting the extending direction of the word line WL. In the AND circuit composed of TFTs, control signals BSL in two layers for selecting the bit line BL are arranged to form the gate of each TFT in the AND circuit. As shown in FIG. 28, if the same number of TFTs are formed in two TFT layers (transistor layers) immediately beneath the cell array layer, selection of a pair from control signals BSL in two TFT layers makes it possible to select a row of bit lines VBL aligned in the extending direction of word lines WL. In addition, if TFTs are formed fewer in the first-layer TFT layer than those in the second-layer TFT layer, as shown in FIG. 29, the first-layer TFT layer makes it possible to configure the channel width by both surfaces of the TFT and form the gates on both sides. Thus, the first-layer TFT layer makes it possible to form TFTs having larger conductivity than those in the second-layer TFT layer, thereby obtaining larger conductance. A combination of selections of a logic circuit and a word line WL makes it possible to select a row of cells MC along the extending direction of the word line WL. These selected cells MC are driven by a global bit line GBL. Selective driving of the global bit line GBL makes it possible to control the number of cells MC simultaneously selected and write operation/read operation. Also in the case of the VBL structure, for control of the global bit line GBL, the same system for multi-value write operation and read operation as that in the case of the stacked structure can be applied to realize multi-valuing of a memory system having a three-dimensional structure.
The TFT having a gate supplied with the control signal BSL is formed of an oxide semiconductor. The TFT gate width cannot be made larger structurally and accordingly cells are desirable if they are of the voltage-driven type and resistance variable.
In a word, the VBL structure is more suitable for the voltage-driven ion memory and so forth than NT cells and so forth requiring current for phonons as is said. In the case of the use of the ion memory, the center of the pillar-shaped bit line VBL can be formed of a metal serving as an ion source, for example, Ag.
In the case of the VBL structure, cell MC groups along bit lines VBL are different in characteristic little by little from each other. Accordingly, variations arise in the conditions of setting multi-value levels at cells MC. Therefore, the above-described data storage on a pair-cell basis becomes effective.
FIG. 30 is an equivalent circuit diagram of a VBL-structured cell array in the memory system according to the embodiment. In FIG. 30, TFTs are used as transistors.
As shown in FIG. 30, when the bit line VBL is driven by the control signal BSL and the word line WL shown with chain lines, the cell MC is electrically connected to the global bit line GBL. In the stacked TFTs, the number of nodes is reduced every time passing through logic, and accordingly the number of TFTs can be changed at every TFT layer. In the case of FIG. 30, the number of TFTs in the lower-layer TFT layer closer to the global bit line GBL is designed to become lower so as to increase the effective size of TFTs in the lower-layer TFT layer to gain lager conductance. Depending on the convenience of the design, the number of TFTs in the upper-layer TFT layer may be reduced.
The above description has been given to raising the information density by cell multi-valuing and the configuration of the corresponding specific memory system. In such the memory system, error correction becomes important in the presence of failed setting of a multi-value level. Then, the following description is given to ECC processing using an LMC capable of processing the error correction strongly and fast.
FIG. 31 is a functional block diagram of the memory system according to the embodiment.
This memory system comprises a CPU, a memory controller, and a memory device composed of multi-value storable cells and so forth. In FIG. 31, the memory controller is a separate chip from the memory device though it may be mounted on the same chip as that for the memory device. The CPU sends a command to the memory controller. The memory controller receives this command and sends the corresponding command to the memory device to control the memory device. The CPU, the memory controller and the memory device are controlled by clocks. The clocks can be supplied to the CPU, the memory controller and the memory device commonly though they may be supplied via the CPU and the memory controller to the control-targeted memory device.
M bits of binary data input to the memory controller via the data bus are converted into the quantity in a finite field Zp, that is, a data processing system in the memory controller. Batch-processed binary data, in the presence of a relation 2h-1<p<2h and in the presence of a relation 2g-1<q<2g with successive primes q and p (p<q), becomes a set of M bits that satisfies qg≦M<ph. This is a restriction determined by LMC processing, and the relations among specific M, p and so forth are detailed later.
Binary data is processed at every M bits in the memory controller. At the start, binary data is converted into a p-adic expression in Zp at a ‘binary to p-adic decode’ circuit block. Then, the values on digits of the p-adic expression are applied to create an LMC. At that time, binary data is regarded as a 2h-adic number divided by h bits and converted into a p-adic number.
ECC processing is executed in an ‘LMC ECC system’ circuit block.
Subsequently, coded elements in Zp are related to levels of a multi-valued cell composed of a pair cell in the memory device and subjected to data conversion so that Lee metrics in Zp correspond to distances between cell levels. This conversion is executed in a ‘p-adic < > MLC binary mapping’ circuit block. In this ‘p-adic < > MLC binary mapping’ circuit block, elements in Zp are converted into pieces of data corresponding to multi-values of a cell and stored in a page buffer. When the page buffer is filled with data, these pieces of data are transferred from the memory controller to the memory device and written in pair cells. These operations are controlled by a command sent from a ‘control’ circuit block to the memory device in accordance with the command input to the memory controller. The page buffer is configured reflecting the relation between multi-value levels of a cell and pages. The elements in Zp are stored as multi-value levels of a cell after data is transferred from the page buffer to the memory device.
In reading data from the memory device, data corresponding to the multi-value level of the cell is read out in accordance with the command received from the memory controller, and this data is transferred to a page buffer in the memory controller and held therein. The data held in the page buffer is converted into a numeral in Zp at the ‘p-adic < > MLC binary mapping’ circuit block. The converted data is subject to error correction at the ‘LMC ECC system’ circuit block and restored to the correct LMC, and then converted into data expressed in a p-adic number. Thereafter, the data expressed in a p-adic number is converted into M bits of binary data at the ‘p-adic to binary decode’ circuit block and provided to external from the memory controller.
In the above ECC processing, simplification of computation processing at the ‘LMC ECC system’ circuit block and the computation speed become important. Then, the following description is given to one of methods for making simpler the computation process of ECC processing.
At the start, an LMC is briefly described.
Symbols of a code C are representative elements in Zp, or integers cj of 0 to p−1, as shown in Expression 1.

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

The metrics of these integers are represented by Lee metrics |cj|, and all Lee metrics |cj| are represented by integers of p/2 or below. Lee metrics |cj| are defined as in Expression 2.

0≦cj<p/2:|cj|=cj 

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

As the code C can be considered a row of n=p−1 symbols cj, it can be represented by C=(c1, c2, . . . , cp-1) A metric w(C) of the code C can be defined as the sum of Lee metrics |cj| of the symbols as in Expression 3.

w(C)=|c1|+|c2|++|cp-1|  [Expression 3]

The distance between codes can be defined by the sum of Lee metrics of the differences between the symbols corresponding to the codes. Here, two symbols c and y have a difference (Lee distance) dL (c, y), which is given in Expression 4.

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

In this case, the LMC 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 5 and that can correct γ−1=E 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
          ⁢
          
            
          
          ⁢
          5
        
        ]
      
    
  




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. If γ=n−k=3, then dL(C)≧2γ=6, which makes it possible to obtain a code capable of correcting the variation total sum of Lee metrics if it is equal to γ−1=ε=2 or below.

For the purpose of generating the LMC thus configured, input-converted data is represented by a k-digit, p-adic number. Numerals on digits of this p-adic number correspond to the elements in Zp and therefore can be used as a data word X of LMC to obtain the code C through an operation C=XG using the generator matrix G. The obtained code is stored in the memory. Information about the error caused in the numeral in Zp stored is used as a code Y of LMC read out of the memory to obtain a syndrome through an operation S=YHt (Ht is a transpose of H) so that the position and quantity of the error can be computed to correct the error.
The data word X is obtained as X=CG−1 from the error-corrected code expression C where G−1 is generally as in Expression 6.



  
    
      
    
    ⁢
    
      [
      
        Expression
        ⁢
        
          
        
        ⁢
        6
      
      ]
    
  




  
    
      G
      
        -
        1
      
    
    =
    
      
        (
        
          p
          -
          1
        
        )
      
      ⁡
      
        [
        
          
            
              
                1
                
                  -
                  1
                
              
            
            
              
                1
                
                  -
                  2
                
              
            
            
              •
            
            
              
                1
                
                  
                    -
                    k
                  
                  -
                  1
                
              
            
            
              
                1
                
                  -
                  k
                
              
            
          
          
            
              
                2
                
                  -
                  1
                
              
            
            
              
                2
                
                  -
                  2
                
              
            
            
              •
            
            
              
                2
                
                  
                    -
                    k
                  
                  -
                  1
                
              
            
            
              
                2
                
                  -
                  k
                
              
            
          
          
            
              •
            
            
              •
            
            
              •
            
            
              •
            
            
              •
            
          
          
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  -
                  1
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  -
                  2
                
              
            
            
              •
            
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  
                    -
                    k
                  
                  -
                  1
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  -
                  k
                
              
            
          
          
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  -
                  1
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  -
                  2
                
              
            
            
              •
            
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  
                    -
                    k
                  
                  -
                  1
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  
                    -
                    k
                  
                  ,
                
              
            
          
        
        ]
      
    
  



In the case of ε=2, G and H are as in Expression 7.




  
    
      
        
          G
          =
          
            [
            
              
                
                  1
                
                
                  2
                
                
                  •
                
                
                  
                    (
                    
                      p
                      -
                      2
                    
                    )
                  
                
                
                  
                    (
                    
                      p
                      -
                      1
                    
                    )
                  
                
              
              
                
                  
                    1
                    2
                  
                
                
                  
                    2
                    2
                  
                
                
                  •
                
                
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                    2
                  
                
                
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    2
                  
                
              
              
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  •
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  
                    1
                    
                      p
                      -
                      4
                    
                  
                
                
                  
                    2
                    
                      p
                      -
                      4
                    
                  
                
                
                  •
                
                
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                    
                      p
                      -
                      4
                    
                  
                
                
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    
                      p
                      -
                      4
                    
                  
                
              
            
            ]
          
        
        ⁢
        
          

        
        ⁢
        
          H
          =
          
            [
            
              
                
                  1
                
                
                  1
                
                
                  •
                
                
                  1
                
                
                  1
                
              
              
                
                  
                    1
                    1
                  
                
                
                  
                    2
                    1
                  
                
                
                  •
                
                
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                    1
                  
                
                
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    1
                  
                
              
              
                
                  
                    1
                    2
                  
                
                
                  
                    2
                    2
                  
                
                
                  •
                
                
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                    2
                  
                
                
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    2
                  
                
              
            
            ]
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          7
        
        ]
      
    
  




From a data word A composed of k=p−4 elements in Zp, a syndrome created by the code C=AG is created through S=YHt.

The following description is given to a relational expression required for a specific circuit in the case of γ=ε+1=3, ε=2.
The binary data of the code C held in the memory device includes a collection of p−1 symbols. The code symbols themselves cause variations when suffer various disturbances. Then, the code C is restored from the code Y in decoding. Prior to the decoding, a syndrome is sought at the start. Each symbol is represented by h bits as binary-expressed data.
The syndrome can be sought as elements S0, S1, S2 shown in Expression 8 through an operation S=YHt using a syndrome matrix H where yj=aj+ej.




  
    
      
        
          
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  p
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  1
                
                ⁢
                
                  c
                  j
                
              
            
            =
            
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  k
                
                ⁢
                
                  
                
                ⁢
                
                  
                    a
                    
                      i
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      ∑
                      
                        j
                        =
                        1
                      
                      
                        p
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        (
                        j
                        )
                      
                      
                        l
                        +
                        i
                      
                    
                  
                
              
              =
              
                
                  0
                  ⇒
                  
                    S
                    1
                  
                
                =
                
                  
                    
                      ∑
                      
                        j
                        =
                        1
                      
                      
                        p
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        
                          (
                          j
                          )
                        
                        1
                      
                      ⁢
                      
                        y
                        j
                      
                    
                  
                  =
                  
                    
                      ∑
                      
                        j
                        =
                        1
                      
                      
                        p
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        
                          (
                          j
                          )
                        
                        1
                      
                      ⁢
                      
                        e
                        j
                      
                    
                  
                
              
            
          
          ,
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              S
              0
            
            =
            
              Σ
              ⁢
              
                
              
              ⁢
              
                e
                j
              
            
          
        
        ⁢
        
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          8
        
        ]
      
    
  




The generator matrix G and the syndrome matrix H are configured to satisfy GHt=0 (mod p). Accordingly, a substitution of Y=C+E yields S=EHt. If E=(e1, e2, . . . , ep-1), then a syndrome S0 corresponds to the total sum of errors in code symbols as can be found. Only the syndromes S provide information on errors and, on the basis of the 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 two sets J+ and J− as in Expression 9.

J+={jε(1,2,,p−1);ej<p/2}

J−={jε(1,2,,p−1);ej<p/2}  [Expression 9]

Namely, they are classified into J+ that is an arrangement of the positions j of the code symbols cj in the case of the symbol error quantity ej<p/2, and J− that is an arrangement of the positions j of the code symbols cj in the case of the symbol error quantity ej>p/2. Polynomials λ(x), V(x) in the Galois field GF(p) are configured as in Expression 10 on the basis of these sets.





  
    
      
        
          
            Λ
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              ∏
              
                j
                ∈
                
                  •
                  +
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                (
                
                  1
                  -
                  jx
                
                )
              
              
                e
                j
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            V
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              ∏
              
                j
                ∈
                
                  •
                  -
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                (
                
                  1
                  -
                  jx
                
                )
              
              
                p
                -
                
                  e
                  j
                
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          10
        
        ]
      
    
  




Thus, the polynomial λ(x) is a polynomial that has a reciprocal number of the position j of an error symbol in J+ as a root and that has a Lee metric ej of that code 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−ej, of that code symbol as the multiplicity of the root. Decoding is a process of finally configuring these polynomials only from the information on the syndrome S1 and solving them, thereby obtaining information on errors. In a word, it is required to seek a relation among these polynomials λ(x), V(x) and the syndrome S1.
Subsequently, as shown in Expression 11, when it is configured with a series polynomial having each syndrome S1 on a coefficient of the corresponding degree, it is represented by a rational polynomial having the error quantity ej, the position j and the value of the symbol.




  
    
      
        
          S
          ⁡
          
            (
            x
            )
          
        
        =
        
          
            
              ∑
              
                l
                =
                1
              
              ∞
            
            ⁢
            
              
            
            ⁢
            
              
                S
                l
              
              ⁢
              
                x
                1
              
            
          
          =
          
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  p
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  e
                  j
                
                ⁢
                
                  
                    ∑
                    
                      l
                      =
                      1
                    
                    ∞
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      (
                      jx
                      )
                    
                    1
                  
                
              
            
            =
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  p
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  e
                  j
                
                ⁢
                
                  jx
                  
                    1
                    -
                    jx
                  
                
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          11
        
        ]
      
    
  




From Expression 11, a relational equation shown in Expression 12 can be established among the polynomials λ(x), V(x) and the syndrome S(x).





  
    
      
        
          
            (
            
              
                Λ
                ⁡
                
                  (
                  x
                  )
                
              
              
                V
                ⁡
                
                  (
                  x
                  )
                
              
            
            )
          
          ⁢
          
            S
            ⁡
            
              (
              x
              )
            
          
        
        =
        
          -
          
            
              x
              ⁡
              
                (
                
                  
                    Λ
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  
                    V
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
                )
              
            
            ′
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          12
        
        ]
      
    
  




Subsequently, the relational equation shown in Expression 12 is utilized to seek the polynomials λ(x), V(x) from the syndrome S(x).
The syndrome S(x) is used to find a polynomial Ψ(x) at a degree of (γ−1) or lower shown in Expression 13.




  
    
      
        
          
            
              Ψ
              ⁡
              
                (
                x
                )
              
            
            ⁢
            
              S
              ⁡
              
                (
                x
                )
              
            
          
          ≡
          
            
              -
              x
            
            ⁢
            
              
            
            ⁢
            
              
                Ψ
                ′
              
              ⁡
              
                (
                x
                )
              
            
            ⁢
            
              
            
            ⁢
            
              (
              
                mod
                ⁢
                
                  
                
                ⁢
                
                  x
                  3
                
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              Ψ
              ⁡
              
                (
                x
                )
              
            
            =
            
              1
              +
              
                
                  ∑
                  
                    l
                    =
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    ψ
                    1
                  
                  ⁢
                  
                    x
                    1
                  
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              ψ
              j
            
            =
            
              
                -
                
                  1
                  j
                
              
              ⁢
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  j
                
                ⁢
                
                  
                
                ⁢
                
                  
                    ψ
                    
                      j
                      -
                      1
                    
                  
                  ⁢
                  
                    S
                    i
                  
                
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          13
        
        ]
      
    
  




In an expansive expression of the polynomial Ψ(x), a coefficient ψj can be sought, from a comparison between the coefficients at the homogeneous degree on both sides of the expression shown in Expression 13, through an iterative method using the syndrome Si and an already-determined coefficient ψj-1. The coefficients ψ0−ψ2 of the polynomial ψ(x) are sought from the syndrome S=(S0, S1, S2). The results are shown in Expression 14.

ψ0=1

ψ1=−S1 

ψ2=−(ψ1S1+ψ0S2)/2=(S12−S2)/2  [Expression 14]

This polynomial Ψ(x) is a polynomial equivalent to λ(x)/V(x) while the polynomials λ(x), V(x) are given key conditions shown in Expression 15. Therefore, they can be sought through a Euclid iterative method applied to x3 and the polynomial Ψ(x) to remove constant multiples.

V(x)Ψ(x)≡λ(x)(mod x3)

deg λ(x)+deg V(x)<3

λ(x) and V(x) are irreducible

deg λ(x)−deg V(x)≡S0(mod p)  [Expression 15]

Therefore, if the polynomial Ψ(x) can be configured from the syndrome S=(S0, S1, S2), the syndrome S0 can be used as the stop condition on the iterative method to seek the polynomials λ(x), V(x). Namely, the iterative method is applied to seek the polynomials λ(x), V(x) from a set of (S0, Ψ(x)).
A Euclid iterative method applicable to x3 and Ψ(x) is described next.
The following description is given to a method for deriving polynomials λ(x) and v(x) that satisfy a congruence equation, v(x)Ψ(x)≡λ(x) (mod x3), using the Euclidean iterative method, in accordance with the stop condition, deg λ(x)−deg v(x)≡S0 (mod p). Of the polynomials λ(x) and v(x) derived, one that satisfies deg λ(x)+deg v(x)<3 is the error searching polynomial.
The Euclidean iterative method is a method for deriving functions f0, f1, . . . , fn in turn using divisions of polynomials. These quantities have relations shown in Expression 16.




  
    
      
        
          
        
        ⁢
        
          
            
              
                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
                            3
                          
                        
                        )
                      
                    
                  
                
              
            
            ,
            
              

            
            ⁢
            
              
            
            ⁢
            
              
                f
                0
              
              =
              
                x
                3
              
            
            ,
            
              

            
            ⁢
            
              
            
            ⁢
            
              
                f
                1
              
              =
              Ψ
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          16
        
        ]
      
    
  




In this case, increases in n inevitably find fn having a smaller degree than the previous degrees at a certain n as shown in Expression 16. This fact leads to the condition indicating the presence of the possibility of deriving a solution that satisfies the stop condition in the Euclidean iterative method.
In particular, with sequential introductions of pn and qn from the quotient polynomials kn obtained in the process of divisions, these polynomials can satisfy simple relations. Therefore, fn can be represented by f0, f1, pn−1 and qn−1. Namely, fn=(−1)n(qn−1f0−pn−1f1) is established such that the degrees of pn−1 and qn−1 increase as the degree of fn decreases. Because the degree of pn−1 increases as the degree of fn decreases in this way, the difference between degrees decreases inevitably to satisfy the stop condition.
Generally, in the Euclidean iterative method, fn=knfn+1+fn+2 utilizes the sequential decreases in degree in relation to divisions while kn assumes a first- or zero-degree equation here and accordingly the degree cannot decrease always. Rather, the degree may increase but cannot exceed the degree of f0. In any way, if the relation about the factorization of the above polynomial Ψ(x) is established, the relation shown in Expression 16 can be established. Therefore, it is possible to finally lower the degree to satisfy the stop condition on the iteration.
When substitutions of f0=x3, f1=Ψ(x) are made to create a congruence equation at x3, the stop condition on the iteration comes to deg fn−deg pn−1=S0 (mod 13). With respect to n that satisfies this stop condition, if deg fn+deg pn−1<3, then substitutions of λ(x)=fn, V(x)=pn−1 are possible.
On the other hand, if it is not possible to achieve such the degree relation, it means the occurrence of an error that cannot satisfy the error-correctable condition.
The use of the above-described Euclid iterative method makes Ψ(x) become a second-order polynomial in the case of ε=2. As the polynomial of Ψ(x) has a smaller degree in this way, it is possible to compute operation results of Ψ(x) for the coefficients of a specific easy general polynomial. The results are shown in Expression 17.

Case 1:

ψ2≠0ψ2≠ψ12 

f0=x3 

f1=ψ2x2+ψ1x+1

f2={(ψ12−ψ2)/ψ22}x+ψ1/ψ22 

f3=ψ22/(ψ12−ψ2)2 

f4=0

p−1=0

p0=1

p1=(1/ψ2)x−ψ1/ψ22x+1

p2={ψ22/(ψ12−ψ2)}x2/−{(ψ1ψ2/(ψ12−ψ2)2}+x+ψ22/(ψ2−ψ2)2 

p3={(ψ12−ψ2)2/ψ22}x3 

Case 2:

ψ2≠0 ψ2=ψ12 

f0=x 

f1=ψ2x2+ψ1x+1

f2=ψ1/ψ22 

f3=0

p−1=0

p0=1

p1=(1/ψ2)x−ψ1/ψ22 

p2={ψ22/ψ1}x3 

Case 3:

ψ1≠0ψ2=0

f0=x3 

f1=ψ1x+1

f2=−1/ψ12 

f3=0

p−1=0

p0=1

p1=(1/ψ1)x2−(1/ψ12)x+1/ψ13 

p2=−ψ13x3 

Case 4:

ψ1=0ψ2=0

f0=x 

f1=1

f2=0

p−1=0

p0=1

p1=x3  [Expression 17]

When substitutions of f0=x3, f1=Ψ(x)=1+ψ1x+ψ2x2 are made to seek polynomials using the Euclidean iterative method, four cases shown in Expression 17 arise in accordance with the conditions on coefficients of Ψ(x). The conditions in these cases depend on the presence/absence of divisions by zero. From the polynomials obtained at computation processes in the cases, a pair of f(x) and p(x) that satisfies the key condition shown in Expression 15 is selected to seek λ(x) and v(x). A specific method for selecting a pair of f(x) and p(x) is described later.
The same method as the above-described one can be applied to seek a fourth-degree and a third-degree polynomial in the case of ε=3 or a polynomial in the case of a higher ε as well. In this case, however, as the case classification and so forth are complicated, the complexity becomes equal to that in the case of the clock-operated circuit system that realizes the conventional Euclid iterative method as it is. Therefore, the above-described method is useful as fast direct computations in the case of ε=2.
The above description has been given to the LMC, the ECC processing, and the generation of the error searching polynomial using the Euclid method in the case of ε=2 in relation to the embodiment. Then, the subsequent description is given to the conversion at the entrance of a p-adic Zp world in ECC processing, encoding of data input to the memory system as Zp data, decoding of the code read from the memory system, and the conversion at the exit of the p-adic Zp world. It is also given to a specific example of the circuit for realizing these processing.
A “binary world” is an environment for processing an operation and so forth with binary-expressed data while a “p-adic Zp world” is an environment for processing an operation and so forth with data expressed by numerals in Zp.
FIG. 32 is a flow chart of data processing in the memory system according to the embodiment.
A Zp-determining prime is denoted with p. The minimum number of bits required for a binary expression of p is denoted with h. The number of digits in a 2h-adic number expression of batch-processed data in the binary world is denoted with k−1. The total quantity of Lee metrics of correctable errors is denoted with ε=γ−1=2. In addition, n=p−1, k=n−γ=p−4 are given, and (k−1)h bits of data are subject to ECC processing in batch.
At the start, at the entrance of the p-adic Zp world in step S110, data Dk-1=(d0, d1, . . . , dk-2) expressed in a (k−1)-digit, 2h-adic number is converted into data λ=(a0, a1, . . . ak-1) expressed by k=p−4 elements in Zp. Dk-1 is composed of k−1 pieces of h-bit data. The maximum number expressed by h bits is equal to max(h)=2h−1. When the number of multi-value levels of a cell is denoted with L, a relation can be established as max(h−1)+1≦p<max(h)≦L.
Subsequently, at step S120, A=(a0, a1, . . . ak-1) composed of k=p−4 numerals a0 to ap-5 in Zp is multiplied by a generator matrix G to generate a code C composed of n=p−1 code symbols c1 to cp-1. A code symbol cj is as shown in Expression 18.




  
    
      
        
          C
          j
        
        =
        
          
            ∑
            
              i
              =
              0
            
            
              p
              -
              5
            
          
          ⁢
          
            
          
          ⁢
          
            
              
                (
                j
                )
              
              
                i
                +
                1
              
            
            ⁢
            
              a
              i
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          18
        
        ]
      
    
  




Subsequently, at step S130, the code C is written in a cell array such that the code symbols c1 to cp-1 are associated with multi-value levels of a cell.
Subsequently, at step S140, the code stored and held in the cell array is read out. The read data is a code Y derived from the code C possibly having any error.
Subsequently, at step S150, the code Y is decoded. In decoding, an LMC-using ECC is applied to correct the error in the code Y to restore the code C. Thereafter, based on A=CG−1, data A is restored from the code C. The process of error correction of the code Y is detailed later.
Finally, at the exit of the p-adic Zp world in step S160, binary-expressed data Dk-1 is derived from the data A.
Next, decoding at step S150 shown in FIG. 32 is detailed.
In decoding, ECC processing for correction of errors in an LMC is executed mainly.
FIG. 33 is a flow chart of decoding in the memory system according to the embodiment.
As described above, at step S140, the code Y is read from the cell array. When the error contained in the code Y=(y1, y2, . . . , yp-1) is denoted with E=(e1, e2, . . . , ep-1), the code Y can be represented by Y=C+E.
In decoding, at the start, at step S141, from the code Y=(y1, y2, . . . , yp-1) and S=YHt, a syndrome S=(S0, S1, S2) is computed. A syndrome component S1 is as in Expression 19.




  
    
      
        
          S
          1
        
        =
        
          
            
              ∑
              
                j
                =
                1
              
              
                p
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              
                
                  (
                  j
                  )
                
                1
              
              ⁢
              
                y
                j
              
            
          
          =
          
            
              ∑
              
                j
                =
                1
              
              
                p
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              
                
                  (
                  j
                  )
                
                1
              
              ⁢
              
                e
                j
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          19
        
        ]
      
    
  




Here, as S0=Σej, in the case of S≠0 and |S0|>2, errors have the total quantity of Lee metrics equal to 3 or more and are uncorrectable. Therefore, this case is processed as no solution. The case of S=0 is processed as no error. In other cases, the flow goes to subsequent step S142.
Subsequently, at step S142, for the upper limit, ε=2, of the number of correctable code symbols, a solution searching polynomial Ψ(x)=(1, ψ1, ψ2) is derived from syndrome components S0, S1 and S2 obtained at step S141. Ψ(x) is as shown in Expression 20.




  
    
      
        
          
            Ψ
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              1
              +
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  2
                
                ⁢
                
                  
                
                ⁢
                
                  
                    Ψ
                    j
                  
                  ⁢
                  
                    x
                    j
                  
                
              
            
            =
            
              1
              +
              
                
                  ψ
                  1
                
                ⁢
                x
              
              +
              
                
                  ψ
                  2
                
                ⁢
                
                  x
                  2
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            ψ
            0
          
          =
          
            
              1
              ⁢
              
                

              
              ⁢
              
                ψ
                1
              
            
            =
            
              -
              
                S
                1
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            ψ
            2
          
          =
          
            
              
                -
                
                  (
                  
                    
                      
                        ψ
                        1
                      
                      ⁢
                      
                        S
                        1
                      
                    
                    +
                    
                      
                        ψ
                        0
                      
                      ⁢
                      
                        S
                        2
                      
                    
                  
                  )
                
              
              /
              2
            
            =
            
              
                (
                
                  
                    S
                    1
                    2
                  
                  -
                  
                    S
                    2
                  
                
                )
              
              /
              2
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          20
        
        ]
      
    
  




Subsequently, at step S143, it is diverged based on ψ1 and ψ2 into three cases matching to the solution searching polynomial Ψ(x) obtained through the Euclid method and the key conditions, and further diverged in each case based on S0 to obtain a solution. Three cases are as shown in Expression 21.

Case 1:

ψ2≠0 ψ2≠ψ12 

S0≡2:f1=ψ2x2+ψ1x+1=0

S0≡0:f2={(ψ12−ψ2)/ψ22}x+ψ1/ψ22=0,p1=(1/ψ2)x−ψ1/ψ22=0

S0≡2:

p2={ψ22/(ψ12−ψ2)}x2−{ψ1ψ22/(ψ12−ψ2)2}x+ψ22/(ψ12−ψ2)2=0

Case 2:

ψ2≠0 ψ2=ψ12 

S0≡2:f1=ψ2x2+ψ1x+1=0

S0≡−1:p1=(1/ψ2)x−ψ1/ψ22=0

Case 3:

ψ1≠0 ψ2=0

S0≡1:f1=ψ1x+1=0

S0≡−2:p1=(1/ψ1)x2−(1/ψ12)x+1/ψ13=0  [Expression 21]

At step S143, if the condition of divergences is not applicable, or if the diverged solution searching polynomial Ψ(x) has no solution, it is not possible to find any solution at ε=2. In this case, errors are uncorrectable, and accordingly decoding is stopped.

Subsequently, at step S144, a solution r obtained at step S143 is used to restore the correct code C. When the position of a component y of the error-containing code Y is denoted with t=r−1, and the error quantity is denoted with et, the correct code C can be restored from ct=yt−et.
Finally, at step S145, the right inverse matrix G−1 of the generator matrix G is used to derive an element aj in Zp from λ=CG−1. Thus, data A=(a0, a1, . . . , ak-1) is restored as k=p−4 symbols.
Next, ECC processing in the case of ε=2 is described. A system described herein can be mounted on a chip by processing ECC asynchronously to realize fast processing and simplification.
FIG. 34 is a block diagram of ECC processing in the memory system according to the embodiment.
Data input to the controller is binary data D having sets of M=h(k−1)=h(p−5) bits. A M-bit, binary-expressed number is converted at a Zp conversion block into data A having digits composed of elements in Zp. The data A is converted at a ×G block into an LMC code C and written in a multi-valued memory device (cell array) from the memory controller.
The data read from the memory device is an LMC code Y, which contains errors caused by failed identification of multi-value levels. The code Y is restored at the following processing blocks to an errorless LMC and further restored to binary data D finally.
At the start, operation processing at an S=YHt block is applied to derive a syndrome from the code Y. If the Lee metric of S0 derived at this operation processing is larger than 2, there are 3 or more individual error code components surely. In this case, error correction may not be achieved through the method of solving in the case of ε=2. Therefore, an NG signal is provided to external and an error-uncorrected code Y is sent directly to the output side.
In addition, if the syndrome vector is S=0, no error arises. Accordingly, the code Y is sent directly to the output side as expected.
In the case of other syndromes, the polynomials λ(x) and v(x), which can be derived from the polynomial Ψ(x) and x3 through the Euclid iteration method, are directly derived by case classification of conditions on coefficients of Ψ(x) regardless of the iteration method. Therefore, the polynomial Ψ(x) is computed from the syndrome S=(S0, S1, S2) to obtain a solution in accordance with the case classification of conditions.
The process of deriving a solution of the equation is diverged based on ψ1 and ψ2 into three cases as shown in Expression 21, and further diverged based on the value of S0 at every case. If no solution is found in each case, there are errors other than ε=2. This case is processed as no solution or NG, and an NG signal is provided. In this case, the code Y is sent directly to the output side as expected.
If solutions of the equation can be found, on the other hand, the position of the error component and the error quantity are derived from these solutions. Namely, if it is possible to obtain a root r and the multiplicity n, the position t=r−1 and the error et can be derived. Then, the derived error et is used in ct=yt−et to restore the code C.
The restored code C is converted at a ×G−1 block into elements in Zp on digits of a p-adic number, and further converted at a binary conversion block into binary data D, which is provided to external.
Next, a specific computation process is shown and described along the flow of ECC processing described with reference to FIG. 34.
The process of creating data to be written in a cell array includes computations for creating a code C from symbols of data A. A specific example thereof is shown in Expressions 22-25.




  
    
      
        
          
        
        ⁢
        
          
            
              m
              
                2
                ⁢
                k
              
            
            ≡
            
              
                
                  (
                  
                    p
                    -
                    m
                  
                  )
                
                
                  2
                  ⁢
                  k
                
              
              ⁢
              
                
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              p
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              m
              
                
                  2
                  ⁢
                  k
                
                +
                1
              
            
            ≡
            
              
                -
                
                  
                    (
                    
                      p
                      -
                      m
                    
                    )
                  
                  
                    
                      2
                      ⁢
                      k
                    
                    +
                    1
                  
                
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              p
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          22
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            C
            =
            AG
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            G
            =
            
              [
              
                
                  
                    1
                  
                  
                    2
                  
                  
                    •
                  
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                  
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                  
                
                
                  
                    
                      1
                      2
                    
                  
                  
                    
                      2
                      2
                    
                  
                  
                    •
                  
                  
                    
                      
                        (
                        
                          p
                          -
                          2
                        
                        )
                      
                      2
                    
                  
                  
                    
                      
                        (
                        
                          p
                          -
                          1
                        
                        )
                      
                      2
                    
                  
                
                
                  
                    
                      
                    
                  
                  
                    
                      
                    
                  
                  
                    •
                  
                  
                    
                      
                    
                  
                  
                    
                      
                    
                  
                
                
                  
                    
                      1
                      
                        p
                        -
                        4
                      
                    
                  
                  
                    
                      2
                      
                        p
                        -
                        4
                      
                    
                  
                  
                    •
                  
                  
                    
                      
                        (
                        
                          p
                          -
                          2
                        
                        )
                      
                      
                        p
                        -
                        4
                      
                    
                  
                  
                    
                      
                        (
                        
                          p
                          -
                          1
                        
                        )
                      
                      
                        p
                        -
                        4
                      
                    
                  
                
              
              ]
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          23
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              C
              j
            
            =
            
              
                
                  ∑
                  
                    i
                    =
                    0
                  
                  
                    p
                    -
                    5
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      (
                      j
                      )
                    
                    
                      i
                      +
                      1
                    
                  
                  ⁢
                  
                    a
                    i
                  
                
              
              =
              
                
                  
                    ∑
                    
                      i
                      =
                      0
                    
                    
                      p
                      -
                      5
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        (
                        j
                        )
                      
                      
                      
                        i
                        +
                        1
                      
                      
                        e
                        
                    
                    ⁢
                    
                      a
                      i
                    
                  
                
                +
                
                  
                    ∑
                    
                      i
                      =
                      1
                    
                    
                      p
                      -
                      4
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        (
                        j
                        )
                      
                      
                      
                        i
                        +
                        1
                      
                      
                        o
                        
                    
                    ⁢
                    
                      a
                      i
                    
                  
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              q
              j
            
            =
            
              
                ∑
                
                  i
                  =
                  0
                
                
                  p
                  -
                  5
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  
                  
                    i
                    +
                    1
                  
                  
                    e
                    
                
                ⁢
                
                  a
                  i
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
              q
              
                p
                -
                j
              
            
            =
            
              
                
                  ∑
                  
                    i
                    =
                    0
                  
                  
                    p
                    -
                    5
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      (
                      
                        p
                        -
                        j
                      
                      )
                    
                    
                    
                      i
                      +
                      1
                    
                    
                      e
                      
                  
                  ⁢
                  
                    a
                    i
                  
                
              
              =
              
                
                  -
                  
                    
                      ∑
                      
                        i
                        =
                        0
                      
                      
                        p
                        -
                        5
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        
                          (
                          j
                          )
                        
                        
                        
                          i
                          +
                          1
                        
                        
                          e
                          
                      
                      ⁢
                      
                        a
                        i
                      
                    
                  
                
                =
                
                  -
                  
                    q
                    j
                  
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              r
              j
            
            =
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  p
                  -
                  6
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  
                  
                    i
                    +
                    1
                  
                  
                    o
                    
                
                ⁢
                
                  a
                  i
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              r
              
                p
                -
                j
              
            
            =
            
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  
                    p
                    -
                    6
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      (
                      
                        p
                        -
                        j
                      
                      )
                    
                    
                    
                      i
                      +
                      1
                    
                    
                      o
                      
                  
                  ⁢
                  
                    a
                    i
                  
                
              
              =
              
                
                  
                    ∑
                    
                      i
                      =
                      1
                    
                    
                      p
                      -
                      6
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        (
                        j
                        )
                      
                      
                      
                        i
                        +
                        1
                      
                      
                        o
                        
                    
                    ⁢
                    
                      a
                      i
                    
                  
                
                =
                
                  r
                  j
                
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          24
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            j
            <
            
              p
              /
              2
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              c
              j
            
            =
            
              
                q
                j
              
              +
              
                r
                j
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              c
              
                p
                -
                j
              
            
            =
            
              
                -
                
                  q
                  j
                
              
              +
              
                r
                j
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          25
        
        ]
      
    
  




As shown in Expression 22, an even-power of an element m in Zp is congruent with an even-power of a Lee metric while an odd-power of the element m in Zp is equal to a minus element of an odd-power of the Lee metric. This relation is utilized in the above computations to reduce by half the computational complexity for the element.
The computation of code symbols derived from the relation C=AG shown in Expression 23 is decomposed into an even sum Σe and an odd sum Σ0 as shown in Expression 24, which are denoted with qj and rj, respectively. In this case, symbols of a calculation code up to j<p/2 can be derived as cj=qj+rj, cp-j=−qj+rj as shown in Expression 25. Therefore, a decoding table of powers of elements can be used to simplify computations.
Specific computation blocks are described next.
FIGS. 35 and 36 are circuit diagrams of computation blocks in the memory system according to the embodiment. FIGS. 35 and 36 show code symbol component computation blocks for deriving components qj and rj of a code symbol cj to be stored in a cell. In the shown case, primes are p=11, 13, 17, and 19.
As shown in FIGS. 35 and 36, in the case of the code symbol component computation blocks, the number of circuit blocks and the number of stages thereof vary in accordance with the value of a prime p. The reason is as follows. In the code symbol component computation blocks, the numbers of even components and odd components alternate in accordance with the prime p as the product of elements in Zp is executed two by two.
For example, qj at p=13 can be obtained using the inputs on the left side of the code symbol component computation block shown in FIG. 35. FIGS. 35 and 36 show general cases while the inputs and the number of stages of ‘h bit AD mod p’ circuit blocks can be determined specifically in accordance with the prime p. All circuit blocks contained in the code symbol component computation block are static circuits, which require no clock synchronization and of which outputs are decided when the inputs are decided.
As described above, the code symbol cj can be derived from the sum of qj and rj and the difference therebetween. Besides, the computation processing in the embodiment frequently uses computations for deriving differences. The following description is given to a circuit block for executing the sum and difference computations.
FIG. 37 is a diagram showing a block symbol of an ‘h bit AD mod p’ circuit block in the memory system according to the embodiment.
The ‘h bit AD mod p’ circuit block is a circuit operative to add the elements A and B in Zp together.
The ‘h bit AD mod p’ circuit block executes operation processing using numerical formulae shown in Expression 26.

A+B+FP0·p*=A+B mod p 

FP0=1(if p≦A+B)

FP0=0(if A+B<p)

p*=inv(p)+1  [Expression 26]

Namely, if the sum of binary expressions of the numerals A and B is smaller than the binary-expressed prime p, then FP0=0, and if larger, then FP0=1. From the sum of binary expressions of the numerals A and B, FP0·p is subtracted to yield an element in Zp.

FIG. 38 is a circuit diagram of a computation block operative to derive a difference in the memory system according to the embodiment.
Subtraction of A from B requires obtaining −A in Zp at the start. −A is an element that becomes congruent with zero when A is added thereto. An operation of obtaining −A and the operation in the Zp world differ from each other in the condition of subtracting p for seeking the complement of A as an h-bit number. Therefore, an ‘h bit AD(2h) mod p’ circuit block is required as a new circuit block.
This ‘h bit AD(2h) mod p’ circuit block executes operation processing using numerical formulae shown in Expression 27.

inv(A)+(p+1)+FP1·p*=A*+p+FP1*p=A mod p 

FP1=1(if p≦A*+p mod 2h)

FP1=0(if A*+p<p mod 2h)

p*=inv(p)+1  [Expression 27]

Namely, if the sum in binary of a prime p and the complement of A in h-bit binary is smaller than p, as a numeral within a range of h bits, that is, a numeral modulo 2h, then FP=0, and if larger, then FP1=1. FP1·p is subtracted to obtain the complement −A of A as an element in Zp.

Further, the operation processing in the embodiment frequently uses powers of elements in Zp. The powers of elements in Zp can be simply obtained by using a table when p is smaller, for example, p=13.
FIGS. 39-42 are power correspondence tables of elements in Zp in the memory system according to the embodiment. FIG. 39 shows an instance of p=11, FIG. 40 shows an instance of p=13, FIG. 41 shows an instance of p=17, and FIG. 42 shows an instance of p=19.
If decoders are configured on the basis of the power correspondence tables of elements in Zp shown in FIGS. 39-42, it is possible to obtain the powers of elements in Zp without using any computation circuit. According to the nature of elements in Zp, even-powers of an element in the case of an element m are equal to those in the case of p-m while odd-powers of an element in the case of an element m are different in sign from those in the case of p-m. Therefore, there is room for simplifying the configuration of the decoder though FIGS. 39-42 show all except those becoming obvious one. In addition, even-powers of p-m are underlined.
The following description is given to a computation process for generating a syndrome S from a code Y read from a cell.
Expressions 28-32 show a specific example of computations for generating the syndrome S from data Y in the case of ε=2.




  
    
      
        
          
        
        ⁢
        
          A
          =
          
            YH
            t
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          28
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          H
          =
          
            [
            
              
                
                  1
                
                
                  1
                
                
                  •
                
                
                  1
                
                
                  1
                
              
              
                
                  
                    1
                    1
                  
                
                
                  
                    2
                    1
                  
                
                
                  •
                
                
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                    1
                  
                
                
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    1
                  
                
              
              
                
                  
                    1
                    2
                  
                
                
                  
                    2
                    2
                  
                
                
                  •
                
                
                  
                    
                      (
                      
                        p
                        -
                        2
                      
                      )
                    
                    2
                  
                
                
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    2
                  
                
              
            
            ]
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          29
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              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
                  
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
              S
              1
            
            =
            
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  
                    p
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      (
                      j
                      )
                    
                    1
                  
                  ⁢
                  
                    y
                    j
                  
                
              
              =
              
                
                  
                    ∑
                    
                      j
                      =
                      1
                    
                    
                      
                        (
                        
                          p
                          -
                          1
                        
                        )
                      
                      /
                      2
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        (
                        j
                        )
                      
                      1
                    
                    ⁢
                    
                      y
                      j
                    
                  
                
                +
                
                  
                    ∑
                    
                      j
                      =
                      
                        
                          
                            (
                            
                              p
                              -
                              1
                            
                            )
                          
                          /
                          2
                        
                        +
                        1
                      
                    
                    
                      p
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        (
                        j
                        )
                      
                      1
                    
                    ⁢
                    
                      y
                      j
                    
                  
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
              
                ∑
                
                  j
                  =
                  
                    
                      
                        (
                        
                          p
                          -
                          1
                        
                        )
                      
                      /
                      2
                    
                    +
                    1
                  
                
                
                  p
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  1
                
                ⁢
                
                  y
                  j
                
              
            
            =
            
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  
                    
                      (
                      
                        p
                        -
                        1
                      
                      )
                    
                    /
                    2
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      (
                      
                        p
                        -
                        j
                      
                      )
                    
                    1
                  
                  ⁢
                  
                    y
                    
                      (
                      
                        p
                        -
                        j
                      
                      )
                    
                  
                
              
              =
              
                
                  
                    (
                    
                      -
                      1
                    
                    )
                  
                  1
                
                ⁢
                
                  
                    ∑
                    
                      j
                      =
                      -
                    
                    
                      
                        (
                        
                          p
                          -
                          1
                        
                        )
                      
                      /
                      2
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        (
                        j
                        )
                      
                      1
                    
                    ⁢
                    
                      y
                      
                        -
                        j
                      
                    
                  
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              S
              1
            
            =
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  
                    (
                    
                      p
                      -
                      1
                    
                    )
                  
                  /
                  2
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  1
                
                ⁢
                
                  (
                  
                    
                      y
                      j
                    
                    +
                    
                      
                        
                          (
                          
                            -
                            1
                          
                          )
                        
                        1
                      
                      ⁢
                      
                        y
                        
                          -
                          j
                        
                      
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          30
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              u
              1
            
            =
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  
                    (
                    
                      p
                      -
                      1
                    
                    )
                  
                  /
                  2
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  1
                
                ⁢
                
                  y
                  j
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              v
              1
            
            =
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  
                    (
                    
                      p
                      -
                      1
                    
                    )
                  
                  /
                  2
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    j
                    )
                  
                  1
                
                ⁢
                
                  y
                  
                    -
                    j
                  
                
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          31
        
        ]
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              S
              
                0
                ,
                2
              
            
            =
            
              
                u
                
                  0
                  ,
                  2
                
              
              +
              
                v
                
                  0
                  ,
                  2
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              S
              1
            
            =
            
              
                u
                1
              
              -
              
                v
                1
              
            
          
        
      
    
    
      
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          32
        
        ]
      
    
  




In the case of ε=2, a matrix H is of 3 rows and p−1 columns as shown in Expression 29. When the sum of elements in Zp is divided by (p−1)/2, as mentioned in the description with reference to FIGS. 39-42, even-powers of an element in the case of an element j are equal to those in the case of p−j while odd-powers of an element in the case of an element j are different in sign from those in the case of p−j. Therefore, the syndrome component S1 can be divided into two parts as shown in Expression 30. In addition, when u1 and v1 are defined as shown in Expression 31, syndrome components S0 and S2 can be represented by the sum of u1 and v1, and the syndrome component S1 can be represented by the difference between u1 and v1.
The following description is given to a specific example of computation blocks for u1 and v1 shown in Expression 31.
FIGS. 43 and 44 are circuit diagrams of computation blocks in the memory system according to the embodiment. In the shown case, primes are p=11, 13, 17 and 19. FIG. 43 shows an instance of p=11 and 19, and FIG. 44 shows an instance of p=13 and 17.
The product of elements in Zp is executed two by two. Therefore, depending on the cases of even and odd (p−1)/2, the number of ‘x Zp’ circuit blocks for product operation is changed so that the configuration of the computation block varies.
For example, in the case of p=13, the inputs on the left side of FIG. 44 are used to obtain u1. In addition, the inputs shown on the right side of FIG. 44 are used to obtain v1. All l-powered inputs in Zp are identical.
FIGS. 43 and 44 show general cases while the inputs and the number of stages of ‘h bit AD mod p’ circuit blocks can be determined specifically in accordance with the prime p. All circuit blocks contained in a u1/v1 computation block are static circuits, which require no clock synchronization and of which outputs are decided when the inputs are decided.
Hereinafter, an error searching process using a syndrome is described.
First, a polynomial that matches the key condition obtained through the Euclid method is used. Substitution of λ(x)=0 and V(x)=0 is made and a common constant factor is factored out from the above polynomial. The remaining polynomial is shown in FIG. 45.
FIG. 45 is a table showing divergences and syndromes of a searching equation of Zp in the memory system according to the embodiment.
When a solution that satisfies the polynomial shown in FIG. 45 is derived in the case of each divergence, the place of the occurrence of an error and the magnitude of the error can be obtained. In accordance with the conditions for ψ1 and ψ2, there are three cases including cases 1-3 as shown in FIG. 45. Each case further diverges in accordance with the value of S0. A J+ row in each S0 row corresponds to λ(x). When errors e are +1 or +2, they each are +1 in the case of a single root and +2 in the case of double roots. A J− in each S0 row corresponds to V(x). When errors e are −1 or −2, they each are −1 in the case of a single root and −2 in the case of double roots.
As the condition-diverged polynomial is a quadratic equation at the maximum, the following description is given to a general method of solving this quadratic equation in Zp.
When a general quadratic equation is represented by x2+Ax+B=0, and x=y−α, α=A/2, D=(α2−Aα+B)=α2−B are given, y2=D is established. This equation can be solved if Zp has a quadratic residue D. When one of solutions of y2=D is y (<p/2), p−y is also a solution. Thus, a quadratic equation of x has roots obtained as r1=y−α and r2=−y−α. If D is not a quadratic residue, y2=D has no solution, and the corresponding error is not equivalent to that in the case of ε=2.
The number of possible values of D in Zp is equal to p. Even in the case of p=19, it is sufficient to execute decoding for p/2 or lower elements of the elements in Zp. Therefore, only nine decoders are required to obtain solutions.
The use of the solutions of y2=D obtained above makes it possible to decide the positional quantities of error components depending on whether the divergence is J+ or J−.
Namely, when a quadratic equation has solutions r1, r2 and a linear solution has a solution s, the error symbol position and the error quantity in the case of J+ are as in Expression 33.

S0=2:

t1=r1−1,t2=r2−1:e=1

t1=t2:e=2

S0=1:

t=s−1:e=1  [Expression 33]

In addition, the error symbol position and the error quantity in the case of J− are as in Expression 34.

S0=2:

t1=r1−1,t2=r2−1:e=−1

t1=t2:e=−2

S0=1:

t=s−1:e=−1  [Expression 34]

The following description is given to the forms of condition-diverged equations and solutions thereof in specific examples, and the major quantities required in computation processes thereof.
A syndrome before divergence and the basic quantity obtained therefrom are as in Expression 35.

S0,S1=−ψ1,

S2→a=2ψ2=S12−S2,b=2(ψ12−ψ2)=S12+S2  [Expression 35]

The condition-diverged equations are given divergence numbers (s-1) to (s-6) and shown in Expressions A36-41, respectively.

(s-1):

ψ2x2+ψ1x+1=0→x2−(2S1/a)x+(2/a)=0 α=−S1/a 

A=α2−(2/a)

r1=A1/2−α,r2=−A1/2−α  [Expression 36]

(s-2):

x2+{ψ1/(ψ12−ψ2)}x+1/(ψ12−ψ2)=0

→x2+(2S1/b)x+(2/b)=0β=S1/b 

B=β2−(2/b)

r1=B1/2−β,r2=−B1/2−β  [Expression 37]

(s-3):

x2−(1/ψ1)x+1/ψ12=0→x2+(1/S1)x+(1/S12)=0γ=1/(2S1)

C=γ2−(1/S12)=−3γ2 

r1=C1/2−γ=γ{(p−3)1/2−1}r2=−C1/2−γ=γ{−(p−3)1/2−1}

p=11: r1=γ{(8)1/2−1},r2=γ{−(8)1/2−1}(8)1/2=no solution

p=13:r1=γ{(10)1/2−1}=5γ,r2=γ{−(10)1/2−1}=6γ(10)1/2=6,7

p=17: r1=γ{(14)1/2−1},r2=γ{−(14)1/2−1}(14)1/2=no solution

p=19:r1=γ{(16)1/2−1}=5γ,r2=γ{−(16)1/2−1}=6γ(16)1/2=4,15   [Expression 38]

(s-4):

ψ1x+1=0→S1x+1=0

s=1/S1=2γ  [Expression 39]

(s-5):

(ψ12−ψ2)x+ψ1=0→(b/2)x−S1=0

s=2S1/b=2β  [Expression 40]

(s-6):

x−ψ1/ψ2=0→x+2S1/a=0

s=−2S1/α=2α  [Expression 41]

In the case of (s-1), as shown in Expression 36, α=−S1/a and A=α2−(2/a) are required, and two roots are determined.
In the case of (s-2), as shown in Expression 37, β=S1/b and B=N2−(2/b) are required, and two roots are determined.
In the case of (s-3), as shown in Expression 38, γ=1/(2S1) is required. Roots are decided by p, and two roots are determined. In the case of p=11, 17, however, no corresponding quadratic residue exists and accordingly no solution exists.
In the cases of (s-4) to (s-6), a linear equation is applied.
In the case of (s-4), as shown in Expression 39, one root is determined by ε=2γ.
In the case of (s-5), as shown in Expression 40, one root is determined by ε=2β.
In the case of (s-6), as shown in Expression 41, one root is determined by ε=2α.
The underlines in Expressions 35-41 indicate the important quantities required at the time of seeking the positions of errors.
The following description is given to a computation process for obtaining the quantities from the syndrome S0, S1, S2 in turn, and a computation process for obtaining the final error position and quantity from the polynomials diverged on the basis of the obtained quantities.
Computation procedures of elements are shown in Expression 42, and solutions of the diverged searching equations are shown in Expression 43.

S0,S1,S2 

a=S12−S2,b=S12+S2 

−α=S1a−1,β=S1b−1,2a−1,2b−1 

A=α2−2a−1,B=β2−2b−1 

Case 1,Case 2,Case 3  [Expression 42]

Case 1:

a≠0,b≠0

S0=2:

(s-1)

t1=r1−1=(A1/2−α)−1et1=1

t2=r2−1=(−A1/2−α)−1et2=1

S0=0:

(s-5)

t1=s−1=(2β)−1et1=1

(s-6)

t2=s−1=(2α)−1et2=−1

S0=−2:

(s-2)

t1=r1−1=(B1/2−α)−1et1=−1

t2=r2−1=(B1/2−α)−1et2=−1

Case 2:

a≠0,b=0

S0=2:

(s-1)

t1=r1−1=(A1/2−α)−1et1=1

t2=r2−1=(−A1/2−α)−1et2=1

S0=−1:

(s-6)

t=s−1=(2α)−1et=−1

Case 3:

S1≠0,a=0

S0=1:

(s-4)

t=s−1=(2γ)−1=S1et=1

S0=−2:

(s-3)

p=13

t1=(5γ)−1=8γ−1=3S1et1=−1

t2=(6γ)−1=11γ−1=9S1et2=−1

p=19

t1=(3γ)−1=13γ−1=7S1et1=−1

t2=(14γ)−1=15γ−1=11S1et2=−1  [Expression 43]

As shown in Expression 42, at the start, a and b are computed. Subsequently, −α, β, 2a−1, 2b−1 are computed from a and b. Subsequently, A and B are computed from −α, β, 2a−1, 2b−1. In the computation process up to now, the inverse element of a zero element is used as a zero element for convenience to advance the computation.
Subsequently, based on the obtained a, b, they are diverged into cases 1-3 shown in Expression 43, and further diverged into groups of solutions corresponding to S0 among the divergences. Through the above computation processes, the positions t1, t2, t of error symbols and the quantities of the errors can be obtained.
The following description is given to correspondence relations among elements in Zp, and inverse elements and square roots thereof present in methods of solving a searching equation of Zp.
FIGS. 46-49 are correspondence tables of elements in Zp, and inverse elements, squares and square roots thereof in the memory system according to the embodiment. FIG. 46 shows an instance of p=11, FIG. 47 shows an instance of p=13, FIG. 48 shows an instance of p=17, and FIG. 49 shows an instance of p=19.
With respect to the squares of elements in Zp, as an element m equal to or below p/2 corresponds to an element p-m, only the correspondence table of elements of 1 to p/2 is sufficient. In FIGS. 44-47, elements above p/2 are underlined. As for the inverse elements of elements in Zp, a zero element has no meaning though it is related to zero for convenience of computation to prevent a failure of computation. At the time of divergence, however, a computation result of division by such zero is excluded so as not to exert an influence on the process of solution searching. As for square roots of elements in Zp, they only exist in elements that are quadratic residues in Zp. Accordingly, FIGS. 46-49 show them with ‘-’ In the absence of square roots for elements in Zp, it is not possible to execute a root computation of the equation. Accordingly, solution searching is finished at that time. This corresponds to the case where an NG signal is provided to external from the memory controller.
The following description is given to computation blocks operative to compute the major quantities present in computation processes for deriving solutions of searching equations.
FIG. 50 is a circuit diagram of a computation block in the memory system according to the embodiment. The computation block shown in FIG. 50 is operative to compute A and B from syndrome elements S1 and S2. A circuit block shown with an ellipse in FIG. 50 is a decoder based on the correspondence table of an element shown in ( ) and a power thereof. The computation block further includes inverters, circuit blocks for seeking the sum, and circuit blocks for seeking the product.
All circuit blocks contained in the computation block are static circuits, and processing by the computation block proceeds in asynchronous with clocks. Based on the quantities herein obtained, computations for seeking solutions diverge.
The divergences include comparisons of quantities and switching of computation paths, which can be assembled by logics of asynchronous circuits. Hereinafter, individual circuit blocks after divergence are described.
The following description is given to circuit blocks operative to compute t1, t2 and t representative of the positions of error-caused symbols in accordance with divergences.
FIGS. 51-54 are circuit diagrams of computation blocks in the memory system according to the embodiment. FIG. 51 shows an instance of (s-1) or (s-2) shown in Expression 43, FIG. 52 shows an instance of (s-3) shown in Expression 43, FIG. 53 shows an instance of (s-4) shown in Expression 43, and FIG. 54 shows an instance of (s-5) or (s-6) shown in Expression 43. Part of circuit blocks in FIG. 51 is given ‘/’. The value ahead of ‘/’ is a value used in the case of (s-1) while the value behind ‘/’ is a value used in the case of (s-2). Similarly, part of circuit blocks in FIG. 54 is given ‘/’. The value ahead of ‘/’ is a value used in the case of (s-5) while the value behind ‘/’ is a value used in the case of (s-6).
These computation blocks can be used before and after divergence. In a word, before divergence, the results computed previously using these computation blocks are selected in accordance with the divergence conditions. On the other hand, after divergence, divergences of (s-1) to (s-6) are executed in advance and a computation block corresponding to each divergence is used in computation to obtain a result. When these computation blocks are used before divergence, no corresponding element may exist in the computation process. Accordingly, ready for such the case, each computation block prepares an output circuit for providing an NG signal to the outside of the memory controller. In addition, as for α and β, sign-different quantities (complements in Zp) are required. Accordingly, circuits for obtaining these quantities are provided.
As the error quantities are determined in accordance with respective divergences, they can be obtained with no computation. In the case of t1=t2, however, double roots exist. Therefore, the error quantities become ±2 depending on divergences. This point should be noted.
The following description is given to a process of converting an LMC code C into symbols of data A in Zp after error correction. Relational equations used in this conversion process are shown in Expressions 43-47. In Expressions 46 and 47, a suffix ‘rev(m)’ indicates an inverse element of an element m in Zp.



  
    
      
    
    ⁢
    
      [
      
        Expression
        ⁢
        
          
        
        ⁢
        43
      
      ]
    
  




  
    
      
    
    ⁢
    
      A
      =
      
        
          CG
          
            -
            1
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        [
        
          Expression
          ⁢
          
            
          
          ⁢
          44
        
        ]
      
    
  




  
    
      G
      
        -
        1
      
    
    =
    
      
        (
        
          p
          -
          1
        
        )
      
      ⁡
      
        [
        
          
            
              
                1
                
                  -
                  1
                
              
            
            
              
                1
                
                  -
                  2
                
              
            
            
              •
            
            
              
                1
                
                  
                    -
                    p
                  
                  +
                  3
                
              
            
            
              
                1
                
                  
                    -
                    p
                  
                  +
                  4
                
              
            
          
          
            
              
                2
                
                  -
                  1
                
              
            
            
              
                2
                
                  -
                  2
                
              
            
            
              •
            
            
              
                2
                
                  
                    -
                    p
                  
                  +
                  3
                
              
            
            
              
                2
                
                  
                    -
                    p
                  
                  +
                  4
                
              
            
          
          
            
              •
            
            
              •
            
            
              •
            
            
              •
            
            
              •
            
          
          
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  -
                  1
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  -
                  2
                
              
            
            
              •
            
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  
                    -
                    p
                  
                  +
                  3
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    2
                  
                  )
                
                
                  
                    -
                    p
                  
                  +
                  4
                
              
            
          
          
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  -
                  1
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  -
                  2
                
              
            
            
              •
            
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  
                    -
                    p
                  
                  +
                  3
                
              
            
            
              
                
                  (
                  
                    p
                    -
                    1
                  
                  )
                
                
                  
                    -
                    p
                  
                  +
                  4
                
              
            
          
        
        ]
      
    
  




  
    
      
    
    ⁢
    
      [
      
        Expression
        ⁢
        
          
        
        ⁢
        45
      
      ]
    
  




  
    
      
    
    ⁢
    
      
        a
        i
      
      =
      
        
          
            (
            
              p
              -
              1
            
            )
          
          ⁢
          
            
              ∑
              
                j
                =
                1
              
              
                p
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              
                
                  (
                  j
                  )
                
                
                  
                    -
                    i
                  
                  -
                  1
                
              
              ⁢
              
                c
                j
              
            
          
        
        =
        
          
            (
            
              p
              -
              1
            
            )
          
          ⁢
          
            
              ∑
              
                j
                =
                1
              
              
                p
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              
                
                  (
                  
                    j
                    
                      -
                      1
                    
                  
                  )
                
                
                  i
                  +
                  1
                
              
              ⁢
              
                c
                j
              
            
          
        
      
    
  




  
    
      
    
    ⁢
    
      [
      
        Expression
        ⁢
        
          
        
        ⁢
        46
      
      ]
    
  




  
    
      a
      i
    
    =
    
      
        
          (
          
            p
            -
            1
          
          )
        
        ⁢
        
          
            ∑
            
              m
              =
              1
            
            
              p
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            
              
                (
                m
                )
              
              
                i
                +
                1
              
            
            ⁢
            
              c
              
                rev
                ⁡
                
                  (
                  m
                  )
                
              
            
          
        
      
      =
      
        
          (
          
            p
            -
            1
          
          )
        
        ⁢
        
          {
          
            
              
                ∑
                
                  m
                  =
                  1
                
                
                  
                    (
                    
                      p
                      -
                      1
                    
                    )
                  
                  /
                  2
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    m
                    )
                  
                  
                    i
                    +
                    1
                  
                
                ⁢
                
                  c
                  
                    rev
                    ⁡
                    
                      (
                      m
                      )
                    
                  
                
              
            
            +
            
              
                ∑
                
                  m
                  =
                  
                    
                      
                        (
                        
                          p
                          -
                          1
                        
                        )
                      
                      /
                      2
                    
                    +
                    1
                  
                
                
                  p
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    (
                    m
                    )
                  
                  
                    i
                    +
                    1
                  
                
                ⁢
                
                  c
                  
                    rev
                    ⁡
                    
                      (
                      m
                      )
                    
                  
                
              
            
          
          }
        
      
    
  




  
    
      
        ∑
        
          m
          =
          1
        
        
          p
          -
          1
        
      
      ⁢
      
        
      
      ⁢
      
        
          
            (
            m
            )
          
          
            i
            +
            1
          
        
        ⁢
        
          c
          
            rev
            ⁡
            
              (
              m
              )
            
          
        
      
    
    =
    
      
        
          ∑
          
            m
            =
            1
          
          
            
              (
              
                p
                -
                1
              
              )
            
            /
            2
          
        
        ⁢
        
          
        
        ⁢
        
          
            
              (
              
                p
                -
                m
              
              )
            
            
              i
              +
              1
            
          
          ⁢
          
            c
            
              rev
              ⁡
              
                (
                
                  p
                  -
                  m
                
                )
              
            
          
        
      
      =
      
        
          
            (
            
              -
              1
            
            )
          
          
            i
            +
            1
          
        
        ⁢
        
          
            ∑
            
              m
              =
              1
            
            
              
                (
                
                  p
                  -
                  1
                
                )
              
              /
              2
            
          
          ⁢
          
            
          
          ⁢
          
            
              
                (
                m
                )
              
              
                i
                +
                1
              
            
            ⁢
            
              c
              
                rev
                ⁡
                
                  (
                  
                    -
                    m
                  
                  )
                
              
            
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        a
        i
      
      =
      
        
          (
          
            p
            -
            1
          
          )
        
        ⁢
        
          
            ∑
            
              m
              =
              1
            
            
              
                (
                
                  p
                  -
                  1
                
                )
              
              /
              2
            
          
          ⁢
          
            
          
          ⁢
          
            
              
                (
                m
                )
              
              
                i
                +
                1
              
            
            ⁢
            
              
                (
                
                  
                    c
                    
                      rev
                      ⁡
                      
                        (
                        m
                        )
                      
                    
                  
                  +
                  
                    
                      
                        (
                        
                          -
                          1
                        
                        )
                      
                      
                        i
                        +
                        1
                      
                    
                    ⁢
                    
                      c
                      
                        rev
                        ⁡
                        
                          (
                          
                            -
                            m
                          
                          )
                        
                      
                    
                  
                
                )
              
              ⁢
              
                

              
              ⁢
              
                
              
              [
              
                Expression
                ⁢
                
                  
                
                ⁢
                47
              
              ]
            
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        Q
        i
      
      =
      
        
          ∑
          
            m
            =
            1
          
          
            
              (
              
                p
                -
                1
              
              )
            
            /
            2
          
        
        ⁢
        
          
        
        ⁢
        
          
            
              (
              m
              )
            
            
              i
              +
              1
            
          
          ⁢
          
            c
            
              rev
              ⁡
              
                (
                m
                )
              
            
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        R
        i
      
      =
      
        
          
            ∑
            
              m
              =
              1
            
            
              
                (
                
                  p
                  -
                  1
                
                )
              
              /
              2
            
          
          ⁢
          
            
          
          ⁢
          
            
              
                (
                m
                )
              
              
                i
                +
                1
              
            
            ⁢
            
              c
              
                rev
                ⁡
                
                  (
                  
                    -
                    m
                  
                  )
                
              
            
          
        
        →
        
          

        
        ⁢
        
          
        
        ⁢
        
          i
          ⁢
          
            :
          
          ⁢
          
            
          
          ⁢
          odd
        
      
    
  




  
    
      
    
    ⁢
    
      
        a
        i
      
      =
      
        
          (
          
            p
            -
            1
          
          )
        
        ⁢
        
          (
          
            
              Q
              i
            
            +
            
              R
              i
            
          
          )
        
      
    
  




  
    
      
    
    ⁢
    
      i
      ⁢
      
        :
      
      ⁢
      
        
      
      ⁢
      even
    
  




  
    
      
    
    ⁢
    
      
        a
        i
      
      =
      
        
          (
          
            p
            -
            1
          
          )
        
        ⁢
        
          (
          
            
              Q
              i
            
            -
            
              R
              i
            
          
          )
        
      
    
  



A right inverse matrix G−1 of the generator matrix G is as shown in Expression 44. In addition, a symbol ai of data is the sum of certain powers of all inverse elements of the elements in Zp as shown in Expression 45.
All inverse elements are equal to all elements, and an inverse element of p-m is equal to an element that corresponds to an inverse element of m but has a minus sign. Accordingly, through the rearrangement of the sum and the division by the sum of m=1 to (p−1)/2, each ai becomes the sum of Qi and Ri and the difference therebetween as shown in Expression 47. Qi and Ri are the sum of the products of powers of (p−1)/2 from code components and components 1 in Zp. As shown in Expression 47, ai is the sum of Qi and Ri if i is odd while ai is the difference between Qi and Ri if i is even.
Computation circuits of Qi and Ri are described next.
FIGS. 55 and 56 are circuit diagrams of computation blocks in the memory system according to the embodiment.
FIGS. 55 and 56 both show computation blocks for deriving Qi and Ri. FIG. 55 shows instances of p=11 and 19, and FIG. 56 shows instances of p=13 and 17.
As the product of elements in Zp is executed two by two, the number of ‘X Zp’ circuit blocks for product operation varies depending on whether (p−1)/2 is even or odd, and the circuitry of the computation block varies correspondingly.
In FIGS. 55 and 56, two quantities are shown for certain inputs. The order of these two quantities corresponds to the order of two quantities shown in the output. For example, in the case of p=13, Qi can be obtained using the inputs on the left side in FIG. 55 while Ri can be obtained using the inputs on the right side in FIG. 56. All (i+1)-powered inputs in Zp are identical.
FIGS. 55 and 56 show general cases while specific inputs and the number of stages of ‘h bit AD mod p’ circuit blocks can be determined in accordance with the prime p. The computation blocks shown in FIGS. 55 and 56 are static circuits, which require no clock synchronization and of which outputs are decided when the inputs are decided.
As from the above, the present embodiment makes it possible to construct a memory system of the three-dimensional cross-point type having a higher cell share.
OTHERS
While the embodiments of the present invention have been described, these embodiments are presented by way of example and are not intended to limit the scope of the invention. These novel embodiments can be implemented in a variety of other forms, and various omissions, substitutions and changes can be made without departing from the spirit of the invention. These embodiments and variations thereof would fall within the scope and spirit of the invention and also fall within the invention recited in claims and equivalents thereof.

## Claims

1. A memory system, comprising:
a cell array of plural cells having three or more settable physical quantity levels and operative to store a code composed of symbols expressed by elements in a finite field Zp (p is a prime),
wherein a set of two cells is defined as a pair cell and a combination of physical quantity levels of said two cells contained in said pair cell is defined as a pair cell level,
wherein said pair cell uses a pair cell level of plural pair cell levels, which maximizes or minimizes a physical quantity level of one cell contained in said pair cell, to assign elements in said Zp to said pair cell levels, thereby storing symbols of said code.

2. The memory system according to claim 1, wherein said pair cell assigns said pair cell levels to elements in said Zp so that a variation of one level in physical quantity level of one cell contained in said pair cell causes a variation within one in element in said Zp.

3. The memory system according to claim 1, wherein said pair cell assigns part of elements in said Zp to plural levels of said pair cell levels.

4. The memory system according to claim 1, wherein said pair cell assigns said pair cell levels to elements in said Zp where p=11 when physical quantity levels of said cells contained in said pair cell are 4 levels.

5. The memory system according to claim 1, wherein said pair cell assigns said pair cell levels to elements in said Zp where p=13 when physical quantity levels of said cells contained in said pair cell are 5 levels.

6. The memory system according to claim 1, wherein said pair cell assigns said pair cell levels to elements in said Zp where p=17 or 19 when physical quantity levels of said cells contained in said pair cell are 6 levels.

7. The memory system according to claim 1, wherein said code stored in said cell array is a Lee metric code composed of symbols expressed by elements in said Zp.

8. The memory system according to claim 1, wherein said plural cells each include a variable resistance element having a structure of nanotubes stacked.