PATENT ABSTRACT
A linear feedback shift calculation apparatus, into which input data is input, and which outputs output data, including: an L generation unit which generates q values of q 0  to q N−2  represented by: 
     
       
         
           
             
               
                 
                   
                     q 
                     k 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             p 
                             0 
                           
                         
                         
                           
                             ( 
                             
                               k 
                               = 
                               0 
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               p 
                               k 
                             
                             + 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 
                                   q 
                                   
                                     k 
                                     - 
                                     1 
                                     - 
                                     i 
                                   
                                 
                                 × 
                                 
                                   p 
                                   i 
                                 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               1 
                               ≤ 
                               k 
                               ≤ 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   1 
                 
               
             
           
         
       
     
     (where, p 0 , p 1 , . . . , p N−1 , q 0 , q 1 , . . . , q N−2  belong to Galois field GF( 2 )) from coefficients p 0  to p N−2  among inputted coefficients p −1  to p N−1  (wherein, N is a natural number of 2 or more); and a matrix calculation unit which outputs the output data calculated from the output data b 0  to b N−1  represented by: 
     
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             b 
                             
                               N 
                               - 
                               1 
                             
                           
                         
                       
                       
                         
                           
                             b 
                             
                               N 
                               - 
                               2 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             b 
                             o 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     L 
                     × 
                     
                       ( 
                       
                         
                           U 
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     a 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       N 
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     a 
                                     0 
                                   
                                 
                               
                             
                             ) 
                           
                         
                         + 
                         
                           
                             p 
                             
                               - 
                               1 
                             
                           
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       N 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   2 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     L 
                     = 
                     
                       ( 
                       
                         
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               1 
                             
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 3 
                               
                             
                           
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 4 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 3 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               q 
                               1 
                             
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                         
                       
                       ) 
                     
                   
                    
                   
                     
 
                   
                    
                   
                     U 
                     = 
                     
                       ( 
                       
                         
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                           
                             
                               p 
                               1 
                             
                           
                           
                             
                               p 
                               0 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                           
                             
                               p 
                               1 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   3 
                 
               
             
           
         
       
     
     from the q values q 0  to q N−2 , the coefficients p −1  to p N−1  and the input data a −N  to a −1 , a 0  to a N−1 .

PATENT DESCRIPTION
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2008-269523, filed on Oct. 20, 2008, the entire contents of which are incorporated herein by reference. 
       FIELD 
       [0002]    The embodiments discussed herein are related to a linear feedback shift calculation apparatus, a communication apparatus, a microprocessor, and a data output method in a linear feedback shift calculation apparatus. 
       BACKGROUND 
       [0003]    Communication apparatuses such as cell phones have conventionally been provided with a linear feedback shift calculation apparatus for processing various signals. For example, a linear feedback shift calculation apparatus is used as a scrambler for pseudo-randomizing transmission signals in order to compress transmission signal jitter and the like. 
         [0004]    Examples of this type of related art are described in Japanese Laid-open Patent Publication No. 2005-101753 and Japanese Laid-open Patent Publication No. H9-190339. 
         [0005]    However, as depicted in FIG. 19B of Japanese Laid-open Patent Publication No. 2005-101753 and FIG. 3 of Japanese Laid-open Patent Publication No. H9-190339, a linear feedback shift calculation apparatus capable of parallel processing of multiple bits with a single clock has a feedback line connected to the next stage, and uses the results of the previous stage to carry out arithmetic processing. Consequently, delays accumulate and a considerable delay results for outputting all bits. 
       SUMMARY 
       [0006]    According to an aspect of the invention, a linear feedback shift calculation apparatus, into which input data is input, and which outputs output data, including: an L generation unit which generates q values of q 0  to q N−2  represented by: 
         [0000]    
       
         
           
             
               
                 
                   
                     q 
                     k 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             p 
                             0 
                           
                         
                         
                           
                             ( 
                             
                               k 
                               = 
                               0 
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               p 
                               k 
                             
                             + 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 
                                   q 
                                   
                                     k 
                                     - 
                                     1 
                                     - 
                                     i 
                                   
                                 
                                 × 
                                 
                                   p 
                                   i 
                                 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               1 
                               ≤ 
                               k 
                               ≤ 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   1 
                 
               
             
           
         
       
     
         [0000]    (where, p 0 , p 1 , . . . , p N−1 , q 0 , q 1 , . . . , q N−2  belong to Galois field GF( 2 )) from coefficients p 0  to p N−2  among inputted coefficients p −1  to p N−1  (wherein, N is a natural number of 2 or more); and a matrix calculation unit which outputs the output data calculated from the output data b 0  to b N−1  represented by: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             b 
                             
                               N 
                               - 
                               1 
                             
                           
                         
                       
                       
                         
                           
                             b 
                             
                               N 
                               - 
                               2 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             b 
                             o 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     L 
                     × 
                     
                       ( 
                       
                         
                           U 
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     a 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       N 
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     a 
                                     0 
                                   
                                 
                               
                             
                             ) 
                           
                         
                         + 
                         
                           
                             p 
                             
                               - 
                               1 
                             
                           
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       N 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   2 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     L 
                     = 
                     
                       ( 
                       
                         
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               1 
                             
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 3 
                               
                             
                           
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 4 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 3 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               q 
                               1 
                             
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                         
                       
                       ) 
                     
                   
                    
                   
                     
 
                   
                    
                   
                     U 
                     = 
                     
                       ( 
                       
                         
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                           
                             
                               p 
                               1 
                             
                           
                           
                             
                               p 
                               0 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                           
                             
                               p 
                               1 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   3 
                 
               
             
           
         
       
     
         [0000]    from the q values q 0  to q N−2 , the coefficients p −1  to p N−1  and the input data a −N  to a −1 , a 0  to a N−1 . 
         [0007]    The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
         [0008]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0009]      FIG. 1  is an example of the configuration of a digital information transmission and reception apparatus (communication apparatus); 
           [0010]      FIG. 2  is an example of the configuration of a linear feedback shift calculation apparatus; 
           [0011]      FIG. 3  is an example of the configuration of an L generation apparatus; 
           [0012]      FIG. 4  is an example of the configuration of a matrix calculation apparatus; 
           [0013]      FIG. 5  is a flow chart depicting an example of processing by the linear feedback shift calculation apparatus; 
           [0014]      FIG. 6  is another example of the configuration of a linear feedback shift calculation apparatus; 
           [0015]      FIG. 7  is another example of the configuration of a linear feedback shift calculation apparatus; 
           [0016]      FIG. 8  is another example of the configuration of a linear feedback shift calculation apparatus; 
           [0017]      FIG. 9  is an example of simulation results; 
           [0018]      FIG. 10  is an example of simulation results; 
           [0019]      FIG. 11  is an example of simulation results; 
           [0020]      FIG. 12  is an example of simulation results; 
           [0021]      FIG. 13  is another example of the configuration of a linear feedback shift calculation apparatus; 
           [0022]      FIG. 14  is another example of the configuration of a linear feedback shift calculation apparatus; and 
           [0023]      FIG. 15  is another example of the configuration of a linear feedback shift calculation apparatus. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0024]    The following provides an explanation of preferred embodiments of the present invention with reference to the drawings. 
         [0025]      FIG. 1  is an example of the configuration of a digital information transmission and reception apparatus (or communication apparatus)  1 . The digital information transmission and reception apparatus  1  is provided with a transmission frame assembly unit  10 , a linear feedback shift calculation apparatus  20 , a channel modulation unit  30 , a CPU  40 , a control register  45 , a frame parameter selection circuit  50 , a conversion characteristic polynomial coefficient selection circuit  55 , a modulation-demodulation parameter selection circuit  60 , a channel demodulation unit  65 , and a transmission frame disassembly unit  75 . 
         [0026]    The transmission frame assembly unit  10  converts digital transmission information to frames corresponding to the communication format (CDMA format, WiMAX format, IEEE802.11a/b or other wireless LAN format) based on frame parameters from the frame parameter selection circuit  50  and outputs those frames. 
         [0027]    The linear feedback shift calculation apparatus  20  outputs encoded data obtained by scrambling and converting data contained in transmission frames based on a characteristic polynomial coefficient from the conversion characteristic polynomial coefficient selection circuit  55 . The characteristic polynomial coefficient can also adopt various values corresponding to the communication format. The linear feedback shift calculation apparatus  20  is also a digital data conversion apparatus. 
         [0028]    Furthermore, in addition to scrambling conversion, the linear feedback shift calculation apparatus  20  can also be embodied in the case of generating or testing data CRC codes or generating spread codes according to the CDMA format. In the present embodiment, the linear feedback shift calculation apparatus  20  is explained using the example of scrambling conversion. 
         [0029]    The channel modulation unit  30  modulates each data of transmission frames following scrambling conversion based on the modulation parameters from the modulation-demodulation parameter selection circuit  60 . The demodulation parameters can also adopt different values corresponding to the communication format. Modulated transmission frames are output to the channel. 
         [0030]    The CPU  40  outputs control data indicating the communication format and the like. 
         [0031]    The control register  45  retains control data from the CPU  40  and outputs the data to the frame parameter selection circuit  50 , the conversion characteristic polynomial coefficient selection circuit  55  and the modulation-demodulation parameter selection circuit  60 . 
         [0032]    The frame parameter selection circuit  50  selects frame parameters corresponding to the communication format based on control data from the CPU  40 , and outputs the frame parameters to the transmission frame assembly unit  10 . 
         [0033]    The conversion characteristic polynomial coefficient selection circuit  55  selects a characteristic polynomial coefficient corresponding to the communication format based on control data from the CPU  40 , and outputs the coefficient to the linear feedback shift calculation apparatus  20 . 
         [0034]    The modulation-demodulation parameter selection circuit  60  selects modulation parameters and demodulation parameters corresponding to the communication format based on control data from the CPU  40 , and outputs the parameters to the channel modulation unit  30  and the channel demodulation unit  65 , respectively. 
         [0035]    The frame parameter selection circuit  40 , the conversion characteristic polynomial coefficient selection circuit  55  and the modulation-demodulation parameter selection circuit  60  may each be memories, and frame parameters, characteristic polynomial coefficients and modulation-demodulation parameters are stored therein. 
         [0036]    The channel demodulation unit  65  demodulates data contained in transmission frames from the channel based on demodulation parameters. 
         [0037]    The linear feedback shift calculation (descrambling conversion) apparatus  20  on the receiving side has the same configuration as the linear feedback shift calculation apparatus  20  on the sending side. Input data input to the receiving-side linear feedbacks shift calculation apparatus  20  is demodulated data, while output data is data output to the transmission frame disassembly unit  75 . Data is deconverted to the original input data (digital transmission information) by carrying out scrambling conversion twice. 
         [0038]    The transmission frame disassembly unit  75  extracts digital reception information from transmission frames containing descrambled converted data. 
         [0039]    The digital transmission and reception apparatus  1  can carry out communication corresponding to multiple communication formats. 
         [0040]    In addition, in the digital transmission and reception apparatus  1 , the linear feedback shift calculation apparatus  20  may be made to calculate a portion of data contained in transmission frames output from the transmission frame assembly unit  10 . For example, the linear feedback shift calculation unit  20  may be made to substitute a portion of the transmission frames with descrambled converted data. 
         [0041]    Moreover, the linear feedback shift calculation apparatus  20  may be made to calculate a portion of data contained in transmission frames and insert the calculated data into transmission frames. 
         [0042]    The receiving-side linear feedback shift calculation apparatus  20  may also be made to calculate a portion of the demodulated transmission frames and substitute a portion of those transmission frames with calculated data. 
         [0043]      FIG. 2  is an example of the configuration of the linear feedback shift calculation apparatus  20 . The linear feedback shift calculation apparatus  20  is provided with an L generation apparatus  210 , a pq value storage element  220 , a matrix calculation apparatus  230 , and an output storage element  240 . 
         [0044]    The L generation apparatus  210  is input with characteristic polynomial coefficients p −1  to p N−1  (where, N is a natural number of 2 or more) from the conversion characteristic polynomial coefficient selection circuit  55 , and outputs q values q 0  to q N−2  using characteristic polynomial coefficients p 0  to p N−2 . The L generation apparatus  210  brings together those specific portions of calculations executed by the linear feedback shift calculation apparatus  20  that can be calculated by characteristic polynomial coefficients only, the details of which are described later. 
         [0045]    The pq value storage element  220  stores characteristic polynomial coefficients p −1  to p N−1  from the conversion characteristic polynomial coefficient selection circuit  55  and q values q 0  to q N−2  from the L generation apparatus  210 . 
         [0046]    The matrix calculation apparatus  230  calculates output data b 0  to b N−1  from input data a −N  to a −1 , output values from the pq value storage element  220  (q values q 0  to q N−2  and characteristic polynomial coefficients p −1  to p N−1 ), and output values a 0  to a N−1  from the output storage element  240 , and outputs these values as scrambling conversion values. In addition, the matrix calculation apparatus  230  stores output data b 0  to b N−1  in the output storage element  240 , reads out output data b 0  to b N−1  stored in the output storage element  240  each time input data a 0  to a N−1  is input to the matrix calculation apparatus  230 , and uses that output data as input data a −N  to a −1 . The details of the matrix calculation apparatus  230  are described later. 
         [0047]    The output storage element  240  retains output data b 0  to b N−1 . 
         [0048]      FIG. 3  is an example of the configuration of the L generation apparatus  210 . The L generation apparatus  210  is provided with a plurality of multipliers  211  and adders  212 . However, this multiplication and addition refers to multiplication and addition in respective Galois fields GF( 2 ), and consists of arithmetic operations realized by logic AND arithmetic units and exclusive logic OR arithmetic units, respectively. In the L generation apparatus  210 , for example, the first coefficient p 0  of the characteristic polynomial coefficients is output directly as q 0 , the coefficient p 0  and the q value q 0  are multiplied by the multipliers  211 , that value and the next coefficient p 1  are added by the adders  212 , and that value is output as the q value q 1  of the next bit. The L generation apparatus  210  employs a configuration in which these calculations are sequentially repeated. An output value q k  (wherein, 0≦k≦N−2, and N is a natural number of 2 or more) of the L generation apparatus  210  can be represented by: 
         [0000]    
       
         
           
             
               
                 
                   
                     q 
                     k 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             p 
                             0 
                           
                         
                         
                           
                             ( 
                             
                               k 
                               = 
                               0 
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               p 
                               k 
                             
                             + 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 
                                   q 
                                   
                                     k 
                                     - 
                                     1 
                                     - 
                                     i 
                                   
                                 
                                 × 
                                 
                                   p 
                                   i 
                                 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               1 
                               ≤ 
                               k 
                               ≤ 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   19 
                 
               
             
           
         
       
     
         [0000]    (wherein, p 0 , p 1 , . . . , p N−1 , q 0 , q 1 , . . . , q N−2  belong to Galois field GF( 2 )), and provided that N is a natural number of 2 or more. The L generation apparatus  210  has a circuit equivalent to Equation 19. A detailed description of q value and the like will be subsequently provided. 
         [0049]      FIG. 4  is an example of the configuration of the matrix calculation apparatus  230 . The matrix calculation apparatus  230  carries out arithmetic processing on q values q 0  to q N−2 , characteristic polynomial coefficients p −1  to p N−1  and input data a −N  to a −1  and a 0  to a N−1  from the L generation apparatus  210  with a plurality of multipliers  231  and adders  232 , and outputs output data b 0  to b N−1 . However, this multiplication and addition refers to multiplication and addition in respective Galois fields GF( 2 ), and consists of arithmetic operations realized by logic AND arithmetic units and exclusive logic OR arithmetic units, respectively. In the matrix calculation apparatus  230 , for example, input data a −1  and characteristic polynomial coefficient p −1  are multiplied by the multipliers  231 . Output value a N−1  and characteristic polynomial coefficient p N−1  from the output storage element  240  are multiplied by the multipliers. These two products are then added by the adders  232 . The matrix calculation apparatus  230  repeats these calculations and outputs output data b 0  to b N−1 . Output values b 0  to b N−1  of the matrix calculation apparatus  230  can be represented by: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             b 
                             
                               N 
                               - 
                               1 
                             
                           
                         
                       
                       
                         
                           
                             b 
                             
                               N 
                               - 
                               2 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             b 
                             o 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     L 
                     × 
                     
                       ( 
                       
                         
                           U 
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     a 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       N 
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     a 
                                     0 
                                   
                                 
                               
                             
                             ) 
                           
                         
                         + 
                         
                           
                             p 
                             
                               - 
                               1 
                             
                           
                           × 
                           
                             ( 
                             
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     a 
                                     
                                       - 
                                       N 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   20 
                 
               
             
           
         
       
     
         [0050]    Here, L and U are Nth order square matrices, respectively, represented by: 
         [0000]    
       
         
           
             
               
                 
                   
                     L 
                     = 
                     
                       ( 
                       
                         
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               1 
                             
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 3 
                               
                             
                           
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 4 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             
                               q 
                               
                                 N 
                                 - 
                                 3 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               q 
                               1 
                             
                           
                           
                             
                               q 
                               0 
                             
                           
                           
                             1 
                           
                         
                       
                       ) 
                     
                   
                    
                   
                     
 
                   
                    
                   
                     U 
                     = 
                     
                       ( 
                       
                         
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                           
                             
                               p 
                               1 
                             
                           
                           
                             
                               p 
                               0 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                           
                             
                               p 
                               1 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               p 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               p 
                               
                                 N 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   21 
                 
               
             
           
         
       
     
         [0000]    The matrix calculation apparatus  230  depicted in  FIG. 4  is a circuit equivalent to Equation 20. 
         [0051]      FIG. 5  is a flow chart depicting an example of processing by the linear feedback shift calculation apparatus  20 . Once processing starts (S 10 ), the L generation apparatus  210  acquires characteristic polynomial coefficients p −1  to p N−1  from the conversion characteristic polynomial coefficient selection circuit  55  and outputs q values q 0  to q N−2  (S 11 ). 
         [0052]    Next, the matrix calculation apparatus  230  calculates and outputs output data b 0  to b N−1  (S 12 , S 13 ). Namely, the matrix calculation apparatus  230  calculates output data b 0  to b N−1  based on the first N number of input data a −N  to a −1  and output values a 0  to a N−1  (initial value: 0) from the output storage element  240  and outputs that data (S 12 ). Moreover, when input data a −N  to a −1  is input, the matrix calculation apparatus  230  calculates output data b 0  to b N−1  obtained by the processing of S 12  from output storage element  240  as input data a 0  to a N−1  (S 13 ). 
         [0053]    Next, the matrix calculation apparatus  230  carries out processing of S 13  if input data a −N  to a −1  has been input (Yes in S 14 ), or ends processing (S 15 ) if input data has not been input (No in S 14 ). The matrix calculation apparatus  230  then outputs data obtained by scrambling and converting input data a −N  to a −1  as output data b 0  to b N−1 . 
         [0054]    Next, an explanation is provided of the configuration and equations of the L generation apparatus  210  and the matrix calculation apparatus  230 .  FIGS. 6 and 7  are an example of the configuration of a linear feedback shift calculation apparatus  25  of an 8-bit input (N=8). The linear feedback shift calculation apparatus  25  depicted in  FIG. 6  is equivalent to the linear feedback shift calculation apparatus  20  depicted in  FIG. 2 . That in which the L generation apparatus  210  and the matrix calculation apparatus  230  and the like have been removed from the linear feedback shift calculation apparatus  25  is the linear feedback shift calculation apparatus  20  depicted in  FIG. 2 . Furthermore, the linear feedback shift calculation apparatus  25  depicted in  FIG. 7  is an example of a configuration in which the linear feedback shift calculation apparatus  25  depicted in  FIG. 6  has been slid over by one stage each. 
         [0055]    The linear feedback shift calculation apparatus  25  is able to make the current tap position active as a result being imparted with linear polynomial coefficients p −1  to p N−1  of arbitrary values. The linear feedback shift calculation apparatus  25  is able to calculate the output of multiple bits (N=8 in the example of  FIG. 6 ) in parallel with a single clock as a result of the combinational circuit portions of each stage being connected in the form of a cascade connection. When input data a 0  to a N−1  is imparted to this linear feedback shift calculation apparatus  25 , pseudo-randomized output data b 0  to b N−1  is output for input data a 0  to a N−1  in the same manner as the linear feedback shift calculation apparatus  25  depicted in  FIG. 2 . 
         [0056]    Output data b 0  to b N−1  of this linear feedback shift calculation apparatus  20  can be represented as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     b 
                     
                       N 
                       - 
                       1 
                       - 
                       k 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 
                                   N 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 
                                   p 
                                   i 
                                 
                                 × 
                                 
                                   a 
                                   i 
                                 
                               
                             
                             + 
                             
                               
                                 p 
                                 
                                   - 
                                   1 
                                 
                               
                               × 
                               
                                 a 
                                 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               k 
                               = 
                               0 
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               
                                 
                                   
                                     
                                       ∑ 
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       
                                         N 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       
                                         p 
                                         i 
                                       
                                       × 
                                       
                                         a 
                                         
                                           i 
                                           + 
                                           k 
                                         
                                       
                                     
                                   
                                   + 
                                   
                                     
                                       ∑ 
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       
                                         p 
                                         i 
                                       
                                       × 
                                       
                                         b 
                                         
                                           N 
                                           - 
                                           k 
                                           + 
                                           i 
                                         
                                       
                                     
                                   
                                   + 
                                 
                               
                             
                             
                               
                                 
                                   
                                     p 
                                     
                                       - 
                                       1 
                                     
                                   
                                   × 
                                   
                                     a 
                                     
                                       
                                         - 
                                         1 
                                       
                                       - 
                                       k 
                                     
                                   
                                 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               1 
                               ≤ 
                               k 
                               ≤ 
                               
                                 N 
                                 - 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   22 
                 
               
             
           
         
       
     
         [0000]    (wherein, a N−1 , a N−2 , . . . , a 0 , a −1 , a −2 , . . . , a −N , p N−1 , p N−2 , . . . , p 0 , p −1  belong to Galois field GF( 2 )). The linear feedback shift calculation apparatus  25  is a circuit equivalent to this Equation 22. 
         [0057]    Here, the linear feedback shift calculation apparatus  25  can be divided into two circuit portions.  FIG. 8  is an example of a configuration in which the linear feedback shift calculation apparatus  25  depicted in  FIG. 6  and the like is divided into two circuit portions. 
         [0058]    As depicted in the drawing, the linear feedback shift calculation apparatus  25  can be divided into a first circuit  26  and a second circuit  27 . The first circuit  26  is a circuit portion capable of carrying out calculations directly using input values. The second circuit  27  is a circuit portion has a feedback line connected thereof and carries out calculations using output from the previous stage. 
         [0059]    Here, intermediate variables c[0] to c[7] are introduced. The intermediate variables c[0] to c[7] are values obtained when input values have been determined. Output values b[0] to b[7] can be represented using these intermediate variables c[0] to c[7] in the following manner: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             b 
                              
                             
                               [ 
                               7 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               6 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               5 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               4 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               3 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               2 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             b 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               7 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               6 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               5 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               4 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               3 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               2 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             c 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 3 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 4 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 3 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 5 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 4 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 3 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               p 
                                
                               
                                 [ 
                                 6 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 5 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 4 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 3 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                           
                             
                               p 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                       
                       ) 
                     
                     · 
                     
                       ( 
                       
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 7 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 6 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 5 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 4 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 3 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               b 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 7 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 6 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 5 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 4 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 3 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 2 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                           
                         
                         
                           
                             
                               c 
                                
                               
                                 [ 
                                 0 
                                 ] 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   23 
                 
               
             
           
         
       
     
         [0000]    For example, b[5]=p[1]b[7]+p[0]b[6]+c[5]. This Equation 23 represents a recursion formula relating to output values b[0] to b[7] in the form of a matrix. This matrix can be represented as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           b 
                         
                       
                       
                         
                           c 
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               T 
                               P 
                             
                           
                           
                             
                               I 
                               N 
                             
                           
                         
                         
                           
                             
                               O 
                               N 
                             
                           
                           
                             
                               I 
                               N 
                             
                           
                         
                       
                       ] 
                     
                     · 
                     
                       [ 
                       
                         
                           
                             b 
                           
                         
                         
                           
                             c 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   24 
                 
               
             
           
         
       
     
         [0000]    wherein, 0 N  is a Nth order zero matrix, I N  is an Nth order unit matrix, and T p  is an Nth order square matrix in which all diagonal components are “0”. 
         [0060]    In Equation 23, b[7] is first determined by the initial substitution, and b[6] is determined in the next substitution. Namely, in the determinant of Equation 23, b[ ] appearing on the right side of Equation 23 can be eliminated by repeating substitution eight times. Thus, each output value b[0] to b[N−1] represented by intermediate variable c[ ] can be obtained by determining the Nth power of the matrix of Equation 24. 
         [0061]    The Nth power of Equation 24 becomes as follows. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               T 
                               P 
                             
                           
                           
                             
                               I 
                               N 
                             
                           
                         
                         
                           
                             
                               O 
                               N 
                             
                           
                           
                             
                               I 
                               N 
                             
                           
                         
                       
                       ] 
                     
                     N 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               T 
                               P 
                               N 
                             
                              
                             
                               ( 
                               
                                 = 
                                 
                                   O 
                                   N 
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 0 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                              
                             
                               T 
                               P 
                               k 
                             
                           
                         
                       
                       
                         
                           
                             O 
                             N 
                           
                         
                         
                           
                             I 
                             N 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   25 
                 
               
             
           
         
       
     
         [0000]    Here, since T p  is an Nth order square lower triangular matrix in which all diagonal components are “0”, Tp becomes as depicted below. 
         [0000]      T P   N =O N   Equation 26 
         [0062]    Thus, once the following is determined, 
         [0000]    
       
         
           
             
               
                 
                   
                     L 
                     P 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                        
                       
                         T 
                         P 
                         k 
                       
                     
                     = 
                     
                       
                         T 
                         P 
                         
                           N 
                           - 
                           1 
                         
                       
                       + 
                       
                         T 
                         P 
                         
                           N 
                           - 
                           2 
                         
                       
                       + 
                       … 
                       + 
                       
                         T 
                         P 
                       
                       + 
                       
                         I 
                         N 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   27 
                 
               
             
           
         
       
     
         [0000]    output values b[ ] can be determined from intermediate variables c[ ]. 
         [0063]    Here, when (I N −T P ) is multiplied from the left to both sides of Equation 27, 
         [0000]      left side=( I   N   −T   P ) L   P , and 
         [0000]      right side= I   N   −T   P   N   =I   N    
         [0000]    Here, deformation on the right side is dependent on Equation 26. The following results since both sides are equal. 
         [0000]        L   P =( I   N   −T   p ) −1   Equation 28 
         [0000]    Namely, L P  is the inverse matrix of (I N −T P ). The matrix (I N −T P ) is as depicted below. 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         1 
                       
                       
                         0 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         1 
                       
                       
                         0 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         1 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         … 
                       
                       
                         0 
                       
                     
                     
                       
                         ⋮ 
                       
                       
                         
                             
                         
                       
                       
                         ⋱ 
                       
                       
                         ⋱ 
                       
                       
                         
                             
                         
                       
                       
                         
                             
                         
                       
                       
                         ⋮ 
                       
                     
                     
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 3 
                               
                               ] 
                             
                           
                         
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 4 
                               
                               ] 
                             
                           
                         
                       
                       
                         … 
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         1 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 2 
                               
                               ] 
                             
                           
                         
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 3 
                               
                               ] 
                             
                           
                         
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 4 
                               
                               ] 
                             
                           
                         
                       
                       
                         … 
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           - 
                           
                             p 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         1 
                       
                     
                   
                   ) 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   29 
                 
               
             
           
         
       
     
         [0000]    Here, L P  is assumed to be a lower triangular Toeplitz matrix in which all diagonal components are “1”. A Toeplitz matrix is the generic term for a matrix in which the same elements are arranged diagonally. This assumption is based on the fact that (I N −T P ) indicated in Equation 29 is a lower triangular Toeplitz matrix in which all diagonal components are “1”, and that in general, a lower triangular Toeplitz matrix in which all diagonal components are “1” has the property of having an inverse matrix in the form a lower triangular Toeplitz matrix in which all diagonal components are “1”. On the basis of this assumption, matrix L P  is represented as depicted below. 
         [0000]    
       
         
           
             
               
                 
                   
                     L 
                     p 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             q 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             q 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                         
                           
                             q 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                         
                           1 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           
                               
                           
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             q 
                             ( 
                             
                               N 
                               - 
                               3 
                             
                             ] 
                           
                         
                         
                           
                             q 
                              
                             
                               { 
                               
                                 N 
                                 - 
                                 4 
                               
                               ] 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             q 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                         
                           
                             q 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                         
                           1 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             q 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 2 
                               
                               ] 
                             
                           
                         
                         
                           
                             q 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 3 
                               
                               ] 
                             
                           
                         
                         
                           
                             q 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 4 
                               
                               ] 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             q 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                         
                           
                             q 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                         
                           1 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   30 
                 
               
             
           
         
       
     
         [0000]    Since L P (I N −T P )=I N  from Equation 28, each component q[ ] of matrix L P  is required to satisfy the following equation by comparing the first column of L P (I N −T P ) with the first column of I N . 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             q 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             q 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             q 
                              
                             
                               [ 
                               2 
                               ] 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             q 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 2 
                               
                               ] 
                             
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             
                               ( 
                               1 
                               ) 
                             
                              
                             
                               ( 
                               
                                 p 
                                  
                                 
                                   [ 
                                   0 
                                   ] 
                                 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 ( 
                                 
                                   q 
                                    
                                   
                                     [ 
                                     0 
                                     ] 
                                   
                                 
                                 ) 
                               
                                
                               
                                 ( 
                                 
                                   p 
                                    
                                   
                                     [ 
                                     0 
                                     ] 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 ( 
                                 1 
                                 ) 
                               
                                
                               
                                 ( 
                                 
                                   p 
                                    
                                   
                                     [ 
                                     1 
                                     ] 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 ( 
                                 
                                   q 
                                    
                                   
                                     [ 
                                     1 
                                     ] 
                                   
                                 
                                 ) 
                               
                                
                               
                                 ( 
                                 
                                   p 
                                    
                                   
                                     [ 
                                     0 
                                     ] 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 ( 
                                 
                                   q 
                                    
                                   
                                     [ 
                                     0 
                                     ] 
                                   
                                 
                                 ) 
                               
                                
                               
                                 ( 
                                 
                                   p 
                                    
                                   
                                     [ 
                                     1 
                                     ] 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 ( 
                                 1 
                                 ) 
                               
                                
                               
                                 ( 
                                 
                                   p 
                                    
                                   
                                     [ 
                                     2 
                                     ] 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             
                               
                                 
                                   
                                     
                                       ( 
                                       
                                         q 
                                          
                                         
                                           [ 
                                           
                                             N 
                                             - 
                                             3 
                                           
                                           ] 
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       ( 
                                       
                                         p 
                                          
                                         
                                           [ 
                                           0 
                                           ] 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       ( 
                                       
                                         q 
                                          
                                         
                                           [ 
                                           
                                             N 
                                             - 
                                             4 
                                           
                                           ] 
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       ( 
                                       
                                         p 
                                          
                                         
                                           [ 
                                           1 
                                           ] 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   … 
                                   + 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       ( 
                                       
                                         q 
                                          
                                         
                                           [ 
                                           0 
                                           ] 
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       ( 
                                       
                                         p 
                                          
                                         
                                           [ 
                                           
                                             N 
                                             - 
                                             3 
                                           
                                           ] 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                      
                                     
                                       ( 
                                       
                                         p 
                                          
                                         
                                           [ 
                                           
                                             N 
                                             - 
                                             2 
                                           
                                           ] 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   31 
                 
               
             
           
         
       
     
         [0000]    Conversely, since L P  defined as in Equation 30 results according to q[ ] that satisfies Equation 31, and I N  results when the product of the matrix represented by Equation 29 is calculated, L P (I N −T P )=I N , or in other words, Equation 28 is valid without contradiction. L P  was determined this manner. 
         [0064]    On the other hand, b[ ]=L p c[ ] from Equations 27 and 25. Thus, once matrix L p  has been determined, b[ ] can be determined by calculating the matrix from the value of c[ ]. 
         [0065]    Equation 19 is a representation of each component of Equation 31 in the form of an equation, and the L generation apparatus  210  is a representation of Equation 31 in the form of a circuit. As was previously described, these Equations 31 and 30 are determined by deformation of the second circuit  27  of the linear feedback shift calculation apparatus  25  so as to be able to be represented with the variable c[ ]. Thus, the second circuit  27  of a circuit configuration in which a feedback line is connected to the next stage can be substituted with the product of the matrix L p  determined according to the value (q[ ]) output by the L generation apparatus  210  and a vector composed of the variable c[ ]. 
         [0066]    On the other hand, in  FIG. 8  a matrix calculation formula for obtaining an intermediate variable c[ ] (equivalent to the first circuit  26 ) can be represented in the following manner. 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             c 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 1 
                               
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               c 
                                                
                                               
                                                 [ 
                                                 
                                                   N 
                                                   - 
                                                   2 
                                                 
                                                 ] 
                                               
                                             
                                           
                                         
                                         
                                           
                                             ⋮ 
                                           
                                         
                                       
                                     
                                   
                                   
                                     
                                       
                                         c 
                                          
                                         
                                           [ 
                                           1 
                                           ] 
                                         
                                       
                                     
                                   
                                 
                               
                             
                             
                               
                                 
                                   c 
                                    
                                   
                                     [ 
                                     0 
                                     ] 
                                   
                                 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       
                         U 
                         p 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 a 
                                  
                                 
                                   [ 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                   ] 
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   a 
                                                    
                                                   
                                                     [ 
                                                     
                                                       N 
                                                       - 
                                                       2 
                                                     
                                                     ] 
                                                   
                                                 
                                               
                                             
                                             
                                               
                                                 … 
                                               
                                             
                                           
                                         
                                       
                                       
                                         
                                           
                                             a 
                                              
                                             
                                               [ 
                                               1 
                                               ] 
                                             
                                           
                                         
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       a 
                                        
                                       
                                         [ 
                                         0 
                                         ] 
                                       
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         p 
                          
                         
                           [ 
                           
                             - 
                             1 
                           
                           ] 
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   a 
                                   ′ 
                                 
                                  
                                 
                                   [ 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                   ] 
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   
                                                     a 
                                                     ′ 
                                                   
                                                    
                                                   
                                                     [ 
                                                     
                                                       N 
                                                       - 
                                                       2 
                                                     
                                                     ] 
                                                   
                                                 
                                               
                                             
                                             
                                               
                                                 ⋮ 
                                               
                                             
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               a 
                                               ′ 
                                             
                                              
                                             
                                               [ 
                                               1 
                                               ] 
                                             
                                           
                                         
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         a 
                                         ′ 
                                       
                                        
                                       
                                         [ 
                                         0 
                                         ] 
                                       
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   32 
                 
               
             
           
         
       
     
         [0000]    Here, matrix U p  is as indicated below. 
         [0000]    
       
         
           
             
               
                 
                   
                     U 
                     p 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 1 
                               
                               ] 
                             
                           
                         
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 2 
                               
                               ] 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             p 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                         
                           
                             p 
                              
                             
                               [ 
                               0 
                               ] 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 1 
                               
                               ] 
                             
                           
                         
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 2 
                               
                               ] 
                             
                           
                         
                         
                           
                               
                           
                         
                         
                           
                             p 
                              
                             
                               [ 
                               1 
                               ] 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           
                               
                           
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           0 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 1 
                               
                               ] 
                             
                           
                         
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 2 
                               
                               ] 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           
                             p 
                              
                             
                               [ 
                               
                                 N 
                                 - 
                                 1 
                               
                               ] 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   33 
                 
               
             
           
         
       
     
         [0067]    In summary of the above, the output value b of the linear feedback shift calculation apparatus  25  can be represented as depicted below using U p , L p , p[−1], a[ ] and a′[ ]. 
         [0000]        b=L   p   {U   p   a+p[− 1] a′}   Equation 34 
         [0000]    This Equation 34 is equivalent to the previously described Equation 20. 
         [0068]    In this manner, the linear feedback shift calculation apparatus  20  depicted in  FIG. 2  separates the circuit portion for feeding back by a feedback line from the linear feedback shift calculation apparatus  25  depicted in  FIG. 6  (the second circuit  27 ) and the circuit portion for determining the product of the L generation apparatus  210  for calculating the matrix L p  and vector composed of matrix L p  and variable c[ ]. 
         [0069]    Next, an explanation is provided of simulation results of the linear feedback shift calculation apparatus  20  configured in this manner.  FIGS. 9 to 12  are examples of simulation results. 
         [0070]    Among these drawings,  FIG. 9  is an example of simulation results in the case of polynomial coefficient p changing each time input data a is input in the case of using the linear feedback shift calculation apparatus  25  ( FIG. 6 ). Time is depicted in the vertical axis, while each stage of the linear feedback shift calculation apparatus  25  is depicted on the horizontal axis. As depicted in  FIG. 9 , when the time at which calculation begins in the linear feedback shift calculation apparatus  25  is defined as “0”, results are obtained in which a time “77” is required until output is obtained from the final stage. 
         [0071]      FIG. 10  is an example of simulation results in the case polynomial coefficient p changes each time input data a is input in the case of using the linear feedback shift calculation apparatus  20  ( FIG. 2 ). As depicted in this drawing, a time of “54” is required until the output from the final stage is obtained, and the delay time is shorter in comparison with the linear feedback shift calculation apparatus  25  in which feedback lines are connected in the manner of a cascade. 
         [0072]      FIG. 11  is an example of simulation results in the case of using the linear feedback shift calculation apparatus  25  and predetermining polynomial coefficient p prior to calculation. In this case as well, results were obtained in which a time “77” is required from the start of calculations by the linear feedback shift calculation apparatus  25  until output is obtained. Regardless of whether or not the polynomial coefficient p changes for each input of input data a, there is no change in the delay time of the linear feedback shift calculation apparatus  25  in which feedback lines are connected in the manner of a cascade. 
         [0073]      FIG. 12  is an example of simulation results in the case of using the linear feedback shift calculation apparatus  20  and predetermining polynomial coefficient p prior to calculation. In this case, results were obtained in which a time “44” is required from the start of calculations by the linear feedback shift calculation apparatus  20  until output is obtained. In this application, there are many cases in which the frequency at which characteristic polynomial coefficient p changes is lower than the frequency of calculation, and thus there are many cases in which the time during which the characteristic polynomial coefficient p is determined prior to calculation is long. In such cases, although delay is improved in the case of using the linear feedback shift calculation apparatus  25 , in the case of using the linear feedback shift calculation apparatus  20  ( FIG. 2 ), delay time is improved as a result of eliminating the effect of the processing delay of the L generation apparatus  210 . 
         [0074]    On the basis of the simulation results described above, the linear feedback shift calculation apparatus  20  provided with the L generation apparatus  210  and the matrix calculation apparatus  230  has a shorter delay time than the linear feedback shift calculation apparatus  25  in which feedback lines are connected in the form of a cascade, and that delay time becomes even shorter in the case polynomial coefficient p is predetermined prior to calculation ( FIG. 12 ). 
         [0075]    Next, an explanation is provided of another example of the configuration of the linear feedback shift calculation apparatus  20 .  FIGS. 13 to 15  are the configuration examples, and depict examples in which the linear feedback shift calculation apparatus  20  is configured with a microprocessor. The linear feedback shift calculation apparatus  20  enables the use of dedicated commands to the use of a microprocessor. 
         [0076]    As depicted in  FIG. 13 , a microprocessor  250  is provided with the matrix calculation apparatus  230 , a command fetcher  251 , a program counter  252 , a command decoder  253 , an immediate value generation unit  254 , a bit string concatenation unit  256 , a register file  257  and a function unit  258 . Among these, the immediate value generation unit  254 , the matrix calculation apparatus  230 , the register file  257  and the function unit  258  are mutually connected to an s1 bus and s2 bus. In addition, the bit string concatenation unit  256 , the register file  257  and the function unit  258  are mutually connected to a d bus. 
         [0077]    The microprocessor  250  is connected to a memory apparatus  270 . The memory apparatus  270  stores the results (q values) of calculations carried out by the L generation apparatus  210  (Equation 19) and characteristic polynomial coefficient p values. The q values are determined in advance by calculation, and those values are stored in the memory apparatus  270 . The memory apparatus  270  may also be an external storage apparatus of the microprocessor  250 . 
         [0078]    Next, an explanation is provided of an example of the operation of the microprocessor  250 . The case of input of a command “LUOP d, s1, s2”, for example, is explained. This command indicates that outputs b 0  to b N−1  are calculated from register values represented by operand “s1” (p −1  to p N−1 , q 0  to q N−2 ) and register values represented by operand “s2” (a −N  to a −1 , a 0  to a N−l ), and that a value obtained by articulating N bit “0” superordinate to that value is written to a register represented by operand “d”. 
         [0079]    This command is input to the function unit  258  through the command fetcher  251 , the command decoder  253  and the immediate value generation unit  254  and the like. The function unit  258  refers to the data address and reads out the required value from the memory apparatus  270 . The read value is then stored in the register file  257  via the d bus. 
         [0080]    The matrix calculation apparatus  230  reads out characteristic polynomial coefficient p values p −1  to p N−1  and q values of q 0  to q N−2  via the s1 bus from the register file  257 , and then reads out input values a (input data a −N  to a −1 , a 0  to a N−1 ) via the S2 bus. The matrix calculation apparatus  230  then outputs output values b 0  to b N−1  in the same manner as the previously described example ( FIG. 2 ). Since 2N bit data (both p and q values and input values a are 2N bits) is handled on the d bus (to facilitate storage in the memory apparatus  270 ), the bit string concatenation unit  256  articulates the N bit “0” to the superordinate bit and outputs to the d bus for output values b 0  to b N−1  of the matrix calculation apparatus  230 . Values that have been output to the d bus are stored in the register file  257 . 
         [0081]    Output values stored in the register file in this manner are output to the memory apparatus  270  through the function unit  258  by subsequently issuing a store command for storing register values in memory. Output values converted by scrambling input values in the same manner as in the previously described example are stored in the memory apparatus  270 . 
         [0082]      FIG. 14  is another example of the configuration of the linear feedback shift calculation apparatus  20 . In this configuration, the microprocessor  250  is further provided with the matrix calculation apparatus  230 , a p −1  value generation unit  261 , a bit string concatenation unit  262  and a pq register  263 . 
         [0083]    The p −1  value generation unit  261  generates a p −1  value (=0 or 1) among the p values that corresponds to a command decoded by the command decoder  253 , and outputs that value to the bit string concatenation unit  262 . 
         [0084]    The bit string concatenation unit  262  articulates the output (q value) of the L generation unit  210 , the input (characteristic polynomial coefficient p value) and the p −1  value, and outputs to the pq register  263 . 
         [0085]    The pq register  263  then holds the pq value (p −1  to p N−1 , q 0  to on q N−1 ). 
         [0086]    Next, an explanation is provided of the operation. Operation is explained using an example of three commands. The first command is a “GENL0 s1” command. This command calculates a q value of q 0  to q N−1  using a register value represented by the operand “s1” (p 0  to p N−1 ), articulates this q value, the p N−1  value (=0) and register values p 0  to p N−1  and writes this articulated value to the pq register  263 . 
         [0087]    The input data (including input data a and characteristic polynomial coefficient p) is written to the function unit  258 , the d bus and the register file  257 . The L generation apparatus  210  reads out p values p 0  to p N−1  from the register file  257  via the s1 bus and outputs q values q 0  to q N−1 . The bit string concatenation unit  256  articulates the outputs q 0  to q N−1  of the L generation apparatus  210 , p values p 0  to p N−1  and the p −1  value (=0) and writes these values to the pq register  263 . 
         [0088]    The second command is “GENL1 s1”. This command is the same as the command “GENL0 s1” except that the p −1  value (=1) is different. 
         [0089]    The third command is “LOUP d, s1, s2”. An explanation of the operation is as follows. The matrix calculation apparatus  230  reads out input data a 0  to a N−1  via the s1 bus from the register file  257 , reads out input a −N  to a N−1  via the s2 bus from the register file  257 , reads out pq values (q 0  to q N−1 , p −1  to p N−1 ) from the pq register  263 , calculates output b 0  to b N−1  and writes the results to the register file  257  via the d bus. The output b 0  to b N−1  written in the register file  257  is then output to the outside via the function unit  258 . The data output is converted by scrambling the data input. 
         [0090]      FIG. 15  depicts another example of the configuration of the linear feedback shift calculation apparatus  20 . Similar to the previously described examples, the microprocessor  250  is provided with the L generation apparatus  210  and the matrix calculation apparatus  230 , and bit string concatenation units  262  and  256  are respectively provided on the output side of the L generation apparatus  210  and the matrix calculation apparatus  230 . 
         [0091]    The following provides an explanation of operation using two commands. The first command is “GENL d, s1”. The L generation apparatus  210  reads out a value represented by “s1” (p values p −1  to p N−1 ) from the register file  257  via the s1 bus, and calculates a q value of q 0  to q N−2 . The bit string concatenation unit  262  then articulates this q value of q 0  to q N−2  with the p value of p −1  to p N−1  and writes to the register file  257  represented by “d” via the d bus. 
         [0092]    The second command is “LUOP d, s1, s2”. The matrix calculation apparatus  230  reads out data represented by “s1” (input data a −N  to a −1 , a 0  to a N−1 ) from the register file  257  via the s1 bus, reads out values represented by “s2” (p values of p −1  to p N−1 , q values of q 0  to q N−2 ) from the register file  257  via the s2 bus, and then calculates output b 0  to b N−1 . The bit string concatenation unit  256  then articulates the N bit “0” superordinate to the output b 0  to b N−1  and writes to the register file  257  via the d bus. 
         [0093]    The output data written to the register file  257  is data that has been converted by scrambling the input data, and is output to the outside via the function unit  258  by subsequently issuing a store command and the like for storing register values in memory. 
         [0094]    In the examples described above, the digital transmission and reception apparatus  1  has been explained using the example of containing a sending side (transmission frame assembly unit  10  to modulation-demodulation parameter selection circuit  60 ) and a receiving side (CPU  40  to transmission frame disassembly unit  75 ). However, the invention can also be carried out with the digital transmission and reception apparatus  1  containing only a sending side or a receiving side. 
         [0095]    A data transmission method in a communication apparatus having a small delay, a communication apparatus, a linear feedback shift calculation apparatus and a microprocessor can be provided. 
         [0096]    All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a depicting of the superiority and inferiority of the invention. Although the embodiment(s) of the present invention has been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.