Error Correcting Circuit Arrangement Using Cube Circuits

The present invention relates to a 2-bit error correcting circuit arrangement using cube circuits, more particularly, a BCH code check matrix H in which (n+1) cube circuits as check circuits, each corresponding to each of the data bits d.sub.o to d.sub.n, are so arranged in parallel that the error correction may be carried out quickly, and the same circuit arrangement may be adopted for said check circuits.

In order to improve the reliability of a data processing system, error correcting codes are widely used. Among others, a BCH code with a 2-bit error correcting function has been adopted in error correcting systems. Various systems, such as the one proposed by R. T. Chien, are well known for decoding said BCH code. Such systems will be generally referred to hereinbelow as conventional systems.

However, said conventional systems use in general shift registers and cannot correct errors before such registers have been shifted by plural clocks (which will be described later with reference to FIG. 1). Accordingly, when attempts have been made to develop the conventional system, for example, the one by R. T. Chien, so that high speed processing may be done in parallel for error corrections, the system will necessarily become a complicated one as can be seen with reference to FIG. 2. In this case, the individual circuits x.alpha..sup.44, x.alpha..sup.43 . . . x.alpha..sup.3 illustrated in FIG. 2 will take different forms, resulting in a high cost and a complicated structure of the circuit arrangement. This becomes a further obstacle for large-scale integration of such a circuit.

The main object of the present invention is, therefore, to eliminate the above-mentioned drawbacks of the conventional error correcting circuit arrangement, by providing an improved error correcting circuit arrangement which permits a rapid error correction by means of a parallel processing operation and which has a standardized circuit configuration for the checking operation and for said parallel processing. The present invention is characterized in that there is provided an error correcting circuit arrangement using cube circuits, in which a 2-bit error correcting BCH code check matrix H is calculated with respect to data D (d.sub.o, d.sub.1, d.sub.2, . . . d.sub.n), to correct error bits, if any, in said data on the basis of a syndrome S.sub.1 derived from the upper half of said check matrix and of a syndrome S.sub.3 derived from the lower half of said check matrix. Check circuits of (n+1) in total number, each corresponding to each data bit, are disposed in parallel, each of said check circuits being adapted to check, according to line vector (a.sub.i :a.sub.i.sup.3), in said check matrix H, allocated to each said circuit, whether or not the following equation is established in modulo 2 operation

when said equation is established, the errors existing in said data bits are corrected. The present invention will be better understood from the description presented below with reference to the accompanying drawings.

FIG. 1 shows an example of a conventional system;

FIG. 2 shows an example of an arrangement obtainable by improving the system in FIG. 1;

FIGS. 3 to 5 show partial arrangements used in the present invention;

FIG. 6 shows an embodiment constructed according to the present invention; and

FIG. 7 shows an embodiment of a cube circuit used in the present invention.

Before entering into the description of the preferred embodiment according to the present invention, examples of the conventional systems will be described.

First, supposing that .alpha. denotes a root or roots of a polynominal P(x)=1+x+x.sup.6 =0, then .alpha..sup.0, .alpha..sup.1, .alpha..sup.2 . . . .alpha..sup.62 become all the roots of the polynominal P(x)=0. For instance, let us make sure or verify that .alpha..sup.2 is a root of P(x)=0. By substitution of .alpha..sup.2, we obtain the equation P(.alpha..sup.2)=1+.alpha..sup.2 +.alpha..sup.12, where .alpha..sup.12 =(.alpha..sup.6).sup.2, and establishing .alpha..sup.6 =1+.alpha.(in the modulo 2 operation, the value having a symbol (+) and (-) is the same), .alpha..sup.12 becomes (1+.alpha.).sup.2 as the following equation establishes:

Therefore, .alpha..sup.2 is one of the roots of the polynominal P(x)=0. Similarly, .alpha..sup.3 through .alpha..sup.62 can be proved to be the other roots of the polynominal.

Assuming generally that a degree of the polynominal P(x) is k, the number of elements which satisfies P(x)=0 becomes 2.sup.k -1 defining roots .alpha..sup.0 through .alpha..sup.2.spsp.k.sup.-2. Accordingly, for instance, when the data length which is subjected to correct errors is 32 bits to 63 bits, k becomes sixth degree and, when the data length is 64 to 127 bits, k becomes the seventh degree. In general, when the length of data bits is n+1 and the degree of polynominal is k, the following condition must be satisfied:

