Linear intrasummed multiple-bit feedback shift register

Details Linear intrasummed multiple-bit feedback shift register Linear intrasummed multiple-bit feedback shift register

1999-09-30

2002-10-08

Iqbal, Nadeem (Department: 2184)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C714S739000

Reexamination Certificate

active

06463448

ABSTRACT:

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.


REFERENCES:
patent: 3911330 (1975-10-01), Fletcher et al.
patent: 4356559 (1982-10-01), Candy et al.
patent: 5105376 (1992-04-01), Pedron
patent: 5309449 (1994-05-01), Gandini et al.
patent: 5446683 (1995-08-01), Mullen et al.
patent: 5579337 (1996-11-01), Grinstein et al.
patent: 5612973 (1997-03-01), Gershenfeld
patent: 5745522 (1998-04-01), Heegard
patent: 5761239 (1998-06-01), Gold et al.
patent: 6240432 (2001-05-01), Chuang et al.
patent: 6260173 (2001-07-01), Weng et al.

Affiliated with

Also associated with

Rating

Linear intrasummed multiple-bit feedback shift register does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Linear intrasummed multiple-bit feedback shift register, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear intrasummed multiple-bit feedback shift register will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2980086