JPS6114540B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a storage device redundancy system, and particularly to a redundancy system in which only good modules are accessed even if some of the memory modules contain defective bits.

In recent semiconductor technology, the realization of wafer memories is being considered in order to increase the density of elements.
When realizing this wafer memory, an important issue is the manufacturing yield. In order to improve yield, it is necessary to overcome many difficulties in process technology and circuit technology, but these difficulties can be alleviated by designing with redundancy in advance. . Also, from the viewpoint of reliability, it is extremely important to design with redundancy.

There are two ways to provide redundancy: software methods such as ECC, and hardware methods such as preparing a spare module and replacing it with a defective memory module. There is a specific method.

In the latter method, the area of the spare module or the area of the spare chip within the module is determined in advance, as shown in, for example, Japanese Patent Application Laid-open No. 47-7060, Japanese Patent Application Laid-open No. 48-16536, etc. When it is identified that a defective module or defective chip has been accessed, it switches to a specific spare module or chip.

The present invention provides at least one redundancy for the required number of modules as a whole, without limiting the area of spare modules as in conventional redundancy systems,
The purpose is to prevent the defective module from being accessed by using any module other than the defective module as a spare.
It is characterized by assigning Galois field elements as address codes in order to connect only good modules.

First, in explaining the present invention, FIGS. 1a to 1c will be explained in order to introduce the principle of the present invention.

As shown in FIG. 1a, consider a group of eight modules that are selected using ordinary 3-bit information.

In FIG. 1, ADRS represents external address information given from the outside, and adrs represents internal addresses assigned to each module.

Currently, address information ADRS given from outside
It is assumed that there are seven possible addresses from (000) to (011), and that the address (111) is not given. That is, the number of modules actually required is seven, and the other one is a spare.

The codes 1 and 0 shown in the table in Figure 1a are the internal codes assigned to each module mentioned above.In other words, in Figure 1a, the codes 1 and 0 are
When not used, the address code from the outside immediately becomes internal address information, and one of the modules corresponding to this is selected.

As is clear from Figure 1a, when focusing on a certain module, the address codes assigned to the modules before and after it are always the address code assigned to the module of interest minus 1, and 1. is equal to plus Naturally, therefore, the combination of 3 bits assigned to each module as an address code is equal to each element of the sequence of 8 cycles sequentially generated by the 3-bit counter.

Now, suppose that in the module group of FIG. 1a, the module (marked with an x) to which address code (010) is assigned is defective.

Therefore, address information given from outside
Consider inputting ADRS to an adder ADD as shown in FIG. 1a, adding (110), and using this result as internal address information.

Here, the codes in the table in Figure 1a indicate the internal addresses assigned to each module as described above, whereas the codes in the table in Figure 1b indicate the external address ADRS as 0 and 1. It is something that
For example, in Figure 1b, 101 means external address 101, and (110)
is added by the adder ADD and converted to an internal address (000), which means that the top module in FIG. 1a to which the corresponding address is assigned is accessed.

By doing the above, the access (111) that was previously decided not to be granted from the outside becomes equivalent to (010) internally, which means that the access (010) is assigned to the Module (×
mark) is no longer accessed.

The external address information ADRS for the other seven modules is also converted into an internal address ADRS as shown in FIG. 1c. Therefore, in this module group, address codes are apparently assigned in order from the module following the defective module, as shown in FIG. 1b.

FIG. 10 shows the above diagrammatically.

Now, in the above example, ordinary 3-bit binary information was used for explanation, and a condition was added that (111) would not be accessed, but in reality, there are almost no cases where such a condition is met. This example is not practical.

Next, we will consider assigning elements of another sequence group to each module as address codes, without using binary information.

In other words, an address that allows you to select only 2 ⁿ modules from a group of 2 ⁿ +1 modules.
Consider how to assign codes.

Now, according to the teachings of algebra, the Galois field GF(2 ⁿ ) is a polynomial ring modulo an irreducible polynomial of degree n over the Galois field GF(2) whose elements are 1 and 0. It consists of the cosets of . Therefore, if the root of the irreducible polynomial F(x) is α, then GF
The elements of (2 ⁿ ) can be expressed as follows by a linear combination of 1, α, α ² , . . . α ^n-1 .

a ₀ +a ₁ α+a ₂ α ² +……a _o-1 α ^n-1 Also, as another way of expressing, coefficients a ₀ , a ₁ , a ₂ …
...It can also be expressed as a vector containing only a _o-1 .

(a ₀ , a ₁ , a ₂ ... a _o-1 ) Furthermore, the remaining elements from GF (2 ⁿ ) after removing the zero element form a cyclic group, and generally each element of GF (2 ⁿ ) is It can be expressed as the power of α.

Now, as an example, if we consider the Galois field GF(2 3 ), which is a polynomial ring modulo the third-order irreducible polynomial F(x)=x ³ +x+1 over GF( ² ), then GF(2 ³ ) Each element of can be represented as shown in FIG.

That is, due to F(x)=x ³ +x+1, x ³ +
The root of x+1=0 is expressed as a linear combination of 1, a, and ^α3 , so without considering the positive or negative sign, 1+α+
If we move the term α ³ of α ³ = 0 to the right-hand side, we get 1+α
= α ³ , and 1+α is expressed as the power of α ³ . In the same way, if we multiply both sides of 1 + α = α ³ by α, we get α + α ² = α ³・α, so α
+α ² is represented by α ⁴ , and by adding α ² to both sides of 1+α=α ³ , 1+α+α ² = α ³ +α ² = α
² (α+1)= ^α5 , so 1+α+ ^α2 is represented by ^α5 .

In other words, each element on this GF(2 ³ ) has a period of 2 ³ −1
is a cyclic sequence of , and when focusing on a certain element, the elements before and after it are equal to the focused element divided by α and multiplied by α.

Therefore, in GF(2 ⁿ ), find the element whose order is 2 ^m +1, use the modulus polynomial of the Galois field, and use this Galois field as each address code of the module. The first example (1st example) can be achieved by allocating the elements of
The impracticality of figures a, b, c) is improved.

Examples will be described below.

Now, if we search for a Galois field whose elements have order 2 ³ +1, it will be found in GF(2 ⁶ ), and its modulo polynomial will be F(x)=1+x ³ +x ⁶ . Moreover, each element of this Galois field is as shown in FIG.

In the embodiment shown in FIG. 4, the modulus is an irreducible polynomial of degree n (n=6) over the Galois field GF(2) whose elements are 1 and 0, and the power of the root α of the polynomial is the element. In the Galois field GF(2 ⁶ ), the order of the elements is 2 ^m +i
(m=3, i=1) using a Galois field, m
= 23 elements out of ²³ +1 elements of the Galois field are associated with each of the 23 addresses determined by ³ -bit address information, while on the chip there are ^{23 +1} elements. Prepare a module, assign 2 ³ + 1 elements ^of the Galois field to each module as an address code, and create a correspondence between the 2 ³ addresses and the 2 ³ elements of the Galois field. to the power of the root α of the irreducible polynomial (α ^k ) (k=
3) allows the existence of i=1 defective module in 2 ³ +1 modules, and FIG. 4 shows an example of its configuration.

That is, in this embodiment, 1+α ³ +α ⁶ is an irreducible polynomial, and 1+α ³ +α ⁶ is the basic equation. Here, "+" represents EOR.
Since "+" is EOR, the sign can be ignored when transferring terms between the left and right sides of this equation. That is, α ⁶ =1+α ³ .

As mentioned above, the elements of the Galois field GF(2 ⁿ ) are
a ₀ + a ₁ α + a ₂ α ² +...a _o-1 α ^n-1 , but in this example n=6, so a ₀ + a ₁ α+
Various elements are represented by a ₂ α ² +……a ₅ α ⁵ .

Focusing on the coefficients a ₀ , a ₁ , a ₂ ... a ₅ and expressing the various elements as (a ₀ , a ₁ , a ₂ ... a ₅ ), (a ₀ , a ₁ , a ₂ ... a _Five )
becomes as follows.

