Abstract:
A linear intrasummed multiple-bit feedback shift register is presented which comprises a multi-stage multi-bit feedback shift register and further includes an adder situated before the input to each stage and which is used to modify the shifted signals according to predefined constants. The additional intrastage summing increases the complexity of the feedback function and makes it more difficult to determine the specific structure from a limited stream of output bits, thus increasing the security of the circuit.

Description:
FIELD OF THE INVENTION 
     This invention generally relates to the circuitry which generates periodic pseudo-random numbers. 
     BACKGROUND OF THE INVENTION 
     A Feedback Shift Register (“FSR”) is a circuit element which is used to generate periodic pseudo-random numbers for various applications, such as self-testing circuits, CDMA spread code generating circuit, etc. A sample 5-stage FSR  10  is illustrated in FIG.  1 . 
     As shown, the FSR  10  comprises a sequence of single-bit shift registers  12  connected such that the value of the i th  stage at time t equal the value of the previous stage at time t−1. The output of the last stage is combined with the output of one or more intermediate stages with one or more corresponding adders  14  to form a feedback signal  16  which is input to the first stage. 
     The contents of an FSR can be expressed as a vector (b 0 b 1 b 2  . . . b n−1 ), where b j  presents the value of i-th stage and the feedback signal  16  equals c 0 b 0 +c 1 b 1 + . . . +c n−1 b n−1 , where all c j  are constants. In the circuit of FIG. 1, constants c 0 , c 2 , and C 3  are zero (and hence corresponding adders are not necessary) and the feedback signal  16  equals b 1 +b 4 . Because the representative equation of the feedback signal is linear, this FSR configuration is called a linear feedback shift register (LFSR). LFSRs are simple to design and have a period which is easy to determine. 
     A variation on the linear FSR shift register is the linear intrainverted FSR (“IFSR”). This circuit is similar to the FSR but includes an inverter between each stage such that b j+1 ={overscore (bj)} in next cycle. A particular advantage of an IFSR is that it is harder to determine the structure of the feedback arrangement when compared to a linear FSR. If successive 2n−1 output bits are of an n-stage linear FSR are known, the feedback arrangement can be determined. However, substantially more than 2n−1 successive bits must be known to detect the feedback-shift arrangement if some or all the register outputs are inverted and then fed to next stages. 
     It is also known to provide feedback shift registers where each stage contains more than one bit. Such a linear multiple-bit feedback shift register (MFSR)  20  is illustrated in FIG.  2 . The circuit includes a plurality of t-bit registers  22  in which the input of the i th  stage at time t is dependent on the value of the previous stage at time t−1. The output of the last stage is summed with the outputs of one or more previous stages using adders  24  to produce a feedback signal  26  which is input to the first stage. In preferred implementations, the extracted intrastage signals are fed to respective multipliers  28  and multiplied by a constant associated with the stage from which the signal is extracted. In this circuit  20  of FIG. 2, the outputs of the last stage and the first two stages are each multiplied by a respective constant and the resultant values summed to produce the feedback signal  26  provided as input to the first stage. 
     The use of a MFSR permits parallel or low power operation. In data scrambling operations, multiple bits can be scrambled each clock cycle, rather than scrambling one bit per time. Alternatively, power can be saved if only one random bit is needed in each cycle since a MFSR shifts out multiple bits in each cycle and thus an mt-bit wide MSFR will only need to be clocked every m cycles. However, the MFSR shares many disadvantages with binary LFSR, such as low hardware testability, low security etc. 
     Accordingly, it would be advantages to provide a modified MSFR which has at least the same period as a conventional MSFR but requires a longer sequence of bits to determine the feedback function, and therefore, is more secure. 
     SUMMARY OF THE INVENTION 
     According to the invention, a Linear Intrasummed Multiple-bit Feedback Shift Register (LIMFSR) is presented. The configuration of the LIMFSR circuit is similar to a multiple feedback shift register but further includes an adder situated before the input to each stage and which is used to modify the shifted signals by predefined constants. This additional intrastage summing increases the complexity of the feedback function and makes it more difficult to determine the specific structure from a limited stream of output bits, thus increasing the security of the circuit. The particular values of the intrasummed constants needed for specific implementations of the LIMFSR circuit can be determined in accordance with a technique based on finite field theory. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and other features of the present invention will be more readily apparent from the following detailed description and drawings of illustrative embodiments of the invention in which: 
     FIG. 1 is a block diagram of a conventional linear feedback shift register; 
     FIG. 2 is a block diagram of a conventional multiple-bit feedback shift register; and 
     FIG. 3 is a block diagram of a linear intrasummed multiple-bit feedback shift register according to the invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 3 is a block diagram of a linear intrasummed multiple-bit feedback shift register  30 . The circuit  30  comprises n stages  32 .i, 0&lt;i&lt;n−1 each having an input  33 .i and an output  34 .i. Each stage  32  comprises a t-bit register  36  and an adder  37 . The adder combines the input  33  and a predefined constant Y i  which is associated with the particular stage  32  to produces an intermediate signal  38 . The intermediate signal  38  is loaded into the register  36  during the next clock cycle. 
     The output  34 .i of each stage except the last is connected directly to the input  33 .i+1 of the subsequent stage. The output  34 .n−1 of the last stage is summed with the outputs of one or more previous stages using summers  39  to produce a feedback signal  40  which is input to the first stage. The output signals which are combined to generate the feedback signal  40  are preferably fed to respective multipliers  42  and multiplied by a constant associated with the stage from which the signal is extracted before being input to the respective summer  39 . The circuit  30  may be formed from discrete components. Preferably, however, the circuit  30  is implemented as an integrated circuit which may be combined with other circuit elements on a single chip. In addition, while summers  39  are shown as separate elements, it is understood that one summer having more than two inputs can be used instead. 
     The use of the intrastage adders  37  to modify the shifted values increases the number of parameters which must be determined by a party analyzing the output of the circuit  30  before they can deduce the structure of the circuit itself. In particular, successive 3n−1 output numbers must be known to generate the 2n linear equations needed to determine the specific structure of a particular implementation of the circuit  30 . In contrast, the structure of a conventional MFSR, such as shown in FIG. 2, can be deduced with only 2n−1 successive outputs. Therefore, the circuit  30  of the invention provides increases security when used in data scrambling applications. 
     The determination of the specific values for the feedback and intrastage constants requires reference to finite field theory. As known to one of skill in the art, each finite field GF(p n ) has an associated primitive polynomial defined as                  α   n     +       ∑     i   =   1       n   -   1                         c   i     ·     α   i         +     c   0       ,       c   0     ≠   0.             (     Equ   .              1     )                                
     Every element e of finite field GF(p n ) can be expressed as            ∑     i   =   0       n   -   1                         e   j     ·     α   i         ,                          
     where α is the primitive element. Every element e can also be expressed in dual base as:                ∑     i   =   0       n   -   1                           b   j     ·     β   j            〈       β   0     ,     β   1     ,       β   2          …β     n   -   1           〉               (     Equ   .              2     )                                
     Using the primitive polynomial of GF(p n ) and its dual base, a MSFR circuit, such as shown in FIG. 2, can be designed, where the i-th stage presents b j , and the feedback function is determined by the primitive polynomial. If and only if c j  is not zero, the output of i-th stage is multiplied by −c j+1 /c 0 , then summed (inside a finite field) with the multiplication of the output of the last stage and −1/c 0 . The generated sequence has a period p n −1, containing all the elements in GF(p n ) except 0. It is linear multiple-bit feedback shift register. When p=2, the circuit reduces to a binary LFSR, such as shown in FIG. 1 
     As shown in FIG. 3, in the circuit of the invention, the input to the i-th stage is summed with a constant Y j , 0&lt;=Y j &lt;p for all i. For an n-stage circuit where each stage has t bits, the feedback arrangement to produce the maximum cycle length is determined by the primitive polynomial defined as:                GF        (     p   n     )       =       α   n     +       ∑     i   =   1       n   -   1                         c   i     ·     α   i         +       c   0          (       c   0     ≠   0     )                 (     Equ   .              3     )                                
     If c i  is not zero, the output of i-th stage is multiplied by −c i+1 /c 0 , then summed with the multiplication of the output of the last stage by −1/c 0  and further summed with Y 0  when fed back to the first stage. Stated another way, the feedback function is:              ∫     =       ∑     i   =   1       n   -   1                         -     c   i       ·       b   i     /     c   0                     (     Equ   .              4     )                                
     where b i  is the output of i-th stage. Since the feedback function is still linear and the output of each stage is “intrasummed” when input to the following stage, this FSR is called Linear Intrasummed Multiple-bit Feedback Shift Register (LIMFSR). As will be recognized by those of skill in the art, p can be any number which is a prime power number. However, the most efficient design is p=2 t  to fully utilize the register array. 
     The specific cyclic behavior of the LIMFSR circuit  30  according to the invention is very complicated to predict. However, several design principles have been determined which are sufficient to design specific instances of the circuit  30 . These principles are detailed below. 
     The next state value of the various stages in the circuit  30  can be predicted using the current state, the feedback function, and the intrastage constants. For an LIMFSR is designed on GF(p n ), if the value presented by the current cycle is          v   =       ∑     i   =   0       n   -   1                         b   j     ·     β   j           ,                          
     where b j  is i-th stage value, and the value presented 
     by next cycle is            v   ′     =       ∑     i   =   0       n   -   1                         b   j   ′     ·     β   j           ,                          
     the following relationships are true:                v   ′     =       v   ·   α     +       ∑     i   =   0       n   -   1                         Y   i     ·     β   i                   (     Equ   .              5     )                                
     and                b   0     =       Y   0     -       b     n   -   1       /     c   0       +       ∑     i   =   0       n   -   1                         -     c     i   +   1         ·       b   i     /     c   0                     (     Equ   .              7     )                                
     where 0&lt;i&lt;n. 
     In addition, it can be shown that if the LIMFSR is designed on GF(p n ), the period of the pseudo-random number sequence is p n −1. This is the same period as for a conventional MFSR designed on GF(p n ). Thus, the security of the circuit is increased without reducing the period. The resulting periodic number sequence for the LIMFSR contains all of the numbers in GF(p n ) except one, which can be calculated as:                α          ∑     i   =   0       n   -   1                         Y   j     ·     β   j             α   -   1             (     Equ   .              8     )                                
     Utilizing general design principles for feedback shift registers, and the specific principles specified in Equations 5-8, one of skill in the art can implement a specific LIMFSR by (1) selecting the primitive polynomial to determine the feedback function, (2) selecting the parameters Y 0 −Y n−1  in accordance with the desired circuit operation, and (3) initializing the circuit to any number except the one specified in Equation 7. 
     In addition to an increase in security, the LIMFSR  30  of the invention also has improved usefulness in testability. For example, in an LIMFSR  30  built on GF(4 n ), each stage has two bits, the constants Y 0 −Y n−1  can each be set to equal “3.” Note that in GF(4), 3+0=3, and 3+3=0. To detect and locate a specific register which is stuck at zero, all of the registers are first reset to 0s, then shifted out serially in cycles. Because each stage has two bits, two bits are shifted out in each cycle. The position where the serial output produces continues 1s can be used to detect the location of the faulty register. Similarly, to detect stuck-at−1 faults, LIMFSR is first set to all 1s then shifted out serially. 
     Although preferred embodiments of the invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that many additions, modifications and substitutions are possible, without departing from the scope and spirit of the invention as defined by the accompanying claims. Preferably, all components are digital. However, those components may be analog and/or digital.