Patent Publication Number: US-6668012-B1

Title: Identification of an identifiable code sequence in a received signal by correlation with summed different-phase replicas of the sequence

Description:
FIELD OF THE INVENTION 
     This invention relates to acquisition of control or other information signals which included an identifiable code sequence such as a direct spreading sequence. 
     BACKGROUND OF THE INVENTION 
     It is often necessary to detect, acquire, and track the frequency and time of a received direct-sequence spread-spectrum (DS/SS) signal or of a unique-word message preamble in order to reliably de-spread andor demodulate the received signal. In direct-sequence spread-spectrum, the transmitted information bits are multiplied or spread by a high rate pseudorandom (PN) spreading sequence. 
     In many DS/SS systems, detection and acquisition of received signal timing and frequency is difficult because the signal energy is well below the associated noise level. In code-division multiple access systems in which multiple users access the same frequency bandwidth by use of different spreading codes having advantageous cross-correlation properties, the noise contribution from the codes of the other users adds to the thermal noise to exacerbate the detection and acquisition problem. 
     ordinary prior-art approaches to the acquisition problem are based mainly on correlation or matched filtering operations performed on the received signal, variants of which are termed sliding correlation, serial search, and recursion aided sequential estimation. In the presence of a signal, many of these techniques ultimately generate a signal correlation or autocorrelation function, the peak of which should indicate signal timing. However, the noise and other interferences associated with the signal may make determination of the correlation peak difficult. Frequency errors or cumulative phase errors between the information carrier and the local frequency will tend to decrease the magnitude and increase the spread of the peak correlation. 
     A standard technique for acquisition of signals in the presence of frequency errors or frequency shifts is to use frequency bin searching, either by use of a plurality of correlators operating in parallel, one for each frequency of the received signal, or by searching frequency serially, or both. The use of one correlator for each possible frequency requires a great deal of hardware (or equivalent software), but provides fast acquisition. Serial searching of the frequencies requires only one correlator, but may require significant time to complete a search, especially considering that each attempted correlation may take as long as the recurrence period of the spreading code. Thus, there is a tradeoff between speed and complexity; two correlators could be used in parallel to search using various different frequency hypotheses, thereby presumably cutting the search time in half (by comparison with a single comparator using serial search) by a doubling of the complexity of the equipment. 
     Correlation or filtering is well known, and can be implemented by many techniques, as for example by Finite Impulse Filters (FIR) or by use of Fast Fourier Transforms (FFT). 
     Improved techniques for determination of the presence of spread-spectrum signals, or of the frequency andor time of spread-spectrum signals, is desired. 
     SUMMARY OF THE INVENTION 
     A method according to the invention is for acquisition, which may be in the presence of Doppler shift, of a received message with at least a preamble encoded by a pseudorandom spreading code or other identifiable code sequence. The method includes the step of generating a plurality of different phases of the spreading code. The different phases of the spreading code may be stored in memory for later use, if desired. A plurality of the different phases of the spreading code are summed together or linearly superposed, to thereby produce summed PRN code signals. If desired, the summed PRN code signals may be stored for later use, together with (or instead of) the different phases of the spreading code. The incoming spreading code is correlated with the summed PRN code signals, to thereby generate a cross-correlation signal. The cross-correlation signal indicates whether (or if) the desired phase is among those phases in the summed PRN code signals. If the cross-correlation signal indicates that the desired phase is among those phases in the summed PRN code signals, individual cross-correlations are performed between the incoming spreading code and those of the phases of the spreading code which make up the summed PRN code signals. This identifies the particular phase of the spreading (or other identifiable) code by which the message should be decoded. 
     A particularly advantageous mode of the method according to the invention includes the further step, after the correlating step, of determining if (a) the cross-correlation signal indicates that the desired phase is among those phases in the summed PRN code signals and (b) the number of different phases in the summed PRN code signals exceeds a particular number, and if both conditions exist, dividing the summed PRN code signals into at least two portions, each having fewer different phases than the particular number, and performing the step of correlating the incoming spreading code with at least one of the portions. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     FIG. 1 is a simplified block diagram of an embodiment of the invention; and 
     FIG. 2 is a simplified flow chart or graph illustrating the logic flow of the processor of FIG.  1 . 
    
    
     DESCRIPTION OF THE INVENTION 
     In FIG. 1, a receiver designated generally as  10  is intended to receive and decode or demodulate a message from a remote source, which is encoded with a recurrent pseudorandom spreading sequence or code, or which includes a unique- or identifiable-word header code. Receiver  10  includes an antenna  12 . Signal received by antenna  12  is applied to a receiver illustrated as a block  14 , which performs ordinary receiver functions, such as, for example, low-noise amplification, filtering, and frequency downconversion, so as to enable further processing. The signals processed by receiver  14  are applied over a signal path illustrated as  16 , in parallel (or in common) to a bank or array  18  of a plurality, illustrated as being three in number, of multipliers  18   a ,  18   b , and  18   c . Multipliers  18   a ,  18   b , and  18   c  also receive individual signals at their input ports from a memory arrangement, illustrated as a memory  30 . 
     According to an aspect of the invention, memory  30  is preprogrammed with summed sequences of the spreading or header code, differing from each other in phase. Suppose that the spreading code for a spread-spectrum transmission is a sequence of 1024 chips, so that each bit or symbol of the message is encoded with a 1024-chip code. In order to properly decode or demodulate the message bits, the 1024-chip decoding sequence must be in-phase with the received sequence. Since there are 1024 chips in the spreading sequence, there are 1024 possible phase conditions which the received sequence can assume relative to the local sequence, and only one of those sequences is the correct sequence, which will properly decode the message sequence. The remaining 1023 possible phase conditions are out-of-phase and will not properly decode the message sequence. Since there is no a priori synchronization between the local sequence and the received sequence, it is very unlikely that the local decoding sequence will be in the phase for correct decoding of the message. 
     In one possible arrangement, memory  30  may include a memory  20  which is preprogrammed with a plurality, as for example 1024, of spreading codes, each of different phase, which is to say that each code sequence is offset in time by one chip relative the previous and the following code sequences. Thus, memory  20  will have 1024 output ports, one for each phase (φ) of the sequence. As illustrated in FIG. 1, the outputs of memory  20  include phases φ 1 , φ 2 , φ 3 , φ 4 , φ 5 , φ 6 , φ 7 , . . . , φ 1022 , φ 1023 , and φ 1024  of the sequence. As illustrated within block  30  of FIG. 1, a set  22  of adders or summing circuits is connected to the output ports of memory  20 . Each adder  22   a ,  22   b , . . . ,  22   c  of set  22  of adders is illustrated as having four input ports, which are connected to the output ports of memory  20  in contiguous sets of four. Thus, summing circuit  22   a  is connected to phases φ 1 , φ 2 , φ 3 , and φ 4  of memory  20 , summing circuit  22   b  is connected to phases φ 5 , φ 6 , φ 7 , and to one additional phase which is not illustrated. Similarly, summing circuit  22   c  has its four input ports connected to the output ports of memory  20  associated with phases φ 1022 , φ 1023 , and φ 1024 , and with an additional phase (not illustrated). Thus, for four-input-port adders and for a sequence of 1024 chips, there will be a total of 256 adders in set  22 , and the output sum of each adder represents the superposition or sum of four of the phase-offset codes. More particularly, the output of adder  22   a  represents the sum of phases φ 1-4 , the output of adder  22   b  represents the sum of phases φ 5-8  . . . , and the output of adder  22   c  represents the sum of phases φ 1021-1024 . While each adder of set  22  has been described as summing the code sequence of four contiguous phases, there is no absolute requirement that the phases be contiguous, but they may instead be randomly selected (although not duplicated). The set  22  of adders in conjunction with multiphase code memory  20  provides the same effect as overall memory  30 , which is to produce sums of various different phases of the known spreading code or unique word. 
     According to an aspect of the invention, the received message, including the received sequence which is to be synchronized to, is correlated in the multipliers or correlators of set  18  with the summed signals from memory  30  (or equivalently from the summing circuits of set  22 ). More particularly, multiplier  18   a  receives the received signal over path  16  and the sum of phases φ 1-4 , multiplier  18   b  receives the received signal over path  16  and the sum of phases φ 5-8 , . . . , and multiplier  18   c  receives the received signal over path  16  and the sum of phases φ 1021-1024 . Since, for a 1024-chip spreading or unique-word code, there are 256 four-input adders in set  22 , and there is one multiplier in set  18  for each adder in set  22 , there are 256 multipliers in set  18 . Different numbers of inputs of the adders, or a different-length codeword, will change the requisite number of multiplier elements. Since the received signal has the spreading or unique-word code in only one phase, the correlations of the received signal with most of the sums will not result in any indication of correlation at the outputs of the multipliers (although there may be various partial correlations). However, the sum signal applied to one of the multipliers will be in-phase with the received signal, and that particular multiplier will produce a strong indication of correlation. Those skilled in the art know that the correlation of a binary word of 1024 chips or bits length results, in principle, in a peak output word at maximum correlation which has a value of 1024. In this particular case, there are three other “random” or uncorrelated signals present together with the one which is in-phase with the received signal. These additional words add a noise floor on which the desired correlation is superposed. Thus, it is conceptually simple to determine that one of the sums in which the phase of one of the plural different-phase versions of the “local” code occurs, because it is the only one which is likely to display a peak value in excess of a given value. The noise level and the magnitudes of stray peaks will depend on cross-correlation properties of the set of out-of-phase codes. 
     Processor  26  of FIG. 1 examines the correlations from each of the correlators of set  18 , and determines the presence of the correct phase at the output of one of the summing circuits. This may be accomplished in a variety of ways, all of which are embodiments of the present invention. For example, the correlation value with largest magnitude may be used to determine the presence of the correct phase. In another embodiment, determination of the correct phase may be made only if the re-correlation is performed until the threshold is exceeded. Other embodiments are apparent to those with ordinary skill in the art. In any case, the presence of the correct phase at the output of one of the summing circuits is determined (with high probability). However, this knowledge narrows the field in which the correct phase is to be found, but does not identify that one of the phases which is in-phase with the received code. More particularly, in the example in which the code sequence has 1024 chips and the summers  22  produce sums of four sequences, the field is narrowed from 1024 to four. According to an aspect of the invention, those code sums which are deemed not to contain the desired phase of the code are discarded for the current determination, and the remaining sum (or sums, in some cases) are split into portions, so that each sum contains less than the number of phases of code than it previously contained, and the correlation is performed again. In some cases, the received signal may include a repetition of the unique word or the spreading code, so that the next correlation can be performed on a newly received signal. In other cases, it may be necessary to store the header or preamble of the received signal, and to use the stored information repeatedly to obtain the desired information. However accomplished, the received signal is again correlated with the sum, which now represents fewer different phases of the code. Processor  26  again evaluates the results of the correlation, and determines, among the remaining sums, which ones do not contain the desired phase of code, and identifies that one (or those, in some cases) which contain the code. The process is repeated, until the number of different versions or phases of code in the sum containing the correct version is small enough so that they may efficiently be individually correlated with the received signal. When the particular one of the spreading or unique-word codes is identified, it is then used to perform the decoding of the received message. 
     FIG. 2 is a simplified flow chart or graph illustrating the operation of the processor  26  of FIG. 1 in performing the method of the invention. Before describing the logic flow, it should be understood that in a preferred embodiment of the invention, memory  30  is preloaded with the various sums of different phases of the spreading or unique-word code, so no actual logic (such as set  22  of summers) is required to generate the sums. All that is necessary is to specify which of the stored sums is (are) to be presented for correlation. In FIG. 1, the logic starts at a START block  210 , and flows to a further block  212 , which represents cross-correlation of the received sequence with the memorized sums at stage i, which for the first iteration is unity. From block  212 , the logic flows to a decision block  214 , which determines if one of the sums exhibits significant cross-correlation. If not, the logic flows from the NO output of decision block  214 , by way of a logic path  216 , back to a block  218 , which resets i to equal unity. If one (or more) of the sums exhibits significant correlation, the logic leaves decision block  214  by the YES output, and arrives at a further decision block  220 . Decision block  220  determines if the sum in which correlation was found contains only one phase. If so, the logic leaves decision block  220  by the YES output, and arrives at a FINISHED block  222 . The desired phase is the one in the current sum. 
     On the other hand, if the sum in which decision block  220  of FIG. 2 found significant correlation contains more than one phase of the spreading or unique-word code, the logic leaves decision block  220  by the NO output, and proceeds to a block  224 . Block  224  represents the incrementing of index i to (i+1). From block  224 , the logic flows to a further block  226 , which represents the commanding of memory  30  (FIG. 1) to output a new set of sums. This new set of sums is selected from that one set (or possibly a plurality of sets) which exhibited correlation, and so the new set of sums must presumably contain the desired-phase sequence. The (i+1) th  set of sums includes fewer individual phases of the code than the i th  set, and therefore each sum contains fewer different-phase codes. From logic block  226 , the logic of FIG. 2 flows by way of a logic path  228  back to block  212 , to begin another iteration. The iterations continue until, eventually, the remaining sum contains only a single phase, at which time decision block  220  directs the logic to FINISHED block  222 . The desired phase is the one identified by decision block  220 . As mentioned above, this phase can then be read from memory  30  (FIG. 1) and applied for decoding of the spreading sequence or identification of the timing of a unique word. 
     Other embodiments of the invention will be apparent to those skilled in the art. For example, while the signal has been illustrated as received by an antenna, other transducers may be used, such as photodiodes, particle detectors, and the like. While a single memory  20  has been illustrated as containing all of the summed codes, individual memories could be used, or the memory (not illustrated) of processor  22  could be used to store the summed codes. As mentioned, each adder of set  22  has been described as summing the code sequence of four contiguous phases, but there is no absolute requirement that the phases be contiguous, but they may instead be randomly selected (although not duplicated). Similarly, there is no particular reason that the summers of set  22  each sums four sequences, increasing the number of sequences summed in each adder reduces the total number of adders required for a given code length, but results in a larger number of codes in each sum, which may require more iterations to identify the desired phase. 
     Other embodiments of the basic invention could include techniques for dealing with unknown frequency shifts in the received signal, as caused by Doppler shift, for example. Standard techniques such as serial and/or parallel correlations over multiple frequency bins may be employed in such cases, as is apparent to those with ordinary skill in the art. 
     Thus, a receiver ( 10 ) for a unique word sequence or a spreading code sequence includes a memory ( 30 ) which is preloaded with all possible phases of the code. The sequence in the received signal (on signal path  16 ) is correlated, in parallel (in correlation set  18 ), with sums of various ones of the different phases of the code. Thus, the received code is correlated with all possible phases of a replica of its own code. Consequently, one of the sums will exhibit a correlation peak, which indicates that the desired phase of the code is included in that particular sum. The other sums will not exhibit a correlation peak, and are discarded. The different phases in the one sum which displayed correlation are divided into new sums, each having fewer phases, and the correlation is again performed. Again, those sums exhibiting no correlation are discarded, and the sum exhibiting correlation is divided into sums of fewer codes. The process in continue until that one of the sums exhibiting correlation contains only one phase of the code, and it is perforce the one with the desired phase. The in-phase code is used to decode the received code. 
     Yet another embodiment of the invention may be apparent to those skilled in the art. will not be synchronous relative to the chip In many real-world systems, the received signal boundaries. Thus, in order to ensure that adequate correlation peaks are attained, one may correlate with all phases of the spreading code offset by one-half of the chip duration. Finer offsets may also be employed if desired.