α ₀ ... (100000) α ¹ ... (010000) α ² ... (001000) α ³ ... (000100) α ⁴ ... (000010) α ⁵ ... (000001) α ⁶ = 1 + α ³ ... ( 100100) α ⁷ = α・(1+α ³ ) =α+α ⁴ ...(010010) α ⁸ =α・(α+α ⁴ ) =α ² +α ⁵ ...(001001) α ⁵ =α・(α ² +α ⁵ )= α ³ + α ⁶ = 1 + α ³ + α ³ = 1 (100000) Here, α ³ = α ⁰ , which returns to the original state. That is, ×
Multiplying by α follows this irreducible polynomial:
Only nine pairs (a ₀ , a ₁ , a ₂ ... a ₅ ) are possible. In this embodiment of the present invention, of the nine sets, eight sets are effectively used, and the remaining one set provides address translation so that it cannot be accessed from the outside. In Figure 4,
Each module is composed of 4KW x 1 bit, and these modules are arranged in a 9 x 22 matrix to form a 32KW 22 bit SEC-DED memory system as a whole. In the figure, the 12-bit 4KW selection address and ECC-related circuits are omitted because they are not directly related to the present invention.

The above GF is used as the code for selecting each module.
Each element of (2 ⁶ ) is allocated, for example, (100000)
The module assigned is the address signal 6.
Enabled when bit reaches (100000).

The address signal ADRS3 bit for selecting 8 modules externally input is first
It is input to a read-only memory (hereinafter referred to as ROM) and converted into an element (α ⁿ ) of a 6-bit GF (2 ⁶ ). The contents of this ROM are shown in FIG. At the same time, this address signal ADRS is input to a defective module address register REG provided for each column. If an error is detected in the ECC circuit and the CRU determines that module switching is necessary based on the error history regarding this module, the SET signal and syndrome (position information POS) are sent to the decoder shown in Figure 4. circuit
Input to DEC. As a result, a SET signal is input to the defective module address register REG at the specified bit position (column), and the address at this time is latched. At this time, at the same time
The SET signal is also latched to also remember that a switch occurred on this column.

6-bit GF from 3-bit binary information
The address information converted into the elements of (2 ⁶ ) is sent to the α multiplication circuit (× α ^k ) provided for each module column.
is input. The value of k is the address register
Controlled by information latched to REG.
This truth table is shown in FIG.

FIG. 7 is a detailed connection diagram of the α multiplication circuit in FIG. 4. In addition, "selection input" in Figure 6
indicates which input terminal of the multiplexer MPX in FIG. 7 outputs information.

The α multiplication circuit (×α ¹ ) is designed by the following method. Now, if an arbitrary element in GF(2 ³ ) is (a ₀ a ₁ a ₂ a ₃ a ₄ a ₅ ) and expressed in the form of a polynomial, the following equation holds true.

α × (a ₀ + a ₁ x + a ₂ x ² + a ₃ x ³ + a ₄ x ⁴ + a ₅ x ⁵ ) = b ₀ + b ₁ x
+b ₂ x ² +b ₃ x ³ +b ₄ x ⁴ +b ₅ x ⁵ mod ₁ x ⁶ +x ³ +1 Solving this and finding the relationship between a ₀ ... a ₅ and b ₀ ... b ₅ is as follows. Become.

b ₀ = a ₅ , b ₁ = a ₀ , b ₂ = a ₁ , b ₃ = a ₂ + a ₅ , b ₄ = a ₃ , b ₅ = a _4In the same way, α ² , α ³ ... The calculation results as shown in FIG. FIG. 4 shows a logic configuration based on FIG. 8.

In Figure 4, for example, if the third module (001000) in the first column is defective, the GF
The external address information ADRS corresponding to the element (001000) of (2 ⁶ ) is (010) as shown in Figure 5, so the address register REG of this column is (1010) as shown in Figure 6. is set. As a result, the value of k of the α multiplication circuit (×α ^k ) becomes 3.
The address signals distributed to this column are as shown in FIG. As is clear from FIG. 9, since converted address codes are assigned in order from the module following the defective module (001000), 2 ^{to 3} are selected up to the module before the defective module. Therefore, the defective module (001000) can no longer be accessed from the outside, and the eight good modules can now be accessed, meaning that a switching operation has been performed.

