Abstract:
Searcher architecture for use in a CDMA radio system for determining transmission delay in order to synchronize a receiver&#39;s binary code generators with those used to modulate a received, modulated signal comprises a combining means for combining samples of the received signal, buffer means for storing sequences of the combined samples, and correlators for correlating, at high clock speed, multiple sequences of the receiver&#39;s binary code generators with the stored sequences of samples in order to find correlation with a particular one of the multiple sequences of the receiver&#39;s binary code generators and thus determine the transmission delay.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to radio communication systems such as CDMA systems, and more particularly to synchronization of a receiver with the received signal, which may have experienced transmission delays. 
     BACKGROUND OF THE INVENTION 
     CDMA (code-division multiple access) systems are well known. See, generally,  CDMA Cellular Mobile Communications and Network Security,  Dr. Man Young Rhee, Prentice Hall 1998, ISBN 0-13-598418-1, and standard TIA/EIA/IS-95, hereinafter “IS-95”. 
     In CDMA systems, information bits transmitted from a mobile station to a base station may undergo convolutional encoding, symbol repetition, and block interleaving, the result of which is a bit stream comprising what are known as code symbols. As shown in FIG. 1 (prior art), the code symbols are then modulated into “Walsh chips”. They are then “spread” into PN (pseudo-noise) chips by sequential bits of what is known in the CDMA art as the “long code” (LC). The PN chips are then OQPSK (offset quadrature phase-shift keying) modulated into two channels, known as the I channel and the Q channel, the latter being delayed by one-half a PN chip duration. Spreading to the two channels is accomplished by adding the PN chip stream in modulo-2 arithmetic to sequential bits of two different pseudo-noise binary sequences known as PN I  and PN Q  respectively. The PN chips are then converted from baseband to a radio transmission frequency for “air link” (radio transmission) to the base station. 
     When the base station demodulates the signal it converts back to baseband and undoes the aforementioned OQPSK modulation, long-code spreading, and Walsh modulation. To this end, counterparts of the mobile station&#39;s Walsh functions, long code generator, PN I  generator, and PN Q  generator can exist in the base station in order to produce “local replicas” of the codes used to spread and modulate the transmitted data. However, at the inception of transmission from the mobile station, the base station&#39;s generators are generally not synchronized with the received signal because of, among other things, delays occurring in transmission. Also, the mobile station may introduce delay for purposes of collision avoidance. It is thus necessary for the base station to determine the amount of transmission delay in order to effect synchronization. This is done by apparatus generally known as a “searcher”. It can generally be assumed that the delay will be no greater than a particular amount, known as the “uncertainty region”. 
     Conventional searchers generally operate on trial and error, trying varying amounts of delay with correlator circuits against the incoming received signal until meaningful results are obtained. 
     A “one-branch” search scheme attempts correlation against live, incoming input using only one correlator. Such a scheme is quite slow and cannot meet strict requirements for CDMA systems (as set forth in the IS-95 standard, for example). 
     A “multibranch” scheme using live input data (essentially, a plurality of one-branch searchers, each trying a different amount of delay) are commensurately faster than one-branch schemes, but in many cases still fall short of meeting strict standards, as those for CDMA systems. 
     A “total parallel” search strategy optimizes searching according to the maximum-likelihood criterion. Such schemes are much faster than “one-branch” and meet the strict requirements for CDMA systems; however, this is obtained at the expense of much greater complexity and expense. 
     Passive “matched filter” schemes acquire signals rapidly, since the time to cover all possible unknown positions of the uncertainty region is simply the length of the section of the PN code that is loaded as coefficients of the matched filter plus the length of the uncertainty region. However, building a matched filter of appropriate length can be quite expensive. 
     Accordingly there is a need for a relatively high-speed, low-cost searcher for determining transmission delay in a radio transmission system. 
     It is thus an object of the present invention to provide a relatively high-speed searcher for determining transmission delay. 
     It is another object of the present invention to provide a relatively low-complexity searcher for determining transmission delay. 
     It is another object of the present invention to provide a relatively inexpensive searcher for determining transmission delay. 
     These and other objects of the invention will become apparent to those skilled in the art from the following description thereof. 
     SUMMARY OF THE INVENTION 
     In accordance with the teachings of the present invention, these and other objects may be accomplished by the present high-speed, low-cost systems and methods of determining transmission delay. An embodiment of the present invention includes A/D converters for taking samples of the received signal after conversion to baseband, buffers for storing the samples, means for generating local replicas of the mobile station&#39;s code generators and for presenting various sequential states of the local replicas to correlators for time-compressed correlation of the local replicas with the stored samples, and determination of the transmission delay according to the relative position of a correlation value significantly greater than all the other correlation values. 
     The invention will next be described in connection with certain exemplary embodiments; however, it should be clear to those skilled in the art that various modifications, additions and subtractions can be made without departing from the spirit or scope of the claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention will be more clearly understood by reference to the following detailed description of an exemplary embodiment in conjunction with the accompanying drawings, in which: 
     FIG. 1 (prior art) is a block diagram showing functions performed in a CDMA transmitter; 
     FIG. 2 is a block diagram of a searcher in accordance with the present invention; 
     FIG. 3 is a block diagram illustrating operation of the multibranch OQPSK correlators depicted in FIG. 2; 
     FIG. 4 depicts the logic functions performed by the correlators of FIG. 3; 
     FIG. 5 is a graphical representation of exemplary outputs of the correlators of the present invention; and 
     FIG. 6 is a graphical representation of exemplary outputs of the correlators of the present invention which might occur during multipath reception. 
    
    
     DESCRIPTION OF THE INVENTION 
     The present invention discloses a form of “searcher” which determines a delay imparted to received signals by oversampling the signals, summing at least some of the samples of these signals, storing the sums in a buffer, and correlating the stored sums at an accelerated clock rate against local replicas generated with incrementing amounts of delay to determine a correlation identifying the amount of delay. 
     FIG. 2 is a block diagram of the searcher architecture according to the present invention. The following parameters may apply to an embodiment of the present invention. 
     PN chip rate: 1.2288 Mcps 
     Frame duration: 20 ms. 
     One frame contains 96 Walsh symbols 
     Long Code from a 42-bit LFSR 
     I-channel and Q-channel PN codes from 15-bit LFSR&#39;s 
     Modulation: OQPSK 
     Access procedure: Sending of an access probe consisting of an Access Channel preamble and an Access Channel message capsule. 
     Access Channel preamble can be from 1 to 16 frames (20-320 ms) 
     Uncertainty region is less than 512 PN chips. 
     One Walsh symbol comprises 256 PN chips. 
     Those skilled in the art will recognize that these parameters may be changed depending upon the choice of components. 
     It is assumed by way of example that the architecture resides in a CDMA base station covering three sectors in which each sector has two diversity antennas. There are thus six antennas, designated A 1  through A 6 . It will be apparent to those skilled in the art that more or fewer than 3 sectors may be involved and more or fewer than two antennas per sector may be employed. The delay may be determined separately for each of the diversity antennas in a sector because each may be receiving over a different path in a multipath environment. 
     It will also be clear to those in the art that the embodiment chosen as exemplary and about to be discussed, although practicable, is but one possible design choice among many and that other combinations of the disclosed elements may be employed without departing from the spirit of the invention. 
     Each antenna connects to an RF unit  1 , which converts the received signal to baseband. Analog-to-digital (A/D) converters  2  take 4-bit samples of the signals, at a rate of 8 times the PN chip rate (oversampling). In alternative embodiments, greater or lesser sampling rates could be employed. 
     Switch  3  processes samples from one antenna at a time. For the current antenna, precombining element  4 , under control of Control_Searcher  13 , stores four sequences of combinations of the four-bit samples into buffers  5 . In the present embodiment, the range of samples used corresponds to the duration of one Walsh symbol (256 PN chips). It is assumed that the samples are numbered  1 ,  2 ,  3 ,  4 ,  5 , . . . . For a sequence of samples in each of the I and Q sample streams: 
     Buffer_odd_I stores the sums of samples  3  and  7 ,  11  and  15 ,  19  and  23 , . . . ,  2043  and  2047  from the stream of I samples; 
     Buffer_odd_Q stores corresponding sums from the stream of Q samples; 
     Buffer_even_I stores the sums of samples  7  and  11 ,  15  and  19 ,  23  and  27 , . . . ,  2047  and  2051  from the stream of I samples; 
     Buffer_even_Q stores corresponding sums from the Q stream of samples. 
     The present embodiment contemplates oversampling for possible use of other portions of the receiver not discussed in conjunction with the present invention. For example, some portions of the receiver may rely on oversampling in order to adjust delay by increments considerably finer than one PN chip duration. The present embodiment uses only two samples per PN chip duration. 
     There are thus 256 stored sums in each buffer, each five bits in size since they are each the sums of two four-bit samples. Samples used in filling even buffers are inherently delayed one-half of a PN chip from samples used in filling odd buffers by virtue of being derived from samples taken half a chip time later. These special combinations of samples, working in conjunction with the interconnectivity of the buffers with the correlators, impart the ability to double the speed of signal processing with no loss in signal-to-noise ratio. 
     Correlators  6  correlate the “piece” of the received signal stored in buffers  5  against all the possible states, over the uncertainty region, of the PN code generators  10 . In the mobile station the Long Code is typically produced by a 42-bit LFSR of known configuration, and the PN I  and PN Q  codes by-15-bit LFSR&#39;s of known configurations. By means well known to those in the art, LFSR&#39;s of the same configurations may be included in the base station receiver, as may Initial_State_Mask  11 , and thus the Long Code and PN codes may be generated in the base station. Also by means well known to those in the art, the inputs LC+I and LC+Q to shift registers  8  and  9  are produced by adding successive bits of PN I  and PN Q  respectively to successive bits of LC in modulo-2 arithmetic. The bit sequences thus produced, being “local replicas” of the codes employed in the mobile station, are shifted serially into shift registers  8  and  9 , as shown in FIG.  2 . 
     FIG. 3 shows further detail of the present invention. In particular the correlators  6 , first shown in FIG. 2, are now shown in FIG. 3 as elements  6 - 1  and  6 - 2 , connoting correlators Z 1  and Z 2 , along with a generalized correlator element  6 -N schematically representing correlators Z 3 , Z 4 , Z 5 , . . . Z 32 . The present embodiment employs 32 correlators, although in alternative embodiments that number may be adjusted upward to improve performance or downward to enhance economy. 
     The number of correlators is double (32) the number of taps available from either of shift registers  8  or  9  (16 taps). Each pair of correlators (i.e., Z 1  and Z 2 ; Z 3  and Z 4 ; . . . Z 31  and Z 32 ) uses the same “local replicas” from shift registers  8  and  9 . Special connections of the pairs of correlators  6  with buffers  5  provide calculation of correlation integrals in such a way that correlation values from each pair of correlators Z 1  and Z 2 ; Z 3  and Z 4 ; . . . Z 31  and Z 32  are one-half PN chip apart. 
     Any clock rate may be used provided it does not exceed the capabilities of the circuitry employed. The present embodiment uses a clock rate of 19.66 MHz., which is 16 times the PN chip rate and which is within the capabilities of modern circuitry. 
     Also, further detail is shown of buffers  5 , shown in FIG. 3 as buffers  5 - 1  through  5 - 4 . Each of these has outputs  1  and  2 , although output  2  is used only on buffers  5 - 1  and  5 - 2 . Output  2  is delayed one PN chip time from output  1 . 
     Each of the correlators  6  has four inputs from the buffers, labeled I, I delay , Q, and Q delay . FIG. 3 shows detail of the interconnectivity of the buffers  5  and the correlators  6 . Each of correlators  6  also has an input from a particular tap on each of shift registers  8  and  9 ; it is seen that two correlators connect to corresponding taps; e.g., correlators Z 1  and Z 2  connect to tap  15  on the respective shift registers, correlators Z 3  and Z 4  (implicit in generalized element  6 -N) to tap  14 , etc. Because of the aforementioned delays, the correlators within a pair work with stored samples one-half a PN chip duration apart. Said delays are summarized in Table 1. 
     
       
         
               
               
               
             
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 INPUT 
                 DELAY (PN chips) 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Correlator Z1: 
                 I-input 
                 0 
               
               
                   
                 (Exemplary for 
                 I_input_delay 
                 1/2 
               
               
                   
                 odd-numbered 
                 Q_input 
                 0 
               
               
                   
                 correlators) 
                 Q_input_delay 
                 1/2 
               
               
                   
                 Correlator Z2: 
                 I_input 
                 1/2 
               
               
                   
                 (Exemplary for 
                 I_input_delay 
                 1 
               
               
                   
                 even-numbered 
                 Q_input 
                 1/2 
               
               
                   
                 correlators) 
                 Q_input_delay 
                 1 
               
               
                   
                   
               
             
          
         
       
     
     It is seen from Table 1 that Z 2  (and all the even-numbered correlators) have all inputs delayed one-half PN chip relative to the inputs to Z 1 . Thus the two correlation values produced by each pair of correlators are one-half PN chip duration apart. It is also seen that the aforementioned precombining of samples one-half PN chip duration apart facilitates obtaining correlation values with 1/2 PN chip resolution. 
     The “piece” of received signal stored in buffers  5  is to be correlated against segments of the local replicas over the uncertainty region to determine which one yields a significantly greater correlation value and thus to determine the delay. Each segment is 256 bits in length (to match the number of sample sums in each buffer), which in turn was chosen so as to cover one Walsh symbol period. The total number of segments used, for each of PN I  and PN Q  sequences, will be 512, equal to the size of the uncertainty region. The first segment used will start from the first bit position of the local replicas, and each of the 511 succeeding segments will start with the 511 next succeeding bit positions. Since the correlators work in pairs, each member of a pair working with data samples one-half a PN chip duration apart, the use of 512 segments results in 1024 correlation values, enabling the determination of the delay within half a PN chip duration. 
     FIG. 4 shows the logic functions performed within each of correlators  6 . The two I and the two Q inputs from buffers  5  each consist of five-bit samples, and each five-bit sample is multiplied, by multipliers  601 - 604 , by respective ones of the outputs of the taps from shift registers  8  and  9 . These multipliers, as well as other components of correlator  6 , are depicted schematically to indicate functionality. Detail of handling multiple bits is left as a design choice. 
     Pairs of the resultant five-bit products thus obtained are added as shown by adders  605  and  606  to produce six-bit sums. 256 such sums are integrated by each of integrators  607  and  608  as 256 bits of the local replica are clocked through shift registers  8  and  9 . The integral of 256 six-bit sums can be 14 bits in length. The integrals are then squared by elements  609  and  610  respectively; the squares are truncated to 15 bits in length, which is sufficiently precise for the present application. The two results from elements  609  and  610  are summed by element  611  to produce the 16-bit Z output for the particular correlator, which is one of 32 correlators producing Z 1  through Z 32 . 
     Referring again to FIG. 2, the correlator outputs are stored in Accumulator (ACC)  7 , seen to have 6144 sixteen-bit cells, equal to 1024 sixteen-bit cells for each of the six antennas of the present embodiment. It has thus far been shown how the first 32 cells for the current antenna were determined and loaded. It will now be shown how a similar process is performed an additional 31 times to complete the 1024 cells for one antenna. The setup of LC+I and LC+Q local replica data for each of the  32  “passes” is referred to as a “segment”. 
     Initially, the shift registers  8  and  9  (referring to FIG. 3) are loaded with the first 15 bits of the sequences from each of the PN code generators  10 . Denoting the bits of the LC+I and LC+Q PN sequences as bits  1 ,  2 ,  3 , etc., it is seen in FIG. 3 that correlators Z 1  and Z 2  are now presented with bit  1  (of the two sequences respectively, from tap  15  of shift registers  8  and  9  respectively), correlators Z 3  and Z 4  with bit  2 , and so on up through correlators Z 31  and Z 32  being presented with bit  16 . Shift registers  8  and  9  are then shifted (and the PN code generators are advanced) 256 times. Referring to Table 2 at the “First Pass” entry, it is seen that correlators Z 1  and Z 2  now correlate bits  1 - 256  against the 256 sums stored in each of buffers  5 , correlators Z 3  and Z 4  correlate bits  2 - 257 , and so on, up through correlators Z 31  and Z 32  correlating bits  16 - 271 . This completes the first pass and results in storing the first 32 correlator values (for the current antenna) in ACC  7 . 
     
       
         
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                 Bits 
                 Bits 
                   
                 Bits 
                 Leading 
               
               
                   
                 presented 
                 presented 
                   
                 presented 
                 bit in- 
               
               
                   
                 to CORR&#39;s 
                 to CORR&#39;s 
                   
                 to CORR&#39;s 
                 volved 
               
               
                   
                 Z1, Z2 
                 Z3, Z4 
                 . . . 
                 Z31, Z32 
                 in save 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 First Pass 
                  1-256 
                  2-257 
                 . . . 
                 16-271 
                 17 
               
               
                 (256 shifts with 
               
               
                 save after 16) 
               
               
                 (Restore) 
                  17-272 
                  18-273 
                 . . . 
                 32-287 
                 33 
               
               
                 Second Pass 
               
               
                 (Restore) 
                  33-288 
                  34-289 
                 . . . 
                 48-303 
                 49 
               
               
                 Third Pass 
               
               
                 . 
                 . 
                 . 
                   
                 . 
                 . 
               
               
                 . 
                 . 
                 . 
                   
                 . 
                 . 
               
               
                 . 
                 . 
                 . 
                   
                 . 
                 . 
               
               
                 (Restore) 
                 . 
                 . 
                   
                 . 
                 497  
               
               
                 Thirty-first 
                 . 
                 . 
                   
                 . 
               
               
                 Pass 
                 . 
                 . 
                   
                 . 
               
               
                 (Restore) 
                 497-752 
                 498-743 
                 . . . 
                 512-767  
                 xxx 
               
               
                 Thirty-second 
               
               
                 Pass 
               
               
                   
               
             
          
         
       
     
     After 16 shifts of each pass, state buffer  12  stores the states of shift registers  8  and  9  and the PN code generators. In the First Pass, the PN sequences are thus saved beginning with bit  17  of each, as shown in Table 2. (In the present embodiment, state buffer  12  consists of 102 bits— 42  for the LC generator,  15  for each of the PN generators, and 15 for each of shift registers  8  and  9 ). 
     Prior to each successive pass, shift registers  8  and  9  and the PN and LC code generators are restored from state buffer  12 . After the restore preparatory to the Second Pass, bit  17  of the respective PN sequences is the leading bit in shift registers  8  and  9  respectively. As shown in Table 2, the 256 shifts comprising the Second Pass present bits  17 - 272  to correlators Z 1  and Z 2 , and so on up through presenting bits  32 - 287  to correlators Z 31  and Z 32 . Saving in state buffer  12  after 16 shifts of the Second Pass stores bits from  33  on, which are restored preparatory to the Third Pass. 
     The net effect of the 32 passes is to present 32 bit sequences to each of the 32 correlators for a total of 1024 bit sequences (512 PN I  and 512 PN Q  sequences) presented to correlators, where each sequence consists of 256 consecutive bits, the first sequence begins with bit  1 , the second with bit  2 , and so on up through the 512th sequence beginning with the 512th bit. 1024 correlation values are thus stored in ACC  7 , the correlation values representing time steps of one-half a PN chip duration. The correlation values thus span 512 PN chip durations. The uncertainly region having been taken to be 512 PN chips, the entire uncertainty region is represented. 
     The correlator values may be examined as is well known in the art. FIG. 5 shows a graph of 1024 ACC contents for one antenna with a significant peak at the 400th entry; since the step-size in the present embodiment is one-half PN chip, it can thus be determined that the transmission delay is 200 PN chip times for this example. 
     FIG. 6 is a graph of a selected range of correlator values (positions  400  through  435 ) connoting delays corresponding to three received copies of the signal in a multipath environment. The relative increments of delay can be determined and, as is known in the art, can be used to configure the “fingers” in a “rake receiver” to optimize the quality of multipath reception. 
     The described embodiment, with its 32 correlators, 32 passes, and clock rate of 16 times the PN chip rate, is but one possible design choice for these parameters. It will be clear to those skilled in the art that an embodiment can be constructed having, for example, one-fourth the number of correlators but operating at a clock rate four times higher and with four times the number of passes, and that such an embodiment would exhibit the same overall performance as the discussed embodiment. The number of correlators could be increased to enhance performance or decreased to improve economy. Numerous other variations can be contemplated. 
     It will thus be seen that the invention efficiently attains the objects set forth above, among those made apparent from the preceding description. In particular, the invention provides a searcher for rapidly determining transmission delay. High speed may be achieved by using a clock rate many times higher than the PN chip rate of radio transmission, or by employing an arbitrarily large number of correlators and shift register stages. It is also seen that the searcher is relatively simple and inexpensive. Those skilled in the art will appreciate that the configurations depicted in FIGS. 1,  2 ,  3 , and  4  attain these objectives. 
     It will be understood that changes may be made in the above construction and in the foregoing sequences of operation without departing from the scope of the invention. It is accordingly intended that all matter contained in the above description or shown in the accompanying drawings be interpreted as illustrative rather than in a limiting sense. 
     It is also to be understood that the following claims are intended to cover all of the generic and specific features of the invention as described herein, and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween.