EP0827655B1 - Method and apparatus for joint frequency offset and timing estimation of a multicarrier modulation system - Google Patents

Description

Field of the Invention

This invention relates generally to transmitting and receiving multicarriermodulated signals. In particular, the invention provides a system and method for estimating andcorrecting any frequency offset and timing mismatch at the receiver, prior to demodulating thereceived signal.

Background of the Invention

In many signal transmission applications, such as television, radio, andtelephony, digital signal schemes are becoming the preferred choice over the traditional analogschemes. For example, Digital Audio Broadcast ("DAB") is a digital system used in Europe forthe transmission and reception of radio signals. One digital signal scheme with which the presentinvention is concerned, involves the transmission of information over multiple frequencies,referred to as multicarrier transmission schemes. These multiple frequencies are combined into asingle signal for transmission in a process referred to as modulation, and are separated at thereceiver for retrieving the information carried by the individual frequencies, in a process referredto as demodulation. The combination of these processes are known as Multicarrier Modulation("MCM").

In MCM schemes, also known in the literature as Orthogonal FrequencyDivision Multiplexing (OFDM), a stream of symbols to be transmitted is divided into blocks ofdata symbols. Each block of data symbols is transformed into another block of symbols by takingthe inverse Fast Fourier Transform ("IFFT"). It is this new block of symbols that is actuallytransmitted. MCM has been studied in the context of telephone modems and most recently as anefficient modulation scheme for DAB. A more detailed description of the general principles ofMCM can be found in John A.C. Bingham,Multicarrier Modulation for Data Transmission:.AnIdea Whose Time Has Come, IEEE Communications Magazine, pp. 5-14 (May 1990).

Two important criteria for effective use of multicarrier digital signal systemsis the ability to accurately identify the individual carrier frequencies, and to do so as quickly aspossible. A delay in identifying the correct frequency will degrade the performance of thesystem. For example, when changing the channel on a radio or television set which are designedto receive multicarrier digital signals, which has a long delay in identifying the individual carrierfrequencies, one would like the picture and sound to appear as soon as possible. However, onedetermining factor in how long it takes to receive a picture or sound on a newly tuned channel isthe delay involved in the receiver in identifying the individual carrier frequencies. The presentinvention relates to a method and an apparatus for implementing the method, for quick andaccurate identification of the individual carrier frequencies.

To better understand the invention, the following additional backgroundinformation on MCM schemes is helpful. A MCM transmitted symbol can be represented by theequation

wherea_k is the complex information symbol sequence,T is the information symbol interval,N isthe number of orthogonal carriers used in the scheme, each of which is to be sampled overTseconds, andNT is the MCM symbol interval. The parametersN and T are chosen to satisfyspecific bit rate requirements of a particular application. For example, in S.N. Hulyalkar,MCMDesign for Transmission of Digitally-Compressed Television Signals in a Simulcast TerrestrialChannel PLB Technical Note TN-92-012,a MCM scheme for the transmission of digitally compressed television over a terrestrialchannel is considered whereN=1024 andNT= 127.19 microseconds.

In the absence of channel distortions, noise, frequency offset and timingerrors, the transmitted information sequence can be recovered perfectly at the receiver bysampling the received signal everyT seconds and after receivingN samples performing an N-pointFFT on the received sequence. The FFT at the receiver performs like a matched filter ateach of the N carrier frequencies. In order to reliably demodulate the received signal and recoverthe transmitted information sequence, the orthogonality of the transmitted carriers has to bemaintained at the receiver. In real systems, however, intersymbol interference ("ISI"), receiverfrequency offset and timing errors all contribute to destroying the orthogonality of thetransmitted carriers and can result in severe performance degradations if left uncompensated.

A well-known technique for dealing with intersymbol interference is theinsertion of a "guard interval" at the beginning of each transmitted symbol. See A. Alard and R.Lassalle,Principles of Modulation and Channel Coding for Digital Broadcasting for MobileReceivers EBU Review, No. 224 (August 1987).

In multi-path systems, such as television signals, a receiver may detect a directsignal and one or more delayed reflections of the same signal, such as off a skyscraper, as thesum of these multiple signals. The guard interval enables the receiver to resolve these signals inorder to accurately detect the direct signal alone.

