Method and Apparatus for Asynchronous Timing Recovery Using Interpolation Filter

This invention relates generally to data communications, and more particularly, to timing recovery for asynchronous data communications systems.

In certain data communication systems such as V.32 modems, there are two clocks that must be synchronized, known as the near-end and the far-end clocks. The near-end clock is the clock that a given station uses to transmit the data. The far-end clock is the other station's clock. For example, two stations may transmit and receive data according to the V.32 specification. V.32 specifies transmission at 9600 bits per second (bps). However, the V.32 standard allows 100 parts-per-million (ppm) or approximately 0.01% variation in clock frequency. Thus the near-end station may be transmitting data at 9601 bps while the far-end station is transmitting data at 9599 bps. A V.32 modem must be able to synchronize the data without introducing distortion and without costly circuitry.

The modem must also solve the problem of echo. A station's received signal includes not only data from the other station, known as far-end data, but also an echo due to the fact that the interface to the common transmission medium used for both reception and transmission reflects some of the transmit data's signal power back to the station. One type of echo, known as near-end echo, results from the signal power reflected by the near-end station's own interface to the transmission medium. A second type of echo, known as far-end echo, results from the signal power reflected from the far-end station's interface to the medium. The basic scheme used to cancel this echo is to substract a delayed fraction of the transmitted signal from the received signal.

A recent improvement in technology is the development of digital signal processors (DSPs), which are data processors optimized for signal processing operations. DSPs have allowed many V.32 modem functions to be performed by mathematical operations on digital data, and have reduced the number of integrated circuits required to implement a data modem to a minimum. However, known clock synchronization systems require external analog-to-digital converters (ADCs) and digital-to-analog converters (DACs) in addition to the DSP. Thus it is desirable to further reduce the number of integrated circuits required to perform signal processing functions.

Accordingly, there is provided, in one form, a method for timing recovery in asynchronous data communication systems. An input signal is sampled at a first data rate to provide a plurality of sampled input signals. Each sampled input signal is interpolated according to a selected one of a first predetermined number of finite impulse response (FIR) filters to provide a plurality of interpolated samples. A positive difference between the first data rate and a second data rate is sensed and corresponding ones of the plurality of interpolated samples are periodically dropped to provide a plurality of output samples at the second data rate in response thereto. A negative difference between the first data rate and the second data rate is sensed and corresponding ones of the plurality of interpolated samples are periodically repeated to provide the plurality of output samples at the second data rate in response thereto. A subsequent one of the predetermined number of FIR filters is selected in response to either sensing the positive difference or sensing the negative difference a second predetermined number of times. The second data rate is recovered from the plurality of output samples.

In another form, there is provided an apparatus for asynchronous timing recovery, comprising storage means, interpolation means, sample rate conversion means, equalizer means, and timing control means. The storage means stores a plurality of sets of coefficients, ordered from a first to a last, each set of coefficients delayed from a prior set by a predetermined amount. The interpolation means is coupled to the storage means, and continually interpolates an input signal, sampled by a first clock having a first clock rate, through a finite impulse response (FIR) filter using a selected one of the plurality of sets of coefficients to provide a plurality of corresponding interpolated samples. The sample rate conversion means is coupled to the interpolation means, and repeats a corresponding one of the interpolated samples in response to a repeat signal and drops the corresponding one of the interpolated samples in response to a drop signal to provide a sample-rate converted signal at a second clock rate. The equalizer means is coupled to the sample rate conversion means, recursively computes a plurality of equalization coefficients, and filters the sample-rate converted signal to provide an output signal in response thereto. The timing control means is coupled to the interpolation means, the sample rate conversion means, and the equalizer means, computes a time drift signal in response to said plurality of equalization coefficients, selects a subsequent one of the plurality of sets of coefficients in response to the time drift signal exceeding a predetermined threshold, activates the drop signal in response to a selection of a first one of the plurality of sets of coefficients when the first clock rate exceeds the second clock rate, and activates the repeat signal in response to a selection of the first one of the plurality of sets of coefficients when the second clock rate exceeds the first clock rate.

These and other features and advantages will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings.

FIG. 1 illustrates in block diagram form a data communication system with asynchronous near-end and far-end data sampling.

FIG. 2 illustrates in block diagram form a V.32 modem using a known sample-rate conversion technique.

FIG. 3 illustrates in block diagram form a V.32 modem in accordance with the present invention.

FIG. 4 illustrates a block diagram of a data processing system implementing the V.32 modem of FIG. 3.

