Abstract:
The invention CONCERNS a device for reconfiguring an assembly of N basic electronic modules associated with k redundant modules comprising: N multiplexers each having a first terminal (d i ) capable of being connected to k+1 second terminals connected to the k+1 input/output terminals of a sequenced group of modules consisting of a basic module (U i ) and k other modules; N+k triggers (F i ) indicating a good or faulty condition of one of the N+k modules; and logic means associated with each multiplexer of rank j, where j is an integer ranging between 0 and N, to determine the number of triggers of rank 0 to j indicating a faulty condition, to determine the number of modules of the sequenced group associated with the module of rank j, to be counted to find a number of good modules equal to the first number, and to convert the first terminal of the multiplexer to its second terminal of rank equal to the second number.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
         [0001]    This application claims priority from the parent French application, serial 01/01884 filed on Feb. 12, 2001, and the related PCT application PCT/FR02/00523 filed on Feb. 12, 2002 which designated the United States.  
         BACKGROUND OF THE INVENTION  
         [0002]    The present invention relates to a device for reconfiguring an assembly of N electronic devices associated with k replacement units or redundant units. The case where the electronic units are memory units that may be blocks of a large-size memory and/or lines or columns of a memory will be here considered. It should however be reminded that the present invention generally relates to the reconfiguring of an assembly of electronic units.  
           [0003]    [0003]FIGS. 1A and 1B illustrate in a very simplified fashion the problem that the present invention aims at solving. Four memory cell blocks M 0  to M 3  are considered. In practice, these will for example be columns of a memory that can comprise more than one thousand columns. Some of the memory blocks may exhibit a defect. Then, it is provided to replace the defective block with a replacement block. Two replacement blocks S 0  and S 1  have been shown. In fact, several tens of replacement blocks may be provided.  
           [0004]    To perform this replacement, instead of connecting the data input/output terminals d 0 , d 1 , d 2 , d 3  directly to memory blocks M 0 , M 1 , M 2 , M 3 , it is provided to connect these terminals to the memory blocks via multiplexers MUX 0 , MUX 1 , MUX 2 , MUX 3 , respectively controlled by control blocks C 0 , C 1 , C 2 , C 3 . In the case where there are k replacement blocks, each multiplexer will comprise k+1 outputs. In the example of FIGS. 1A and 1B, it is assumed that the second one, M 1 , of the base memory blocks and the first one, S 0 , of the replacement memory blocks are defective.  
           [0005]    In the embodiment of FIG. 1A, it is provided to replace each defective memory block with its closest non-defective neighbor. A substitution “from close to close” is performed. Each multiplexer is likely to be connected to the block of same rank and to the two blocks of immediately greater rank. In the case of FIG. 1A, input d 0  is connected to block M 0 , input d 1  is connected to block M 2  (instead of block M 1 ), input d 2  is connected to block M 3  (instead of block M 2 ), and input d 3  is connected to block S 1  (instead of block M 3  or S 0 ). Multiplexer MUX 0  performs a zero shifting, multiplexers MUX 1  and MUX 2  perform a shifting by one step, and multiplexer MUX 3  performs a shifting by two steps.  
           [0006]    In the embodiment block of FIG. 1B, any defective block is replaced not by one of its non-defective neighbors, but by one of the replacement blocks. A “distant” substitution is performed. Thus, input d 0  is connected to block M 0 , input d 1  is connected to block S 1 , and inputs d 2 , d 3  are connected to blocks M 2 , M 3 . Thus, each multiplexer comprises an output towards the corresponding block and two outputs towards blocks S 0  and S 1 . Multiplexers MUX 0 , MUX 2 , and MUX 3  perform a zero shifting and multiplexer MUX 1  performs a shifting by two steps.  
           [0007]    The present invention aims at providing an automatic terminals and non-defective memory blocks, that is, the defective memory blocks are replaced with other blocks selected according to the case from among the neighbors of the defective block (case of FIG. 1A), or directly from redundant blocks (case of FIG. 1B).  
           [0008]    It should be understood that this problem is relatively complex since, for a given block, to determine to which block the rerouting must be performed, account must be taken of the state of the already-examined blocks, for example, those located to the right (or to the left) of a considered block, and of the state of the possible replacement blocks.  
           [0009]    To enable this reconfiguration, the present invention provides for each of the cases (shifting from close to close or distant shifting) a method using sequential operations or a method using a combinational system. Further, in each of the two considered cases, the present invention provides for the operations to be able to be performed in hardware or software fashion.  
         BRIEF SUMMARY OF THE INVENTION  
         [0010]    Generally, the present invention provides using an algorithm in which:  
           [0011]    it is started from the block located at a first end of a block sequence,  
           [0012]    for each block, the number of defective blocks located on the side of the first end (the defective blocks possibly comprising the considered block itself) is counted,  
           [0013]    an assembly of reserve blocks arranged according to an ordered sequence (the neighboring blocks in the case of FIG. 1A or the redundant blocks in the case of FIG. 1B) is associated with each block,  
           [0014]    successive blocks are counted from these reserve blocks until a number of non-defective blocks equal to the number of  
           [0015]    once this result has been obtained, the considered block is replaced with the block shifted in corresponding fashion of the reserve blocks, while non-defective blocks are not replaced in the case where it is directly passed on to the redundant blocks.  
       
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS  
       [0016]    The foregoing objects, features, and advantages of the present invention will be discussed in detail in the following non-limiting description of specific embodiments in connection with the accompanying drawings, in which:  
         [0017]    [0017]FIGS. 1A and 1B show examples of reconfiguration of memory blocks intended to illustrate the problem to be solved by the present invention;  
         [0018]    [0018]FIG. 2 shows an example of embodiment of a device for reconfiguring memory blocks of sequential type and with a shifting from close to close;  
         [0019]    [0019]FIG. 3 shows an alternative of a portion of the logic circuit of FIG. 2;  
         [0020]    [0020]FIG. 4 shows an example of embodiment of devices for reconfiguring memory blocks of sequential type and with a replacement of defective blocks with redundant blocks;  
         [0021]    [0021]FIG. 5 shows two example of 1 counters used in the logic circuit of FIG. 4; and  
         [0022]    FIGS.  6  to  10  illustrate alternative rerouting devices.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0023]    Notations  
         [0024]    The present application will designate as:  
         [0025]    N: the number of base blocks of the memory likely to exhibit defects, and  
         [0026]    k: the maximum number of defective blocks that can be replaced.  
         [0027]    A base block of the initial memory will be called U i , with i ranging between 0 and N−1.  
         [0028]    The replacement blocks will indifferently be called S 0 to S k−1  or U N  to U N+k−1 .  
         [0029]    The multiplexers associated with blocks U 0  to U N−1  will be called MUX 0  to MUX N−1.    
         [0030]    d i designates the input of a multiplexer MUX i .  
         [0031]    Flip-flops F 0  to F N−1  and S 1  to S k  are respectively associated with the base and replacement blocks and indicate the initial state of the corresponding block. These flip-flops are at 1 if the block is initially defective and at 0 if the block is initially good. The flip-flops are conventionally initialized in a test step during which the operation of each block is checked. According to the present invention, the case where the base blocks as well as the replacement blocks are likely to be defective is treated.  
         [0032]    Repair From Close to Close  
         [0033]    The case where the repair process is of the type illustrated in FIG. 1A in which, to each multiplexer associated with a block are also associated blocks adjacent to this block will first be considered.  
         [0034]    [0034]FIG. 2 shows an example of a sequential reconfiguring structure for a repair from close to close of possibly defective cells. In the example shown, each multiplexer MUX 0  to MUX N−1  is associated with a counter C 0  to C N−1  which is incremented by a signal R i  (R 0  . . . R N−1 ) generated by a sequential circuit so that signal R i  takes value 1 for several consecutive clock cycles.  
         [0035]    Flip-flops F 0  to F N+k−1  are initially loaded with a 0 if the corresponding block is good and with a 1 if the corresponding block is defective. Signals R i  to be provided to a circuit for controlling a multiplexer C i depend on the value of the corresponding flip-flop F i  but also of the flip-flops of lower rank given that, when a position is to be shifted to the left, any position of a greater rank must also be shifted to the left. The value of R i  also depends on the values of the flip-flops of rank greater than i. Indeed, it must be ensured that the block aimed at to be selected as a replacement block is a good block.  
         [0036]    To solve this problem, the present invention provides the following algorithm:  
         [0037]    a) F i =1 causes R i =1 since, for a defective block U i , there must be at least one shift. Further, each time a signal R i  is activated, it forces all signals of greater rank to the active state. One must thus have R i =F i +R i−1 ;  
         [0038]    b) When signal R i  is activated (R i =1), the value of flip-flop F i+1  is transferred to flip-flop F i  and, if there is no flip-flop F i+1 , a 0 is transferred to flip-flop F i . This expresses that, at the end of the present clock cycle, input d i is connected to the block to which input d i+1  was previously connected. Thus, flip-flop F i  must indicate the state that was formerly indicated by flip-flop F i+1 . The following sequential equation must be deduced from the preceding points for flip-flops F i :  
         [0039]    F i (t+1)=R i .F i+1  (t), where t and t+1 indicate two successive times. 
           R   i   =R   i−1   +F   i , for  N+k −1 &gt;i &gt;0  (1) 
           F   i ( t +1)= R   i   .F   i+ 1(t), for  N+k −1 &gt;i &gt;0  (2) 
         [0040]    The conditions at the limits are that, for flip-flop R 0 , it is considered that fictitious flip-flop R −1  is at state 0 and, for flip-flop F N+k−1 , it is considered that fictitious flip-flop F N+k  is at state 0.  
         [0041]    [0041]FIG. 2 shows a logic circuit implementing the above logic equations.  
         [0042]    The output F i  of each flip-flop is connected to a first input of an OR gate  11  having its output connected by an AND gate  12  to the input of flip-flop F i . The output of OR gate  11  also provides signal R i . The second input of OR gate  11  is connected to the output of the OR gate  11  of the preceding stage. The output of flip-flop F i+1  is sent back to the second input of AND gate  12 .  
         [0043]    Each of the flip-flops is rated by a clock signal which also controls counters C i .  
         [0044]    It can be seen that this circuit enables fulfilling the above-mentioned logic equations.  
         [0045]    The operation can also be understood by considering the following steps.  
         [0046]    At the first clock pulse, it is assumed that first flip-flops F 0  and F 1  are at state 0. They will thus provide no shift signal to inputs R 0  and R 1  of counters C 0  and C 1 . The first flip-flop at state 1, for example, flip-flop F 2 , will provide a signal R 2  to counter C 2  to increment it. This signal will also be transmitted by the OR gate chain to all the next flip-flops and will increment counters C 3  to C N−1 . The outputs of multiplexers MUX 2  to MUX N−1  will thus all be shifted by one step. Simultaneously, all the AND gates  12  which follow flip-flop F 2  will have a first input enabled and their output will switch to the state of the second input of the corresponding AND gate  12 , that is, to the state of the next flip-flop, the last flip-flop F N+k−1  taking state 0. Thus, if flip-flop F 3  was not at 1, flip-flop F 2  takes state 0.  
         [0047]    At the next clock pulse, the first flip-flop F i  at 1 will send a signal R i  to counters C i to C N−1  and will shift the outputs of multiplexer MUX i  and of all the following multiplexers. Again, the contents of all flip-flops F i  to F N+k−1  will be shifted by one step to the right and the cycle is repeated.  
         [0048]    In as many clock cycles as there are is in flip-flops F 0  to F N+k−1 , multiplexers MUX 0  to MUX N−1  will be set into the appropriate configuration by counters C 0  to C N−1 .  
         [0049]    With the diagram of FIG. 2, the above equations (1) and (2) are implemented by a cascade of OR gates in series. Relatively significant delays may result therefrom, which may result in a relatively long duration for the repair phase. It should however be noted that this has no impact, either on the duration of the test phase or on the subsequent duration of normal operation of the memory. Thus, it is possible to use a specific clock of low frequency for the repair phase or the same clock signal as on the other phases, while reducing the clock frequency during the repair phase.  
         [0050]    The preceding equations may also be implemented by using a circuit with a shorter delay. FIG. 3 shows an example of a circuit usable to provide eight signals R 0  to R 7  based on eight flip-flop states F 0  to F 7 .  
         [0051]    It should further be noted that signal R N+k−1 provided by the last OR gate  11  associated with the last flip-flop F N+k−1  is theoretically useless since it is not intended to control a multiplexer (there are only N multiplexers). However, this signal may be used to indicate the success or the failure of the repair process. If R N+k−1 =0 after k clock cycles of the repair phase, the repair has been successful. However, if R N+k−1 =1 after k clock cycles, more than k defective blocks. R N+k−1 may also be used as a repair phase completion signal. In other words, it is not necessary to wait for k clock cycles to complete the repair phase. It can be stopped as soon as R N+k−1  becomes equal to 0. One of signals R N−1  to R N+k  may be used for this purpose. Signal R N−1  is more advantageous since its value  0  will indicate sooner than the others the end of the repair.  
         [0052]    Further, the present invention is likely to have various alternatives which will readily occur to those skilled in the art. For example, equations (1) and (2) may be simplified if it is considered that redundant blocks U N  to U N+k−1  are defect-free. In this case, flipflops F N to F N+k−1  associated with these blocks and the associated logic circuits can be eliminated.  
         [0053]    The circuit complexity can be reduced by making some assumptions. For example, assuming that when a unit of rank i is reached, i being much smaller than N, there inevitably exists a number of defects k i &lt;k, the number of outputs of the corresponding multiplexers which, instead of being multiplexers with k outputs, may be multiplexers with k i  outputs, can be reduced. The counters associated with these multiplexers may be simultaneously simplified.  
         [0054]    Various other simplifications will occur to those skilled in the art according to practical assumptions that they may make about the repair of possible defects.  
         [0055]    Combinational Reconfiguration  
         [0056]    The previously-described circuit is a circuit with a sequential operation.  
         [0057]    It is now desired to directly determine the shift to be various flip-flops F 0  to F N+k−1 , for example, by iteration.  
         [0058]    To set the state of a multiplexer, it is considered that each multiplexer MUX i  has k control inputs M i   0  to M i   k  which must all be at zero except for the input that corresponds to the shift which is desired to be adopted by the multiplexer. For example, if block U 0  is defect-free, multiplexer MUX 0  must cause no shifting, that is, its control input M 0   0  must be at 1 and all its other control inputs M 1   0  to M k   0  must be at zero.  
         [0059]    Calling F i  the state of flip-flop F i  and {overscore (F)} i  the complementary state, the inputs of multiplexer MUX 0  are expressed according to the state of the associated blocks U 0  to U k  as follows: 
         M 0   0 ={overscore (F 0 )} 
         M 0   1 ={overscore (F 1 )}.F 0  . . .  
         M 0   k ={overscore (F k )}.F k−1 . . . F 0 .  (3) 
         [0060]    In these equations, the points designate ANDo functions. These equations can be well understood noting that, if for example units U 0  and U 1  are defective, multiplexer MUX 0  must perform two shifts, that is, M 0   0  and M 0   1  will be at zero, M 0   2  will be at 1, and all M 0   3  to M 0   k  will be at zero.  
         [0061]    Generally, the state of each of inputs M i+1 j of multiplexer MUX i+1  can be expressed according to the inputs of multiplexer MUX i  as follows:  
                     M   j     i   +   1       =                F     i   +   j   +   1       _     (       M   j   i     +       M     j   -   1     i     ·     F     i   +   j         +       M     j   -   2     i     ·     F     i   +   j   -   1       ·     F     i   +   j         +   …   +                                  M   0   i     ·     F     i   +   1       ·     F     i   +   2                       …                   F     i   +   j         )     ,       for                 0     ≤   j   ≤     k   .                     (   4   )                               
 
         [0062]    Based on equations (3) and (4), the equations of M i   j  can generally be obtained for any value of i and j according to variable F i . This may be performed by a simple algorithm. Such an algorithm first establishes in equation (4) value i+1=1 to obtain the equations of signals M 1   j  according to variables F i  and to variables variables M 0   r  with their expressions according to variables F i  as described by equations (3). Then, functions M 2   j  can be similarly calculated by setting i+1=2 in equation (4) then by replacing the expressions of functions M 0   r  and M 1   q  obtained at the preceding step and so on in functions M 3   j , M 4   j , . . . M N−1   j . The calculation of course stops for position N since, as seen previously, there are no multiplexers beyond this position. Signal R f =hu N 0 .M N   1 . . . M N   k  may be used to signal the success (R f=1 ) or the failure (R f=0 ) of a repair.  
         [0063]    Distant Repair  
         [0064]    As recalled in the introduction of the present application, repair operations from close to close such as illustrated in FIG. 1A are distinguished from distant repair operations such as illustrated in FIG. 1B in which the good units remain associated with their initial inputs while the defective units are replaced with units selected from the redundant unit group.  
         [0065]    For this distant repair mode, a sequential repair mode and a combinational repair mode will as previously be distinguished.  
         [0066]    Sequential Reconfiguration  
         [0067]    [0067]FIG. 4 illustrates a diagram of an embodiment of a sequential repair system.  
         [0068]    As in the diagram of FIG. 2, multiplexers MUX 0  to MUX N−1  associated with inputs d 0  to d N−1  intended to be connected to non-defective units are shown.  
         [0069]    In this example, the multiplexers are arranged from right to left instead of being arranged from left to right as previously. It could also have been chosen to modify the numbering and to start from N− 1  down to 0  
         [0070]    To each unit is associated a control circuit which, instead of being as previously a counter is, this time, formed of an assembly of k+1 flip-flops to memorize the exact values of the control signals in a 1-among-k+1 code. These control circuits are designated in FIG. 4 with references B 0  to B N-l .  
         [0071]    The flip-flops indicating the good or defective state of the blocks initially associated with the various multiplexers are designated as previously with references F 0  to F N−1  for the flip-flops associated with the base blocks and with references S 1  to S k  in the shown example for redundant blocks.  
         [0072]    As concerns the multiplexer control flip-flops, a smaller number of flip-flops may also be used in each assembly to code the values of these signals in a more compact code, for example, a binary code, combined with a decoder which provides the 1-among-k+1 code. This flip-flop assembly may be formed to only carry out the load function. In this case, another circuit will have to be used to calculate the number of positions by which the input output terminal d i  must be shifted towards the redundant blocks and these results will have to be loaded in the repair flip-flops.  
         [0073]    Another possibility is to provide the repair flip-flops according to a counter configuration as previously done.  
         [0074]    It should be noted that in the case of FIG. 4, the repair is performed according to a shifting to the right, which means that the leftmost functional unit is first repaired. Two sequential functions acting at the rate of a clock which, at each cycle, especially activates flip-flops F 0  to F N−1  and S 1  to S k  will be used.  
         [0075]    The first sequence using flip-flops F 0  to F N−1  generates signals EN 0  to EN N−1  which enable or not the corresponding control circuits. Each flip-flop F i  is connected to control circuit B i  by an AND gate  21  which previous flip-flops. Thus, if a flip-flop F i  contains a 0 (good corresponding block), control circuit B i  is inhibited and multiplexer MUX i  is not shifted. The output of flip-flop F i  is connected by an AND gate  22  to the input of flip-flop F i . Thus, if flip-flop F i  initially contains a 0, its state always remains at 0. The second input of AND gate  22  receives the OR function of all the previous flip-flops. Thus, in a clock cycle, only the control circuit associated with the defective block not yet repaired, located leftmost, is enabled.  
         [0076]    The second functional sequence is implemented by using flip-flops S 1  and S k  and generates at any time the number of positions having a defective block, at the considered cycle, signaled by an active signal EN i , which must be shifted towards one of the redundant blocks (not shown in FIG. 4). The output of each flip-flop S i  is connected at its input to an OR gate  23  having its input connected to the output of an AND gate  24  which receives the outputs of flip-flop S i−1  and of the previous AND gate. Call L i  the output of the AND gate which follows flip-flop S i . Outputs L i  are provided to a combinational  1  counter  25  which receives a 1 on its first input. Thus, counter  25  provides the number of positions by which the defective base block indicated by an active signal EN i  must be shifted in the redundant blocks to perform a repair.  
         [0077]    A combinational  1  counter may be formed in various ways. Two examples of such embodiments for k=3 and k=5 using full adders (with three inputs) FA and half-adders (with two inputs) HA are shown in FIG. 5. These counters provide a binary coded result. Other embodiments many provide a result coded in another way, for example, according to a 1-among-k+1 code.  
         [0078]    A sequential  1  counter may also be implemented. For example, this can be done by using a shift circuit with k+1 cells. Cell  0  is loaded with 1. Signals L 1 , L 2  . . . L k  shifted to the right until the first 0 is provided to the output.  
         [0079]    For the shift calculation, intermediary functions FI i  will be used. Function FI i  is at 1 if any one of signals F i , F i+1 , . . . F N−1  is at 1. This provides the following recursive equations: 
           FI   i   =FI   i−1   +F   i , with 0 ≦i≦N −1 and  FI   −1 =0  (5) 
         [0080]    Flip-flop F i  maintains its state while one of flip-flops F i−1 , F i−2 , . . . F N−1  is at 1. This condition implies that FI i−1 =1. One thus obtains: 
         F i (t+1)=FI i−1 .F i (t) with 0≦i≦N− 1   (6) 
         [0081]    Signal EN i switches to 1 if F i  is at 1 and all flip-flops F i−1  to F 0  are at 0. This implies that FI i−1 0. One thus obtains: 
         EN i ={overscore (FI i−1 )}.F i   (7) 
         [0082]    The circuit formed from flip-flops S i  updates the content of these flip-flops at each clock cycle. This updating is such that at any cycle, the flip-flops S i  indicating an available unit contain a 0 and the other flip-flops S i  contain a 1. Thus, an available redundant block is a defect-free block which is not yet taken up by the repair of a defective functional block. A defective redundant block remains always unavailable, that is, S i  remains always equal to 1. A defect-free redundant block becomes unavailable at a cycle t+1 if at cycle t all the preceding flip-flops S i  are at 1. Thus: 
         L 0 =1, L i  =L i− .S i , 1≦i ≦k  (8) 
           S   i ( t +1) = S   1 ( t ) + L   i−1 ,1  ≦i ≦k   (9) 
         [0083]    Based on these equations, signals L 1 , L 2  . . . L k  take values L 1 =L 2 =. . . =L j−1 =1, L j =L j+1 =. . . =L k =0, where j is the smallest integer for which S j =0. In this case, redundant block j+1 is the first redundant block available to perform a repair.  
         [0084]    Signals L k  and FI N−1  may be used to complete the repair phase. FI N−1 =0 indicates that all positions are correct and that the repair can be ended. L k 32 1 indicates that there is no remaining available unit.  
         [0085]    The repair can also be performed by using repair counters rather than repair flip-flops B i . The repair counter may be a binary counter followed by a decoder to generate a 1-among-k+1 code, or a shift register. In this case, counter  25  may be replaced with a sequential 1 counter such as a shift circuit. Value 1 of the leftmost cell of this shift circuit will be used to keep the states of flip-flops F and S. Value 0 of this cell will be used to maintain the state of the sequential counter until its next loading.  
         [0086]    The leftmost cell of the shift circuit will be at 1 for k i  clock cycles, where k i  is equal to the number of signals L j  having value 1, plus 1. Then, k i  is equal to the number of positions by which the defective block U i  indicated by state EN i =1 must be shifted towards the redundant units. Signal EN i  will be maintained at value 1 for k i  clock cycles. Thus, by using signal EN i  as the signal which enables the counting operation of the repair counter of position i, the values required on the control signals of the repair multiplexer of position i can be generated.  
         [0087]    With this last implementation, signals S 1 , S 2  S k  may also be loaded into the register implementing the 1 counter instead of signals L 1 , L 2  . . . L k . The reason for this is that these signals are equal until and including the leftmost position of state 0. These positions are those which determine the circuit operation.  
         [0088]    As previously, the distant repair system may also be implemented by a combinational function which will be defined in incremental fashion. Taking the notations of section 2.2, one has the following equations: 
         M 0   0 ={overscore (F 0 )} 
         M 0   1  ={overscore (S 1 )}.F 0  . . .  
         M 0   k ={overscore (S k )}.S k−1 . . . S 1 .F 0   (10) 
         [0089]    The equations corresponding to an arbitrary terminal d j  imply variables F and S. To calculate variables M i+1   j , it is not possible to use variables M i   r  as indicators of the number of redundant blocks taken up after the repair of some base blocks. This is due to the fact that if base block U i  is defect-free, all functions M i   1  to M i   k  are at 0 although some of blocks U 0  to U i−1  may be defective. Thus, intermediary variables MI i   j  which count the number of redundant blocks taken up by the defective base blocks are thus introduced. These variables are determined by the following equations.  
         [0090]    For position  0 , variables MI are equal to variables M: 
         MI 0   j =M 0   j  for 0≦j ≦k  (11) 
         [0091]    For position i+1, variables MI i+1   j  are equal to variables M i   j  if block U i+1  is defect-free. Otherwise they are equal to M i+1 j. Thus, one has: 
           MI   i+1   j   =MI   i   j   .{overscore (F i+1 )}+   M   i+1   j   .F   i+1 0 ≦i≦N −2 and 0 ≦j≦k   (12) 
         [0092]    Variable M i+1   0  is equal to 1 if block U i+1  is defect-free. Variable M i+1   j+1  is equal to 0 if block U i+1  is defect-free. If U i+1  is defective, M i+1   j+1  becomes equal to 1 if S j+1  is defect-free and if there exists an integer r≦j such that r defective and defect-free redundant blocks are already taken up to repair units U q  with q≦i, and redundant blocks S r+1 , S r+2  . . . S j  are defective. This analysis results in the following equations: 
         M i+1   0   ={overscore (F i+1 )},   
           M   i+1   j+1   ={overscore (S j+1 )}.   F   i+1 ( MI   i   j   +MI   i   j−1   S   j   +MI   i   j−2   S   j−1   S   j   + . . . MI   i   0   S   1   S   2   . . . S   j ), for 0 ≦j≦k −1, 0 ≦i≦k −2,  (13) 
         [0093]    Thus, equations (10) to (13) describe function M recursively and may be implemented by any appropriate software or hardware.  
         [0094]    Of course, the present invention is likely to have various alterations, modifications, and improvements which will readily occur to those skilled in the art. In particular, each state indication flip-flop is associated with enable signals for, in a test mode, loading according to the good or bad state of the corresponding block and, in repair mode, operating in the previously-described fashion.  
         [0095]    Alternative Multiplexings  
         [0096]    In FIG. 2, the data may propagate:  
         [0097]    from units U 1  to U N+k−1  to terminals d 0  to d N+k−1  (for example, in the case where d 0  to d N+k−1  are the read data bus of a memory).  
         [0098]    This case will be called a read-type configuration. from terminals d 0  to d N+k−1  to units U 1  to U N+k−1  (for example, in the case where d 0  to d N+k−1  are the unit selection signals).  
         [0099]    This case will be called a write type configuration.  
         [0100]    in both directions (for example, in the case where d 0  to d N+k−1  are the bi-directional read/write bus of a memory). This case will be called a bi-directional configuration.  
         [0101]    In the case of the bi-directional configuration, the used multiplexers must enable bi-directional propagation of the signals. A multiplexer of 1-among-4 type is shown in FIG. 6. A bi-directional multiplexer may also be used in the case of configurations of read type and of write type.  
         [0102]    In the case of the read-type configuration, a multiplexer only enabling propagation of the k output signals D 0  to D k−1  from units U 1  to U N+k−1  to signal d may also be used. Such a multiplexer for the case k=4 is shown in FIG. 7.  
         [0103]    In the case of the write-type configuration, a “multiplexer” only enabling propagation of signal d towards the k signals D 0  to D k−1  may also be used. This circuit, which is not a multiplexer in the usual meaning of this term, will be called k-among-1 MUX. A circuit of this type for case k=4 is shown in FIG. 8. It should be noted that in this drawing, M j   i =1 implies D j =0. Accordingly, if a signal G is to be generated by combining several signals D j  coming from the outputs of several circuits of k-among-1 type, an OR gate receiving signals D j  and providing signal G must be used. However, if a bi-then the OR gate will not be used since signal G will be generated by using a wired connection of signals D j . Thus, a write-type configuration, using circuits of k-among-1 MUX type, will require replacing the wired connection of signals D j  with OR gates, while the use of bi-directional multiplexers does not require use of OR gates. However, in certain cases, the signal provided to a unit must take value 1 in the active state and value 0 in the inactive state. This constraint is not fulfilled when the bi-directional multiplexer of FIG. 6 is used; it is however fulfilled when the circuit of k-among-1 MUX type shown in FIG. 8 is used, combined with the OR gate. The signal provided to a unit may also have to take value 0 in the active state, and value 1 in the inactive state. In this case, circuits of k-among-1 MUX type performing the function M j   i =1 implies D i =d and M j   i =0 implies D i=1 , combined with AND gates, will be used.  
         [0104]    In other implementations, the outputs d of the several 1-among-k multiplexers may be combined to generate a signal G. If bi-directional multiplexers are used, signal G can be generated by using a wired connection of signals d. However, if 1-among-k multiplexers formed as in FIG. 7 are used, the wired connection must be replaced with an OR gate. The reason for this is that the multiplexer of FIG. 7 implements the following function: M 0   i , M 1   i , .M j   i , . . . M k   i =00 . . . 1 . . . 0 implies d=D j  and M 0   i =M 1   i , . . . =M j   i . . . =M k   i =0implies d=0. Thus, it will be less expensive to use a bi-directional multiplexer. However, signal G may take value 0 in the inactive state. In this case, it will be necessary to use a multiplexer formed as in FIG. 7. On the other hand, if signal G must take value 1 in the inactive state, multiplexers of 1-among-k type must be used, implementing the following function: M 0   i , M 1   i , . . . M j   i , . . . M k   i =00 . . . 1 . . . 0 implies d=D j  and M 0   i =M 1   i , . . . =M j   i , . . . =M k   i =0 implies d=1.  
         [0105]    A last case of the multiplexing circuits corresponds to circuits implementing the same functions as those described previously, except that complementary values are applied to their inputs. For example, implication M 0   i , M 1   i , . . . M j   i , M k   i =00 . . . 1 . . . 0 implies d=D j , becomes M 0   i , M 1   i , . . M j   i , . . . M k   i  =11 . . . 0 . . . 1 implies d=D j .  
         [0106]    Another way of performing the branching from close to close is shown in FIG. 9, in which N=3 and k=2. To perform the multiplexing, branching circuits such as shown in FIGS. 6, 7, and  8  are used. If the circuits of FIG. 1A are bi-directional multiplexers, FIG. 9 will use bi-directional multiplexers. If the circuits of FIG. 1A are 1-among-k multiplexers like the circuit of FIG. 7, FIG. 9 will use branching circuits of k-among-1 MUX type, like the circuit of FIG. 8. If the circuits of FIG. 1A are circuits of k-among-1 MUX type like the circuit of FIG. 8, FIG. 9 will use 1-among-r multiplexers, like the circuit of FIG. 7.  
         [0107]    It is considered that FIG. 9 uses circuits of r-among-1 MUX type. Terminal d of each of these circuits is connected on the input/output signal of one of units U 1 , U 2 , . . . , U N+k−1 . The branching circuit connected to the input/output of unit U i  will be called CM i .  
         [0108]    Terminals D j  of the branching circuits are combined to generate signal d 0 , d 1 , . . . d N+k−1 . For the branching circuits CM i  of r-among-1 type, the values of r will be: 
           r=i +1 for 0 ≦i≦k −1, 
           r=k +1 for  k≦i≦N −1, 
           r=N+k−i  for  N≦i≦N+k −1. 
         [0109]    For 0≦i+j≦N−1, signal M i   j  selects the connection of terminal D i  of circuit CM i+j  to the input/output terminal of unit UM i+j . For N≦i+j≦N+k−1, signal M i   j  selects the connection of terminal D N−j− 1 of circuit CM i+j  to the input/output terminal of unit UM i+j . The terminals D i  selected by signals M i   0 , M i   1 , . . . , M i   k  are combined to same if the branching circuits of FIG. 9 are 1-among-r multiplexers.  
         [0110]    A similar transformation may be used in the case of the distant configuration system illustrated in FIG. 1B. In this case, parameter r of the branching circuits takes the following values: 
         r=1 for 0≦i≦N−1, 
         [0111]    and 
         r=k+1 for N≦i≦N+k−1. 
         [0112]    For 0≦i≦-1, signal M i   0  selects the connection of the input/output terminal of unit U i  to terminal D 0  of branching circuit CM i , which indeed has a single terminal of type D i . For 0≦i≦N−1 and 1≦j≦k, signal M i   j  selects the connection of the input/output terminal of unit U N+j−i  to terminal D i  of branching circuit CM N+j−i . The terminals D i  selected by signals M i   0 , M i   1 , . . . , M i   k  are combined to generate signal d i .  
         [0113]    In systems obtained by the preceding transformations, signals M i   j  take the same values as in the original system. The solutions for generating signals M 1   j  discussed herein are thus valuable for systems obtained by these transformations.  
         [0114]    Repairs Using an Insufficient Redundancy  
         [0115]    A system comprising N functional units, k redundant units and capable of repairing up to r defective units, with r&gt;k≧0 is now considered. In the case where the number of defective units does not exceed k, the system, after repair, will operate with N units. If the number of defective units is q with k&lt;q≦r, the system will operate with N+k−q units. It is assumed that N selection signals d 0 , d 1 , . . . , d N−1  are available, each selecting a unit. The repair will consist of rerouting signals d 0 , d 1 , . . . , d N+k−q−1  to replace each defective functional unit with a defect-free unit. Further, the repair system may possibly units so that the rest of the system only uses the resources of the non-defective units which will be seen by the system as being the first N+k−q units of the configuration.  
         [0116]    To illustrate the advantage of this solution, consider that units U 0 , U 1 , . . . , U N+k−1  are blocks of a memory, each comprising R addresses. The system can exploit a memory comprising a total number of R.N addresses. In this configuration, it provides the best performances, but it may also operate with a memory of smaller capacity.  
         [0117]    Signals d 0 , d 1 , . . . d N−1  are generated, for example, by the decoding of a number of addressing bits equal to [log 2 (N)]. Value 00 . . . 0 of these bits enables signal d 0 , value 00 . . . 1 enables signal d 1 , etc., until value N−1 expressed in binary notation, which will enable d N− 1. In the case of q defective units where the system will use a memory space comprising only R(N+k−q) addresses, it is important for this addressing space not to be fragmented, that is, the system has a memory covering addressing space 0, 1, . . . R(N+k−q). The provided repair system enables this unification by the rerouting of signals d 0 , d 1 , . . . d N+k−q− 1 and may provide signals indicating the invalid addressing space.  
         [0118]    The technique provided herein to d 0  this repair implements the same repair circuit in the case where number k of the redundant units is equal to number r of defective units that are intended to be repaired, except for given multiplexers, as will be described hereafter.  
         [0119]    A local repair is here considered. The missing units to have a number of redundant units equal to r are units U N+r−i  such that 1≦i≦r−k.  
         [0120]    The groups of control signals that select any unit U N+r−i  such that 1≦i≦r−k are signals M N−j   r+j−i  such that 1≦i≦r−k and 1≦j≦i. This control signal group will not enter the multiplexer of rank N−j, which will thus have will further have r+j−i terminals of type D q  instead of r+1. The missing terminals will be the terminals D r−j+1  such that 1≦j≦i .  
         [0121]    Further, the control signals unused by the multiplexers may be used to indicate the invalid addressing space. For this purpose, binary signals @i will be formed for any i, such that 1≦i≦r−k. These signals are determined by:  
         @   i     =       ∏     j   =   1     i          M     r   +   j   -   i       N   -   j                               
 
         [0122]    In this formula,  
         ∏     j   =   1     i          G   j                           
 
         [0123]    represents the logic AND of all terms G j  such that 1≦j≦i. The signal @i with the smallest index i such that @i=1 indicates that the addressing is limited to the sole (N+k+i−r−1)R first addresses.  
         [0124]    [0124]FIG. 10 gives the example of the technique for N=4 functional units, k=2 redundant units, and r=3 repairable defective units. It should be observed that the implementation is the same as in the case where N=4, k=r=3 (4 functional units, 3 redundant units, and 3 repairable defective units), except for the last multiplexer which is a 1-among-3 multiplexer instead of a 1-among-4 multiplexer. Signal @1=M 3   3  indicates that the last R addresses are invalid.  
         [0125]    Repair for a CACHE Memory  
         [0126]    A last repair solution resulting in very low costs relates to the case of CACHE memories. These memories may have a memorization point or flag, called hereafter a validity flag, or Fg. Fg indicates whether a memory word is valid or invalid. For example, Fg=1 indicates that the word is valid and Fg=0 indicates that the word is invalid. In this last case, the system performs the operation in another one of its memories. The value of the memorization point is handled during the system accesses to the CACHE memories and to the other memories. It is here provided to introduce for each word in the CACHE memory (or for a set of words) another flag-type memorization point, here called a defect flag or Fd. The content of Fd is handled only during the circuit testing, and it is set to the value indicating a defective word (for example, for Fd=1) or to the value indicating a non-defective word (for example, for Fd=0). Upon operation of the system, the content of Fd is blocked at its value set in the test phase. Then, if Fd indicates a defective word, the operation will be performed in another memory. Given that the value of Fd has been set before the system operation starts, no operation will be performed in the defective word, and any data which could have been stored in the word had it been non-defective, will be stored in another memory, enabling coherent operation of the system. Given that the number of defects in an integrated circuit is generally small, this approach non-significantly reduces the CACHE capacity and it has but a minute influence upon the system performances.  
         [0127]    The CACHE memories are used to reduce the frequency of the accesses to the system memory. The cells of a word of a CACHE memory are shared in a portion called the key and in a data portion. The addressing bits of the system memory are divided in two parts, called hereafter the first part and the second part. The first part of the addressing bits is used to select a word from the CACHE memory. In a write operation, the second part of the addressing bits is stored in the key portion of the selected word, while the data of the write operation are stored in the data portion. In a read operation, the key portion and the data portion of the selected word are read. The content of the key portion is compared with the second part of the addressing bits of the write operation. If the comparison succeeds, it can be said the values read from the data portion are used as the result of the read operation. If the comparison fails, the system memory is accessed to to perform a reading. In most cases, each value of the first part of the addressing bits selects a single word from the CACHE memory. But in certain CACHE memories, the same value of the first part of the addressing bits may select several words. Thus, in the first case, if a word is invalid since its defect flag indicates a defective word, then each operation, such that the value of the first part of the addressing bits selects this word, will be performed in the system memory. In the second case, an operation selecting a word of which the defect flag indicates that it is defective will not necessarily have access to the system memory, since the operation may succeed in one of the other words of the CACHE memory selected by the same value of the first part of the addressing bits.  
         [0128]    A similar technique may be used for CAM-type memories (Content Addressable Memory). A CAM may be considered as a CACHE memory for which the first part of the addressing bits is empty. Thus, all addressing bits are stored in the key portion. However, the key portion of each word has a comparator. Thus, in a read operation, the read address is compared in parallel with the content of the key portion of each word. If the comparison succeeds for a word, the output of the comparator of this word selects the data portion of the word. Thus, the content of the data portion of the word can be read at the memory output.  
         [0129]    In write mode, there are two possible cases.  
         [0130]    Like for a reading, the address is compared with the key portion of the words. If the comparison succeeds for a word in the CAM, the output of the comparator of this word selects the data portion of the word and the writing is performed into this portion.  
         [0131]    There is no comparison of the address, but a criterion is used to select a word from the CAM, and the write address is written into the key portion of the word, and the data of the write operation are written into the data portion of the word. In this case, to select the word to be written, various criteria are used from one system to the other. Often, this type of writing selects the word to which access has been had the least recently, but other criteria are also used according to the system. The use of flags which allow or forbid access to a word also is a current doing.  
         [0132]    To repair a CAM, a defect flag cell Fd is added to each word. In test phase, if a defect is detected in a word, a 1 is written into the cell of flag Fd of the word. In normal operation, value 1 of flag Fd forbids any access to the defective word. The operations implying the defective word may then be performed in another memory of the system. However, conversely to a CACHE memory, in a CAM, any word can be replaced with any other word. In fact, given that each word is selected only by the content of its key portion, there is no word differentiation according to the value of the addressing bits. Thus, in the present case, there is no need to access to another system memory, since all operations can be performed in the non-defective words of the repaired CAM. Further, the CAM may comprise a sufficient number of words to have after repair a satisfactory capacity for the system.  
         [0133]    The CAM provided herein may further be used to repair another memory by replacing each defective word with a non-defective word of the CAM. For this purpose, the following steps are carried out.  
         [0134]    The CAM is first tested and, each time a defect is detected in a word, a 1 is written into flag Fd of this word. The content of flags Fd is no longer modified after  
         [0135]    The memory to be repaired is tested and, each time a defect is detected in a word, the value of the address which has selected the defective word is written into the key portion of a word in the CAM. To select the CAM word in which this writing will be performed, various procedures may be used. Such a procedure consists of using, in the test phase of the memory, a binary counter with a decoder. Each output of the decoder selects in a test phase of the memory a CAM word. On each writing into the CAM, the counter is incremented. Thus, the next writing of an address will be performed into another word. During this phase, the value of flag Fd is also verified. If, for a CAM word, one has Fd=1, then another CAM word is selected to write an address. In the implementation using the counter and the decoder, each time a word is selected with Fd=1, the counter is incremented again, before writing an address. Of course, the counter and the decoder may be replaced with a shift register having one bit set to 1, and all its other bits at 0.  
         [0136]    In normal operation, each address of a write or read operation in the memory is compared in parallel with the key portions of all the CAM words. If the comparison succeeds for a word, which further has Fd=0, the current operation is performed in this CAM word, instead of being performed in the memory. Thus, in the case of an operation intended to write into the memory, the data to be written are written into the data portion of this CAM word, and in case of a reading, the data portion of this CAM word is read from and the result is provided to the system instead of the data that should be read from the memory.  
         [0137]    It is thus succeeded in repairing the defective words in the memory, as well as in protecting the system against defects in the CAM words. It should be noted Fd, and in another portion of the word, the defective flag may indicate that the word is not defective. To reduce the probability of this event, the cell of this flag may be repeated once or several times, and the word may be invalidated if at least one of the flag cells is at 1. However, the probability of occurrence of such defects remains very low for current technologies and a single cell will be used for flag Fd. The increase in the density of the defects provided for nanotechnologies may make the replication of the cells of flag Fd advantageous.  
         [0138]    The repair system may be provided so that the memory can be reconfigured not only during the manufacturing test, but also during the different test phases executed along the circuit lifetime. In this case, Fd will be stored in a reprogrammable memorization point (volatile or non-volatile). On the other hand, if the repair is only performed during the manufacturing test, Fd may be stored in a non-reprogrammable memorization point, for example, in a device setting a logic value by means of a fuse.  
         [0139]    In the foregoing description of combinational reconfiguration systems, codings of 1-among-k+1 type of states M i   0  to M i   k  of demultiplexer inputs have been described. Binary coding systems could also have been provided. It will be within the abilities of those skilled in the art to perform a bi-unique correspondence between the two coding types. In this case, the binary signals will take value q when signal M i   q  is equal to 1 and all the other signals M i   0  to M i   k are at  0. Those skilled in the art may further apply this principle to code the number of shifts by one position according to any other code.  
         [0140]    Such alterations, modifications, and improvements are intended to be part of this disclosure, and are intended to be within the spirit and the scope of the present way of example only and is not intended to be limiting. The present invention is limited only as defined in the following claims and the equivalents thereto.