# Connexions

You are here: Home » Content » Signal and Information Processing for Sonar » Time-Delay Estimation

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

Course by: Laurence Riddle. E-mail the author

# Time-Delay Estimation

Module by: Don Johnson. E-mail the author

An important signal parameter estimation problem is time-delay estimation. Here the unknown is the time origin of the signal: slθ=slθ s l θ s l θ . The duration of the signal (the domain over which the signal is defined) is assumed brief compared with the observation interval L L. Although in continuous time the signal delay is a continuous-valued variable, in discrete time it is not. Consequently, the maximum likelihood estimate cannot be found by differentiation, and we must determine the maximum likelihood estimate of signal delay by the most fundamental expression of the maximization procedure. Assuming Gaussian noise, the maximum likelihood estimate of delay is the solution of min θ θ (rsθ)T K n -1(rsθ) θ r s θ K n r s θ The term sT K n -1s s K n s is usually assumed not to vary with the presumed time origin of the signal because of the signal's short duration. If the noise is white, this term is constant except near the "edges" of the observation interval. If not white, the kernel of this quadratic form is equivalent to a whitening filter. As discussed later, this filter may be time varying. For noise spectra that are rational and have only poles, the whitening filter's unit-sample response varies only near the edges (see the example). Thus, near the edges, this quadratic form varies with presumed delay and the maximization is analytically difficult. Taking the "easy way out" by ignoring edge effects, the estimate is the solution of max θ θ rT K n -1sθ θ r K n s θ Thus, the delay estimate is the signal time origin that maximizes the matched filter's output.

In addition to the complexity of finding the maximum likelihood estimate, the discrete-valued nature of the parameter also calls into question the use of the Cramér-Rao bound. One of the fundamental assumptions of the bound's derivation is the differentiability of the likelihood function with respect to the parameter. Mathematically, a sequence cannot be differentiated with respect to the integers. A sequence can be differentiated with respect to its argument if we consider the variable to be continuous valued. This approximation can be used only if the sampling interval, unity for the integers, is dense with respect to variations of the sequence. This condition means that the signal must be oversampled to apply the Cramér-Rao bound in a meaningful way. Under these conditions, the mean-squared estimation error for unbiased estimators can be no smaller than the Cramér-Rao bound, which is given by Eε21 k , l kl K n -1k,lskθslθ ε 2 1 k l k l K n k l s k θ s l θ which, in the white-noise case, becomes

Eε2 σ n 2lsl2 ε 2 σ n 2 l s l 2
(1)
Here, s· s · denotes the "derivative" of the discrete-time signal. To justify using this Cramér-Rao bound, we must face the issue of whether an unbiased estimator for time delay exists. No general answer exists; each estimator, including the maximum likelihood one, must be examined individually.

## Example 1

Assume that the noise is white. Because of this assumption, we determine the time delay by maximizing the match-filtered observations. argmaxθ l lrlslθ=θ^ML θ l l r l s l θ θ ML The number of terms in the sum equals the signal duration. Figure 1 illustrates the match-filtered output in two separate situations; in one the signal has a relatively low-frequency spectrum as compared with the second.

Because of the symmetry of the autocorrelation function, the estimate should be unbiased so long as the autocorrelation function is completely contained within the observation interval. Direct proof of this claim is left to the masochistic reader. For sinusoidal signals of energy E E and frequency ω 0 ω 0 , the Cramér-Rao bound is given by Eε2= σ n 2 ω 0 2E ε 2 σ n 2 ω 0 2 E . This bound on the error is accurate only if the measured maximum frequently occurs in the dominant peak of the signal's autocorrelation function. Otherwise, the maximum likelihood estimate "skips" a cycle and produces values concentrated near one of the smaller peaks. The interval between zero crossings of the dominant peak is π2 ω 0 2 ω 0 ; the signal-to-noise ratio E σ n 2 E σ n 2 must exceed 4π2 4 2 (about 0.5). Remember that this result implicitly assumed a low-frequency sinusoid. The second example demonstrates that cycle skipping occurs more frequently than this guideline suggests when a high-frequency sinusoid is used.

