|NDT.net Nov 2005 Vol. 10 No.11|
Time-of-flight estimation using binary search system identification techniqueA. Ragauskas, A. Bagdonas
Telematics Scientific Laboratory
Kaunas University of Technology
Published in ISSN 1392-2114 ULTRAGARSAS, Nr.2(55) 2005
IntroductionTime–of–flight (TOF) estimation is the process of determining the relative shift D between a reference x(t) (or transmitted) signal and delayed s(t) (or received) signal:
The TOF lies at the core of many modern signalprocessing algorithms. In medical ultrasound for example, the TOF is employed in blood flow estimation, tissue motion measurement, tissue elasticity estimation and a number of other algorithms. To these and numerous other algorithms the TOF accuracy and computational cost are critical important.
The TOF has been widely and meticulously studied over the past forty years. Early work focused on applications in radar and sonar. While efforts over the past two decades have broadened to include speech processing, medical imaging, and a broad array of other applications, classical TOF there are a few approaches depending on the reference signal and other conditions.
TOF measurement methods when the reference signal is random or when TOF measurement is based on direct time-to-digital conversion have been analyzed in studied literature [12-16]. A some kind of “critical point” inside the signal, where the signal energy have maximum value or other conditions are detected, is applied to the signal for determining a point of measurement (positive or negative slope zero crossing, maximum value, a special marker, etc.). The disadvantage of the method is that a signal-tonoise ratio could be changed only by increasing the power of used signals. There are physical and other limitations on a maximal energy used in the measurement.
For the case of a deterministic reference signal, the classical methods are generally based on the second order statistics , notably computing the lag for which the cross-correlation between the reference and the delayed signal have a maximum value. Another popular method involves the minimization of the squared error (a least squares approach) between the signals for different lags. The advantage of the statistical methods is so called “process gain” means that the signal-to-noise ratio could be increased by increasing the length (or bandwidth) of the reference signal . Up to 60 dB “process gain” is available in practical situations. The higher gain is limited by a sampling jitter and clock stability. A popular method to estimate the time delay is to search for the global extreme R(tm) of the crosscorrelation function :
As the true value of D is not an integer, the estimate may be improved by the well-known parabolic fit:
The similar is Fourier Transform-Phase-Slope determination method in TOF measurements . The method makes use of the fact that the cross-spectral density estimate is Pxs(w) = Prr·(w)ejq, where q = - w·D and Prr (w) is power spectrum of the signal. Slope of the phase is determined by linear regression of weighted data points within the signal bandwidth and a weighted y-intercept.
Other methods to determinate the TOF are based on system identification [4, 5]. The time delay estimation is considered as a noisy input–output FIR/IIR system identification problem where the task is to find the unknown transfer function h(n) using the adaptive filter. Most common adoption algorithm is the least-mean square (LMS):
The LMS algorithm has many advantages (due to its computational simplicity), but its convergence rate is slow. The improvements of the convergence [4, 5] are based on assumption that hi (D. (k)) , then estimated delay is updated during iteration:
The biggest disadvantage of this method is a slow convergence rate.  Hundreds or even thousands of iteration cycles are required to achieve a high TOF resolution.
Improvement of the adaptive algorithmThe literature analysis shows, that the most accurate results could be observed by the system identification method. The biggest disadvantage of the method could be avoided by dramatical reduction of iteration cycles. We propose to change Eq.5 of estimation of new TOF cycle to the binary tree search algorithm.
The binary search technique is a fundamental method for locating an element of a particular value within a sequence of sorted elements. The idea is to eliminate half of the search space with each comparison. First, the middle element of the sequence is compared to the value we are searching for. If this element matches the value we are searching for, we are done. If, however, the middle element is “less than” the value we have chosen for (as specified by the relation used to specify a total order over the set of elements), then we know that if the value exists in the sequence, it must exist somewhere after the middle element. Therefore, we can eliminate the first half of the sequence from our search and simply repeat the search in the exact same manner on the remaining half of the sequence. If, however, the value we are searching for comes before the middle element, then we repeat the search on the first half of the sequence.
Lets take a look to Eq.3. There we have three points of the main lobe of the correlation function. The peak value is somewhere in between (from tm - 1 to tm ) or in between (from tm to tm +1). If we decide that our maximum is in one of the interval then again we could divide the interval in two parts and search for another interval. All the time we repeat this by two decreases the interval length. This is true only if the lobe of correlation is monotonous from both sides. Everything sounds like in the binary search. Actually we do not need to calculate Eq.3, it is enough to compare the values of R(tm - 1) and R(tm +1):
then Dt > 0 (condition to select interval from tm to tm +1 ) could be extracted to two expressions:
Eq. 9a it is not our case, because R(tm -1)+ R(tm +1) ≤ 2. R(tm ) is not valid in our case, and Eq. 9b is only one solution of Eq.8. We have showed that it is enough to check R(tm -1) ≤ R(tm +1) condition and choose the interval (from tmto tm +1) if this condition is true, and the interval (from tm -1 to tm ) if the condition is false.
We propose to use sin(x)/x FIR reconstruction filter as a fractional delay element in Fig.1. The impulse response of such a filter is well known from the Shannon’s reconstruction theorem:
where x(k) is the correlation function, T is the sampling period and fs is the sampling frequency.
Modeling and resultsThe simulated system is showed in Fig. 2. We were using the signal phase modulation by the 13-order Barker code. The synthesizer then is calculating the complex waveform of a signal to be transmitted. The DAC is converting the digital code stream to the analogue signal, which then is amplified and transmitted by a transmitting transducer to the medium. The receiver includes the receiving transducer and the amplifier. The received analog signal is converted back to the digital form and the cross-correlation function of the transmitted and received signals is calculated. The time of flight is extracted from the correlation function by a special unit by using the binary search technique to search for the peak of the correlation function.
Various distortions are canceled by introducing calibration step. The reference signal (used for correlation calculation) is copy of the received signal at the defined conditions (TOF sense).
Simulation model of medium, where the signal is propagating, will not include effects of nonlinear harmonics generation. The frequency dependent attenuation and velocity of sound in the medium are evaluated. Signal is split to the harmonic components traveling from the transmitter to the receiver:
where 2·In In is the amplitude of the n-th harmonic; a(w) is the attenuation coefficient; c0(w)is the velocity of sound; x is the distance between receiver and transmitter; N(t) is the noise.
The receiving and transmitting transducers were modeled as resonance systems with defined resonance frequencies and bandwidths. The pulse response of such a system is:
where Dw is the bandwidth of the transducer; w0 is the resonance frequency of the transducer. Another amplifiers, other electronic circuit and transducers effects are not simulated. Simulation tests had been conduced to evaluate the delay estimation performance of the proposed and two prior art methods. Performance criteria’s are showed in Table 1. Each test had all criteria’s fixed except one, which was variable during the tests. Each point was calculated from 100 independent measurements (see Fig.6). The medium parameters were fixed during simulations.
ConclusionsUnder the simulation conditions considered here, the new binary search of peak of correlation method had a higher possible resolution limit than the parabolic fit of the peak of a correlation function and the Fourier Transform- Phase-Slope determination methods (see Fig. 5). The proposed method is less sensitive to the frequency dependent attenuation and velocity of waves in the medium, as well to the variation of influence factors (see Fig. 6 to 10). Increasing the length and coding of the reference signal one could achieve the required SNR ratio for defined accuracy of TOF estimation. The computation speed is dramatically reduced from hundreds or even thousands iterations to ten without accuracy degradation. The new binary search adoption algorithm could be used in another system identification applications as well. Modeling results show, that it is possible to achieve few ps standard deviation of time–of –flight measurement or 1/10000 of the sampling period.