Frequency offset and time synchronization are also critical to accuratelyretrieve the transmitted data. Frequency offset occurs when a carrier frequency undergoes a phaseshift during transmission and the receiver frequency is not perfectly aligned with thetransmission frequency. This phase shift causes the carriers to lose their orthogonalcharacteristic. Because the carriers are inherently closely spaced in frequency compared to thechannel bandwidth, there is a very low tolerance for even a small frequency offset relative to thechannel bandwidth. To properly retrieve the transmitted data from the carrier, the receiver mustbe able to compensate for this frequency offset.

When correcting for frequency offset, it is also advantageous to determineand correct any frequency offset prior to the FFT operation of the receiver. This allows thereceiver to quickly converge onto the accurate frequency of the carriers and process the receivedsignals. If, however, the FFT operation is performed before any frequency offset is corrected, theprocess of determining and correcting any frequency offset is delayed.

To properly synchronize a receiver and an incoming signal, a receiver mustknow the bit transfer rate, so that as a signal is received, the receiver samples the incoming signalat the appropriate sample interval T. However, timing involves more than the sample interval T.The receiver must also know the sample marking the beginning of each symbol intervalNT. Ifthe sampler is not properly aligned with the symbol interval, the sampling window will overlapand process the symbols detected over multiple symbol intervals as if they were all part of onesymbol interval, rather than process the symbols of one symbol interval, alone. Determining thebeginning of each symbol interval is referred to as symbol synchronization. Symbolsynchronization and accurate knowledge of sample interval T.are collectively known as timesynchronization. The importance of frequency offset and time synchronization notwithstanding,very little has appeared in the literature regarding frequency and time synchronization issues forMCM systems.

One method for frequency offset estimation is described in P.H. Moose,ATechnique for Orthogonal Frequency Division Multiplexing Frequency Offset Correction IEEE- Transactions on Communications Vol. 42 No. 10 (October 1994).Moose, however, relies on perfect timing information, inother words, the receiver knowsT exactly, which in practice,i.e.. useful, real-world situations, isnot available to the receiver.

Neglecting to compensate for a timing mismatch can have a serious impacton the receiver's ability to detect an incoming signal. Consider a received MCM signal over onesymbol interval. Taking into account the guard interval, a frequency offset and additive whiteGaussian noise ("AWGN"), the received signal can be represented as:

whereH_k represents the frequency response of the channel at thek^th carrier, ε is the frequencyoffset andw(t) is complex AWGN. This signal is sampled by the receiver at intervals ofT+ΔTand an initial offset τ. The clock error ΔT is assumed to be small enough so thatN samples areobtained during the symbol interval. Sampling r(t) at [n(T + ΔT) + τ], each sample along symbolintervalNT can be expressed as

Assuming symbol synchronization is available so that the receiver knowswhich sample marks the beginning of each symbol interval, the FFT ofr_n can be written as:

One skilled in the art will recognize that each sample R_n comprises a direct signal component S_n'an interference component I_n and an AWGN componentW_n.
The signal component can be expressed as

while the interference component can be expressed as

To one skilled in the art, it is apparent from equation (7) that the interference due to frequencyoffset ε and sampling interval mismatch ΔT, appears as a time-varying convolution involving allthe k carriers. In other words, the orthogonality of the carriers has been destroyed. Assuming anindependent, identically distributed data stream a_k and a flat channel,i.e., no ISI, the signal-to-interference-ratio,("SIR") can be written as

When the frequency offset ε is zero, the SIR(n) is a function ofn due to the fact that theconvolution is time variable, and the SIR can be approximated to

Thus, it is clear that even a small timing error, for example, an error on the order of 10^-4, canreduce the SIR drastically. If instead ΔT is assumed to be zero when in fact it is not, and it is notcorrected, the receiver will perform poorly. Moreover, this effect, unlike the effect of frequencyoffset ε, is not uniform over all carriers. This can be seen from equation 9 where it is apparentthat if there is a timing mismatch, the SIR is a function of n. Thus, it is important for the receiverto employ accurate timing recovery schemes to estimate ΔT/T and thereby improve the SIR.

