Abstract:
Digital signals transmitted on an RF carrier modulated in phase and amplitude and subject to noise constitute separate bursts each comprising information symbols of data and a pair of separated unique words. The signals are subjected to processing which involves reception of the signals and an initial conversion to approximate baseband and then analog to digital sampling. Quadrature and in phase samples are then stored in a buffer. The buffered samples are subjected to coarse timing, coarse frequency synchronization, a first phase correction, fine timing, further phase and amplitude correction and finally to fine frequency correction and subsequent reliability estimation.

Description:
FIELD OF THE INVENTION 
     This invention relates to the detection of short digital messages transmitted by radio, either terrestrial or relayed by satellite. More particularly the invention is directed to a novel method for effective synchronization and detection of short digital radio messages reliably under very noisy channel conditions. 
     BACKGROUND OF THE INVENTION 
     Traditional digital radio transmission techniques use a single channel per carrier where one channel is dedicated to each user, the user transmissions are typically long in duration. Synchronization techniques for such systems often rely on long term averaging in order to work reliably. With greater demand for spectral resources, time division multiple access (TDMA), where multiple users share the same channel in a time ordered fashion, is becoming common. A current example is TDMA cellular telephony standard, see Ref  7 , IS-54, TIA Interim Standard. With TDMA systems, the individual messages or bursts transmitted are often very short, so that very efficient and non-traditional synchronization techniques must be employed. 
     For short message transmission each burst typically includes a unique word, that is, a sequence of known bits or symbols, distributed in some manner throughout unknown data symbols making up the rest of the burst. The purpose of the unique word is to assist synchronization to the burst, in frequency, time, and phase. Synchronization in many current systems is also assisted through precompensation of the burst, so that uncertainty in time and frequency is limited to a small range. This precompensation information is obtained from feedback from the synchronization of previously transmitted bursts. This reduces the search range of the receiver synchronization circuitry, but does not preclude the necessity to perform fine synchronization for proper extraction of the data from the noise. It is with fine synchronization that the present invention is concerned. 
     Although forward error correction is employed to reduce the error rate, as lower power transmitters are deployed and radio channel environments become noisier, the raw channel bits become even less reliable before the forward error correction decoding is undertaken, and synchronization of the unique word becomes more crucial for synchronization. Furthermore for short bursts, the unique word length must be minimized to reduce the overhead (portion of the signal not carrying the data). A further constraint in mobile radios is that limited processing power and time is available. Thus, although greater demands are being placed on the synchronization techniques they still must be simple and practical enough to be implemented in a mobile terminal. 
     SUMMARY OF THE INVENTION 
     It is an object of this disclosure to provide a method, which is of relatively low complexity, for reliably synchronizing and detecting very short digital radio messages under very noisy channel conditions. 
     is a further object to provide a method for integrating synchronization, detection, and forward error correction decoding in such messages. 
     Here described is a multi-stage method for reliably detecting short digital messages. It assumes the message contains unique words, known at the receiver, and unknown data. The unique words are assumed to be multiple phase shift keying (MPSK) modulated, the preferred embodiment is binary phase shift keying (BPSK). The data portion of the burst may be MPSK modulated or multiple quadrature amplitude modulation (MQAM). The method described comprises a series of steps that produce successive refinements of the synchronization and detection process. 
     The method is implemented using a digital software receiver. That is, in the receiver, the received, modulated, RF signal is down-converted to an approximate complex baseband signal and then both in-phase and quadrature components are sampled by an analog to digital converter (A/D). The frequency uncertainty (the error in the down-conversion process) can be typically up to 10% of the symbol rate, beyond this the synchronization reliability decreases. The timing uncertainty can be any number of symbol periods but the synchronization reliability improves as the timing uncertainty decreases. 
     In the described method for more reliably detecting and decoding short digital messages received over a noisy channel, nine steps are preferred. The first step is to obtain initial frame synchronization for the received burst. The second to obtain an initial estimate of the carrier frequency error. The third is to correct this frequency error in the received samples. The fourth step is to obtain a refined timing estimate. The fifth step is to perform detection filtering, simultaneously correcting for the residual timing error and decimating to one sample per symbol. The sixth step is to estimate the phase and amplitude of the received burst and correct it. The seventh step is to obtain a refined frequency estimate and correct for it. The eighth step is to compute reliability estimates or, optionally, to make hard decisions for the individual bits defining each transmitted symbol. A ninth and optional step is to use the reliability estimates in a soft-input decoding algorithm. 
     In the process here described some of the steps are known in the prior art. 
     The first step of coarse timing (frame synchronization) is prior art, for example see, Ref. 1), R. A. Scholtz, “Frame Synchronization Techniques,” IEEE Trans. Commun., vol. COM-28, No. 8, Aug. 1980, pp. 1204-1213, which is included herein by reference. This step briefly comprises; differentially detecting the received signal over that time interval which potentially corresponds to the unique word (including the estimated uncertainty in this); correlating the result with the known differential unique word; and choosing the point of maximum correlation in the uncertainty window as the frame synchronization point. 
     The second step of coarse carrier frequency synchronization is also known in the prior art, for example, see Ref. 2), S. Crozier, “Theoretical and simulated performance for a novel frequency estimation technique,” Third Int. Mobile Satellite Conf., Jun. 16-18 th , 1993, Pasadena, Calif., pp.423-428, which is included herein by reference. The steps of this algorithm are, briefly: using the soft symbol estimates implied by the timing estimate of the first step, remove the modulation from the signal (such as by multiplying by the conjugate, if using multiple phase shift keying MPSK). With the derived pure carrier modulation-removed signal, compute the average phase-differential between successive symbols of the unique word. In the third step, improve this phase differential estimate by correcting the derived carrier frequency by the initial phase-differential estimate. The frequency estimate and correction provided by the second and third steps can be further improved by estimating the phase-differential over more than one symbol period. Crozier discusses details on determining the best delay spacing. 
     The fourth step of fine timing estimation also draws partly upon the prior art, for example, see Ref. 3), A. D. Whalen, Detection of Signals in Noise, San Diego: Academic Press, 1971 and also see Ref. 4), H. L. van Trees, Detection, Estimation and Modulation Theory, New York: John Wiley &amp; Sons, 1968, both of which are included herein by reference. These authors indicate that the maximum likelihood approach to obtaining the timing of a known signal is to correlate the noisy signal received with the known signal over the window of timing uncertainty. The time of peak correlation between the two corresponds to the optimum timing. 
     In this present disclosure, the known signal is the filtered unique word that is part of the transmitted burst, and correlation is performed in the discrete sample domain. The steps of this algorithm comprise: 
     i) perform a correlation at the timing given by the initial estimate of frame sync obtained from the first step above, and at one sample on either side of this; 
     ii) perform an interpolation between the magnitudes of the resulting correlations; and 
     iii) determine the time shift in terms of the offset (delay or advance) with respect to the coarse timing at which the interpolation peak occurs over the range of these three samples. 
     The preferred approach is to use a parabolic interpolation function. The timing error can then be corrected using a digital filter with a compensating timing offset. The preferred approach for the filter is to precompute a number of filters with relative fraction sample delays, e.g, 0, ¼,½,¾ (when using four fraction sample offsets), and select the one that most closely compensates the timing error. 
     Background to the sixth step of phase and amplitude estimation is described, for example, in Ref. 5), D. C. Rife and R. R. Boorsty, “Single-tone parameter estimation from discrete-time observations,” IEEE Trans. Inform. Theory, Vol. IT-20, No. 5, September 1974., which is included herein by reference. In this algorithm, once one has an estimate of the timing of the unique word, one removes the unique word modulation. The result is a single-tone to which the prior art can be applied directly. As is well known in the art, if the unique word is MPSK modulated, the modulation can be removed by multiplying by the complex conjugate of known symbols. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Embodiments of the invention will now be described with reference to the accompanying drawings, in which: 
     FIG. 1 is a schematic block diagram of a typical burst structure to which embodiments of the present invention can be applied; 
     FIG. 2 is a schematic block diagram of the steps embodied in the present invention; 
     FIG. 3 is a schematic block diagram of the fine frequency resolution step; 
     FIG. 4 is a schematic block diagram of the calculation of the reliability estimates for individual bits; 
     FIG. 5 is a schematic block diagram of a 16QAM constellation with preferred bit-mapping. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the novel method of processing received signal samples of a short digital radio transmission, an example of a typical transmitted burst structure  9  to which this method can be applied is shown in FIG.  1 . There is a data portion  10 ,  11 ,  12  plus two unique words  13 ,  14 , one at either end or close to the end. The unique word symbols may also be interleaved with the data symbols if desired. The symbols making up the unique words are known at the receiver but need not be the same, nor of the same length. For transmission, such a burst would have undergone modulation, filtering, frequency translation, and amplification. This description here assumes a linear modulation scheme but the method applies when distortion is present due to other transmission elements. This distortion may be unintentional or intentional, such as predistorting the symbol constellation before passing through nonlinear amplification. 
     The transmitted burst is received in a digital software receiver and the received burst is subjected to analog to digital conversion A/D. In a preferred embodiment, the RF signal is down-converted to an approximate complex baseband signal and then both in-phase and quadrature components sampled by the analog to digital converter. There are alternative approaches to obtaining the same result as those skilled in the art will appreciate, for example, using a single A/D to sample at a low IF and then down-converting to baseband in software. A preferred embodiment is to sample the received signal at four times the symbol rate of the modulation. The number of bits of A/D resolution required in any particular case depends upon i) the dynamic range of the signal, and ii) the degradation due to quantization noise that can be tolerated. 
     FIG. 2 shows a schematic block diagram of a preferred embodiment of the present invention, indicating the different processing steps to be performed. The input at  100  is the in-phase and quadrature baseband digitized samples of the received signal over the time interval of the duration of the burst plus any timing uncertainty. These samples are stored in buffer  200  to allow multiple processing passes. 
     The first step is to establish frame synchronization  210 . The frame synchronization algorithm is applied only to that portion of the samples in the buffer  200  corresponding to the position in the burst of the unique word symbols plus any timing uncertainty in the position. Frame synchronization is estimated using prior art, see Sholtz Ref. 1) as described above. 
     The frame synchronization is estimated by processing the sampled signal as follows: 
     Let x(nT) be samples of the complex received sequence after detection filtering, nominally, n=0, . . . , and T represents the spacing between samples. Normally one samples at multiple times the symbol rate; often, a good sampling rate is four times the symbol rate, i.e., T=T s /4 where T s  is the symbol period. Let c(mT), m=1, . . . ,N be noiseless samples of the known unique word. For the case shown in FIG. 1 where there is an initial  13  and final  14  unique word, this can be represented as {c(mT)}={c(T),c(2T), . . . c(N i ), 0,0,0 . . . 0, c(N-N f ),c(N-N f +1), . . . ,c(N)}, where N i  is the number of samples in the initial Unique Word, N f  is the number of samples in the final Unique Word, and the zeros are place holders for the unknown data between the unique words. In practice, one takes advantage of these zeros by not including them in the calculation. 
     The signal is first differentially detected by performing the calculation 
     
       
           y ( nT )= x ( n )* x (( n −4) T ) c   
       
     
     when four times over sampling has been performed, and (.) c  represents complex conjugation. A differential unique word is computed in the same manner to produce {c d (mT)}. The differential received sequence is then correlated with the differential unique word to form a frame sync sequence          f        (   nT   )       =            ∑     j   =   2     N                         y        (       (     n   +   j     )        T     )       *              c   d          (   jT   )       c                                     
     Frame sync is then obtained by comparing f(nT) to a threshold for different values of n and declaring frame sync whenever the threshold is exceeded. Alternatively, if the unique word is known to occur within a given time interval, choose the largest f(nT) in the given interval as the start of the unique word. This type of approach to frame sync has been described in Sholtz. 
     The output of the frame synchronization process is a reference sample number indicating the relative timing position  205  of the burst within the buffer  200  and also a set of buffered soft decisions  220  corresponding to the unique word symbols. 
     The second step of the method is to process the soft unique word symbols  220  according to the prior art, as represented by block  230 , (see Crozier Ref. 2), as described above, to produce a coarse frequency estimate  240 . 
     This initial coarse frequency estimate is obtained by processing the received samples as follows. Having obtained frame sync, one knows where the unique word symbols are in the received sequence. Without loss of generality, assume that the symbol estimates at the output of the differential detector, described above, y(n*T), y((n*+5)T), y((n*+9)T), . . . , correspond to noisy estimates of the differential unique word symbols c d (T), c d (5T), c d (9T), . . . where n* is the sample index corresponding to the estimated start of frame obtained from the first step. Then the following calculation          A                        jΔω                 T         ≈       ∑     j   =   0       N   -   2                           y        (       (       n   *     +     4      j       )        T     )       *            c   d          (       (     1   +     4      j       )        T     )                                  
     provides an estimate of the complex phasor defining the frequency difference between adjacent symbols. The frequency error Δω can be determined from the argument of the resulting phasor. This is a coarse estimate of the frequency error in the received signal. This approach has been described by Crozier. 
     The coarse frequency estimate  240  is used in the third step of the method to update the frequency of a digital oscillator  310 . The output of oscillator  310  is input to a multiplier  300 . The entire buffer of received samples is then fed out of  200  to multiplier  300 , the resultant frequency corrected samples (baseband frequency corrected) are stored in a buffer  400 . 
     The fourth step of the method is to obtain a fine timing estimate. This uses only the portion  405  of the coarse frequency corrected burst samples in the buffer  400  corresponding to the unique word samples. These samples are correlated with a locally stored filtered unique word matched to the transmitted unique word of interest in  405 . As is well known in the art, the correlator  410  can be embodied as a mixer (or multiplier), a waveform generator (or a stored waveform), and an integrator. The digital correlation  410  is performed at three different time offsets, the one indicated by the initial timing reference sample  205  and one sample on either side. This produces three correlation values  420 . A parabolic interpolation  430  is performed between the squared magnitudes of the three resulting correlation values. The location of the maximum of the interpolation function, over the range of the three samples, is determined. This location value is converted to a relative offset  435 , as a fraction of a sample period. This best value offset is used to select or compute a detection filter  500  into which the frequency corrected burst samples from buffer  400  are fed. 
     The calculations performed in this step are described in the following. Let x c (nT) represent the received samples after having been frequency corrected as described previously. If n* corresponds to the sample estimated to be the start of the frame, the following three correlations          p        (   jT   )       =            ∑     k   =   0     N                         x   c          (       (     j   +   k     )        T     )              c        (   kT   )       c                                     
     for j=n*−1, n*, n*+1, are then performed. The parabolic interpolation is performed through the three values: p((n*−1)T),p(n*T),p((n*+1)T). The location of parabola maximum in this range corresponds to the optimum timing estimate 
     The fifth step of the method is the filtering in filter  500  of the coarse frequency corrected sample from buffer  400  to reduce noise and interference. The filter is selected to compensate for the fractional sample offset (delay or advance) estimate  435  and thus correct the residual timing error after frame sync. The filtered output is down-sampled to one sample for each symbol in the burst, including the unique word symbols, to be used in subsequent steps, and stored in a buffer  510 . 
     The sixth step of the method is in  520  to estimate and correct for the phase and amplitude errors of all the symbols in the burst which have undergone coarse frequency and fine timing correction and as now stored in buffer  510 . This is done by removing the modulation from each unique word to produce a single tone. The phase and amplitude of each unique word is then estimated using the prior art, see Rife and Boorstyn Ref. 5) as described above, for discrete samples of a single tone. 
     Phase and amplitude estimates can be obtained by performing a correlation similar to that used for fine timing. These calculations are performed on the signal samples after fine timing correction. Let x cc (nT) be the signal samples after coarse frequency and fine timing correction. Then the correlation with the known unique word is performed.        P   =       ∑     j   =   1     N                         x   cc          (   jT   )              c        (   jT   )       c                                
     Then, the argument of the complex correlation P is an estimate of the phase error relative to the reference unique word c(kT). The magnitude of the complex correlation P is an estimate of the received signal amplitude, assuming the reference unique word is normalized to unit amplitude. This method is described in Rife and Boorstyn. Thus, in  520  the amplitude and phase corrections for the unique word samples in  510  are estimated. As further explanation of this step; the correlation with the known word is equivalent to multiplying by the conjugate, i.e., removing the modulation to produce a tone, and then summing. This tone is very low frequency and is consequently of almost constant phase over the duration of the unique word. Summing the samples of this very low-frequency tone produces a complex number. The magnitude of this complex number is a measure of the average amplitude over the duration of the unique word; the phase of this number provides an estimate of the average phase. 
     The amplitudes of the other symbol samples are then normalized using either the average or an interpolation of the amplitude estimates from the unique words. The phase of these symbol samples can be corrected using a linear interpolation of the phase estimates from the unique words. This phase correction can alternatively be included in the seventh step of fine frequency estimation to be described. Corrected samples in the sixth step are buffered in  520 . 
     The seventh step is fine frequency estimation at  530 , and is based on resolving any remaining frequency ambiguities. The preferred embodiment of this is illustrated in detail in FIG. 3, and is comprised of the following sub-steps: 
     a) from the phase estimates for the unique words  13  and  14  at either end of the burst found in the previous step at  520 , determine  531  the phase difference between the beginning and end unique words. 
     b) select  532  one of the possible frequencies in the acceptable range to produce this phase difference. These permissible frequencies are determined by the separation of the unique words and the phase difference found in a) ±2kπ, where k=0,∀1,∀2, . . . (i.e., is the set of integers positive and negative including zero over a range that covers the residual frequency uncertainty). 
     c) for the frequency estimate selected in b), frequency correct the samples stored in buffer  520  with a digital oscillator  533  and multiplier  534 . Make hard symbol decisions  535  on each unknown data symbol of the burst by choosing the closest symbol, and use the correct decision for each unique word symbol. As is well known in the art, when the burst amplitude is approximately normalized, making hard decisions on undistorted 16QAM symbols, for instance, can be embodied by comparisons of the in-phase and quadrature samples with the thresholds of 0 and ±2. In general, for any MQAM constellation (distorted or undistorted), compute the squared error  536  between the symbol decisions and the soft symbol samples, and store the result in a buffer  537 . In general, one can use all of the unique word symbols and, optionally, either all, some, or none of the data symbols in the burst when computing this squared error. The squaring process not only removes sign in the error figures but also provides optimum weighting when summed. The contribution of the unique word portion and the data symbol portion to the sum of squared errors may be weighted differently to reflect the confidence in the decisions depending on whether it relates to the unique word or to data and on its relative position within the burst. Low signal to noise ratio will, for instance, reduce confidence level. 
     d) iterate  538  steps b) and c) for all frequency ambiguities in the acceptable range. 
     e) determine  539  the frequency ambiguity corresponding to the smallest sum of the squared errors for each interaction of b) and c). Frequency correct the soft symbol samples from buffer  520  for this residual frequency error using a digital oscillator  543  and multiplier  541 . Alternatively, the versions of frequency corrected bursts obtained in step c) above, could be stored and the appropriate version selected. 
     f) store the fine frequency corrected symbol samples from  520  in buffer  542 . 
     The eighth step of the present process, as shown in FIG. 2, is to compute approximate reliability estimates and provide improved soft decisions for the bits for the data symbols. In FIG. 4 the computation of the reliability estimate for a particular bit associated with a soft symbol s is illustrated in detail. This step is based on the fact that each MQAM symbol (and specifically 16QAM) has both a binary representation, e.g., 1101, and graphically a constellation point representation, e.g. (+3,−3). A preferred mapping between the binary representations and the constellation points for 16QAM is shown in FIG.  5 . There the first two binary digits signify the in-phase coordinate and the second two signify the quadrature coordinate. The process for the eighth step is comprised of the following sub-steps; 
     a) determine  555  those eight 16QAM constellation points with a “0” in the first bit of the corresponding binary representation, i.e., having the binary representation “0xxx” where x is either 0 or 1. 
     b) for the soft symbol s, compute  557  for each of those eight constellation points in step a) the square of the distance from s. 
     c) determine  560  the first minimum of the squared distances. 
     d) determine  555  those eight 16QAM constellation points with a “1” in the first bit of the corresponding binary representation, i.e., having the binary representation “1xxx”. 
     e) for the soft symbol s compute  558  for each of those eight constellation points in step 
     d) the square of the distance from s. 
     f) determine  561  the second minimum of these last mentioned squared distances. 
     g) determine the difference  565  between the first minimum and the second minimum and store this in buffer  570  as the reliability estimate for the first bit in s. The squaring process in b) and e) not only removes sign but also provides optimum weighting in step g). 
     h) iterate  575 ,  550  steps a) to g) for the second, third, and fourth bit positions and store in buffer  570  as the reliability estimates for the second, third and fourth bits in s. 
     i) iterate  580 ,  540  steps a) to h) inclusive for each soft symbol sample. 
     The eighth step can be simplified with correlations and table lookups for the squared symbol powers to correct/convert to squared distances. Table lookups can also be used for each of the constellation points and their binary subsets. This eighth step assumes that the phase and amplitude of the symbol samples have been approximately normalized in the sixth step to the assumed constellation point scaling. The reliability estimates in the buffer  570  must be ordered to correspond to the transmitted bits. Those skilled in the art will appreciate that the eighth step can be generalized to both distorted and undistorted MQAM constellations including, for example, MPSK constellations. There are a number of ways of doing table lookup, for example, one way is for each symbol to compute the squared distances to each constellation value and store these values in a table. Then for each bit in the table instead of having to compute the squared distances they can be looked up in the table. Another way is to discretize the two dimensional space using a grid pattern, e.g. a 16×16 grid producing 256 grid points, i.e. with much finer resolution than the true constellation points. Then for each symbol value one would determine which grid point was closest. Then a predefined table would map grid points to approximate reliability values for all the bits in the symbol. 
     An optional final step  600  in FIG. 2, is to perform further processing of the soft bit decisions obtained at  570 . An example of such further processing is a forward error correction decoding scheme. An example of such is the Viterbi algorithm where the soft bit decisions are used to determine a metric for all possible received sequences or partial sequences, discard those that are improbable, and determine the bit sequence that was most likely to have been transmitted. This is described in Ref 6), S. Lin and D. J. Costello, Jr., Error Control Coding—Fundamentals and Applications, Englewood Cliffs, N.J.: Prentice Hall, 1983. Another example is the Turbo decoding algorithm as described in Ref. 8) C. Berrou, “Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder,” U.S. Pat. No. 5,446,747, 1995. Both references described above are included herein by reference. 
     Having described preferred specific embodiments of the invention, the subject matter of the invention in which we claim protection by patent is set forth in the following claims. 
     References 
     1) R. A. Scholtz, “Frame Synchronization Techniques,” IEEE Trans. Commun., vol. COM-28, No. 8, Aug. 1980, pp.1204-1213. 
     2) S. Crozier, “Theoretical and simulated performance for a novel frequency estimation technique,” Third Int. Mobile Satellite Conf, Jun. 16-18  th , 1993, Pasadena, Calif., pp.423-428. 
     3) A. D. Whalen, Detection of Signals in Noise, San Diego: Academic Press, 1971. 
     4) H. L. van Trees, Detection, Estimation and Modulation Theory, New York: John Wiley &amp; Sons, 1968. 
     5) D. C. Rife and R. R. Boorstyn, “Single-Tone Parameter Estimation from Discrete-Time Observations,” IEEE Trans. Inform. Theory, Vol. IT-20, No.5, September 1974. 
     6) S. Lin and D. J. Costello, Jr., Error Control Coding—Fundamentals and Applications, Englewood Cliffs, N.J.: Prentice Hall, 1983. 
     7) IS-54, TIA Interim Standard. 
     8) C. Berrou, “Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder,” U.S. Pat. No. 5,446,747, 1995.