The size of the errors encountered in the time-delay estimation problem can be more accurately assessed by a bounding technique tailored to the problem: the Ziv-Zakai bound (Wiess and Weinstein, Ziv and Zakai). The derivation of this bound relies on results from detection theory (Chazan, Zakai, and Ziv). 1 Consider the detection problem in which we must distinguish the signals slτ s l τ and slτ+Δ s l τ Δ while observing them in the presence of white noise that is not necessarily Gaussian. Let hypothesis 0 0 represent the case in which the delay, denoted by our parameter symbol θ θ, is τ τ and 1 1 the case in which θ=τ+Δ θ τ Δ . The suboptimum test statistic consists of estimating the delay, then determining the closest a priori delay to the estimate. θ ^ 0 1 τ+Δ2 θ 0 1 τ Δ 2 By using this ad hoc hypothesis test as an essential part of the derivation, the bound can apply to many situations. Furthermore, by not restricting the type of parameter estimate, the bound applies to any estimator. The probability of error for the optimum hypothesis test (derived from the likelihood ratio) is denoted by P e τΔ P e τ Δ . Assuming equally likely hypotheses, the probability of error resulting from the ad hoc test must be greater than that of the optimum. P e τΔ1/2Prε>Δ2| 0 +1/2Prε<Δ2| 1 P e τ Δ 12 0 ε Δ 2 12 1 ε Δ 2 Here, ε ε denotes the estimation error appropriate to the hypothesis. ε={ θ ^τ  if   under 0 θ ^τΔ  if   under 1 ε θ τ under 0 θ τ Δ under 1 The delay is assumed to range uniformly between 0 and L L. Combining this restriction to the hypothesized delays yields bounds on both τ τ and Δ Δ: 0τ<LΔ 0 τ L Δ and 0Δ<L 0 Δ L . Simple manipulations show that the integral of this inequality with respect to τ τ over the possible range of delays is given by 2 0LΔ P e τΔd τ 1/20LPr|ε|>Δ2| 0 d τ τ 0 L Δ P e τ Δ 12 τ 0 L 0 ε Δ 2 Note that if we define L2 P Δ2 L 2 P Δ 2 to be the right side of this equation so that P Δ2=1L0LPr|ε|>Δ2| 0 d τ P Δ 2 1 L τ 0 L 0 ε Δ 2 P · P · is the complementary distribution function 3 of the magnitude of the average estimation error. Multiplying P Δ2 P Δ 2 by Δ Δ and integrating, the result is 0LΔ P Δ2d Δ =-20L2x2d P d x d x Δ 0 L Δ P Δ 2 -2 x 0 L 2 x 2 x P The reason for these rather obscure manipulations is now revealed: Because P · P · is related to the probability distribution function of the absolute error, the right side of this equation is twice the mean-squared error Eε2 ε 2 . The general Ziv-Zakai bound for the mean-squared estimation error of signal delay is thus expressed as Eε21L0LΔ0LΔ P e τΔd τ d Δ ε 2 1 L Δ 0 L Δ τ 0 L Δ P e τ Δ In many cases, the optimum probability of error P e τΔ P e τ Δ does not depend on τ τ, the time origin of the observations. This lack of dependence is equivalent to ignoring edge effects and simplifies calculation of the bound. Thus, the Ziv-Zakai bound for time-delay estimation relates the mean-squared estimation error for delay to the probability of error incurred by the optimal detector that is deciding whether a nonzero delay is present or not.

Eε21L0LΔ(LΔ) P e Δd Δ L26 P e L0L(Δ22Δ33L)d P e d Δ d Δ ε 2 1 L Δ 0 L Δ L Δ P e Δ L 2 6 P e L Δ 0 L Δ 2 2 Δ 3 3 L Δ P e
(2)
To apply this bound to time-delay estimates (unbiased or not), the optimum probability of error for the type of noise and the relative delay between the two signals must be determined. Substituting this expression into either integral yields the Ziv-Zakai bound.

The general behavior of this bound at parameter extremes can be evaluated in some cases. Note that the Cramér-Rao bound in this problem approaches infinity as either the noise variance grows or the observation interval shrinks to 0 (either forces the signal-to-noise ratio to approach 0). This result is unrealistic as the actual delay is bounded, lying between 0 and L L. In this very noisy situation, one should ignore the observations and "guess" any reasonable value for the delay; the estimation error is smaller. The probability of error approaches 1/2 12 in this situation no matter what the delay Δ Δ may be. Considering the simplified form of the Ziv-Zakai bound, the integral in the second form is 0 in this extreme case. Eε2L212 ε 2 L 2 12 The Ziv-Zakai bound is exactly the variance of a random variable uniformly distributed over 0 L1 0 L 1 . The Ziv-Zakai bound thus predicts the size of mean-squared errors more accurately than does the Cramér-Rao bound.

## Example 2

Let the noise be Gaussian of variance σ n 2 σ n 2 and the signal have energy E E. The probability of error resulting from the likelihood ratio test is given by P e Δ=QE2 σ n 2(1ρΔ) P e Δ Q E 2 σ n 2 1 ρ Δ The quantity ρΔ ρ Δ is the normalized autocorrelation function of the signal evaluated at the delay Δ Δ. ρΔ=1ElslslΔ ρ Δ 1 E l s l s l Δ Evaluation of the Ziv-Zakai bound for a general signal is very difficult in this Gaussian noise case. Fortunately, the normalized autocorrelation function can be bounded by a relatively simple expression to yield a more manageable expression. The key quantity 1ρΔ 1 ρ Δ in the probability of error expression can be rewritten using Parseval's Theorem. 1ρΔ=12πE0π2|Sω|2×(1cosωΔ)d ω 1 ρ Δ 1 2 E ω 0 2 S ω 2 1 ω Δ Using the inequality 1cosxx2 1 x x 2 , 1ρΔ 1 ρ Δ is bounded from above by minΔ2β222 Δ 2 β 2 2 2 , where β β is the root-mean-squared (RMS) signal bandwidth.

β2=ππω2|Sω|2d ω ππ|Sω|2d ω β 2 ω ω 2 S ω 2 ω S ω 2
(3)
Because Q· Q · is a decreasing function, we have P e ΔQμminΔ Δ * P e Δ Q μ Δ Δ * , where μ μ is a combination of all of the constants involved in the argument of Q· Q · : μ=Eβ24 σ n 2 μ E β 2 4 σ n 2 . This quantity varies with the product of the signal-to-noise ratio E σ n 2 E σ n 2 and the squared RMS bandwidth β2 β 2 . The parameter Δ * =2β Δ * 2 β is known as the critical delay and is twice the reciprocal RMS bandwidth. We can use this lower bound for the probability of error in the Ziv-Zakai bound to produce a lower bound on the mean-squared estimation error. The integral in the first form of the bound yields the complicated, but computable result Eε2L26QμminL Δ * +14μ2P χ 3 2 μ2minL2 Δ * 2232πLμ3(1(1+μ22minL2 Δ * 2)eμ2minL2 Δ * 22) ε 2 L 2 6 Q μ L Δ * 1 4 μ 2 P χ 3 2 μ 2 L 2 Δ * 2 2 3 2 L μ 3 1 1 μ 2 2 L 2 Δ * 2 μ 2 L 2 Δ * 2 2 The quantity P χ 3 2 · P χ 3 2 · is the probability distribution function of a χ2 χ 2 random variable having three degrees of freedom.4 Thus, the threshold effects in this expression for the mean-squared estimation error depend on the relation between the critical delay and the signal duration. In most cases, the minimum equals the critical delay Δ * Δ * , with the opposite choice possible for very low bandwidth signals.

The Ziv-Zakai bound and the Cramér-Rao bound for the time-delay estimation problem are shown in Figure 2. Note how the Ziv-Zakai bound matches the Cramér-Rao bound only for large signal-to-noise ratios, where they both equal 1/4μ2= σ n 2Eβ2 14 μ 2 σ n 2 E β 2 . For smaller values, the former bound is much larger and provides a better indication of the size of the estimation errors. These errors are because of the "cycle skipping" phenomenon described earlier. The Ziv-Zakai bound describes them well, whereas the Cramér-Rao bound ignores them.

## Footnotes

1. This result is an example of detection and estimation theory complementing each other to advantage.
2. Here again, the issue of the discrete nature of the delay becomes a consideration; this step in the derivation implicitly assumes that the delay is continuous valued. This approximation can be greeted more readily as it involves integration rather than differentiation (as in the Cramér-Rao bound).
3. The complementary distribution function of a probability distribution function Px P x is defined to be P x=1Px P x 1 P x , the probability that a random variable exceeds x x.
4. This distribution function has the "closed-form" expression P χ 3 2 x=(1Qxx2ex2) P χ 3 2 x 1 Q x x 2 x 2 .

## References

1. A.J. Weiss and E. Weinstein. (1983, April). Fundamental limitations in passive time delay estimation: I. Narrow-band systems. IEEE Trans. Acoustics, Speech and Signal Processing, ASSP-31, 472-486.
2. J. Ziv and M. Zakai. (1969, May). Some lower bounds on signal parameter estimation. IEEE Trans. Info. Th., IT-15, 386-391.
3. D. Chazan, M. Zakai, and J. Ziv. (1975, January). Improved lower bounds on signal parameter estimation. IEEE Trans. Info. Th., IT-21, 90-93.

## Content actions

### Give feedback:

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

### Reuse / Edit:

Reuse or edit collection (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.

| Reuse or edit module (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.