In EP-A-706273 two embodiments of a multicarrier system are described. The firstembodiment described derives a control signal from a signal between retrieving samplingmeans and an FFT demodulator, but contrary to the present invention hereafter does notsuggest to correct the frequency of the signal itself as applied to the FFT demodulator. Thesecond embodiment described comprises as in the present invention multiplier meanscoupled between the sampling means and the FFT demodulator to compensate for thefrequency offset based on the estimate received from estimating means. However these meansare coupled to the output of the multiplier means, which output corresponds to the input ofthe FFT demodulator. This is contrary to the invention as claimed hereafter, where theestimating means are coupled between the retrieving means and the multiplier means. Inaddition the second embodiment does not suggest correcting its sampling means. Acombination of both the embodiments will not be contemplated by the skilled man, as thiswould lead to duplication of the sequence of 111, 112, 113, 114, 115, 116, 118/103, andwould only lead to more complexity and to induced additional -unwanted- delays, which theinvention tends to reduce. Finally such a combination would not suggest to couple the oneestimating means between themeans 11 and 19, as claimed hereafter.

US-A-5,228,062, which is used to delimit the claimed invention from discloses atransmission system for transmitting and receiving multicarrier modulated digital signals. The system comprises a transmitter for transmitting data as a multicarrier modulated signal. Saidtransmitter including means for transmitting at least a plurality of single tone signals toprecede said multicarrier modulated data signal. Said multicarrier modulated data signal andsaid preceding single tone signals comprising a data structure. The system also comprises areceiver for receiving said data structure, said receiver including means for retrieving saidplurality of single tone signals, means for estimating a frequency offset Δf and a timingmismatch ε of said receiver, means 10, 170, 175, 260; 170, 180, 300 for adjusting said receiverto compensate for said estimated frequency offset and timing mismatch, an FFT demodulatorfor performing an FFT operation on the modulated signals and multiplier means coupledbetween said retrieving means and said FFT demodulator to compensate for the frequencyoffset based on the estimate received from said estimating means.

In US-A-5,228,062 both demodulation and decoding are performed in blocks 120 and130 respectively in order to analyse -in a processor- and filter -in low pass filters 170 and 180-toform estimates of remanent carrier and clock frequency offsets. The low pass filters areused for combining processed demodulated and decoded processor output signals a and bwith ε and Δf respectively. These combined feedback signals -which in our application arehowever indicated ΔT/T and ε respectively- are used for controlling the timing mismatch andthe frequency offset respectively.

Summary of the Invention

Accordingly, it is an object of the present invention to provide a transmission systemfor transmitting and receiving multicarrier modulated digital signals, comprising:

a transmitter for transmitting data as a multicarrier modulated signal, said transmitterincluding means for transmitting at least a plurality of single tone signals to precede saidmulticarrier modulated data signal, said multicarrier modulated data signal and said precedingsingle tone signals comprising a data structure; and

a receiver for receiving said data structure, said receiver including means for retrieving saidplurality of single tone signals, means for estimating a frequency offset and a timing mismatchof said receiver, means for adjusting said receiver to compensate for said estimated frequencyoffset and timing mismatch, an FFT block for performing an FFT operation on themodulated signals, and multiplier means coupled between said means and said FFT block tocompensate for the frequency offset based on the estimate received from said means, wherebythe estimating means are coupled between said retrieving means and said multiplier means,characterised in that said means are arranged for compensating for said estimated frequencyoffset and timing mismatch only prior to performing the FFT operation by the block.

Brief Description of the Drawings

Fig. 1 is a block diagram of a MCM receiver showing frequency offsetcompensation and timing estimation according to the present invention.

Fig. 2 depicts a data structure as used in connection with the transmitter-receiversystem of the present invention.

Fig. 3 is a block diagram of the frequency offset compensation and timingestimation process according to the present invention.

Detailed Description of the Invention

