Abstract:
There is provided an error correcting device for correcting errors of a received message in accordance with a processing program including a plurality of error correcting processes for correcting different numbers of errors, wherein a plurality of check codes which are used to discriminate the shift to either one of the plurality of error correcting processes for correcting different numbers of errors and which are formed by syndromes formed from the reception code are sequentially serially generated, the plurality of check codes are output in parallel and the shift of the process in the processing program is executed in accordance with the check codes which were output in parallel.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to an error correcting device and, more particularly, to the realization of its high processing speed. 
     2. Related Background Art 
     In an error correcting device using what is called a program control system in which error correcting processes are executed by a microprocessor or the like in accordance with a predetermined program, a discrimination of a jump (shift of the process) of the program and a change in count value of a program counter in association with the program jump are executed each time the result of the discrimination is obtained. 
     A conventional procedure of the processes will now be described with respect to the syndrome discrimination of the Reed Solomon code as an example. The Reed Solomon code is a multi-dimension block code of a cyclic type and, in recent years, it has been applied to various fields and has widely been known. 
     A decoding method of the Reed Solomon code having a code length (n) and (k) information symbols and comprising (n-k) check symbols will now be described. It is also assumed that each symbol is an element of a Galois field GF (2 m ), a finite field having m binary bits (i.e., 2 m  elements). 
     In this case, a generating polynomial g(x) of the (t)-ply error correction Reed Solomon code is expressed by the following equation (1) or (2) in which (α) is a primitive element of the Galois field GF (2 m ). 
     
         g(x)=(x+α) (x+α.sup.2) . . . (x+α.sup.2t) (1) 
    
     
         g(x)=(x+α.sub.O) (x+α) . . . (x+α.sup.2t-1) (2) 
    
     On the other hand, when a transmission code word is expressed by C(x) and a reception code word is expressed by R(x) and an error polynomial is expressed by E(x), the following relation is satisfied among them. 
     
         R(x)=C(x)+E(x)                                             (3) 
    
     In this case, the coefficients of the polynomial are included in the Galois field GF (2 m ) and the error polynomial E(x) includes only the terms corresponding to the error location and a value (size). 
     Therefore, assuming that an error value at a position x j  is set to Y j . ##EQU1## In the equation (4), Σdenotes the sum of errors at all positions. 
     Assuming that the syndromes S i  are defined as follows 
     
         S.sub.i =R(α.sup.i) [where, i=0, 1 . . . 2t-1]       (5) 
    
     from the equation (3), 
     
         S.sub.i =C(α.sup.i)+E(α.sup.i) 
    
     In this case, since C(x) can always be divided by g(x), 
     
         C(.sup.αi)=0 
    
     
         Therefore, 
    
     
         S.sub.i =E(α.sup.i) 
    
     From the equation (4), the syndromes can be expressed as follows. ##EQU2## However, it is assumed that α j  =X j  and X j  denotes an error location in the case of α j . 
     When the number of errors is set to e, an error location polynomial σ(x) is defined as follows. ##EQU3## 
     The following relation is provided between σ 1  to σ e  in the equation (7) and the syndromes S i . 
     
         S.sub.i+e +σ.sub.1 S.sub.i+e-1 +. . . σ.sub.e-1 S.sub.i+1 +σ.sub.e S.sub.i                                    ( 8) 
    
     Namely, the above Reed Solomon code is decoded in the following procedure. 
     (I) The syndromes S i  are calculated by the equation (5). 
     (II) The coefficients σ 1  to σ e  of the error location polynomial are calculated by the equation (8). 
     (III) A root X j  of the error location polynomial is obtained by the equation (7). 
     (IV) The error value Y j  is obtained by the equation (6) and the error polynomial is obtained by the equation (4). 
     (V) The error correction is executed by the equation (3). 
     A practical example of the error correction by the decoding procedure as mentioned above will now be described with respect to the case where four check symbols are used in one-block data. 
     That is, the generating polynomial g(x) in this case is as follows. ##EQU4## The correction until the double error can be corrected. 
     The case of actually executing the error correction will now be considered with respect to the following four cases: e=0; e=1, e=2, and e≧3. When e=0, this means that the received message word is correct, so that no error correcting process is executed. On the other hand, when e≧3, this also means that such a case exceeds the error correcting capability, so that the error correcting process other than the process to set an error flag into 1 is not executed. That is, the error correcting process is actually executed only in the cases where e=1 and e=2. 
     The error correcting process is schematically executed by the following procedure in correspondence to the above decoding procedures (I) and (II). 
     (a) The syndromes S 0  to S 3  are calculated. 
     (b) The syndromes S 0  to S 3  are checked and when S 0  =S 1  =S 2  =S 3  =0, it is determined that e=0 and the error correcting process is finished. Further, when only one of the values of the syndromes S 0  to S 3  is equal to 0, this means that e≠1. When any two or more of the values of the syndromes S 0  to S 3  are equal to 0, it will be obvious from the equation (6) that e≧3. 
     (c) When the equation (8) is rewritten with respect to e=1 and e=2. 
     in the case where e=1. ##EQU5## 
     and in the case where e=2. ##EQU6## 
     It is now assumed that the actual decoder starts the operation from the case where e=1. Then, the solution σ 1  which satisfies the simultaneous equation (9) must be first obtained. If such a solution does not exist, the decoder must obtain the solutions σ 1  and σ 2  which satisfy the simultaneous equation (10) with respect to the case of e=2. If no solution is derived here, it can be regarded such that e≧3. 
     The solution σ 1  of the equation (9) is obtained as follows. ##EQU7## The solutions σ 1  and σ 2  of the equation (10) are obtained as follows. ##EQU8## 
     In the above procedures, the values of the various equations are calculated and compared in each step. It is then necessary to change the program flow indicative of the processing in accordance with the result of the discrimination. 
     For instance, the number e of errors can be determined as shown in Table 1 in accordance with the values of the syndromes S 0  to S 3  in the step (b). 
     
                       TABLE 1______________________________________S.sub.0   S.sub.1            S.sub.2      S.sub.3                              e______________________________________=0        =0     =0           =0   =0=0        =0     =0           ≠0                              ≧3=0        =0     ≠0     =0   ≧3=0        =0     ≠0     ≠0                              ≧3=0        ≠0            =0           =0   ≧3=0        ≠0            =0           ≠0                              ≧3=0        ≠0            ≠0     =0   ≧3=0        ≠0            ≠0     ≠0                              ≧2≠0  =0     =0           =0   ≧3≠0  =0     =0           ≠0                              ≧3≠0  =0     ≠0     =0   ≧3≠0  =0     ≠0     ≠0                              ≧2≠0  ≠0            =0           =0   ≧3≠0  ≠0            =0           ≠0                              ≧3≠0  ≠0            ≠0     =0   ≧3≠0  ≠0            ≠0     ≠0                              ≧1______________________________________ 
    
     An outline of the flow of the processes according to the determination is shown in a flowchart of FIG. 1. The step shown by &#34;e≧3&#34; in FIG. 1 denotes that the number of errors is decided to be 3 or more and that the processing routine advances to the processing routine for the excessive error correcting capability. The step shown by &#34;e≧2&#34; denotes that the number of errors is decided to be 2 or more and that the processing routine advances to the processing routine for correction of double error. Further, the step shown by &#34;e≧1&#34; denotes that the number of errors is decided to be 1 or more and that the processing routine advances to the processing routine for correction of single error. 
     On the other hand, consider the following as one example in which the flow of the program is changed as mentioned above, that is, the program is jumped. When the coefficients σ 1  and σ 2  of the error location polynomial are calculated in the foregoing step (c), checks are made to see if the denominator (S 1   2  +S 0  S 2 ) and the numerators (S 0  S 3  +S 1  S 2 ) and (S 1  S 3  +S 2   2 ) are equal to 0 and the program is jumped in accordance with the results of the discriminations. That is, when the denominator (S 1   2  +S 0  S 2 ) is equal to 0, the processing routine advances to the processing routine for the excessive error correcting capability. When either one of the numerators (S 0  S 3  +S 1  S 2 ) and (S 1  S 3  +S 2   2 ) is equal to 0, the processing routine advances to the processing routine for correction of single error. 
     However, in the above conventional example using S 0 , S 1  and S 2  for discrimination rather than σ1 and σ2, for instance, assume that the program is jumped in the case where the result of the discrimination is &#34;Yes&#34; (&#34;Y&#34;) in each of the discriminating step in the flowchart of FIG. 1. It is then necessary to jump the program one or two times until the processing routine advances to the double-error correction processing routine through the step shown by &#34;e≧2&#34;. It is necessary to jump the program about four times until the processing routine advances to the no-error processing routine through the step shown by &#34;e=0&#34;. Moreover, it will be obvious from FIG. 1 that a fairly large program step area is needed to describe the above programs. 
     On the other hand, even in the procedure to calculate the coefficients σ 1  and σ 2  of the above error location polynomial, there is also an increase in the program step area increases. Even in the case of sequentially executing the steps of checking to see if (S 1   2  +S 0  S 2 ), (S 0  S 3  +S 1  S 2 ), and (S 1  S 3  +S 2   2 ) are equal to 0 or not, the program step area also similarly increases. 
     As mentioned above, when the program step area increases and the possibility of the program jump increases, it takes time to execute the above programs so that processes cannot be performed at high speed. Thus, it is difficult to process the received message of a high bit rate. 
     SUMMARY OF THE INVENTION 
     Under the aforementioned circumstances, it is an object of the invention to solve the foregoing problems. 
     Another object of the invention is to realize the high processing speed of an error correcting device for processing in accordance with programs. 
     Still another object of the invention is to provide an error correcting device which can reduce the number of program processing steps and the number of program jumping times in the error correcting device. 
     Under such objects, according to the present invention, as a preferred embodiment, there is provided an error correcting device comprising: (a) a processor for executing a processing program which includes a plurality of kinds of code error correction processing routines and is used to correct code errors of a received message; (b) first means for sequentially serially outputting a plurality of check codes to determine a shift to either one of the plurality of kinds of code error correction processing routines by using a plurality of syndromes formed from the reception code; (c) second means for outputting the plurality of check codes in parallel; and (d) third means for executing the shift of the program in the processing program in accordance with an output of the second means. 
     The above and other objects and features of the present invention will become apparent from the following detailed description and the appended claims with reference to the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flowchart showing the outline of the flow of conventional error correcting processes; 
     FIG. 2 is a block diagram showing a construction of a main section of an error correcting device as an embodiment of the present invention; 
     FIG. 3 is a flowchart showing the outline of the flow of error correcting processes according to the device of FIG. 2; and 
     FIG. 4 is a block diagram showing a construction of the main section in an error correcting device as another embodiment of the invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     An embodiment of the present invention will be described hereinbelow with reference to the drawings. 
     FIG. 2 is a diagram showing a construction of a program processing section as a main section in an error correcting device as an embodiment of the invention. 
     In the diagram, reference numeral 1 denotes an input terminal of a received message word. A code word train including errors generated in a transmission path is input to the input terminal 1. Syndrome calculating circuits 2a, 2b, 2c, and 2d calculate the syndromes S 0 , S 1 , S 2 , and S 3  in accordance with the foregoing equation (6), respectively. The error correcting process is executed by operating a processor 8 in accordance with programs which have previously been described. 
     FIG. 3 is a flowchart for explaining the processes according to the above programs. The processing programs which are executed by the processor 8 will now be described hereinbelow in accordance with the flowchart of FIG. 3. 
     Step 1 in FIG. 3 will be first executed. In step 1, a gate of the calculating circuit 2a is opened and the syndrome S 0  is output to a data bus DB and is temporarily stored into a register REG 3 as a temporary memory circuit. Next, to check whether S 0  =0 or not, the value 0 is output from a program memory in the processor 8 to the data bus (DB) and is temporarily stored into a register REG 4. The operations of the calculating circuits 2a to 2d, REG 3, and REG 4 can be controlled by the processor 8 through a control bus (not shown). 
     At this time, the processor (ALU) as an arithmetic operating unit 8 compares outputs of the REG 3 and REG 4 and outputs the result of the comparison as a 1-bit data. That is, when the syndrome S 0  is equal to 0, the ALU 8 outputs &#34;0&#34;. When the syndrome S 0  is set to a value other than 0, the ALU 8 outputs &#34;1&#34;. The output of the ALU 8 is input as a 1-bit data to a shift register 5. 
     By repeating the above processes with respect to the syndromes S 1 , S 2 , and S 3 , respectively, four data (check codes) indicating whether the syndromes S 0  to S 3  are equal to 0 or not are stored in the shift register 5, so that a 4-bit data is derived. 
     Table 2 shows the corresponding relations in the case where the results of the determination of Table 1 are expressed as a 1-bit data as an output of the ALU 8 and the processing routines to be shifted are expressed by &#34;0&#34;, &#34;1&#34;, &#34;2&#34;, and &#34;3&#34; in correspondence to the number of errors. 
     
                       TABLE 2______________________________________S.sub.0    S.sub.1            S.sub.2      S.sub.3                             e______________________________________0          0     0            0   00          0     0            1   30          0     1            0   30          0     1            1   30          1     0            0   30          1     0            1   30          1     1            0   30          1     1            1   21          0     0            0   31          0     0            1   31          0     1            0   31          0     1            1   21          1     0            0   31          1     0            1   31          1     1            0   31          1     1            1   1______________________________________ 
    
     Therefore, in step 2 in FIG. 3, a 4-bit pattern &#34;0000&#34; corresponding to the routine &#34;0&#34; in Table 2 is input to a comparator 6 from the data bus DB. At this time, an address (k bits) on the jump destination side of the program to execute the routine &#34;0&#34; is input to a program counter 7 from the data bus DB. The comparator 6 compares an output of the shift register 5 with &#34;0000&#34;. When they coincide, the program counter 7 is set by the jump destination address data. In association with it, the process of the routine &#34;0&#34; is executed by a processing section (not shown). 
     The process of the routine &#34;0&#34; is executed in the case where no error exists as mentioned above. In this routine, the error correcting process is not executed but the next process of the received message is executed. In FIG. 3, the process of the routine &#34;0&#34; corresponds to the process to jump the program from step 2 to step 7. 
     In step 2, if it is decided that the output of the shift register 5 is not &#34;0000&#34;, a 4-bit pattern &#34;1111&#34; corresponding to the routine &#34;1&#34; is input to the comparator 6 from the data bus DB. In a manner similar to the above, when the output of the shift register 5 is set to &#34;1111&#34;, the program counter 7 is set by the jump destination address data corresponding to step 8 in FIG. 3, namely, the routine &#34;1&#34;. The process of the routine &#34;1&#34; relates to the single-error correcting process as mentioned above. In the case where the code stored in a memory 9 was error corrected by the routine &#34;1&#34;, the processing routine advances from step 9 to step 6 (routine &#34;3&#34;addition of correction flap). If the error correction cannot be executed, the processing routine advances from step 9 to step 10 (routine &#34;2&#34;). 
     Further, if it is determined in steps 2 and 3 that the output of the shift register 5 is neither &#34;0000&#34; nor &#34;1111&#34;, 4-bit patterns &#34;0111&#34; and &#34;1011&#34; corresponding to the routine &#34;2&#34; are sequentially input to the comparator 6. When the 4-bit pattern coincides with the output of the shift register 5, the program counter 7 is set by the jump destination address data corresponding to the routine &#34;2&#34;. Thus, the processing routine of the program advances to the routine &#34;2&#34; (step 10). 
     The process of the routine &#34;2&#34; relates to the double-error correcting process as mentioned above. After the processor 8 corrected the code stored in the memory 9, the processing routine advances to the routine &#34;3&#34; (step 6). There is no need for an &#34;OK&#34; decision as in step 9 since error correction is completed in step 10. Therefore, the flag operation of step 6 may be entered directly from step 10. 
     On the other hand, if data other than &#34;0000&#34; &#34;0111&#34;, &#34;1111&#34;, and &#34;1011&#34; has been stored in the shift register, the processing routine directly advances to the routine &#34;3&#34; (step 6). The program is set so as to automatically execute the shifting from step 5 to step 6 in the case where the program counter 7 is not preset. 
     By constructing the error correcting device as mentioned above, the number of jumping times to change the flow of the program can be reduced and the error correction processing speed can be made high as a whole and the program area can be reduced. 
     FIG. 4 is a diagram showing a construction of a program processing circuit as a main section of an error correcting device as another embodiment of the invention. In the diagram, the parts and components similar to those in FIG. 2 are designated by the same reference numerals and their descriptions are omitted. 
     In the construction of the embodiment shown in FIG. 4, the 4-bit data which is output from the shift register 5 is given to a jump address table 1. In response to a control signal (CONT) from the data bus DB, the jump address table 9 outputs data indicative of the jump destination address of each routine (refer to FIGS. 2 and 3) corresponding to the 4-bit data. The control signal CONT is also input to the program counter 7. In response to the control signal CONT, the program counter 7 is preset by the address data from the table 1. 
     Even in the embodiment of FIG. 4, it is readily understood that effects similar to the embodiment of FIG. 2 are obtained. Further, in the embodiment of FIG. 4, the four comparing operations of the comparator 6 in the embodiment of FIG. 2 can be executed in a single step, so that the processing speed can be further increased. 
     In the above embodiment, the results of the discriminations to see if the syndromes S 0  to S 3  are equal to 0 or not are used as check codes and are simultaneously output, thereby realizing the high processing speed. However, similar effects can be also obtained even when the invention is applied by using the results of the discriminations to see if the numerators and denominator of the coefficients σ 1  and σ 2  of the foregoing error location polynomial are set to 0 or not as check codes. 
     For instance, the construction shown in FIG. 2 is used as it is, (S 1   2  +S 0  S 2 ), (S 0  S 3  +S 1  S 2 ), and (S 1  S 3  +S 2   2 ) are sequentially stored into the REG 3, and 0 is stored into the REG 4, thereby sequentially inputting the 1-bit check codes indicating whether those data are equal to 0 or not into the shift register 5. By supplying those data together with the control signal CONT to the jump address table, the program is shifted to a desired routine. 
     Although the embodiments have been described with respect to a particular example of the double-error correction Reed Solomon code, similar effects may also obtained by applying the principles of the invention to an error correcting device using error correction code. 
     As described above, according to the invention, an error correcting device in which high processing speed can be realized and the program area can be reduced can be obtained.