FIG. 1 illustrates in block diagram form a data communication system 20 with asynchronous near-end and far-end data sampling. System 20 includes generally a far-end station 21, a first transmission-line coupler 22, a transmission line 23, a second transmission-line coupler 24, and a near-end station 25. The operation of system 20 will be described from the perspective of near-end station 25. However, far end station 21 is structurally identical to near-end station 25 and corresponding element are assigned the same reference numbers.

Near-end station 25 has a transmitter 30 connected to coupler 24 for transmitting data through coupler 24 onto transmission line 23 for reception by far-end station 21. Near-end station 25 also has a receiver 32 connected to coupler 24 for receiving far-end data. During transmission, coupler 24 reflects some of the signal power supplied by transmitter 30 into receiver 32. This reflected signal, called near-end echo, is synchronous with the clock of transmitter 30. In addition, coupler 22 reflects some of the signal power at the far end of transmission line 23 back through transmission line 23 and into receiver 32. This reflected signal, called far-end echo, is also synchronous with the clock of transmitter 30. Transmitter 30 also provides an output to an echo canceller 31, which delays and attenuates the transmitted data signal and provides the resulting signal to receiver 32. Receiver 32 subtracts the delayed, attenuated signal from the received data.

Receiver 32 also receives the incoming data from far-end station 21, which is asynchronous to the clock of transmitter 30. For example, for V.32 modem communication systems, each station must transmit data at 9600 bps with a tolerance of 0.01%, or approximately 9599 to 9601 bps. Ideally, receiver 32 will be able to recover the asynchronous data without introducing distortion and without using unnecessary components or data processing capability.

Three conventional sample-rate conversion techniques are commonly used for sample-rate conversion but each has drawbacks. First, a direct technique simply stores data in a data buffer at the near-end clock rate, and outputs the data at the far-end clock rate. When the two sample rates are very close to each other and the signal which will be converted has a relatively low frequency content, the resulting jitter will be small. However, when the signal has a relatively high frequency content, the output signal will exhibit discontinuities. Thus, the direct method is only useful in very low-frequency applications.

A second method is known as the M/N technique. This approach is useful when the ratio of the two samples rates can be represented by two rational numbers, M and N. M and N represent the least-common-multiple ratio of the input sampling rate to the output sampling rate. The input data is first interpolated up at a 1:M interpolation ratio. The resulting signal is successively input to a reconstruction digital filter, an anti-aliasing digital filter, and a decimator having a N:1 decimation ratio to provide the output data at the second frequency. The problem is that the M/N technique can only be used when M and N are small numbers, typically less than 10. Thus, the M/N technique is impractical for such applications as a V.32 modem which may have a 9599 Hz. near-end clock sampling 9601 bps far-end data.

A third conventional technique, known as the D/A and A/D technique, converts the digital input data to the analog domain using a digital-to-analog converter (DAC) and reclocks the data at the recovered far-end clock frequency using an analog-to-digital converter (ADC). FIG. 2 illustrates in block diagram form a V.32 modem using the D/A and A/D sample-rate conversion technique. Modem 40 includes generally a transmitter and echo canceller 41, a DAC 45, a transmission line coupler 42, and a receiver 43. Transmission line coupler 42 is connected to a transmission line 44.

Transmitter and echo canceller 41 receives digital data labelled "TRANSMIT DATA" at the near-end clock rate. In the illustrated embodiment, the near-end clock rate is 9600 Hz. with 0.01% tolerance. Transmitter and echo canceller 41 modulates TRANSMIT DATA to the carrier frequency according to the V.32 specification. The modulated signal is provided to DAC 45, which converts the modulated signal to an analog signal. Transmitter and echo canceller 41 provides a timing control signal labelled "CONTROL" which clocks DAC 45 at the near-end clock rate. DAC 45 provides the analog signal to transmission line coupler 42, which is a conventional two-wire/four-wire (2W/4W) hybrid providing a physical interface to transmission line 44.

Transmission line coupler 42 also receives a far-end signal from transmission line 44 and provides the far-end signal, along with near-end and far-end echoes, to receiver 43. Receiver 43 includes an analog-to-digital converter (ADC) 50 to convert the far-end signal and echoes to a digital representation. ADC 50 receives signal CONTROL from transmitter and echo canceller 41 with which to sample the incoming data. Since transmitter and echo canceller 41 provides CONTROL at the near-end clock rate, receiver 43 must perform sample-rate conversion to recover data at the correct (far-end) rate. However, both the near-end and far end echoes are synchronous with the near-end clock. The output of ADC 50 is thus provided to a positive input of a summing device 51. An echo canceller in transmitter and echo canceller 41 provides a negative input signal to summing device 51, and receives the output thereof as a feedback signal. The echo canceller provides delayed and attenuated versions of the modulated TRANSMIT DATA in order to cancel the corresponding echoes.