The arbitrary constants a.sub.0 . . . a.sub.n which will appear in this specification denote the elements selected from .alpha..sup.0 . . . .alpha..sup.2.spsp.k.sup.-2. In this way, the k.sub.th degree of the polynominal can be used in accordance with the data length. From this discussion, it should be understood that an arbitrary number of k.degree. can be utilized among 63 elements.

Now, referring back to the system according to the conventional technique, a BCH check matrix H is formed in accordance with the given data D (d.sub.0, d.sub.1, d.sub.2, . . . d.sub.n) as follows: ##EQU2##

From the right side of this matrix, the check matrix H' can be calculated by utilizing line vectors of n+1. That is: ##EQU3## Assuming now that errors occur in bits d.sub.i and d.sub.j, a syndrome S.sub.1 produced from the upper half of said check matrix and a syndrome S.sub.3 from the lower half will be expressed by the formulae: ##EQU4## The above formula (3) will give the following: ##EQU5## As a result, said .alpha..sup.i and .alpha..sup.j are the roots of the following:

accordingly, .alpha..sup.19, .alpha..sup.20, . . . .alpha..sup.62 are substituted for the x's in the formula (5) to determine the values i and j which satisfy the formula (5 ), in order to correct the data bits d.sub.i and d.sub.j.

However, it is not very easy to construct hardware which can check to see that the formula (5) is satisfied. For this reason, however, there is provided in the conventional system a circuit which checks whether or not the formula:

is satisfied, by modifying the formula (5) on the assumption that .alpha..sup.i+N =.alpha..sup.63 =.alpha..sup.0 =1 is established.

In FIG. 1 there is shown an example of a conventional circuit arrangement which corrects data bits d.sub.i and d.sub.j by determining N=i, j which satisfies the above formula (6). In FIG. 1, the reference numeral 1 indicates a shift register in which data d.sub.0 through d.sub.43 are read from, for example, a memory, are set, and then are shifted by each clock to deliver bits one by one; 2 indicates a circuit to detect F(x)=0; 3 and 4 indicate flip flop circuits; 5 indicates an x .alpha. circuit; 6 indicates an x.alpha..sup.3 circuit; and the numeral 7 indicates a bit correcting circuit.

In synchronism with the data bits d.sub.43 through d.sub.0 delivered from the shift register 1 for each clock, the F(x)=0 detector circuit 2 checks whether or not F(x)=0 is satisfied. If F(x)=0 is satisfied, a logic "1" is applied from the detector circuit 2 to the bit correcting circuit 7 to invert data bits delivered also in the above-mentioned synchronism. Namely, the errors are thus corrected. With the aforementioned conventional system using shift registers, errors cannot be corrected before they have been shifted by 44 clocks. As a result, such a system is inconvenient in that the processing speed is low. FIG. 2 shows an improvement of the arrangement in FIG. 1, namely, another conventional arrangement in which 44 check circuits are disposed in parallel correspondingly to data bits d.sub.0 to d.sub.43. In FIG. 2, the reference numeral 8-0 indicates a check circuit; 2-0 to 2-43 indicate circuits corresponding to the F(x)=0 detector circuit 2 in FIG. 1, respectively; 7-0 to 7-43 indicate circuits corresponding to bit correcting circuit 7 in FIG. 1; 9 indicates an error occurrence detector circuit; 10-0 to 10-43 and 11-0 to 11-43 indicate multiplication circuits, respectively; and 12-0 to 12-43 indicate AND circuits, respectively.

The multiplication circuit 10-i will generate .alpha..sup.N, which appears in the previously-mentioned formula (6), while the circuit 11-i will generate .alpha..sup.3N. When syndromes S.sub.1 and S.sub.3 are given, each F(x)=0 detector circuit checks whether or not the F(x)=0 is satisfied. If it is satisfied, a logic "1" is delivered at the output of the detector circuit. When the error-occurrence detector circuit 9 detects the existence of an error, the AND circuit 12-i is energized to invert data bits d.sub.i and/or d.sub.j corresponding to the data bits d.sub.0 through d.sub.43 supplied in parallel. It should be noted that when no error exists, all the syndromes S.sub.1 become zero.

