Abstract:
Error detection that detects an error in an input data sequence, the input data sequence created by regarding a data sequence having a specified bit length as a polynomial, dividing that polynomial by a generator polynomial for generating error detection code and adding the error detection code to the data sequence so the remainder becomes ‘0’. Including calculating remainder values by dividing polynomials that correspond to each respective bit position by the generator polynomial and saving those remainder values; inputting together with an input data sequence, bit position information that indicates proper bit position of each data of the input data sequence, finding remainder values that correspond to proper bit positions of data of the input data sequence that are not ‘0’, performing bit-corresponding addition of each of the found remainder values; and determining no error in the input data sequence when all bits of the addition result become ‘0’.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    This is a continuation of Application PCT/JP2007/065441, which was filed on Aug. 7, 2007, now pending, the contents of which are herein wholly incorporated by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    The present invention relates to an error detection device, error correction/error detection decoding device and method thereof. 
         [0003]    Error detection code is used in systems such as data communication systems that require that data be transmitted without errors, and in systems such as external memory devices that require data to be read without error, and is used for detecting transmission errors and reading errors. 
         [0004]      FIG. 13  shows an example of the construction of a communication system to which error detection has been applied. On the transmitting side  1 , an error detection code encoding unit  1   b  performs a process of error detection encoding on a data sequence having a specified bit length that was generated by an information generation unit  1   a , and an error correction code encoding unit  1   c  performs a process of error correction encoding on the input data sequence using a specified encoding method, and transmits that encoded data sequence to the receiving side  3  via a transmission path  2 . On the receiving side  3 , an error correction decoding unit  3   a  decodes the input encoded data sequence by an error correction decoding process, and inputs the decoded data sequence to an error detection decoding unit  3   b . The error detection decoding unit  3   b  detects whether or not there is any error by performing an error detection decoding process on the decoded data sequence, and when there is error, transmits a retransmission request signal to the transmitting side. When there is no error, an information extraction unit  3   c  extracts and outputs the data. 
         [0005]    Cyclic redundancy check (CRC) code is able to detect continuous error, so it is often used as error detection code. On the transmitting side, N-bits of data sequence is regarded as a polynomial, that polynomial is divided by a generator polynomial, the m-bit of remainder obtained by the division is added to the N-bits of data sequence as CRC code so that the (N+m)-bits of data sequence is divisible by the generator polynomial and the (N+m)-bits of data sequence is transmitted. On the receiving side, error detection is performed by dividing the received data sequence by the aforementioned generator polynomial, and when the remainder is ‘0’ there is no error, otherwise there is error. For example, in a case where the generator polynomial G(x) is 16 bits, and the following equation 
         [0000]        x   16   K ( x )÷ G ( x )= Q ( x ), remainder R(x) 
         [0000]    is given, W(x) represented by 
         [0000]        W ( x )= x   16   K ( x )+ R ( x ) 
         [0000]    is defined as a CRC code word and transmitted to the receiving side. Here, x 16 K(x) is a data sequence obtained by adding 16 bits of “0s” to the lower-order side of the N-bits of data sequence K(x). On the receiving side, when W′(x)=W(x)+E(x), which is the code word W(x) to which error E(x) is added, is received, W′(x) is divided by G(x), and when the remainder is ‘0’, there is no error, however, when the remainder is something other than ‘0’, it is detected as error. More specifically, the operation 
         [0000]      W′(x)/G(x) 
         [0000]    is performed, and whether or not W′(x) is divisible is detected. 
         [0006]    When performing CRC encoding and decoding, the division described above must be performed, however, the divider used can be constructed using hardware with relatively simple circuits. An example of the construction of a circuit for performing division by the mth degree polynomial 
         [0000]        G ( x )= x   m   +g   m-1   x   m-1   + . . . +g   1   x +1  (1) 
         [0000]    is shown in (A) of  FIG. 14 . In the figure, g i  becomes a coefficient ‘0’ or ‘1’, in the case where g i =1 the output terminal is connected by to EORi, and in the case where g i =0 the output terminal is not connected to EORi. An example of a divider of a CRC operation unit for the case in which the generator polynomial is G(x)=x 16 +x 12 +x 5 +1, for example, is shown in (B) of  FIG. 14 . This divider comprises: a 16-stage shift register SR, exclusive OR circuits EOR 1  to EOR 3  that are provided on the input side of the 0-bit position, 5-bit position and 12-bit position and that perform an exclusive OR operation on the previous stage output data and feedback data; and a switch SW that is provided on the output side of the 15-bit position. With the switch SW switched to the feedback side (A side), division can be performed by inputting the data sequence from the higher order to EOR 1  one bit at a time. 
         [0007]    With the construction shown in (A) of  FIG. 14 , by inputting the coefficients of each degree of the polynomial W′(x) from the left side of the shift register in order starting from the coefficient of the highest degree, a quotient polynomial is output from the right side of the shift register, and after the coefficient of each degree has been input, the remainder polynomial is saved in the shift register. A divider can be constructed in this way with simple circuitry from a shift register and exclusive OR circuits. Incidentally, in the construction of the divider shown in  FIG. 14 , even if the circuitry is simplified it is necessary that the coefficient is sequentially input from a high-degree bit. Therefore, when a bit sequence that is not arranged in the proper order is input, for example, in the case of inputting a bit sequence in which the data sequence has been arranged by interleaving, the data sequence must be rearranged into the proper order using a memory or the like before being input to the divider. 
         [0008]      FIG. 15  is drawing showing the construction of a CRC check circuit when inputting a bit sequence that is not arranged in the proper order, where there are a RAM  4   b  for rearranging the data order provided in the stage before the divider  4   a  shown in (A) of  FIG. 14 , and in the rear of the divider  4   a  an all zero detection circuit  4   c  that determines whether or not the remainder found by the divider  4   a  is ‘0’ and outputs the check result. Together with the bit sequence (input data sequence), the proper order of each bit (data numbers) is input to the RAM  4   b  for rearranging the data order. By doing so, RAM  4   b  rearranges the bit sequence to the proper order by writing input data for each bit in the position instructed by the data number, and then reading the data in order. In other words, when a rearrangement operation such as interleaving is complex, it is necessary to store all of the input data first in memory, and then read the data in the proper order before inputting the data to the divider  4   a , therefore, time is required for rearranging the data. For example, in the case of N bits of input, the CRC operation cannot start until after N clock intervals of time have elapsed, so as a result, the CRC check results cannot be obtained until 2N clock intervals of time have elapsed. 
         [0009]    Incidentally, there is a decoder whose ability to correct error improves the more times that decoding is performed. In this kind of decoder, decoding of the input data is repeated until there is no error, and as soon as the error is gone, decoding of that data stops and decoding of the next input data begins.  FIG. 16  shows an example of a communication system that uses turbo code as error correction code, and uses CRC code as error detection code. 
         [0010]    On the transmitting side  5 , a CRC addition unit  5   b  performs a process for adding CRC code to a data sequence having a specified bit length that was generated by an information generation unit  5   a , and a turbo encoding unit  5   c  performs a turbo encoding process on the input data sequence to which CRC code has been added and sends the result to the communication path (transmission path)  6 . On the receiving side  7 , a turbo decoder  7   a  decodes the input encoded data sequence using a turbo decoding process, and inputs the decoded result to a CRC detection unit  7   b.    
         [0011]    By repeating decoding, the turbo decoder  7   a  can improve the error rate characteristics. In order to accomplish this, the turbo decoder  7   a  performs the decoding process a specified number of times, and the CRC detection unit  7   b  performs error detection on the decoded result, and when there is error, sends a retransmission request RRQ to the transmitting side, and when there is no error, instructs the information extraction unit  7   c  to extract information. Moreover, when error disappears before the decoding process has been performed the specified number of times, the decoder  7   a  is able to improve the efficiency of the decoding process by immediately stopping the decoding process and beginning decoding of the next encoded data sequence. In order to do this, the CRC detection unit  7   b  detects whether or not there is error in the decoded result after each time the decoding process is performed, and sends the error detection result as feedback to the turbo decoder  7   a . The turbo decoder  7   a  repeats the decoding process when an error detection result indicating that there is error is inputted, however, when an error detection result indicating that there is no error is inputted, the turbo decoder  7   a  stops the decoding operation even though the process may not yet have been performed the specified number of times, and begins decoding the next encoded data. 
         [0012]      FIG. 17  is drawing showing the construction of the turbo encoder  5   c , where u is N bits of input data to which CRC bits have been added, and xa, xb and xc are encoded data resulting from the turbo encoder  5   c  encoding the input data u. The encoded data xa is the input data u itself, the encoded data xb is the input data u that has undergone convolutional encoding by an encoder  8   a , and encoded data xc is the information data u that has been interleaved (n) by an interleaver  8   b  and then undergone convolutional encoding by an encoder  8   c . In other words, the encoded data that is output from the turbo encoder a systematic code having an encoding rate of ⅓ and comprising the input data u (=xa) to which parity bits xb, xc have been added. 
         [0013]      FIG. 18  is a drawing of the construction of a turbo decoder  7   a . The turbo decoder first uses Ys and Yp 1  selected from among the received signals Ys, Yp 1  and Yp 2  of the encoded data xa, xb and xc to perform decoding by a first element decoder  9   a . Next, the decoder uses the decoded result (likelihood), which is output from the first element decoder  9   a , and Ys and Yp 2  to perform similar decoding by a second element decoder DEC 9   b . However, Yp 2  is a received signal that corresponds to xc, which is the original data u that has been interleaved and encoded, so before being inputted to the second element decoder  9   b , Ys and the likelihood that is output from the first element decoder are interleaved (Π) by interleavers  9   c  and  9   d.    
         [0014]    After the likelihood that is outputted from the second element decoder  9   b  is deinterleaved (Π −1 ) by a deinterleaver  9   e , it is fed back to the first element decoder  9   a  as input. The first element decoder  9   a  uses the fed back likelihood u′, Ys and Yp 1  to perform decoding, after which decoding is repeated by the first and second element decoders  9   a ,  9   b  until the number of times decoding has been performed reaches a specified number of times, or the decoding described above is repeated until there is no error. 
         [0015]      FIG. 19  is a drawing showing the construction of a turbo decoder that combines the first and second element decoders shown in  FIG. 18  into one element decoder  9   a , wherein a switch  9   f  switches the input to the element decoder  9   a  according to whether the decoding operation is an odd number time or even number time. A communication path value RAM  9   g  stores the signals Ys, Yp 1 , Yp 2  that are received from the communication path, and together with suitably inputting these signals to the element decoder  9   a  via the switch  9   f , inputs the signals to the interleaver  9   c . A decoded result RAM  9   h  saves the decoded results and inputs those results to an interleaver  9   d  and deinterleaver  9   e . A hard judgment unit  9   i  determines whether the decoded result is “0” or “1”, and inputs the judgment result to the CRC detection unit  7   b  ( FIG. 16 ). 
         [0016]    In the turbo decoder shown in  FIG. 19 , first, a first decoding is performed by the connection at the switch  9   f  indicated by the solid line. At this time, the decoded result is output in the proper order. Next, decoding is performed with the connection at the switch  9   f  indicated by the dashed line. In this second decoding process, information bits Ys and the decoded result are interleaved and then decoding is performed. Here, the output of decoded result is in an interleaved order. After that, these decoding processes are repeated, and when taking a look at the decoded result, the output order after each repetition is repeated as: Proper order→Interleaved order (IL order)→Proper order→Interleaved order→ . . . . 
         [0017]      FIG. 20  is a drawing showing the timing for acquiring the CRC check result, and shows the case in which no error is detected in the decoded result of the fourth repetition. As explained in  FIG. 15 , the CRC check result can be output at the same time as the time when decoding ends in a case where the input data, which is the decoded result, is in the proper order. However, when the bit sequence of the input data is interleaved, the input data must be rearranged into the proper order before performing the CRC check, so the output timing of the CRC check result is delayed. Therefore, during decoding, the number of times decoding is performed and the timing for acquiring the CRC check result are as shown in  FIG. 20 . 
         [0018]    In other words, when performing a CRC check of the turbo decoding result, the data in the decoded result of an odd repetition are in the proper order, so the data can be input as is to the divider of the CRC operation unit, and the CRC check result can be output at the same time as the time when the turbo decoding ends. However, the data in the decoded result of an even repetition are in the interleaved order and the data must be rearranged into the proper order, so the decoded result must first be stored in memory before being input to the divider of the CRC operation unit, and the timing for acquiring the CRC check result is delayed. Therefore, even though error is not detected in the decoded result of the fourth repetition and the turbo operation tries to stop, the next turbo decoding (fifth repetition) is already being performed during the CRC operation, and the turbo decoder is operated excessively. In other words, the turbo decoding operation is performed one time too many, which causes a decrease in the processing efficiency of the turbo decoding process. 
         [0019]    As related art, there is a syndrome calculating technique that is capable of properly performing syndrome calculation even though the order of data during the syndrome calculation is different from the order when the check data is created (Japanese patent publication no. H5-165660A). However, in the case where the bit sequence of input data has been interleaved by an interleave operation or the like, this related art is not a technique for quickly outputting the CRC check result without rearranging the data into the proper order. 
       SUMMARY OF THE INVENTION 
       [0020]    Taking the above into consideration, when the bit sequence of input data is arranged differently from the proper order, the object of the present invention is to output the CRC check result without rearranging the data into the proper order. 
         [0021]    Another object of the present invention is to immediately output the CRC check result at the instant when error in the decoded result disappears. 
         [0022]    Another object of the present invention is to reduce the number of times decoding is performed by the decoder. 
         [0023]    A further object of the present invention is to make possible the objective CRC operation device having compact hardware construction. 
         [0024]    Error Detection Method 
         [0025]    A first form of the present invention is an error detection method that detects whether or not input data sequence has error wherein the input data sequence is created at an encoder by regarding a data sequence having a specified bit length as a polynomial, dividing that polynomial by a generator polynomial for generating error detection code and adding the error detection code to the data sequence so that the remainder becomes ‘0 ’ comprising: a step of calculating remainder values by dividing polynomials that correspond to each respective bit position by the generator polynomial and saving those remainder values beforehand in a memory; a step of inputting together with an input data sequence, bit position information that indicates the proper bit position of each data of the input data sequence; a step of finding from the memory remainder values that correspond to the proper bit positions of data of the input data sequence that are not ‘0’, and performing bit-corresponding addition of each of the found remainder values; and a step of determining that there is no error in the input data sequence when all of the bits of the addition result become ‘0’, and otherwise determining that there is error. 
         [0026]    The step of saving the remainder values, includes substeps of saving remainder values that correspond to every bit position at each interval of a constant number of bits; and interpolating remainder values of the bit positions that have not been saved by using the saved remainder values. 
         [0027]    Error Correction/Error Detection Decoding Method 
         [0028]    A second form of the present invention is an error correction/error detection decoding method that decodes encoded data sequence wherein the encoded data sequence is created at an encoder by regarding a data sequence having a specified bit length as a polynomial, dividing that polynomial by a generator polynomial for generating error detection code, adding the error detection code to that data sequence so that the remainder becomes 0, then encoding data sequence to which the error detection code has been added by a specified encoding method, comprising: a step of calculating remainder values by dividing polynomials that correspond to each respective bit position by the generator polynomial beforehand, and saving those remainder values in a memory; a step of repeatedly decoding an encoded data sequence; a step of inputting together with a decoded data sequence indicating the decoded result, bit position information that indicates the proper bit position of each data of the decoded data sequence; a step of finding remainder values from the memory that correspond to the proper bit positions of data of the decoded data sequence that are not ‘0’, and performing bit-corresponding addition of each of found remainder values, a step of determining that there is no error in the input data sequence when all of the bits of the addition result become ‘0’, otherwise determining that there is error; and a step of stopping decoding of the encoded data at the instant that error is no longer detected. 
         [0029]    Error Detection Device 
         [0030]    A third form of the present invention is an error detection device that detects whether or not input data sequence has error wherein the input data is created at an encoder by regarding a data sequence having a specified bit length as a polynomial, dividing that polynomial by a generator polynomial for generating error detection code and adding the error detection code to the data sequence so that the remainder becomes ‘0’ comprising: a remainder memory that saves remainder values that are obtained when polynomials corresponding to each respective bit position are divided by the generator polynomial; an addition unit to which, together with an input data sequence, bit position information that indicates the proper bit position of each data of the input data sequence is input, finds remainder values from the remainder memory that correspond to the proper bit positions of data of the input data sequence that are not ‘0’, and performs bit-corresponding addition of each of the found remainder values; and an error judgment unit that determines that there is no error in the input data sequence when all of the bits of the addition result are ‘0’, otherwise determines that there is error. 
         [0031]    Error Correction/Error Detection Decoding Device 
         [0032]    A fourth form of the present invention is an error correction/error detection decoding device that decodes encoded data sequence wherein the encoded data sequence is created at an encoder by regarding a data sequence having a specified bit length as a polynomial, dividing that polynomial by a generator polynomial for generating error detection code, adding the error detection code to that data sequence so that the remainder becomes 0, then encoding the data sequence to which the error detection code has been added by a specified encoding method, comprising: a decoder that repeatedly decodes the encoded data sequence as an input data sequence; and an error detection unit that detects whether or not there is error in the decoded result, and notifies the decoding unit of the error detection result; wherein the decoding unit comprises: a decoding unit that repeatedly decodes an encoded data sequence and outputs the decoded result; a bit position management unit that outputs the proper bit position of each data of the decoded result; and a control unit that controls whether the decoding device continues or stops the decoding process; and the error detection unit comprises: a remainder memory that saves remainder values when polynomials that correspond to each respective bit position are divided by the generator polynomial; an addition unit to which, together with a decoded result bit position information that indicates the proper bit position of each data of the decoded result is input, finds remainder values from the remainder memory that correspond to the proper bit positions of data of the decoded result that are not ‘0’, and performs bit-corresponding addition of each of the found remainder values; and an error judgment unit that determines that there is no error in the input data sequence when all of the bits of the addition result become ‘0’, otherwise determines that there is error. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0033]      FIG. 1  is a drawing showing the theoretical construction of a CRC operation device. 
           [0034]      FIG. 2  is a drawing explaining the timing from the start of data input to the output of the check result. 
           [0035]      FIG. 3  is a drawing showing the construction of a first embodiment of the present invention. 
           [0036]      FIG. 4  is a drawing explaining the relationship between the bit number i and P and k of a second embodiment. 
           [0037]      FIG. 5  is a drawing explaining the contents of a remainder memory of the second embodiment. 
           [0038]      FIG. 6  is a drawing showing the construction of a CRC operation unit of the second embodiment. 
           [0039]      FIG. 7  is a drawing explaining the number of input bits and the number of output bits of each portion of a remainder value interpolation unit. 
           [0040]      FIG. 8  is a drawing explaining the construction of a remainder calculation unit. 
           [0041]      FIG. 9  is a drawing of a third embodiment wherein the CRC operation device of the first embodiment is used for error detection of a turbo decoding result. 
           [0042]      FIG. 10  is a drawing that shows the output timings of the decoded result from the turbo decoder and the CRC check result of the third embodiment. 
           [0043]      FIG. 11  is a drawing showing the construction of a CRC check device of a fourth embodiment. 
           [0044]      FIG. 12  is a drawing explaining the case where input bit sequences are input in parallel. 
           [0045]      FIG. 13  is an example of the construction of a communication system to which error detection is applied. 
           [0046]      FIG. 14  is an example of the construction of a divider circuit. 
           [0047]      FIG. 15  is a drawing showing the construction of a CRC check circuit when a bit sequence is input that is not arranged in the proper order. 
           [0048]      FIG. 16  is an example of a communication system that adopts the use of turbo code for error correction code, and uses CRC code for error detection code. 
           [0049]      FIG. 17  is a drawing showing the construction of a turbo encoder. 
           [0050]      FIG. 18  is a drawing showing the construction of a turbo decoder. 
           [0051]      FIG. 19  is a drawing showing the construction of a turbo decoder that combines a first and second element decoder into one element decoder. 
           [0052]      FIG. 20  is a drawing explaining the number of times decoding has been performed and the timing for acquiring the CRC check result. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     (A) Theory of the Invention 
       [0053]    The present invention makes it possible to perform CRC operation on data of which bit sequence is arranged differently from the proper order without returning to the proper order. For example, in the CRC operation method in the case of data that have been input in an order that has been randomized by an interleaving process or the like, the present invention makes it possible to quickly output an error detection result by performing CRC operation without rearrangement processing. All of the operations described below are for “bit-corresponding modulo 2 operation” where “bit-corresponding operation” is operation performed for bits at the same bit location, and modulo 2 addition uses the operator “+”. More specifically, modulo 2 addition is an exclusive OR operation, so bit-corresponding modulo 2 addition is an exclusive OR operation for bits at the same bit location. Also, the “+” operation symbol that appears in the figures showing circuit configuration similarly indicates a bit-corresponding exclusive OR operation. 
         [0054]    In the remainder operation that is used for the CRC operation the input data expressed by a polynomial A(x), and the remainder is obtained by dividing A(x) by an m-degree generator polynomial G(x). 
         [0055]    An input bit sequence having N bits 
         [0000]      {a N-1 , a N-2, . . . , a   1 , a 0 } 
         [0000]    is expressed as the following polynomial. 
         [0000]    
       
         
           
             
               
                 
                   
                     A 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           a 
                           
                             N 
                             - 
                             1 
                           
                         
                          
                         
                           x 
                           
                             N 
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           a 
                           
                             N 
                             - 
                             2 
                           
                         
                          
                         
                           x 
                           
                             N 
                             - 
                             2 
                           
                         
                       
                       + 
                       … 
                       + 
                       
                         
                           a 
                           1 
                         
                          
                         x 
                       
                       + 
                       
                         a 
                         0 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           x 
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    In addition the m-degree generator polynomial is expressed as below. 
         [0000]        G ( x )= x   m   +g   m-1   x   m-1   + . . . +g   1   x+ 1  (3) 
         [0056]    The remainder R i (x) that is obtained by dividing polynomial x i  that corresponds to the ith bit position of the input bit sequence by G(x) can be expressed as the following. 
         [0000]        x   i   =R   i ( x )+ Q   i ( x ) G ( x )  (4) 
         [0000]    Here, x i  indicates a bits-sequence (polynomial) which is created by adding i number of “0s” after a 1. Moreover, Q i (x) is a quotient polynomial resulting from dividing x i  by G(x). From this, A(x) can be rewritten as below. 
         [0000]    
       
         
           
             
               
                 
                   
                     A 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           ( 
                           
                             
                               
                                 R 
                                 i 
                               
                                
                               
                                 ( 
                                 x 
                                 ) 
                               
                             
                             + 
                             
                               
                                 
                                   Q 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                                
                               
                                 G 
                                  
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                      
                     
                       
 
                     
                      
                     
                         
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                          
                         
                           
                             a 
                             i 
                           
                            
                           
                             
                               R 
                               i 
                             
                              
                             
                               ( 
                               x 
                               ) 
                             
                           
                         
                       
                       + 
                       
                         
                           G 
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                          
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             
                               N 
                               - 
                               1 
                             
                           
                            
                           
                             
                               a 
                               i 
                             
                              
                             
                               
                                 Q 
                                 i 
                               
                                
                               
                                 ( 
                                 x 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The second item on the right side of Equation (5) is divisible by the generator polynomial G(x), so the remainder R(x) resulting from dividing A(x) by G(x) is the remainder obtained by dividing the first item on the right side of Equation (5) by G(x), and since the first item is not divisible by G(x), R(x) becomes as given below. 
         [0000]    
       
         
           
             
               
                 
                   
                     R 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                      
                     
                       
                         a 
                         i 
                       
                        
                       
                         
                           R 
                           i 
                         
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Therefore, by knowing R i (x) in advance, the value of the remainder R(x) can be calculated by calculating a i R i (x) and finding the total sum of the results for all of the bits, regardless of the order of the input. 
         [0057]      FIG. 1  is a drawing showing the construction of a CRC operation device that corresponds to the theory described above, where bit data a i  is input to the CRC operation device 1 bit at a time together with bit position information (data number) that indicates the proper bit position i of that bit data. A remainder memory  11  correlates the m bit of remainder R i (x), which is obtained in advance by dividing x i  by the generator polynomial G(x), with the bit position i (i=0 to N, N+1 is the number of bits in the input data sequence), and stores that correlation, and when bit position information i is input, outputs the remainder R i (x) that corresponds to that bit position. A multiplier  12  outputs the remainder R i (x) as is when a i  is “1”, and outputs m bits of 0s when a i  is “0”. An adder  13  performs bit-corresponding modulo 2 addition (exclusive OR operation) of the addition results up to that point (initial value is m bits of 0s) and the output from the multiplier  12 , and saves the addition result in a register  14 . After that, the process described above is repeated for all of the bits of input data, and the last modulo 2 addition result is output as the remainder R(x). An error detection unit  15  determines that there are no errors in the input data when all of the bits of the remainder R(x) are “0”, otherwise determines that there is error and outputs the judgment results. 
         [0058]    By doing the above, it becomes possible to output CRC check results at nearly the same time as the time when the input of N+1 bits of data is complete even when the input order is not in the proper order. And in regards to the time from when data input starts to when the check result is output, it takes conventionally a time of 2×N as shown in (a) of  FIG. 2 , but it takes only a time of N as shown in (b) in the present invention. Therefore, it is possible to output the CRC check results immediately every time turbo decoding is repeated and finished, and when there is no error in the decoded result, it becomes possible to immediately stop the turbo decoder, so there is no need for unnecessary decoder operation. 
       (B) First Embodiment 
       [0059]      FIG. 3  is a drawing showing the construction of a first embodiment of the present invention, where the same reference numbers are given to parts that are identical to those in  FIG. 1 . This drawing differs in that the contents of the remainder memory  11  are clearly shown, the number of input bits and output bits at each unit  11  to  15  is shown, and the number of bits m of the remainder R i (x) is 24 bits. 
         [0060]    The values of the remainder R(x) are stored in a remainder memory  11  beforehand as a table of R i (x) values that are computed from the right side of Equation (6). Input data a i  is input together with the data number i, and the remainder R i (x) is obtained by referencing the ROM table according to the data number i. The obtained R i (x) is multiplied by the input data a i , and the multiplication result is added to the addition result (initial value is m bits of 0s) up to that point that has been saved in a register  14 . Here, bit-corresponding modulo 2 addition is performed as the addition operation. By performing the operation described above for all bits, the value of the remainder R(x) is found after data input is complete. An error detection unit  15  determines whether the remainder R(x) is 0, and when it is 0, outputs a check result of “OK”, however, when it is something other than 0, outputs a check result of “NG”. 
         [0061]    In other words, according to this first embodiment; (1) each data a i  of an input data sequence is input together with bit position information i that indicates the proper bit position of each data; (2) the CRC operation device finds the value of the remainder R i (x) that corresponds to the proper bit position i of each data of the input data sequence that is not 0, and performs bit-corresponding modulo 2 addition of each of the found remainder values Ri(x); and (3) taking the addition result to be the remainder value R(x), determines that there is no error in the input data sequence when all of the bits of the remainder value R(x) are 0, otherwise determines that there is error. In this way, with this first embodiment, the CRC check result can be output immediately every time turbo decoding is repeated and finished. 
       (C) Second Embodiment 
       [0062]    In the first embodiment, it was necessary to store a remainder value R i (x) for each bit of a maximum bit length N+1 of input data, so when N is large, for example when N=10,000, there is a problem in that the remainder memory  11  becomes large. Therefore, in a second embodiment of the invention, the size of the remainder memory  11  can be reduced by storing a remainder value in the remainder memory  11  after every P bits. 
         [0063]    With P taken to be an arbitrary constant, then as shown in  FIG. 4 , i, which indicates the bit position, is decomposed as in Equation (7) where P=2 s . 
         [0000]        i=P·n+k,  0≦ k≦P− 1  (7) 
         [0064]    Here, the necessary remainder value R i (x) is the remainder obtained by dividing x i  by the generator polynomial G(x). When the quotient polynomial obtained by dividing x Pn  by the generator polynomial G(x) is expressed as Q Pn (x), and the remainder polynomial is expressed as R Pn (x), then x i  is given by the following equation, 
         [0000]    
       
         
           
             
               
                 
                   
                     x 
                     i 
                   
                   = 
                   
                     
                       x 
                       
                         Pn 
                         + 
                         k 
                       
                     
                      
                     
                       
 
                     
                      
                     
                         
                     
                     = 
                     
                       
                         
                           x 
                           Pn 
                         
                         · 
                         
                           x 
                           k 
                         
                       
                        
                       
                         
 
                       
                        
                       
                           
                       
                       = 
                       
                         
                           ( 
                           
                             
                               
                                 
                                   Q 
                                   Pn 
                                 
                                  
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                                
                               
                                 G 
                                  
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                             + 
                             
                               
                                 R 
                                 Pn 
                               
                                
                               
                                 ( 
                                 x 
                                 ) 
                               
                             
                           
                           ) 
                         
                          
                         
                           x 
                           k 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    so the remainder value R i (x) becomes equal to the remainder obtained by dividing R Pn (x)·x k  by G(x). Therefore, as shown in  FIG. 5 , R Pn (x) are correlated to a bit position n every P bits and stored as a table, and a remainder is found by finding R Pn (x) that corresponds to n of bit position i (i=P·n+k) and multiplying it by x k , then dividing the multiplication result R Pn (x)·x k  by G(x), and that remainder is taken to be the remainder value R i (x). R Pn (x)·x k  is computed by performing an operation of shifting R Pn (x) that is obtained from the table by k bits to the left, and inserting 0 into the empty bits. 
         [0065]      FIG. 6  is a drawing showing the construction of a CRC operation device of a second embodiment according to the theory described above, where the same reference numbers are given to parts that are identical to those shown in  FIG. 1 . This embodiment differs from the first embodiment in that remainder values R Pn (x) that correspond to bit positions P×n every constant P bits are saved, and a remainder value interpolation unit  20  is provided that interpolates the remainder values for bit positions that are not saved by using the saved values, and a separation unit  30  is provided into which bit positions i (i=P·n+k) are input and it separates the bit positions i into P and k. 
         [0066]    The remainder value interpolation unit  20  comprises: a remainder memory  21  that saves remainder values R Pn (x) that correspond to the bit positions P×n every constant P bits; a shifting unit  22  that shifts the R Pn (x) that corresponds to n of bit position i (i=P·n+k) by k bits to the left; and a remainder calculation unit  23  that divides R Pn (x)·x k , which is obtained by shifting, by the generator polynomial G(x), and outputs the remainder R i (x). Together with bit data a i  being input 1 bit at a time, bit position information (data number) that indicates the proper bit position i (=P·n+k) of that bit data is input to the CRC operation device. The separation unit  30  separates the bit position i into n and k, and the remainder memory  21  outputs the remainder R Pn (x) that corresponds to n. The shifting unit  22  shifts R Pn (x) by k bits to the left and performs the operation R Pn (x)·x k , then the remainder calculation unit  23  divides R Pn (x)·x k  by the generator polynomial G(x) and outputs the remainder R i (x). 
         [0067]    When a i  is “1”, a multiplier  12  outputs the remainder R i (x) as is, and when a i  is “0”, outputs m bits of 0s. An addition unit  13  performs bit-corresponding modulo 2 addition of the addition result (the initial result is m bits of 0s) up to that point that is saved in a register  14  and the output of the multiplication unit  12 , and saves the addition result in the register  14 . After that, the process described above is repeated for all of the bits of the input data, and the final modulo 2 addition result is output as the remainder R(x). An error detection unit  15  determines that there is no error in the input data sequence when all of the bits of the remainder R(x) are “0”, otherwise determines that there is error and outputs the judgment result. 
         [0068]    When taking the remainder value to be m bits, the shifting operation result becomes a maximum of m+P−1 bits, and when m=24 and P=32 (2 6 ), the shifting operation result becomes 55 bits. In (A) and (B) of  FIG. 7 , the number of input bits and the number of output bits of each portion of the remainder value interpolation unit  20  are clearly shown for the case in which m=24, P=32 (2 6 ), s=6 and N=12, where k is expressed as five bits  0  to  4 , and n is expressed as eight bits  5  to  12 . The remainder memory  21  correlates the 24-bit R Pn (x) (=R 32n (x)) with n, and stores that correlation. The output I from the shifting unit  22  is 55 bits  0  to  54 , and the output R i (x) (=R Pn+k (x)) from the remainder calculation unit  23  is 24 bits. 
         [0069]    When the remainder calculation unit  23  in  FIG. 6  and (A) of  FIG. 7  comprises a shifting register (divider) as explained using  FIG. 14 , it is not preferred that 55 clock units be required for division. Incidentally, the number of bits of input I of the remainder calculation unit  23  is set at 55. Therefore, dividing the input I by G(x) can be considered to be division of a fixed input bit length, and the remainder calculation unit  23  can be realized by a unique fixed circuit which is consisted of only exclusive OR circuit without the use of a shifting register. For example, when the generator polynomial is taken to be 
         [0000]        G ( x )= x   24   +x   23   +x   6   +x   5   +x+ 1  (9) 
         [0000]    and P=32, the output bits O[ 0 ] to O[ 23 ] from the remainder calculation unit  23  can be found from an exclusive OR operation of a specified combination of input bits I[ 0 ] to I[ 54 ] as shown in  FIG. 8 . As an example, O[ 22 ] can be found from the exclusive OR operation of I[ 45 ], I[ 40 ] and I[ 22 ]. 
         [0070]    With this second embodiment, similar to the first embodiment, the CRC check result can be output immediately every time turbo decoding is repeated and finished, and the capacity of the remainder memory can also be reduced. 
       (D) Third Embodiment 
       [0071]      FIG. 9  shows the construction of a third embodiment in which the CRC operation device of the first embodiment is used for error detection of a turbo decoding result. In addition to the turbo decoder  51   a  that was explained using  FIG. 19 , a turbo decoding unit  51  comprises a bit number output unit  51   b  that outputs a bit number that indicates the proper bit position of each bit of the decoded result. When the decoded result is in the proper order, the bit number output unit  51   b  outputs bit numbers in that proper order, however, when the decoded result is in an interleaved order, outputs bit numbers in that interleaved order. A CRC operation unit  52  that comprises the construction of the first embodiment shown in  FIG. 3  and to which decoded results and bit numbers from the turbo decoder  51   a  and bit number output nit  51   b  are respectively input, checks whether or not error is contained in the turbo decoded results, and outputs check results. When the check results from the CRC operation unit  52  indicates that there is “no error” even before the set number of decoding repetitions has been reached, a turbo decoder control unit  53  causes the turbo decoder  51   a  to stop turbo decoding, and to start decoding the next encoded data. It is also possible to use the construction of the second embodiment shown in  FIG. 6  as the CRC operation device  52 . 
         [0072]      FIG. 10  is a drawing explaining the output timing of the decoded result from the turbo decoder and output timing of the CRC check result in this third embodiment, and shows the case when error has disappeared after the fourth decoding repetition (CRC OK). With this third embodiment, the CRC operation device  52  is able to perform the CRC operation as the turbo decoder  51   a  inputs the decoded results one bit at a time, so, in other words, the CRC operation device  52  can perform the CRC operation while the turbo decoder  51   a  performs turbo decoding. Therefore, after the turbo decoder  51   a  has repeated and finished turbo decoding operation, the CRC operation device  52  immediately can output the CRC check result for that decoding result, and as soon as a CRC OK is detected, the turbo decoder control unit  53  can send a stop instruction to the turbo decoder  51  and stop the turbo decoding operation. As a result, the turbo decoder  51   a  does not need to perform unnecessary repetitions, and can start the decoding operation for the next encoded data. 
         [0073]    When referencing the decoded result of the third timing shown in  FIG. 20 , in this example of prior art, the CRC check operation in the interleaved order of the second time, and the CRC check operation in the proper order of the third time must be performed at the same time. Therefore, in this example of prior art, in order that the CRC operation can be performed at the same time, mounting two CRC operation devices can be supposed. However, with this third embodiment, it is possible to perform the CRC operation on the turbo decoded results using only one CRC operation device, and thus it is possible to reduce the number of mounted CRC operation devices. 
       (E) Fourth Embodiment 
       [0074]      FIG. 11  is a drawing of the construction of a CRC operation device of a fourth embodiment of the invention, and comprises construction for calculating the remainder R i (x) for each parallel input data in the case where input bit sequences are input in parallel. The same reference numbers are given to parts that are identical to those shown in  FIG. 3 . 
         [0075]      FIG. 12  is a drawing explaining the case when input bit sequences are input in parallel to the CRC operation device. On the transmission side, a CRC bit is added to the transmission information, and information to which CRC bits are added are separated into a plurality of blocks (five blocks in the figure), after which turbo encoding is performed, for example by turbo encoders TCDR 1  to TCDR 5 , for each separated block, and then each block is transmitted. The information length is taken to be 5×M bits, and is separated as 0 to M−1, M to 2M−1, 2M to 3M−1, 3M to 4M−1, and 4M to 5M−1. 
         [0076]    Turbo decoders TDEC 1  to TDEC 5  on the receiving side perform turbo decoding of each of the received encoded data, and input the decoded results in parallel to a parallel type CRC operation device  60  as shown in  FIG. 12 . The CRC operation device  60  comprises the construction shown in  FIG. 11 , and performs the remainder calculation of the first embodiment, for example, on each of the respective M bits of data that were input in parallel, calculates the remainder value R(x) for 5×M bits using the remainder values obtained for each of the parallel data, checks whether that remainder value R(x) is 0, and outputs the check result. 
         [0077]    In  FIG. 11 , the M bits of decoded results and bit numbers that were output from each of the turbo decoders TDEC 1  to TDEC 5  are input to first thru fifth remainder calculation units  61   a ,  61   b , . . . ,  61   e  in the proper order or an interleaved order. For example, M bits of the decoded result a 0  to a M-1  are input in the proper order or interleaved order, and together with those decoded result bits, the bit numbers 0 to M−1 indicating the proper bit positions are input to the first remainder calculation unit  61   a . In addition, M bits of the decoded result am to a 2M-1  are input in the proper order or interleaved order, and together with those decoded result bits, the bit numbers M to 2M−1 indicating the proper bit positions are input to the second remainder calculation unit  61   b . Similarly, M bits of the decoded result a 4M  to a 5M-1  are input in the proper order or interleaved order, and together with those decoded result bits, the bit numbers 4M to 5M−1 indicating the proper bit positions are input to the fifth remainder calculation unit  61   e.    
         [0078]    The remainder calculation units  61   a ,  61   b , . . . ,  61   e  correspond to the remainder memory  11  and multiplication unit  12  in the first embodiment shown in  FIG. 3 , where remainders R i (x) that are correlated with the bit positions are stored in each remainder memory unit  11   a  to  11   e . In other words, remainders R 0 (x) to R M-1 (x) are correlated with the bit positions i=0 to M−1 and stored in the remainder memory  11   a , remainders R M (x) to R 2M-1 (x) are correlated with the bit positions i=M to 2M−1 and stored in the remainder memory  11   b , and thereafter similarly, remainders R 4M (x) to R 5M-1 (x) are correlated with the bit positions i=4M to 5M−1 and stored in the remainder memory  11   e . Each remainder memory  11   a  to  11   e  outputs remainders that correspond to the input bit positions. Multiplication units  12   a  to  12   e  multiply the respectively input decoded result bits by the remainder values that are input from the remainder memories  11   a  to  11   e , and input the result to an addition unit  13 . Overall, the 5-bit remainders are input together to the addition unit  13  from the multiplication units  12   a  to  12   e . The addition unit  13  performs bit-corresponding modulo 2 addition of the addition result up to that point (saved in a register  14 ; initial value 0) and the output from the multipliers  12   a  to  12   e , and saves that addition result in the register  14 . After that, the addition unit  13  repeats the processing described for the M bits of input data, and outputs the final modulo 2 addition result as the remainder R(x). An error detection unit  15  determines that there is no error in the input data sequence when all of the bits of the remainder R(x) are ‘0’, otherwise determines that there is error, and outputs the judgment result. In  FIG. 11 , the construction is based on that of the CRC operation device of the first embodiment shown in  FIG. 3 , however, it is also possible to base the construction on the CRC operation device of the second embodiment shown in  FIG. 6 . 
         [0079]    To summarize, the CRC operation device  60  is such that when decoded results are input in parallel, the remainder values that correspond to the proper bit positions of the bit data of the parallel data sequences that are not ‘0’ are all added by modulo addition by the adder  13 , and when all of the bits of the addition result become ‘0’, determines that there is no error in the input data sequence, otherwise determines there is error, and outputs the check result. 
       ADVANTAGES OF THE INVENTION 
       [0080]    With the present invention, even when the bit sequence of the input data is not arranged in proper order, the CRC check result can be computed and output without rearranging the data into the proper order). In addition, with the present invention, the CRC check result can be output immediately at the instant when error in the decoded result is eliminated. Moreover, with the present invention, the decoding operation can be stopped and decoding of the next encoded data can be started immediately at the instant when error in the decoded result is eliminated, and thus the number of times decoding must be performed by a decoder for one sequence of encoded data can be reduced. Furthermore, with the present invention, a CRC operation device could be constructed with small-scale hardware configuration.