A sample rate converter 52 receives the output of summing device 51. Sample rate converter 52 uses the D/A and A/D method for sample rate conversion. Sample rate converter 52 includes a digital-to-analog converter (DAC) 60, a reconstruction filter 61, a sample and hold block 62, and an ADC 63. DAC 60 receives signal CONTROL and thus converts the output of summing device 51 into an analog signal using the near-end clock. Reconstruction filter 61 and sample and hold block 62 then provide a continuous input to ADC 63 and cancel image frequencies created by DAC 60. Then, ADC 63 reclocks the received data at the recovered far-end clock rate.

A timing and equalization block 53 receives the output of ADC 63. Timing and equalization block 53 recovers the far-end clock and provides it to ADC 63. In addition, timing and equalization block 53 eliminates adjacent symbol interference in the received data which is caused by channel distortion to provide "MODULATED RECEIVE DATA". A system which may be used for timing recovery and equalization block 53 based on a transversal equalizer and decision feedback mechanism was described by Ungerboeck, G., "Fractional Tap-Spacing Equalizer and Consequences for Clock Recovery in Data Modems," IEEE Transactions on Communications, vol. COM-24, no. 8, August 1976.

The principal problem with modem 40 is that sample rate converter 52 requires costly hardware circuitry. Most V.32 modem signal processing functions, like transmitter and echo canceller 41, summing device 51, and timing and equalization block 53, may be performed by software running on a digital signal processor (DSP). However, DACs and ADCs are implemented as hardware circuitry, adding to modem cost and size. For example, one DAC and one ADC are commonly available as a single separate integrated circuit. Thus, the D/A and A/D method adds a costly additional component to the modem design.

FIG. 3 illustrates in block diagram form a V.32 modem 80 in accordance with the present invention. Modem 80 includes generally a transmitter and echo canceller 81, a DAC 85, a transmission line coupler 82, and a receiver 83. Transmission line coupler 82 is connected to a transmission line 84. The transmission of data and echo cancellation are performed similarly to that of modem 40.

Transmitter and echo canceller 81 receives TRANSMIT DATA at the near-end clock rate. In the illustrated embodiment, the near-end clock rate is 9600 Hz with 0.01% tolerance. Transmitter and echo canceller 81 modulates TRANSMIT DATA to the carrier frequency according to the V.32 specification. The modulated signal is provided to DAC 85, which converts the modulated signal to an analog signal. Transmitter and echo canceller 81 provides a timing control signal labelled "CONTROL" which clocks DAC 85 at the near-end clock rate. DAC 85 provides the analog signal to transmission line coupler 82, which is a conventional two-wire/four-wire (2W/4W) hybrid providing a physical interface to transmission line 84.

Transmission line coupler 82 also receives a far-end signal from transmission line 84 and provides the far-end signal, along with near-end and far-end echoes, to receiver 83. Receiver 83 includes an analog-to-digital converter (ADC) 90 to convert the far-end signal and echoes to a digital representation. ADC 90 receives signal "CONTROL" from transmitter and echo canceller 81 with which to sample the incoming data. Since transmitter and echo canceller 81 provides CONTROL at the near-end clock rate, receiver 83 must perform sample-rate conversion to recover data at the correct (far-end) rate. However, both the near-end and far end echoes are synchronous with the near-end clock. The output of ADC 90 is provided as a positive input to a summing device 91. An echo canceller in transmitter and echo canceller 41 provides a negative input signal to a summing device 91, and receives the output thereof as a feedback signal. The echo canceller provides a delayed and attenuated version of the modulated TRANSMIT DATA in order to cancel the echo. Summing device 91 provides a substantially echo-free signal labelled "x(n)" sampled at the near-end rate.

Modem 80, however, reduces the amount of integrated circuit hardware required by eliminating the need for DAC 60 and ADC 63 used in modem 40 of FIG. 2. Receive data and clock recovery are performed using software running on a conventional digital signal processor (DSP) (not shown in FIG. 3). Other methods of implementing data and clock recovery include firmware or microcode running on a DSP, hardware circuitry which may require less integrated circuit area than DAC 60 and ADC 63 in modem 40, or combinations thereof.

The output of summing device 91 is provided to a windowed, all-pass interpolation filter 92. Interpolation filter 92 passes signal x(n) through a causative, 31-tap FIR filter having a sinc(x) response multiplied by a Hanning window function. In modem 80, the particular window function used is not critical, and other known window functions, such as the Blackman-Harris window function, may be used.

