This invention generally relates to the circuitry which generates periodic pseudo-random numbers.
A Feedback Shift Register (xe2x80x9cFSRxe2x80x9d) 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 ith stage at time t equal the value of the previous stage at time txe2x88x921. 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 (b0b1b2 . . . bnxe2x88x921), where bj presents the value of i-th stage and the feedback signal 16 equals c0b0+c1b1+ . . . +cnxe2x88x921bnxe2x88x921, where all cj are constants. In the circuit of FIG. 1, constants c0, c2, and C3 are zero (and hence corresponding adders are not necessary) and the feedback signal 16 equals b1+b4. 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 (xe2x80x9cIFSRxe2x80x9d). This circuit is similar to the FSR but includes an inverter between each stage such that bj+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 2nxe2x88x921 output bits are of an n-stage linear FSR are known, the feedback arrangement can be determined. However, substantially more than 2nxe2x88x921 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 ith stage at time t is dependent on the value of the previous stage at time txe2x88x921. 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.
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.
USPTO Backgrounds
USPTO Backgrounds