Use FFTs To Time Align Asynchronous Waveforms

Feb. 4, 2002
A basic Fourier transform identity coupled with an iterative convergence algorithm provides a powerful method to align band-limited signals.

Recently, I wrote automated test software for a multichannel data-acquisition system that I had designed, where sampled waveform accuracy and repeatability were very important. The input waveforms pass through anti-alias filtering, gain, and offset stages before being sampled. It's important to verify that this analog circuitry, which precedes the analog-to-digital converter (ADC), operates properly. One good method is to check the pulse response of the analog circuitry by running a pulse through it and examining the resulting waveform samples.

Prior to testing the analog filters for go/no-go acceptability, a tolerance window must be determined. Then, any filter whose response lies outside the window is rejected. This window may be created by a Spice simulation of the filter using Monte Carlo variation of the component values. Another option is measuring a number of known-good units and calculating an average response and variation from the measurement data.

But a problem arises when the pulse excitation isn't synchronized with the a-d sampling system. This often happens with independent test-equipment modules. The samples from one acquisition exhibit a random time shift relative to samples from another acquisition, or to the reference Spice simulation. Given an analog waveform input, the sampling system may record an infinite number of sample sequences, depending on the phase of the sample clock relative to the input signal (Fig. 1).

Even though the two sample sequences in Figure 1 represent the same analog waveform, averaging or comparing them is difficult due to the time shift between them. You can't simply pair up corresponding samples because the two sequences sample slightly different points on the analog waveform. If you increase the sample rate, either in hardware or by sample interpolation in software, the situation improves. But it never becomes ideal.

Ideally, you want to time shift the samples of each independent sequence to a fixed reference point in time. Then, the sequences may be directly combined and compared, sample by sample. In this application, it's convenient to shift all waveform samples some fraction of one sample period, so that the first positive sample (just past a rising-edge zero-crossing) shifts earlier in time to exactly the zero-crossing. Such a time shift is equivalent to synchronizing the sampling clock to a zero-crossing of the input test square wave.

This is a fine plan, but how do you shift to new sample points along an analog wave without the original wave? After sampling, all that remains is the set of samples acquired from the particular points at which sampling took place. But if the analog signal is properly bandwidth limited prior to sampling, then the samples contain all of the information in the original wave. In other words, all frequencies greater than half the sampling frequency (in this baseband application) must be suppressed to below the sampler's least significant bit (LSB). This provides the information necessary to accurately reconstruct samples in between the actual samples.

To perform the time shift, we can take advantage of a Fourier transform identity. These identities link operations in the time domain to equivalent operations in the frequency domain (see the table). Some operations are equivalent in their implementation. For instance, Identities 2 and 3 show that multiplication by a constant in the time domain is equivalent to multiplication by the same constant in the frequency domain. Or, the addition of two time-domain waveforms is equivalent to adding their frequency-domain counterparts.

But some identities involve very different operations, like Identity 5. It states that multiplication of two time-domain waveforms is equivalent to the convolution of their frequency-domain transforms. Identity 4 shows that to perform a constant time shift of c in the time domain, you may perform a constant-slope phase shift in the frequency domain, which the multiplication by ejcƒÖ indicates. This is exactly the operation required to time align the samples for the application example in this article.

Multiplication by ejcƒÖ in the frequency domain might not look like a phase-shifting operation, but don't be fooled. Each frequency-domain sample, F(ƒÖn), produced by the Fourier transform is a complex vector that can be represented as a magnitude and phase A?ÚƒÆ. Using Euler's equation and trigonometric identities yields:

or a vector of length 1 with an angle of cƒÖn. Therefore,

shows that multiplying a complex vector by ejcƒÖn results in a simple addition of cƒÖn to its phase, without affecting its magnitude. Because the cƒÖn term is directly proportional to frequency ƒÖn, the amount of phase shift to be applied to the frequency-domain samples increases linearly with frequency.

To accomplish our time shift, we will transform our time samples to the frequency domain and back, which means an additional requirement to ensure accurate results. The time-domain signal must exhibit an exact integer number of periods within the frame of N samples to be transformed. If this requirement isn't satisfied, a discontinuity will exist between the first and last samples of the frame. This discontinuity causes spectral "leakage" in the frequency domain, leading to ringing at the beginning and end of the time sequence when the inverse transform is performed.

The requirement for periodicity within the sample frame is frequently met by windowing the time data with a function that forces the beginning and ending portions of the time waveform to have the same value and slope. This eliminates any discontinuity between them. In many cases, this is the only re-course when real-world data won't line up nicely within the sample frame.