The coefficients for interpolation filter 92 are provided as a selected one of twenty sets of filter coefficients stored filter coefficient memory 93. Each set of filter coefficients in memory 93 includes coefficients of a windowed sinc(x) function in which the coefficients are phase-shifted relative to the preceding set of coefficients. The first filter in memory 93 includes coefficients of the windowed sinc(x) function perfectly-centered around the center tap (i.e., tap 16). The second entry includes coefficients of the windowed sinc(x) function which are slightly delayed; i.e., the maximum value is slightly to the right of the center tap. For a set of twenty filters, the delay between filters is 0.05 of the normalized sampling period. Subsequent filters add increasing delays and shift the maximum value with an increasing delay from the center tap; the twentieth filter represents a windowed sinc(x) function with a maximum value 0.05 normalized sampling periods to the left of tap 17. By having a tap length of 31, modem 80 meets the V.32 timing standard. Memory 93 receives a control input labelled "CHANGE FILTER" which selects each filter in order. When the twentieth filter is selected and CHANGE FILTER is activated, memory 93 again selects the first filter.

A sample rate conversion block 94 receives the output of interpolation filter 92 and provides an output signal at the recovered far-end clock rate. Sample rate conversion block 94 receives a control input labelled "DROP/REPEAT SAMPLE" from a timing control block 96 which controls which interpolated samples are to be included in developing the output signal thereof. Sample rate conversion block 94 provides the output signal to a passband phase-splitting, fractionally-spaced equalizer (PS-FSE) 95.

Equalizer 95 continuously receives the output provided by sample rate conversion block 94, passes this signal through an FIR filter, and provides a signal labelled "x.sub.k " to a V.32 decoder 97. Equalizer 95 processes the received signal to compensate for any nonlinearity associated with the channel and any analog hardware circuitry. Equalizer 95 also recursively updates its filter coefficients and provides these coefficients to a timing control block 96.

Timing control block 96 compares the energy in the signal around the filter's center tap. Thus, timing control block 96 is able to sense the change in phase over time, which is equivalent to sensing a sampling frequency difference. Timing control block 96 controls interpolation filter 92 and sample rate conversion block 94 to correctly interpolate signal x(n) so as to provide signal x.sub.k at the correct far-end timing. Timing control block 96 provides control signals CHANGE FILTER to memory 93 and DROP/REPEAT SAMPLE to sample rate conversion block 94.

If timing control block 96 senses that the near-end clock rate is faster than the far-end clock rate, then timing control block 96 periodically activates CHANGE FILTER to cause memory 93 to provide coefficients for a subsequent FIR filter to filter 92. When timing control block 96 activates CHANGE FILTER after memory 93 has been providing coefficients for the twentieth filter, memory 93 again provides the first filter coefficients. In addition, timing control block 96 activates DROP SAMPLE, thereby completing the sample rate conversion.

On the other hand, if the near-end clock rate is slower than the far-end clock rate, then timing control block 96 activates CHANGE FILTER as above. However, interpolation filter 92 uses the symmetry of the windowed sinc(x) function to mirror the coefficients around the center tap and cause a leftward shift of the maximum value of the windowed sinc(x) function. When timing control block 96 activates CHANGE FILTER after memory 93 has been providing coefficients for the twentieth filter, memory 93 again provides the first filter coefficients. In addition, timing control block 96 activates REPEAT SAMPLE, thereby completing the sample rate conversion.

The function of the various blocks used in clock recovery and sample rate conversion may be represented mathematically. Let x(n) represent samples from ADC 90 taken at a sample rate of f.sub.s =1/T.sub.s, where T.sub.s is the near-end sample period. By the sampling theorem, the time-domain signal x(t) can be obtained from its samples:

where x(t) is the time-varying signal at time t, x(n) is the nth sample, sinc(x)=sin(x)/.pi.x, and the summation over n is from -.infin. to .infin.. Now let t=kT.sub.s ', T.sub.s '=T.sub.s +.epsilon., where T.sub.s ' represents the far-end clock period and .epsilon. represents a difference between the near-end and far-end sampling periods. The time-varying signal can then be expressed as:

where .epsilon.'=k.epsilon./T.sub.s. Equation [2] can be rewritten as

where * represents convolution, and

Thus, a resampling of x(n) can be realized by having x(n) as an input to an FIR filter with an impulse response as given by equation [4]. This filter has an all-pass frequency characteristic and an infinite number of taps. Just a phase offset is introduced to produce the required time delay. The impulse response may be truncated to a low number of tap gains, and with the application of a window function, filter 92 provides effective sample rate conversion. Filter 92 has an overall impulse response of

