LFSR's are used in many applications for generating pseudorandom numbers, which in turn may be used for such purposes as encryption, or synchronization of data transmissions.
A well known such use is in the CDMA (Code Division Multiple Access) scheme employed in the IS-95 standard for cellular telephone transmission. Both the base station and the mobile stations employ a 42-bit LFSR to generate a periodic code with period 2.sup.42 -1 bits (known to those in the cellular telephone art as "the Long Code"). For a base station to communicate with a mobile station, their Long Codes must be synchronized. Due to range uncertainty (which affects transmission time) and randomized delays introduced to avoid multiple user traffic collisions, at a given time a mobile station's Long Code and a base station's Long Code may be different, and thus require synchronization in order to communicate. (Typically, the base station's code is ahead of the mobile station's code.)
Synchronization requires a "searcher" in the base station to determine the number of shifts (bit offsets) by which the base station's LFSR leads the mobile station's LFSR. The two LFSRs must then be syunchronized. The base station's LFSR cannot simply be backward-shifted to accomplish this, because the feedback mechanisms are not susceptible of reversal.
One conventional method for accomplishing synchronization in the case where the mobile station's LFSR is ahead of the base station's is to run the base station's LFSR forward at a clock rate many times (typically, 48 times) higher than normal until it has advanced to the desired state.
In the case where the base station's LFSR leads the mobile station's LFSR, the base station's LFSR is simply stopped until the mobile LFSR "catches up" to it. These conventional methods have the disadvantage of requiring extra hardware for the high-speed forward shift, and the disadvantage of wasting time while the LFSR is stopped.
Another conventional method is to store the base station LFSR output over a sufficient number of bits (typically, 1400) to enable matching with the mobile station's current bit pattern. The obvious drawback is that 1400 flip-flops are required, with their resultant increase in cost and power consumption.
Yet another conventional method is to use a mirror-image LFSR in addition to the main LFSR with feedback mechanisms such that it shifts backward through the reverse of the sequence through which the main LFSR shifts forward. This has the obvious drawback of necessitating a great deal of additional circuitry.
While most conventional solutions are hardware-based, some recent algorithms have been posited for determining future states of LFSR's by mathematical methods susceptible of implementation in software or firmware. See the work of Arthur H. M. Ross, Ph.D., at Internet web page http://www.cdj.org/a.sub.-- ross/LFSR.html (date unknown), or the work of M. Serra at http:/www.csr.uvic.ca/home/mserra/CApaper/node4.html (Jun. 24, 1996). These algorithms, however, are not able to determine past states of LFSRs.
Accordingly, there exists a need for a method of determining a past state of a LFSR that does not require significant additional hardware and that does not cause the waste of significant amounts of time.
It is thus an object of the present invention to provide a method of resetting a LFSR that eliminates the drawbacks of conventional CDMA systems.
It is a further object of the present invention to provide a method for resetting a LFSR that has fixed overhead for shifting backward or forward independent of shift length.
It is a further object of the present invention to provide a practical method of performing very large shifts, which are impractical in conventional systems.
It is a further object of the present invention to provide a method of resetting a LFSR that may be easily embedded in firmware in an application-specific integrated circuit (ASIC) and ideally in parallel operation where multiple shift positions are needed, as in multi-user detection.
These and other objects of the invention will become apparent to those skilled in the art from the following description thereof.