A more detailed illustration of one I/O in FIG. 4 is shown in FIG. 11. That is, the output of the ×α ^k multiplier in FIG. 4 is decoded, and one bit is selected from nine bits. In this example,
As mentioned above, this shows the case where k=3. ROM output addresses for external addresses are assigned from the table of FIG. Conversion from a ROM output address to an internal address can be accomplished by viewing the "pre-conversion internal address" in FIG. 9 as the ROM output, and the "post-conversion address information (xα ³ )" as the new internal address. Therefore, the part without a corresponding external address, ie, the bit for the internal address (001000), is not accessed.

In the embodiment, a case has been described in which only one module is provided with redundancy in the required number, but by preparing an arbitrary number of spare modules, it is possible to tolerate the same number of burst failure modules as the spare modules. For example, prepare 2 ^m + i modules on a chip, and each module has 2 ^{m +} i modules of Galois field GF(2).
i elements are assigned as an address code, and when up to i consecutive defective modules are detected, the correspondence between the address and the Galois field element is changed, and the modules are assigned sequentially from the next module after the defective module. By assigning the converted address code, it is possible to access only 2 ^m good modules.

As described above, according to the present invention, it is possible to switch a defective module to any good module and have it selected without specifying the location of the spare module, and furthermore, it is possible to allocate an element of a Galois field as an address code. Therefore, there is no need to set any restrictions on the address information given from the outside, so the configuration is extremely practical and simple, and the yield during manufacturing can be improved.

[Brief explanation of the drawing]

Fig. 1 is an explanatory diagram used to derive the principle of the present invention, and Fig. ² is a GF(2 ³ ), Figure 3 is an explanatory diagram of the elements of the 6th order irreducible polynomial F(x) = x ⁶ + x ³ + 1 modulo GF (2 ⁶ ), Figure 4 is the method of displaying the elements of the present invention. A block configuration diagram of a storage device showing one embodiment, FIG. 5 is an explanatory diagram of the storage contents of the read-only memory ROM in FIG. 4, FIG. 6 is an explanatory diagram of information of the α multiplier circuit, and FIG. 8 is a relationship diagram of elements for designing the α multiplication circuit in FIG. 4, and FIG ^. 9 is an explanation showing an example of the conversion address in FIG. 4. Figure 10 is a to c of Figure 1.
11 is a diagrammatic explanatory diagram supplementing the fourth aspect of the present invention.
FIG. 2 is a detailed configuration diagram regarding one I/O of the illustrated embodiment; ADRS: Module selection address from outside,
ADD: Adder, ROM: Read-only memory, SET:
Set information, DEC: Decoder circuit, POS: Position information, REG: Defective module address register, ×α ^k : α multiplier circuit, I/OBUF:
Input/output buffer, SELSIG: module selection signal, EOR: exclusive OR circuit,
SW: switching information, MPX: multiplexer.

Claims (1)

[Claims] 1 n over the Galois field GF(2) with elements 1 and 0
Using the Galois field whose element order is 2 ^m + i out of the Galois field GF(2 ⁿ ) whose elements are the powers of the roots of the polynomial and whose modulus is the following irreducible polynomial, Each of the 2 ^m addresses determined by the information is associated with 2 ^m elements out of 2 ^m + i elements of the Galois field, and on the other hand, 2 ^m + i modules are prepared on the chip. 2 ^m + i elements of the Galois field are assigned to each module as an address code, and the correspondence between the 2 ^m addresses and 2 ^m elements of the Galois field is expressed as an irreducible polynomial in the 2 ^m addresses. The power (α) of the root (α) of
A storage device redundancy system characterized in that it allows the existence of up to i burst-defective modules among 2 ^m +i modules by performing a multiplication of ^k ).