As will be clear from the foregoing, the circuit arrangement as shown in FIG. 2 uses no shift registers, which are used in the example in FIG. 1, and permits a high-speed error correction by processing in parallel the data bits d.sub.0 through d.sub.43. With the second conventional system in FIG. 2, the F(x)=0 detector circuits 2-0 to 2-43 among the check circuits 8 can be circuits each of which having the same construction, but the multiplication circuits 10 and 11 need 44 different circuit configurations. For this reason, the circuit arrangement in FIG. 2 will be high in production cost and complex in structure. Attempts have been made at integration (for example, integration of the circuits 8, 12 and 7 in FIG. 2 into one IC circuit) in order to raise the packaging density and to reduce the manufacturing cost. Because of the above-mentioned difference in circuit configurations, however, such integration is impossible.

The present invention will now be described. The present invention is based on the following concept. When the BCH code check matrix H: ##EQU6## is calculated with respect to data D (d.sub.0, d.sub.1, . . . d.sub.43), and if errors occur in the data bits for example, d.sub.i and d.sub.j, syndrome, S.sub.1 produced from the upper half of the formula (7) and syndrome S.sub.3 from the lower half will be expressed as follows. ##EQU7## If the formula (1).degree. is modified, ##EQU8## Accordingly, the following equations are established. ##EQU9## Therefore, it becomes:

According to the present invention, check circuits to provide for the above-mentioned processing operation are constructed. It is possible to determine data bits d.sub.i and d.sub.j where errors exist by substituting .alpha..sup.0, .alpha..sup.1, .alpha..sup.2, . . . .alpha..sup.43 one by one for the value of x. It should be noted that subtraction in binary numbers is equivalent to addition, both of them being able to be realized in an EXCLUSIVE OR circuit.

The hardware according to the present invention can also be realized by using shift registers as in FIG. 1. In order to obtain higher-speed data processing, however, a parallel processing circuit as illustrated in FIG. 2 is advantageously adopted.

FIG. 3 shows a circuit arrangement by which (S.sub.1 - x) and (S.sub.3 - x.sup.3) in the formula (11) are provided. In FIG. 3, the reference numerals 13-0 to 13-43 indicate registers to give .alpha..sup.0 through .alpha..sup.43 in the upper half of the formula (7); 14-0 through 14-43 indicate registers to give .alpha..sup.0 to .alpha..sup.3 in the lower half of the formula (7); and 15-0 through 15-43 and 16-0 through 16-43 indicate subtraction circuits, respectively. It should be noted that addition and subtraction of binary "1" bits can be performd with EXCLUSIVE OR circuits.

The circuit arrangement illustrated in FIG. 3 will give (S.sub.1 - x) and (S.sub.3 - x.sup.3). Data to be stored in the registers 13-0 through 13-43 and 14-0 through 14-43 will be determined depending on said check matrix H. Consequently, read only memories (ROM) may be adopted, but there remains something to be improved. As seen in FIG. 4, the arithmetic function A .sym. B will result in A .sym. B = A if B = 0, for example. And, if B = 1, the arthmetic function A .sym. B will result in A .sym. B = A. Thus, if S.sub.1 and S.sub.3 are conditioned for the syndromes S.sub.1 and S.sub.3, respectively, as shown in FIG. 5, when obtaining, for instance, it should be understood that a condition will be satisfied by alloting the first bit of S.sub.1 as the first bit of (S - .alpha..sup.0) and the second to sixth bits of S.sub.1 as the second to sixth bits of (S - .alpha..sup.0) because .alpha..sup.0 = 100,000. According to the present invention, the circuit arrangement is considerably simplified by adopting the circuit configuration as shown in FIG. 5.