Referring to FIG.1, a block diagram of a MCM receiver is shown. As asignal is received, Analog Digital Converter (11) samples the incoming analog signal at intervalsof T seconds. After digitizing the received analog signal, Null Detect block (12) detects the nullsymbol as shown in FIG.2. The digitized signal also enters block (13) in which a Hilberttransform filter converts the received real signal to a complex form. The signal then enters block(14) which uses the output of Null Detect (12) as a rough indicator of the first symbol of each block of data. Remove Guard block (14) removes the guard interval preceding each symbol. Asthe signal exits block (14), single frequency offset and timing mismatch of the sampler arecalculated simultaneously, prior to the FFT operation of the receiver. The timing synchronizationinformation ΔT/T, is input to Timing Control block (16) and the frequency offset ε is input toFrequency Control block (18). These control blocks can be implemented with standardcomponents, such as a phase-locked loop.

In multiplier (19), the received signal is adjusted to compensate for anyfrequency offset based on the estimate received from block (15). At this point, Analog-DigitalConverter (11) has been corrected for ΔT/T and any frequency offset of the sampled signal, hasbeen compensated. The receiver now takes the FFT of the synchronized and compensated signalin block (20). Symbol Synchronizer and Channel Estimator (21) tap symbols S3 and S4 from theoutput of FFT block (20) and determine the start of each symbol interval and also estimate thefrequency response of each carrier,i.e., H_k. The symbol synchronization is input to RemoveGuard block (14) to be used together with the information from Null Detect block (12) todetermine the start of the first symbol of the next symbol interval. The estimated frequencyresponseH_k is input to Equalizer (22) which determines the maximum likelihood representationof each data symbol at their respective carrier frequencies.

The transmitter receiver system of the present invention, in which frequencyoffset compensation and timing synchronization occurs simultaneously and prior to the FFToperation of a receiver, involves a specific data structure which includes at least two (2) singletone symbols which precede the symbols corresponding to the information sought to betransmitted. Referring to FIG.2, one preferred data structure as used in the present invention, isshown comprising a preamble, composed of five symbols, followed by a sequence of datasymbols,i.e. the information sought to be transmitted. The first symbol is a null symbol, used toobtain a coarse estimate of the start of each symbol interval. A simple energy detector detects asudden increase in energy from the null symbol to S1 thereby roughly indicating the first symbolof each block of data.

Following the null symbol are single tone symbols S1 and S2 with differentfrequencies, transmitted over consecutive data intervals of lengthNT, and separated by a guardinterval of lengthN_gT. The frequencies of S1 and S2 can be expressed asM₁/NT andM₂/NT,respectively. As shown below, M₁ and M₂ should have relatively small values, whose differenceis large. S1 and S2 are then followed by symbols S3 and S4 which contain all the carrier frequencies of the data symbols and are used for symbol synchronization. Finally, S3 and S4 arefollowed by the symbols corresponding to the desired information.

By concatenating single tone symbols to the front end of the transmitteddata, the frequency offset and timing mismatch can be determined prior to performing an FFTover the received symbols, since these symbols do not require any demodulation. The mechanicsof estimating the frequency offset and timing mismatch using S1 and S2, proceeds asfollows:.The expression for the received samples over a symbol interval, as shown in equation(3), can be rewritten as

whereH'k=Hkej2πτ(k+ε)/NTFor S and S2, the received sample sequence over their respective symbol intervals, can beexpressed asrn=H'M1aM1ej2πnN(M1+ε)(1+ΔTT)+wnandrn=H'M2aM2ej2πnN(M2+ε)(1+ΔTT)+wnrespectively.
These sequences are input to Frequency Offset and Timing Estimator block (15). As shown inFIG. 3, Estimator (15) begins in block (31) by dividing the samples of each symbol interval, inhalf, and forms the following sample vectors from the samples of S1 and S2.

Note that although S1 and S2 are consecutive symbols, each of lengthNT, due to the guardinterval of lengthN_gT between these two symbols, S2 is first sampled at time(N+N_g)T.