where w(n) represents the windowing function. In the illustrated embodiment, the Hanning window was used. This represents just a signal filter, however, and to accommodate a varying symbol frequency offset a polyphase filter bank is stored in memory 93. Memory 93 includes filters for a delay ranging from 0.05T.sub.s to T.sub.s in increments of 0.05T.sub.s. The size of the increments may be varied depending on the requirements of the application.

A PS-FSE was taught by Mueller, K. and Werner, J., "A Hardware Efficient Equalizer Structure for Data Transmission," IEEE Transactions of Communication, vol. COM-30, pp. 538-541, March 1982. Equalizer 95 is a T/3-tap spaced PS-FSE which minimizes both the passband mean-squared error with respect to equalizer tap gains, and the phase required for carrier recovery. The real, passband input to equalizer 95 is given by

where z(m) are the V.32 data symbols, f(.multidot.) is the complex baseband channel impulse response, .omega..sub.0 is the sampled carrier angle (including a .+-.1 Hz offset), n.sub.k is channel noise, and the summing interval is over all values of m. An error for equalizer and carrier recovery estimates is

where (C.multidot.X).sub.k is the output of equalizer 95 at a discrete time k, X is a vector of samples x.sub.k as defined in equation [1] (the equalizer state vector), and C is the equalizer tap gain vector. The recursive updates of C.sub.k and .theta..sub.k are:

where

k' is every third sample, IM(z) is the imaginary part of a complex number, .DELTA. is the step size of equalizer 95, and .DELTA..sub.p is the phase-updated step size. z.sub.k is either known training data or an early decision of z.sub.k.

Timing control is suppressed for a training period of 200 symbols following the start of transmission. When clock drift occurs after the training period, a specific time variation is introduced into the channel impulse response, which causes the tap gains to drift relative to the center tap corresponding to the time drift between the near-end and far-end clocks. The drift D is determined by the following:

where M=N/2, N is the number of taps, 2 L is the number of terms used for timing correction relative to the center tap, the first summing interval is from (M-L) to M, and the second summing interval is from (M+1) to (M+L). M=N/2 is best for use with a passband filter such as filter 92. With the phase difference, labelled ".tau.", increasing, the tap gains shift right in distribution, which produces D>0 and the timing update is thus

where .DELTA..sub.T is the step size. In the illustrated V.32 modem, .tau..sub.k' is quantized into intervals of 0.05 normalized to the sampling period. When .vertline..tau..sub.(k'+1) .vertline. crosses the threshold of 0.05, timing control block 96 causes memory 93 to provide a new interpolation filter.

FIG. 4 illustrates a block diagram of a data processing system 100 implementing the V.32 modem of FIG. 3. Data processing system 100 includes a digital signal processor 101 connected to a communication bus 102 for conducting address, data, and control information therebetween. An external memory 103, including an external program memory 104 and an external data memory 105, is also connected to bus 102. External data memory 105 includes memory 93 of modem 80. A sigma-delta type ADC 107 and a sigma-delta type DAC 108 which may be part of a single integrated circuit 106 are also connected to bus 102. DAC 108 is part of transmitter and echo canceller 81 of FIG. 3, and receives data via bus 102 and provides an analog signal to a transmission line coupler 109. Transmission line coupler 109 is also connected to a transmission line 110 for transmission and reception of data. Far-end data is also conducted on transmission line 110 and provided by transmission line coupler 109 to sigma-delta ADC 107. ADC 107 performs the function of ADC 90 of modem 80, and provides data to bus 102.

Except for ADC 107 and DAC 108, which are part of the receiver and transmitter, respectively, data processing system 100 performs all the functions of a V.32 modem in software stored in external program memory 104. Filter coefficients and other data are stored in external data memory 105. By contrast, modem 80 of FIG. 3 illustrated a functional block diagram of a V.32 modem. In an actual software implementation, various signals such as the far end clock are inherently developed from the program flow and are never be explicitly stored or further processed.

DSP 101 is a conventional digital signal processor such as the Motorola DSP 56001 or the like. The software used to implement modem 80 in data processing system 100 is listed in APPENDIX A. However, it should be apparent to those skilled in the art that other software may be used. In addition, different combinations of hardware and software may be used. Preferably, data processing system 100 implements all the functions of a modem on a single integrated circuit.

While the invention has been described in the context of a preferred embodiment, it will be apparent to those skilled in the art that the present invention may be modified in numerous ways and may assume many embodiments other than that specifically set out and described above. For example, different combinations of hardware circuitry and software or microcode executed by a DSP may be used to implement modem 80. In addition, different windowing functions may be used to form coefficients for interpolation filter 92. Accordingly, it is intended by the appended claims to cover all modifications of the invention which fall within the true spirit and scope of the invention.