NDT.net • Nov 2005 • Vol. 10 No.11

Time-of-flight estimation using binary search system identification technique

A. Ragauskas, A. Bagdonas
Telematics Scientific Laboratory
Kaunas University of Technology

Published in ISSN 1392-2114 ULTRAGARSAS, Nr.2(55) 2005


Time–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:
x(t) = r(t)+ gx(t)       (1a)
s(t) = r(t . D)+ gs(t)       (1b)
where the x(t) consists of a reference signal r(t), and Gaussian noise gx(t), while the s(t) consists of the time delayed version of the reference signal r(t-D), and Gaussian noise gs(t). Additionally let us assume that the noise signals are uncorrelated with each other and with the reference 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 [2], 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 [1]. 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 [3]:

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 [3]. 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):

hi (n +1) = hi (n) + ל µ·e(n)·x(n)       (4)
where k is iteration number, ל is step-size parameter, which has a limited range of adjustment in order to insure stability.

Fig. 1. System identification model

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. [5] Hundreds or even thousands of iteration cycles are required to achieve a high TOF resolution.

Improvement of the adaptive algorithm

The 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 results

The 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.

Fig. 2. Time-of-flight measurement using fractional delay approximation of the peak of a 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.

Fig. 3. Sound velocity (a) and attenuation (b) functions of Plexiglas used in the simulations

Fig. 4. Transmitted and received signals (simulation)

Parameter Value Variation (influence test)
Sampling frequency (fs) 100 MHz none
Sampled signal length (N) 512 points none
Center frequency of the reference signal (freq) 3.5 MHz none
TX transducer center frequency 3.5 MHz 3.0 .. 4.0 MHz
TX transducer bandwidth 3.5 MHz (or ±1.75 MHz) 2.0 .. 4.5 MHz
RX transducer center frequency 3.5 MHz 3.0 .. 4.0 MHz
RX transducer bandwidth 3.5 MHz (or ±1.75 MHz) 2.0 .. 4.5 MHz
SNR (if not other specified) 200 dB 0 .. 90 dB
Table 1. Parameters for simulations

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.

Fig. 5. TOF standard deviation for the proposed (dash-dot line), Fourier Transform-Phase-Slope determination (dotted line) and parabolic fit of the peak of the correlation function (solid line) methods


Under 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.


Fig. 6. TOF error of the proposed method

Fig. 7. TOF standard deviation of the proposed (dash-dot line), Fourier Transform-Phase-Slope method (dotted line) and parabolic fit of the peak of a correlation function (solid line) methods

Fig. 8. TOF standard deviation of the proposed (dash-dot line), Fourier Transform-Phase-Slope (dotted line) and parabolic fit of the peak of a correlation function (solid line) methods

Fig. 9. TOF standard deviation of the proposed (dash-dot line), Fourier Transform-Phase-Slope (dotted line) and parabolic fit of the peak of a correlation function (solid line) methods

Fig. 10. TOF standard deviation of the proposed (dash-dot line), Fourier Transform-Phase-Slope determination (dotted line) and parabolic fit of the peak of a correlation function (solid line) methods


  1. Dixon R. C. Spread spectrum systems with commercial applications. Third Edition, ISBN 0-471-59342-7. New York. 1994.
  2. Kay S. M. Fundamentals of statistical signal processing: Estimation theory. Prentice Hall. 1994.
  3. Dooley S. R. and Nandi A. K. Comparison of subsample time delay estimation methods applied to narrowband signals. IOP Measurement Science & Technology. September 1998. Vol. 9(9). P.1400-1408.
  4. So H. C. Noisy input–output system identification approach for time delay estimation. Signal processing’82. January 2002. P. 1471– 1475.
  5. Dooley S. R. and Nandi A. K. Adaptive subsample time delay estimation using Lagrange interpolators. IEEE Signal Processing Letters. March 1999. Vol. 6(3). P.65-67.
  6. Maskell D. L. and Wood G. S. Adaptive subsample delay estimation using a Windowed quadrature phase detector. IEEE TENCON – 2003. Advanced DSP (X03) session.
  7. Grennberg A., Sandell M. Estimation of subsample time delay differences in narrowband ultrasonic echoes using the Hilbert transform. IEEE Transactions on ultrasonics, ferroelectrics and frequency control. Vol. 41. No.5. P. 588-595.
  8. Lai X., Torp H. Member IEEE, Interpolation methods for time-delay estimation using cross-correlation method for blood velocity measurement. IEEE Transactions on ultrasonics, ferroelectrics and frequency control. Vol. 46. No. 2. P. 277-290.
  9. Torp H., member IEEE Kristoffersen K., Angelsen B.A.J., senior member, IEEE. Autocorrelation techniques in color flow imaging: signal model and statistical properties of the autocorrelation estimates. IEEE Transactions on ultrasonics, ferroelectrics and frequency control. Vol. 41. No. 5. P. 604-612.
  10. Lai X., Torp H., member IEEE Kristoffersen K. An extended autocorrelation method for estimation of blood velocity. IEEE Transactions on ultrasonics, ferroelectrics and frequency control. Vol.44. No. 6. P. 1332-1342.
  11. Rabben S. I., Bjaerum S., Sorhus V., Torp H. Ultrasound-based vessel wall tracking: an auto-correlation technique with RF center frequency estimation. Ultrasound in Med. & Biol. Vol. 28. No. 4. P. 507-517.
  12. Umekage Y., Nagaoka Y., Eguchi O. Flowmeter, Patent no. EP1243901, Issued: 25 September, 2002.
  13. Freund W., Letton W. and others. Method and apparatus for measuring the time of flight of a signal, Patent no. EP5983730, Issued: 16 November, 1999.
  14. Ragauskas A. V., Danilov V. G. Radio signal receiver. Patent No. SU862364, Issued: 7 September, 1981.
  15. Feller M. F. Ultrasonic transit time flow sensor and method, Patent No. US6370963, Issued: 16 April, 2002.
  16. Sang-Yong Nam. Ultrasonic flow velocity measuring apparatus. Patent No. US6435038, Issued: 20 August, 2002.
  17. Vaseghi Saeed V. Advanced digital signal processing and noise reduction, second edition. ISBN 0-471-626962-9. John Willey & Sons Ltd. 2000.
  18. Haykin Simon. Adaptive filter theory, third edition. ISBN 013322760X. Prentice Hall. 1995.

© NDT.net |Top|