For purposes of estimating any frequency offset and timing mismatch, it isnot necessary to have precise symbol synchronization. Indeed, since S3 and S4, the symbols usedfor precise symbol synchronization are modulated over multiple carriers, precise symbolsynchronization is only available after demodulating S3 and S4, whereas an objective of thepresent invention is to estimate and correct any frequency offset and timing mismatch prior todemodulation. Rather, coarse symbol synchronization is sufficient if the length of each vector isreduced fromN/2 to a value which will ensure that vectorsR1_a andR1_b have samples from thesample interval corresponding to S1 and vectorsR1_a andR1_b have samples from the sampleinterval corresponding to S2. Although the actual vector length used will affect the variance ofthe estimates, it will not affect the nature of the estimator, namely, that it is a maximum-likelihoodestimation.

From equations (12) and (13), the relationship between the vectors for eachsymbol can be shown asR1b=R1aejπM1ejπ(ε+M1ΔTT+εΔTT)R2b=R2aejπM2ejπ(ε+M2ΔTT+εΔTT)AssumingM₁ andM₂ are even, the termse^jπM₁ ande^jπM₂ equal 1 and the vector relationshipscan be rewritten asR1b=R1aejπ(ε+M1ΔTT+εΔTT)R2b=R2aejπ(ε+M2ΔTT+εΔTT)Now, let1=π(ε+M1ΔTT+εΔTT)2=π(ε+M2ΔTT+εΔTT)Accordingly, Estimator (15) computes the maximum likelihood estimate of ₁ and ₂, as shownin block (32) and given by1=tan-1(R1TbR1*a)Im(R1TbR1*a)Re2=tan-1(R2TbR2*a)Im(R2TbR2*a)ReSince the maximum likelihood estimate is a consistent estimate, which means that the estimate ofa function, for example, the estimates of ₁ and ₂, can be used to estimate a function, such asfrequency offset ε and timing mismatchΔT/T, of the estimated ₁ and ₂, ε and.ΔT/T can beestimated from the estimates of ₁ and ₂. The maximum likelihood estimates of ε and ΔT/T arecomputed in block (33) as,ε =1M2 -2M1π(M2-M1)+(2-1)andΔTT=2-1π(M2-M1)respectively. The range of e that can be estimated by this procedure can be increased byshortening the length of each of the vectors used in the estimation procedure. For small ΔT/T anda vector length ofN/2, the range over which ε can be estimated unambiguously is |ε| <1. Themathematical operations involved in arriving at these estimates can be implemented with specificphysical components, such as multipliers, adders, and a readable memory for storage of a lookuptable, or they can be implemented through a general purpose or dedicated microprocessorexecuting software instructions.

As indicated above the frequency offset and timing mismatch estimates areobtained prior to exact symbol synchronization and FFT operations and hence do not delay theestimation process. Furthermore, since these are maximum likelihood estimates, they are veryefficient, even at low signal to noise ratios ("SNR").

Since the frequency, offset and clock error are estimated jointly, a jointCramer-Rao lower bound ("CRLB") on the variances of the frequency offset and timingmismatch estimates is given by

The Cramer-Rao lower bound is a measure of the variance of the best estimator for any problem.Indeed, these expressions can be used as exact variances instead of lower bounds, since themaximum likelihood estimate satisfies the Cramer-Rao lower bound. A more detailed descriptionof the Cramer-Rao lower bound can be found in J.M. Mendel,Lessons in Digital EstimationTheory, (1987), hereby incorporated by reference as if fully set forth herein.

As indicted above, selectingM₁ andM₂ is an important design issue.Equations (26) and (27) show that lower variance of frequency offset ε and timing mismatchΔT/T is obtained by using values ofM₁ andM₂ which are widely spaced. In addition,M₁ andM_2'should each be relatively small. One skilled in the art will be able to readily experiment with andascertain highly efficient values ofM₁ andM₂, in order to minimize the variance of the estimates.Other factors, such as distortion due to frequency band edges and known interferers at certainfrequencies will also influence the optimum choice of M₁ andM₂. For example, the MCMscheme being considered for the transmission of digitally compressed television over a terrestrialchannel, where N = 1024 and NT = 127.19^µ sec, the bestM₁ andM₂ were shown by simulationsto be 100and 400, respectively. In general, the bestM₁ andM₂ will be determined on a case-by-casebasis by simulation, actual experimentation, or both.

Claims (8)

