Abstract:
A method of demodulation is provided for demodulating a signal in which different data symbols are represented by different frequencies, such as a modem. A set of undelayed and a set of delayed sample values are provided and a frequency transform calculation is performed on the difference between the first N undelayed values and the last N delayed values. An early/late synchronization decision is taken dependent on the difference value.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to a method of demodulation of a signal in which different data symbols are represented by different frequencies. The method is suitable for fast symbol synchronisation in modems. This method is particularly applicable to U.S. Federal Standard 1045 and Military Standard 188-141A. 
     SUMMARY OF THE PRIOR ART 
     One of the most popular methods of symbol synchronisation in modems is the advance/retard algorithm, otherwise referred to as an early-late gate. The algorithm is described in many publications such as the book &#34;Digital Communications&#34; by Proakis, and is summarised here with reference to FIG. 1. 
     The signal is sampled at a rate of, for example, 64 samples per symbol. The aim of the algorithm is to align the 64 samples accurately on the symbol. The samples in the time domain are transformed by means of fast Fourier transform into the frequency domain, providing frequency components of different magnitudes, as shown in FIG. 2. The symbol represented by the signal is indicated by the strongest frequency component (010 in this example). This frequency domain value is a result of an accumulation of all the components of the transform in the time domain. Referring to the accumulation as being accumulation A, a delay of delta is introduced to the sampling and the operation is repeated for a second set of 64 samples, providing a different result, referred to as accumulation B. The delay delta may be, for example, 1-4 samples. These two very close accumulations in what may be referred to as different matched filters reveal whether the synchronisation is early or late. If the level of the relevant component in the frequency domain in accumulation B is greater than in accumulation A, synchronisation is assumed to be early and an advance command may be given. On the other hand, if the result in B is smaller than in A, synchronisation is assumed to be late and a retard command may be given. An advance or retard command causes sampling to be advanced or retarded by a predetermined amount, e.g. 1-4 samples. 
     The above basic synchronisation algorithm calls for a very large amount of processing. Fourier transforms should be calculated twice, each transform requiring many multiplication operations. Multiplication operations place a heavy burden on the processing capacity. Such a synchronization algorithm is possible in digital signal processors specially designed for fast multiplications/additions. Digital signal processors are between 5 to 10 times more expensive than general purpose microprocessors. For slow data rates such powerful signal processors may be omitted. It would be desirable to provide a synchronisation algorithm that is more efficient and enables slower processors to be used to achieve the synchronisation. 
     The invention may also be used in digital signal processors in order to increase efficiency and symbol rate upper limit. 
     SUMMARY OF THE INVENTION 
     According to the present invention, there is provided a method of demodulation of a signal in which different data symbols are represented by different frequencies, comprising the steps of: 
     sampling the signal at a predetermined number of sampling points to provide a set of undelayed values 
     delaying the sampling by N samples to provide a set of delayed values; and 
     deriving a difference value for the frequency content of the delayed and undelayed values, whereby the difference value is indicative of early or late synchronisation, characterised by 
     performing a transform calculation on the difference between the first N undelayed values and the last N delayed values to provide the difference value. 
     If N=4, there are only 4 difference values on which Fourier transforms need to be calculated in order to implement the early-late gate (it is still necessary to convert one set of samples to the frequency domain in order to demodulate the signal and determine the symbol represented). 
     The method of the invention may be visualised by rotating the last 4 samples of accumulation B to the front of accumulation B and performing a subtraction operation between the accumulations A and B, whereby the remaining 60 samples which are identical in each accumulation cancel each other out. In a preferred embodiment, the actual samples in one of the sets are rotated in order by N positions such that the first N undelayed values and the last N delayed values correspond in position in the sets. This is carried out by suitable manipulation of the memory addresses of the various samples in microprocessor memory. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram of a typical signal for demodulation in the modem (noise not included for purposes of clarity). 
     FIG. 2 is a frequency domain representation of the Fourier components of the signal of FIG. 1. 
     FIG. 3 is a diagram illustrating operation of the invention in a microprocessor. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     As for the prior art method, one bit length of the signal of FIG. 1 is sampled a predetermined number of times M (e.g. 64 times) and the frequency domain values such as those shown in FIG. 2 are calculated by discrete Fourier transform (DFT) in software, e.g. by fast Fourier transform (FFT). A second set of M samples is also taken in matched filter B, after a delay indicated as delta. The delay is equivalent to a predetermined number of samples N, e.g. 4 samples. There is no need to calculate the equivalent values for matched filter B, since the result can be derived in an easier way as shown by the following explanation. 
     The sample points of filter B are rearranged from their initial state: 
     
         &#34;A&#34;a.sub.0, a.sub.1, . . . , a.sub.N-1, a.sub.N, . . . , a.sub.M-1 
    
     
         &#34;B&#34;a.sub.N, a.sub.N+1, . . . a.sub.M+N-1 
    
     to a different cyclic state: 
     
         &#34;A&#34;a.sub.0, a.sub.1, . . . , a.sub.N-1, a.sub.N, a.sub.M-1 
    
     
         &#34;B&#34;a.sub.M, a.sub.M+1, . . . a.sub.M+N-1, a.sub.N, . . . a.sub.M-1. 
    
     This change will alter the phase component of the Fourier transform but not its absolute value. 
     In the specific case where M=64 and N=4, the result is: 
     
         &#34;A&#34;a.sub.0, a.sub.1, . . . , a.sub.3, a.sub.4, . . . , a.sub.63 
    
     
         &#34;B&#34;a.sub.64, a.sub.65, . . . , a.sub.67, a.sub.4, . . . , a.sub.63. 
    
     The samples of accumulator B are simply subtracted from the samples of corresponding position in accumulator A. As a result, there are only N non-zero difference values. In the specific example, these are: 
     
         a.sub.0 -a.sub.64, a.sub.1 -a.sub.65, a.sub.2 -a.sub.66 and a.sub.3 -a.sub.67 
    
     Discrete Fourier transforms are calculated for these N difference values. The additional M-N values are zero and may be omitted. The result has real and imaginary parts. Each part should be added to the corresponding part of the non-delayed DFT result to provide a new value (frequency component). If the frequency component for the symbol in question (already determined as having the strongest component from the DFT results for accumulator a alone) is positive, then synchronisation is assumed to be late, whereas if it is negative, synchronisation is assumed to be early. 
     A general proof of the theory of the invention is as follows. Let it be supposed that the DFT results according to the prior art method are A f1 , . . . A f8  and B f1 , . . . B f8 . For synchronization purposes we have to find whether A q  is higher or lower, with respect to B q , where q is the frequency already determined as having the strongest component. 
     
         B.sub.q =DFT.sub.q {a.sub.N a.sub.N+1, . . . a.sub.M, a.sub.M+1, . . . , a.sub.M+N-1 } 
    
     Referring only to the absolute value, we can say: 
     
         B.sub.q =DFT.sub.q {a.sub.M, a.sub.M+1, . . . a.sub.M+N-1, a.sub.N, a.sub.N+1, . . . ,a.sub.M-1 } 
    
     
         =DFT.sub.q {a.sub.M, a.sub.M+1, . . . a.sub.M+N-1, a.sub.N, a.sub.N+1. . . a.sub.M-1 } 
    
     
         +DFT.sub.q {a.sub.0, a.sub.1. . . a.sub.M-1 }-DFT.sub.q {a.sub.0, a.sub.1. . . a.sub.M-1 } 
    
     because of linearity we can combine the first two of these terms to write the same expression as: ##EQU1## 
     The last part is already known from the first DFT. The first part is mostly zero and can be derived easily in a DFT/FFT algorithm much faster than DFT/FFT with non-zero elements. 
     For one sample difference, for instance, there is no need to make any multiplications at all, just add a N  -a 0  to the real part of the FFT of &#34;A&#34; and recheck absolute values. For N&gt;1 there is a need for a few multiplications. 
     The result should have better accuracy since mathematical manipulations are done only on the differences. 
     The implementation of the algorithm in a microprocessor is illustrated in FIG. 3. In this figure there is shown a microprocessor 10, having an A/D converter 11, memory locations 12, 13 and 14 and an arithmetic and logic unit (ALU) 15. 
     The incoming analog signal is sampled by the A/D converter 11 at a rate of 2400 samples per second. These samples are stored in memory location 12. In memory location 13, the addresses of samples a 0 . . . a M-1  are stored, as are the addresses of samples b 0 . . . b M-1 . Arithmetic and logic unit 15 recalls the data from addresses a 0 . . . a M-1  in memory location 12 and performs the DFT calculation to determine the received symbol. This symbol is stored in memory location 14 and is available as an output. ALU 15 then causes the addresses b 0 . . . b M1  to be rotated in memory location 13. The samples identified by the new pairs of addresses A and B are again recalled from memory location 12 and a difference value is calculated in ALU 15. For each pair of samples, this value is temporarily stored in memory location 14. From these stored difference values, a DFT calculation is performed as described above and an early/late decision is carried out by ALU 15. In response to this decision, the addresses a 0  etc. of the data from memory location 12 are advanced or retarded for the next symbol. 
     In an alternative example, the incoming signal comprises symbols of 8 millisec length and is sampled at a rate of 8 kbits/sec. 
     The number of samples of the delay, N, may be any number from 1 to half of the number of samples in a symbol--i.e. in the above case N may be between 1 and 32. It is preferred that N lies in the range of 1 to 8.