But in this application, it's easy to place our pulse waveform within the sample frame such that the waveform matches itself at the beginning and end of the frame. It forms a perfectly periodic signal, with one period per sample frame. Therefore, no windowing is necessary, and the waveform may be transformed to the frequency domain and back without introducing spectral leakage or time-domain ringing.

Here is the method to obtain our time shift:

  • Fourier transform the band-limited, periodic waveform sample frame to the frequency domain;
  • Apply a constantly increasing (linear) phase shift to all frequency samples;
  • Inverse Fourier transform back to the time domain.

The amount of phase shift applied to each frequency sample is nδ, where n is the index of the frequency sample (0 for the dc frequency sample, 1 for the lowest frequency, etc.), and δ is the phase increment required to produce the desired time shift, up to 360° (2¼ radians) for one full sample period of shift. Now, the only remaining problem is finding the right value for δ—the phase shift increment in the frequency domain that will produce the required time shift in the time domain.

If our underlying analog waveform were a perfectly predictable wave, such as a triangle or sine, we could predict the exact time shift required by interpolating between our original time samples. We could then perform the same interpolation on all samples and avoid the frequency domain processing altogether! Nature, however, usually isn't so cooperative, and our filtered square waves need a different approach.

Because the analog waveform near the zero-crossing forms a nearly straight line, it makes sense to try an iterative method, where we approach the zero-crossing by assuming a straight-line waveform between samples. This approach converges to 16-bit accuracy in just a few iterations.

As shown in Figure 2, points A and B represent two original samples of the analog wave. We want to shift sample B left (earlier) to the zero-crossing at B0. The sample interval is T. If we assume a straight line between A and B, we can specify a time shift of \\[TB/(B - A)\\] to shift B to B'. For example, if sample A has a value of -100, and sample B is 200, the time shift becomes:

200T/\\[200 - (-100)\\] = (2/3)T

to shift B to B'. We then repeat the linear interpolation, using A and B' as the endpoints, to arrive at a closer estimate. This iteration very quickly converges on the exact time shift required to move B to B0 within the resolution of our sampling system.

A pseudo-C algorithm can be written for acquiring and time aligning a single cycle of a test waveform (see the code listing). The points (x1, y1) and (x2, y2) in the code are the coordinates of the two endpoints of the linear approximation to the filtered square wave (initially A and B, respectively, in Figure 2). The x, or time, axis is normalized such that 0.0 is placed at the initial point B and -1.0 is at A.

This way, one x unit equals one sample interval, and the required time shift always lies between 0.0 and 1.0. At each iteration, (x1, y1) and (x2, y2) are updated to hold the most recent two zero-crossing approximations found. The point (x3, y3) is the current zero-cross approximation (B' in Figure 2 for the first iteration).

The vector multiplication required to perform the frequency-domain phase shift is done in rectangular coordinates:

(A + jB)(C + jD)
= (AC - BD) + j(BC + AD)

where A + jB is the original complex vector and C + jD is a unit-length vector with an angle equal to the desired phase shift (rotation) angle. If θ is the rotation angle, then C = cosθ and D = sinθ.

If the frequency of the square-wave signal source is such that one cycle takes place in approximately a power of two samples of the data-acquisition system, then one cycle of the test waveform may be acquired and processed using a fast and convenient FFT algorithm as shown in the code listing.

My system had a sample rate of 48.8 kHz, so I used 64-point FFTs and a 763-Hz input square wave. One cycle of 763 Hz = 1.31 ms = 64 samples at 1/48.8 kHz. Figure 3 shows an actual sequence of 12-bit 2's complement samples before alignment (X's) and after alignment (O's) to the zero-crossing. This particular sequence required a shift of -0.347 sample to move the first positive sample (number six, originally at value +636) back in time to the zero-crossing.

Once the sampled wave is aligned in time using this technique, accumulating or comparing it with other aligned waveforms is a simple matter of operating on sequential samples that start at the zero-crossing sample. This provides a powerful and convenient method for performing sample time shifting on data that's not synchronized to the sample clock.

In my application, I implemented the technique to align data gathered from dozens of known-good boards to create an averaged reference waveform and a tolerance window. I also used it during board test to align incoming test waveforms with the reference wave and tolerance window stored in memory for go/no-go testing.

To download the listings, click Download the Code.


To join the conversation, and become an exclusive member of Electronic Design, create an account today!