Abstract:
An error correction circuit is provided which uses NMOS and PMOS synapses to form network type responses to a coded multi-bit input. Use of MOS technology logic in error correction circuits allows such devices to be easily interfaced with other like technology circuits without the need to use distinct interface logic as with conventional error correction circuitry.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to an error correction circuit and more particularly to an error correction circuit which is based on a neural network model. 
     2. Background of the Invention 
     A data processing system made of conventional logic circuits is getting bigger in size and more complex in its arrangement of components. As a result, increasing circuit complexity creates unexpected problems and rising manufacturing costs. 
     In addition, the need to improve accuracy and reliability of every block in the system or its respective subsystems, demands that techniques for providing error correction be included. However, systems based on simple logic circuits have performance limitations due to inherent property characteristics of logic gates. 
     To overcome such limitations of logic circuit technologies a system design based on the concept of a neural network model has been actively studied. 
     An error correcting system based on neural network principles is shown in FIG. 1. This system was presented in the IEEE first annual international conference on neural networks in Jun. 1987, which has a reference number of IEEE catalog #87TH0191-7, by Yoshiyasu Takefuji, Paul Hollis, Yoon Pin Foo, and Yong B. Cho. 
     The error correcting system presented at the above conference uses the concept of neural network principles, based on the Hopfield model, discloses a circuit which performs significantly faster than prior error correcting systems. 
     However, since the circuit by Yoshiyasu Takefuji et al. uses operational amplifiers as neurons and a passive resistor element network to form synapses, VLSI implementation is quite limited. The reason being that on a semiconductor integrated circuit, a resistor element network has high power consumption and thus hinders manufacturing of a high integration circuit design. 
     Furthermore, the above circuit is further inadequate since it requires additional interfacing circuitry added whenever a digital system based on NMOS and CMOS technologies is coupled thereto. 
     SUMMARY OF THE INVENTION 
     Accordingly, it is an object to provide an error correction circuit having a design which is based on neural network principles and which uses MOS transistors formed on semiconductor VLSI logic. 
     It is another object to provide an error correction circuit which is directly connectable to conventional NMOS and CMOS digital system technology without requiring additional interface logic. 
     In achieving the above objects, the present invention is characterized in that the circuit comprises: 
     n input neurons; 
     2 k  output neurons; 
     a plurality of first synapses; 
     a plurality of second synapses; 
     a plurality of first biasing synapses; 
     n inverters; 
     a plurality of third synapses; and 
     a plurality of second biasing synapses. 
     The neurons are buffer amplifiers in which two CMOS inverters are connected in cascade. A synapse for transferring an excitatory state includes a PMOS transistor, and a synapse for transferring an inhibitory state includes an NMOS transistor. 
     The connecting strength of synapses is determined by the geometrical aspect ratio W/L of each respective transistor and corresponds to the ratio of a transistor&#39;s channel width to its channel length. 
     In the present invention, the error correction circuit is made using CMOS technology and thus designed to be directly interfaceable to other CMOS and related technologies without the use of additional interface logic. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above objects and other advantages of the present invention will become more apparent by describing the preferred embodiment of the present invention with reference to the attached drawings, in which: 
     FIG. 1 is a circuit diagram showing a conventional error correction circuit having a design based on neutral network principles; and 
     FIG. 2A-2F is a circuit diagram of a preferred embodiment showing a 1 bit error correction circuit of (7,4) codewords according to the present invention; 
     FIG. 3A1-3A7 and FIG. 3B1-3B5 combined, illustrate a circuit diagram of another embodiment of the present invention which provides 2 bit error correction of (14,6) codewords; and 
     FIGS. 4 and 5 show input and output waveform signals, respectively, for the circuit in FIGS. 3A and 3B. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In error correcting circuits, an (n,k) code word represents k actual data bits and n-k check bits. That is, the codeword is n bits long and contains k actual data bits. Generally, an (n,k) code can generate all 2 k  codes by using the following polynomial generating equation The equation is 
     
         C(X)=D(X) * G(X) 
    
     where, C(X) is a codeword polynomial of the degree lower than 
     
         n-1, 
    
     D(X) is a data polynomial of the degree lower than n-k, and 
     G(X) is a generating polynomial of the (n-k) the degree. 
     Thus, encoding the data polynomial D(X) means getting the codeword polynomial C(X) from D(X) multiplied by G(X). 
     Embodiment I 
     In a 1 bit error correction circuit of (7,4) codewords, when the generating polynomial of G(X)=X 3  +X+1 is given to code a 4 bit data string as a (7,4) codeword, the following (7,4) codewords shown in Table 1 are obtained. 
     
                                           TABLE 1__________________________________________________________________________date bits                COO = DOO · GOOX.sub.3  X.sub.2    X.sub.1 X.sub.0   DOO       GOO    X.sub.6                      X.sub.5                        X.sub.4                          X.sub.3                            X.sub.2                              X.sub.1                                X.sub.0__________________________________________________________________________0 0 0 0                  0 0 0 0 0 0 00 0 0 1 1                0 0 0 1 0 1 10 0 1 0 X                0 0 1 0 1 1 00 0 1 1 X + 1            0 0 1 1 1 0 10 1 0 0 X.sup.2          0 1 0 0 1 1 10 1 0 1 X.sup.2 + 1      0 1 0 1 1 0 00 1 1 0 X.sup.2 + X             X.sup.3 +X+1                    0 1 1 0 0 0 10 1 1 1 X.sup.2 + X + 1  0 1 1 1 0 1 01 0 0 0 X.sup.3          1 0 0 0 1 0 11 0 0 1 X.sup.3 + 1      1 0 0 1 1 1 01 0 1 0 X.sup.3 + X      1 0 1 0 0 1 11 0 1 1 X.sup.3 + X + 1  1 0 1 1 0 0 01 1 0 0 X.sup.3 + X.sup.2                    1 1 0 0 0 1 01 1 0 1 X.sup.3 + X.sup.2 + 1                    1 1 0 1 0 0 11 1 1 0 X.sup.3 + X.sup.2 + X                    1 1 1 0 1 0 01 1 1 1 X.sup.3 + X.sup.2 + X + 1                    1 1 1 1 1 1 1__________________________________________________________________________ 
    
     As shown in Table 1, when only 1 bit errors can occur, the number of possible errors for each coded 4 bit data string equals 7. For example, code pattern &#34;1011000&#34; is explained in detail in Table 2. 
     
                       TABLE 2______________________________________The error states of code pattern &#34;1011000&#34;______________________________________0011000111100010010001010000101110010110101011001______________________________________ 
    
     As shown in Table 2, each 1 bit error state of &#34;1011000&#34; does not match any of the other codewords. In connection with the smallest Hamming distance, the number of check bits is calculated by using the following equation: 
     
         Df≧2t+1 
    
     where 
     t is the number of corrected bits, and 
     Df is the number of check bits. 
     In FIG. 2, a 1 bit error correction circuit is shown as a (7,4) codeword according to the present invention. The error correction circuit comprises a decoder section of the single layer perceptron model type and an encoder section for providing correction. 
     Decoder 10 includes input neurons IN1 to IN7. Each input neuron is made by interconnecting two CMOS inverters. The output lines of a first one of the CMOS inverters corresponding to inverted output lines RL1 to RL7. The output lines of the other inverter corresponding to non-inverted output lines NRL1 to NRL7. Decoder 10 has 2 4  =16 output neurons ON1 to ON16 made by interconnecting two CMOS inverters. These output means drive respective output lines IL1 to IL16 into one of an excitatory state or an inhibitory state in response to the difference between the excitatory strength and the inhibitory strength pressed on each such respective input line IL1 to IL16. 
     NMOS transistors (first synapses 11) are connected along each position corresponding to a &#34;0&#34; for all of 16 codewords shown in Table 1 and connected at corresponding intersections of the noninverted output lines of the input neurons and the input lines of the output neurons. 
     PMOS transistors (second synapses 12) are connected along each position corresponding to a &#34;1&#34; of the same 16 codewords and connected at corresponding intersections of the inverted output lines of the input neurons and the input lines of the output neurons. 
     Each NMOS transistor is turned on when its corresponding noninverted output line is in a &#34;HIGH&#34; state and serves to transfer an inhibitory state, such as Vss or a ground potential, of unit connecting strength to the input line to which its respective drain is connected. 
     Each PMOS transistor is turned off when its corresponding inverted output line is in a &#34;LOW&#34; state and serves to transfer an excitatory state, such as Vcc or a supplying voltage, e.g. 5 V, of unit connecting strength to the input line to which its respective drain is connected. 
     A unit connecting strength is defined as a transistor width-to-length ration W/L that ratio being 6/2 [μm/mm] for a PMOS transistor and 2/2 [μm/mm] for an NMOS transistor. 
     When the excitatory strength is almost equal to the inhibitory strength, the conductance of the PMOS transistor is designed such that its unit connecting strength is superior to the conductance of a single NMOS transistor. As a result, in a balanced situation where the unit connecting strengths of all PMOS transistors is equal to that of all NMOS transistors, the excitatory state will prevail. 
     In addition, first biasing synapse circuit 13, consisting of NMOS and PMOS bias transistors, is connected to respective input lines of the output neurons. First biasing synapse circuit 13 has transistor excitatory or inhibitory connecting strengths assigned according to the value subtracted the number of bits to be corrected from the number of the second synapses 12 along each corresponding bias line. 
     In an example of code pattern &#34;0001011&#34; which is to be 1 bit error corrected, a corresponding first biasing synapse transistor is coupled to 3 PMOS transistors. As a result, an NMOS first biasing transistor is provided with a connecting strength of 3-1=2 to therefore transfer a bias inhibitory state. 
     This NMOS transistor is formed having a geometrical aspect ratio of W/L=2 . (2/2) [μm/μm]. 
     The first transistor in the first biasing synapse circuit 13 connected to first input line IL1 has no PMOS transistors coupled thereto. Thus, in a 1 bit error correction circuit, a PMOS first biasing transistor is provided in response to a connecting strength of 0-1=-1 which serves to transfer an excitatory state. First biasing synapse circuit 13 makes only the output line of the output neuron, which corresponding codeword has the most similar pattern to the synapse pattern connected to the input line, excitatory. That output neuron will have a value of &#34;1&#34; and the other 15 output lines will be in the inhibitory state and will have value &#34;0&#34;. 
     An excitatory output at each respective output neuron will occur for any one of eight unique code pattern input into decoder 10. 
     As described above, when the correct codeword is decoded among 16 possible codewords in decoder 10, the codeword is corrected in encoder 20. The encoder 20 includes lines L1 to L7 which are crossed with output lines OL1 to OL16 respectively coupled to outputs of output neurons ON1 to ON16. Lines of L1 to L7 are connected to output terminals via respective inverters INV1 to INV7. 
     Encoder 20 includes NMOS transistors (third synapses 21) selectively positioned at corresponding values of &#34;1&#34; of the (7,4) codewords shown in Table 1 and coupled along respective intersections between output lines OL1 to OL16 and lines L1 to L7. The NMOS transistors are turned on in response to a &#34;HIGH&#34; state from an excited output line connected to the gates of the transistors. As such, an inhibitory state (i.e., Vss or ground potential) is transferred with unit connecting strength to the line to which respective drains of the NMOS transistors are connected. Second biasing synapse circuit 22 ncludes unit connecting strength PMOS transistors connected to lines L1 to L7, as shown in FIG. 2. More specifically, first biasing synapses 13 cause the input lines of output neurons ON1 to ON16 to be high or lo in accordance with the following rules: 
     
         ______________________________________1.     If (A - B) + C &gt; D,  THEN TRANSFER INHIBITORY STATE2.     IF (A - B) + C &lt;= D,  THEN TRANSFER EXCITATORY STATE______________________________________ 
    
     where: 
     A is the number of PMOS (second) synapses in the word which should be transferring an excitatory state, 
     B is the number of PMOS (second) synapses in the word which actually are transferring an excitatory state, 
     C is the number of NMOS (first) synapses in the word which actually are transferring an inhibitory state, and 
     D is the number of bits the code corrects. 
     The implementation of these rules is accomplished by connecting the biasing synapses with a connecting strength equal to: 
     
         (# of PMOS (second) synapses in a word)-(# of bits the code corrects). 
    
     Second biasing synapse circuit 22 transfers the exciting state, i.e. Vcc or supplying voltage, to the line to which the respective transistor drains are connected to drive the output terminals of excited input inverters to &#34;0&#34;, i.e. the &#34;LOW&#34; state usually. 
     Generally, in encoder 20 the unit connecting strength of each NMOS transistor is set to 2/2 [μm/μm] and the unit connecting the strength of each PMOS transistor is set to 5/2 [μm/μm]. Therefore, when the excitatory connecting strength is equal to the inhibitory connecting strength, the inhibitory state is eminently activated. The following Table 3 shows the results from the input data of the error correction circuit. 
     
         ______________________________________input DATAoutput DATA______________________________________0000000    0001011     0010110    00111010000001    0001010     0010111    00111000000010    0001001     0010110    00111110000100    0001111     0010010    00110010001000    0000011     0011110    00101010010000    0011011     0000110    00011010100000    0101011     0110110    01111011000000    1001011     1010110    10111010000000    0001011     0010110    0011101______________________________________0100111    0101100     0110001    01110100100110    0101101     0110000    01110110100101    0101010     0110011    01110000100011    0101000     0110101    01111100101111    0100100     0111001    01100100110111    0111100     0100001    01010100000111    0001100     0010001    00110101100111    1101100     1110001    11110100100111    0101100     0110001    0111010______________________________________1000101    1001110     1010011    10110001000100    1001111     1010010    10110011000111    1001100     1010001    10110101000001    1001010     1010111    10111001001101    1000110     1011011    10100001010101    1011110     1000011    10010001100101    1101110     1110011    11110000000101    0001110     0010011    00110000000000    1001110     1010011    1011000______________________________________1100010    1101001     1110100    11111111100011    1101000     1110101    11111101100000    1101011     1110110    11111011100110    1101101     1110000    11110111101010    1100001     1111100    11101111110010    1111001     1100100    11011111000010    1001001     1010100    10111110100010    0101001     0110100    01111111100010    1101001     1110100    1111111______________________________________ 
    
     Embodiment II 
     A 2 Bit Error Correction Circuit Of (14,6) Code 
     When the generating polynomial equation of G(X)=X 3  +X 7  +X 6  +X 4  +1is applied, 2 6  =64 codewords shown in Table 4 can be obtained. 
     
                       TABLE 4______________________________________ 1            000000       00000000 2            000001       00010111 3            000010       00101110 4            000011       00111001 5            000100       01011100 6            000101       01001011 7            000110       01110010 8            000111       01100101 9            001000       1011100010            001001       1010011111            001010       1001011012            001011       1000000113            001100       1110010014            001101       1111001115            001110       1100101016            001111       1101110117            010000       0111000018            010001       0110011119            010010       0101111020            010011       0100100121            010100       0010110022            010101       0011101123            010110       0000001024            010111       0001010125            011000       1100100026            011001       1101111127            011010       1110011028            011011       1111000129            011100       1001010030            011101       1000001131            011110       1011101032            011111       1010110133            100000       0101001034            100001       0100010135            100010       0111110036            100011       0110101137            100100       0000111038            100101       0001100139            100110       0010000040            100111       0011011141            101000       1110101042            101001       1111110143            101010       1100010044            101011       1101001145            101100       1011011046            101101       1010000147            101110       1001100048            101111       1000111149            110000       0010001050            110001       0011010151            110010       0000110052            110011       0001101153            110100       0111111054            110101       0110100155            110110       0101100056            110111       0100011157            111000       1001101058            111001       1000110159            111010       1011010060            111011       1010001161            111100       1100011062            111101       1101000163            111110       1110100064            111111       11111111______________________________________ 
    
     In view of the 64 codewords from Table 4, a 2 bit error corrected state should not be matched with the other codewords. The smallest Hamming distance is known as 5 bits from the above described codewords, 8 bit check codewords are needed. For instance, when errors in the second codeword &#34;00001 00010111&#34; are to be detected, the number of possible error states are 106. That is, there are those cases where the codeword is itself, adds 1 bit, is missing a 1 bit, adds 1 bit and is missing 1 bit, adds 2 bits, and is missing 2 bits. The respective 106 cases will be shown in the following Table 5 to Table 9 for codeword &#34;000001 00010111&#34;. 
     
                       TABLE 5______________________________________The error state of adding 1 bit to&#34;000001 00010111&#34;______________________________________  100001        00010111  010001        00010111  001001        00010111  000101        00010111  000011        00010111  000001        10010111  000001        01010111  000001        00110111  000001        00011111______________________________________ 
    
     
                       TABLE 6______________________________________The error state of missing 1 bit from&#34;000001 00010111&#34;______________________________________  000000        00010111  000001        00000111  000001        00010011  000001        00010101  000001        00010110______________________________________ 
    
     
                       TABLE 7______________________________________The case of adding 1 bit and missing 1bit to &#34;0000100010111&#34;______________________________________100000 00010111 010000   00010111                           001000 00010111100001 00000111 010001   00000111                           001001 00000111100001 00010011 010001   00010011                           001001 00010011100001 00010101 010001   00010101                           001001 00010101100001 00010110 000001   00010110                           001001 00010110000100 00010111 000010   00010111                           000000 10010111000101 00000111 000011   00010011                           000001 00010011000101 00010011 000011   00010011                           000001 00010011000101 00010101 000011   00010101                           000001 00010101000101 00010110 010011   00010110                           000001 00010110000000 00010111 011001   00110111                           000000 00011111000001 01000111 000001   00100111                           000001 00001111000001 01010011 000001   00110011                           000001 00011011000001 01010101 000001   00110101                           000001 00011101000001 01010110 000001   00110110                           000001 00011110______________________________________ 
    
     
                       TABLE 8______________________________________The case of adding 2 bits to &#34;00000100010111&#34;______________________________________110001 00010111 011001   00010111                           001101 00010111101001 00010111 011001   00010111                           001001 00010111100101 00010111 010011   00010111                           001001 10010111100011 00010111 010001   10010111                           001001 01010111100001 10010111 010001   01010111                           001001 00101111100001 01010111 010001   00110111                           001001 00011111100001 00110111 010001   00011111                           100001 00011111000111 00010111 000011   10010111                           000001 11010111000101 10010111 000011   01010111                           000001 10110111000101 01010111 000011   00110111                           000001 10011111000101 00110111 000011   00011111                           000101 00011111000001 01110111 000001   00111111                           000001 01011111______________________________________ 
    
     
                       TABLE 9______________________________________The case of missing 2 bits from &#34;00000100010111&#34;______________________________________000000 00000111 000001   00000011                           000001 00010001000000 00010011 000001   00000101                           000001 00010010000000 00010101 000001   00000110                           000001 00010100000000 00010110______________________________________ 
    
     As described above, when any one of the above 106 inputs is entered, only the output value of the second codeword position will be 1, and the other output values of the remaining 63 codeword positions will be 0. 
     In FIG. 3A and FIG. 3B, the 2 bit error correction circuit of (14,6) code is expanded proportional to the length of the 1 bit error correction circuit of (7,4) shown in FIG. 2 so that it has the same concept and the detailed description will be omitted. 
     FIG. 4 illustrates the input waveforms of the error patterns of &#34;00000100010111&#34; and &#34;000000 000000000&#34;. First the initial value of the input is shown set to 0; then there is input error states which add 1 bit and then add 2 bits; &#34;00000100010111&#34; pattern; missing 1 bit; missing 2 bits; adding 1 bit; and missing 1 bit at 5 msec intervals. 
     FIG. 5 illustrates the respective output waveforms corresponding to the above input waveforms in FIG. 4. When a possible error state to &#34;000000 00000000&#34; is entered, &#34;000000 000000000&#34; is outputted. When a possible error state of &#34;00000100010111&#34; is entered, &#34;00000100010111&#34; is outputted. 
     Therefore, the present invention achieves eminence by providing simplicity, capacity for parallel processing, faster processing velocity, and VLSI implementation.