FIG. 6 shows one embodiment according to the present invention. In FIG. 6, the reference numerals 7-10 through 7-43, 8-0 through 8-43, 9, and 12-0 through 12-43 indicate the corresponding components in FIG. 2; 13-0 through 13-43 indicate cube circuits; 14-0 indicates a subtraction circuit; and 15-0 through 15-43 indicate all-zero detector circuits. According to the present invention, check circuits 8-0 through 8-43 are disposed in parallel correspondingly to the data bits d.sub.0 to d.sub.43, similar to the arrangment as shown in FIG. 2. Also similar to the arrangement in FIG. 2, the occurrence of an error is detected by the parity check circuit 9, and the error correction is carried out with respect to the data bit d.sub.p corresponding to the check circuit 8-p which has issued a logic "1" signal.

This may also be considered as defining that the check circuits 8-0 to 8-43 are supplied at their inputs with (S.sub.1 - .alpha..sup.0) and (S.sub.3 - .alpha..sup.0), (S.sub.1 + .alpha..sup.1) and (S.sub.3 - .alpha..sup.3), . . . (S.sub.1 - .alpha..sup.44) and (S.sub.3 - .alpha..sup.3). That is to say, in the check circuit 8-0, for example, it is arranged to check whether or not the formula:

is satisfied when .alpha..sup.0 is substituted for x. When all the bits are logic "0", namely, the formula (12) is satisfied, cubing the input signal (S.sub.1 - .alpha..sup.0) (to be considered to be bit strings A.sub.0 to A.sub.5) and carrying out the subtraction between said cubed input signal and input signal (S.sub.3 - .alpha..sup.0) for each bit causes the all-zero detector circuit 15-0 to deliver at its output a logic "1" signal. This is true for the check circuits 8-1 to 8-43.

The arrangement of cube circuits 13-0 to 13-43 will now be described.

Assuming that the input signal is generally A.sub.0 + A.sub.1 X + A.sub.2 X.sup.2 + . . . A.sub.5 X.sup.5 and said signal is delivered as B.sub.0 + B.sub.1 X + B.sub.2 X.sup.2 + . . . B.sub.5 X.sup.5 at the outputs of the cube circuits, there should be established the following relation.

when the relation between the factors on the left and right sides are determined by modifying the formula (13) with mod. 1 + x + x.sup.6 (said .alpha. is the root of 1 + x + x.sup.6), the formula: ##EQU10## should be established.

The above-mentioned formula (14) may be expressed in various forms depending on the modification method, so the relation is not always limited to the form of the formula (14).

In any event, by arranging a circuit which can perform the processing operation according to the formula (14), an output derived by cubing a given input can be provided. FIG. 7 illustrates an embodiment of a cube circuit which performs the processing according to the formula (14). In this Figure, the symbol .sym. means addition by the EXCLUSIVE OR circuit, i indicates an inverter circuit and A indicates an AND circuit. As is apparent from FIG. 7, bit B.sub.0, for example, satisfies the top relation in the formula (14).

In the foregoing, the arrangement in which logic circuits are used to form cube circuits has been described. However, the cube circuits may be made of a ROM (read-only memory) which stores a conversion table. In this case, it is sufficient to take 6 bits of (S.sub.1 - .alpha..sup.0) = (A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 A.sub.5) as address data and to prepare ROMs which will deliver at their outputs 6 bits of (S.sub.1 - .alpha..sup.0).sup.3 = (B.sub.0 B.sub.1 B.sub.2 B.sub.3 B.sub.4 B.sub.5). The memory capacity will be 2.sup.6 W x 6 bits.

Referring back to FIG. 6, if signals supplied to the cube circuits 13-0 through 13-43 are taken as input signals A.sub.0 to A.sub.5 shown in FIG. 7, it will be apparent to those skilled in the art that all the cube circuits 13-0 to 13-43 can be arranged identically. Thus, it is evident that all the check circuits 8-0 to 8-43 can be formed identically, except that input signals to the respective check circuits are to be modified into (S.sub.1 - .alpha..sup.0) and (S.sub.3 - .alpha..sup.0), (S.sub.1 - .alpha..sup.1) and (S.sub.3 - .alpha..sup.3), . . . Namely, when adopting the circuit arrangement shown in FIG. 6, it is only necessary to integrate check circuits 16 (including elements 8, 12, and 7) which are of identical configuration. This is very advantageous from the standpoint of higher packaging density and lower manufacturing cost.

As will be understood from the forgoing, the present invention permits the advantageous realization of a higher-speed error correcting circuit arrangement and the standardization of check circuits.