1. A transmission system for transmitting and receiving multicarrier modulateddigital signals, comprising:

   a transmitter for transmitting data as a multicarrier modulated signal, saidtransmitter including means for transmitting at least a plurality of single tone signals toprecede said multicarrier modulated data signal, said multicarrier modulated data signal andsaid preceding single tone signals comprising a data structure; and

   a receiver for receiving said data structure, said receiver including means (11)for retrieving said plurality of single tone signals, means (15) for estimating a frequencyoffset and a timing mismatch of said receiver, means (18, 16) for adjusting said receiver tocompensate for said estimated frequency offset and timing mismatch, an FFT block (20) forperforming an FFT operation on the modulated signals, and multiplier means (19) coupledbetween said means (11) and said FFT block (20) to compensate for the frequency offsetbased on the estimate received from said means (15), whereby the estimating means (15) arecoupled between said retrieving means (11) and said multiplier means (19),characterised inthat said means (18, 16) are arranged for compensating for said estimated frequency offsetand timing mismatch only prior to performing the FFT operation by the block (20).
2. A transmission system according to claim 1, wherein said plurality of distinctsingle tone signals consist of two distinct single tone signals.
3. A transmission system according to claim 2, wherein said data structurecomprises a null symbol, said two distinct single tone signals, and said multicarriermodulated data signals.
4. A transmission system according to claim 3, wherein said data structurecomprises a null symbol, said two distinct single tone signals, one or more multicarriermodulated signals for use in symbol synchronization of said receiver, and said multicarriermodulated data signals.
5. A receiver for application in the transmission system according to one of theclaims 1-4, the transmission system comprising:

   a transmitter for transmitting data as a multicarrier modulated signal, saidtransmitter including means for transmitting at least a plurality of single tone signals toprecede said multicarrier modulated data signal, said multicarrier modulated data signal andsaid preceding single tone signals comprising a data structure; and

   a receiver for receiving said data structure, said receiver including means (11)for retrieving said plurality of single tone signals, means (15) for estimating a frequencyoffset and a timing mismatch of said receiver, means (18, 16) for adjusting said receiver tocompensate for said estimated frequency offset and timing mismatch, an FFT block (20) forperforming an FFT operation on the modulated signals, and multiplier means (19) coupledbetween said means (11) and said FFT block (20) to compensate for the frequency offsetbased on the estimate received from said means (15), whereby the estimating means (15) arecoupled between said retrieving means (11) and said multiplier means (19),characterised inthat said means (18, 16) are arranged for compensating for said estimated frequency offsetand timing mismatch only prior to performing the FFT operation by the block (20).
6. A receiver according to claim 5 wherein said plurality of distinct single tonesignals consist of a first single tone signal and a second single tone signal.
7. A receiver according to claim 6 wherein a sampler (11) is arranged fordetecting N samples of each of said distinct single tone signals over a symbol interval, eachof said single tone signals having a frequency equal to an even multiple of the inverse of saidsymbol interval, and wherein said frequency offset and timing mismatch estimator (15)comprises means (31) for dividing each of said distinct single tone signals into a first andsecond sample vector, for a total of four sample vectors, each of said first sample vectorscomprising a first part of said samples of said single tone signal, respectively, and each ofsaid second sample vectors comprising a second part of said samples of said single tonesignal, respectively; means (32) for computing a first inverse tangent of the ratio of animaginary part to a real part of the product of the transform of said second sample vector ofsaid first single tone signal and said first sample vector of said first single tone signal, andmeans (32) for computing a second inverse tangent of the ratio of an imaginary part to a realpart of the product of the transform of said second sample vector of said second single tonesignal and said first sample vector of said second single tone signal; means (33) for computing said estimated frequency offset as the ratio of the difference between the productof said first inverse tangent and said second multiple and the product of said second inversetangent to said multiple, to the sum of the product of π and the difference between said firstand second multiples and the difference between said first and second inverse tangents; andmeans (33) for computing said estimated timing mismatch as the ratio of the differencebetween said first and second inverse tangents, to the product of π and the difference betweensaid first and second multiples.
8. A receiver according to claim 7 wherein said first part of samples and saidsecond part of samples, for each of said single tone signals comprise disjoint sets of samples.

Images