WO2007007408A1

WO2007007408A1 - Delay estimation apparatus and method

Info

Publication number: WO2007007408A1
Application number: PCT/JP2005/012980
Authority: WO
Inventors: Yihong Qi; Ryuji Kohno
Original assignee: National Institute of Information and Communications Technology
Current assignee: National Institute of Information and Communications Technology
Priority date: 2005-07-07
Filing date: 2005-07-07
Publication date: 2007-01-18
Anticipated expiration: 2008-01-07
Also published as: DE602005019114D1; EP1910862B1; ATE456065T1; US20090296783A1; JP2009500592A; EP1910862A1

Abstract

The delay estimation apparatus (34) according to this invention comprises: a correlator (41) which generates a correlation function between a received signal and a supplied template waveform; an AD (analog to digital) converter (42) which samples said correlation function generated at said correlator into discrete samples; and an arithmetic operation section (43) which obtains time delays of multipath components of said received signal based on said discrete samples generated at said AD converter, wherein said arithmetic operation section includes an iteration procedure where in each iteration, the time delay and the amplitude of the strongest signal component are estimated based on the present sample sequence, and said sample sequence is updated by deducting the estimated strongest component from said sample sequence; said iteration is terminated when a termination criterion is satisfied. Specifically, in each said iteration, said amplitude estimate of said strongest component is given by the maximum likelihood (ML) solution. The delay estimation apparatus according to this invention can be adopted for the first arrival detection or wireless ranging.

Description

DESCRIPTION DELAY ESTIMATION APPARATUS AND METHOD

Technical Field

The present invention relates to a method and an apparatus for delay estimation of radio signals in a wireless communication system.

Background Art

Wireless ranging is to estimate the distance between a transmitter and a receiver by using radio signals propagating from the pair of the transmitter and the receiver in a wireless communication system. It has become an important issue motivated by an increasing demand from a variety of wireless networks. Specifically, ranging in a UWB (ultra wide band) system has been recognized as a key feature of the recently developing IEEE WPAN 802.15.4a standard. In many practical situations, a radio signal is inevitably subject to multipath propagation, which is also a main characteristic of UWB signals. From the viewpoint of ranging, the common wisdom is to estimate the time delay of the first arriving component of the received signal. However, the main difficulty lies in that the estimation performance would be degraded considerably when the energy of the first arriving component is not dominant among multipath components of the received signal.

Several schemes have been proposed for the first arrival detection. A generalized maximum likelihood (ML) method [1] ([1] J-Y. Lee and A. R. Scholtz, "Ranging in a dense mulitpath environment using a UWB radio link," IEEE J. Selected Areas in Communications, vol. 20, pp. 1677-83, December 2002) is examined in a UWB system. With conventional CDMA (Code Division Multiple Access) and WCDMA (Wideband CDMA) signals, techniques such as the minimum variance method [2] ([2] J. Vidal, M. Najar and R. Jativa, "High resolution time-of-arrival detection for wireless positioning systems," Proc. 5βth IEEE Vehicular Technology Conference (VTC 2002-Fall) , vol. 4, pp. 2283-7, September 2002) and the binary hypothesis test [3] ([3] J. Vidal and R. E. Jativa, "First arriving path detection for subscriber location in mobile communication systems," Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing 2002 (ICASSP 2002), vol. 3, pp. 2733-36, May 2002) have been explored. These schemes exhibit various advantages in certain circumstances. Yet their formulations mainly start from analog signals or discrete samples of received signals, hence may not be directly applicable to some practical systems, e.g., some UWB systems. High computational complexity is another limitation.

Disclosure of the Invention

This invention presents a first arrival detection method and an apparatus for a wireless communication system, in particular, for a UWB system. In this invention, an iterative scheme is devised. In each iteration step, the present strongest signal component is estimated, and is removed from sample data to be processed in the next iteration. The iteration is terminated when no more such a component above certain threshold can be detected. The smallest delay estimate is taken as the first arrival estimate. Compared with existing schemes, this invention can greatly improve the estimation accuracy when the first arriving signal component is not dominant among multipath components of a received signal, and the computation complexity is very low.

The first arrival detection apparatus comprises: correlation means which generates a correlation output based on a received signal and a supplied template waveform, AD conversion means which uniformly samples the correlation output generated by the correlation means into discrete samples; and arithmetic operation means which estimates the time delay of the first arriving signal component based on the discrete samples generated by the AD conversion means, specifically, an iterative scheme is devised: in each iteration, samples representing the dominant component of a present sample sequence are selected first, the delay and the amplitude of the dominant component are then estimated based on the selected samples, next check whether a termination criterion is satisfied, if it is satisfied, the iteration is terminated, otherwise, update the sample sequence by first eliminating those samples with time instants later than the delay estimate just obtained and then deducting the detected dominant component from the remaining samples.

In addition, in the iterative scheme adopted by the arithmetic operation means, the amplitude estimate of the dominant component in the present sample sequence is derived as a maximum likelihood solution given the selected samples and the delay estimate corresponding to the dominant component .

The first arrival detection method comprises: a correlation step at which a correlation function between a received signal and a template waveform is computed; an AD conversion step at which the correlation function generated at the correlation step is uniformly sampled into discrete samples; and an arithmetic operation step at which the time delay of the first arriving signal component is estimated based on the discrete samples produced at the AD conversion step, specifically, an iterative scheme is adopted: in each iteration step, samples representing the dominant component of a present sample sequence are selected first, the delay and the amplitude of the dominant component are then estimated based on the selected samples, next check whether a termination criterion is satisfied, if it is satisfied, the iteration is terminated, otherwise, update the sample sequence by first eliminating those samples with time instants later than the delay estimate just obtained and then deducting the detected dominant component from the remaining samples.

Brief Description of the Drawings

FIG. 1 is a structural diagram of a communication system for illustrating the invention.

FIG. 2 is a block diagram of a transmitter for illustrating the invention.

FIG. 3 is a block diagram of a receiver, which contains the first ■ arrival detection apparatus according to the invention.

FIG. 4 is a block diagram of the first arrival detection apparatus according to the invention.

FIG. 5 is a flowchart for illustrating the first arrival detection procedure according to the invention, which corresponds to the block diagram of Fig. 4.

FIG. 6 is a drawing showing samples of a correlation function related to a received signal subject to multipath propagation.

FIG. 7A and 7B are drawings for explaining arithmetic operations in the iteration scheme according to the invention.

FIG. 8A and 8B are other drawings for explaining arithmetic operations in the iteration scheme according to the invention.

Best Mode for Carrying Out the Invention

An embodiment of the invention is now described in detail by referring to the figures in the previous section.

FIG. 1 shows the system configuration of a communication system 1 according to the invention. The communication system 1 is a system for wireless communication between point A and point B, employing the UWB (Ultra Wide Band) technology. The communication system 1 consists of transmitter 2 sited at the point A and receiver 3 sited at the point B.

The UWB technology is a technology for short-range radio communication, involving the intentional generation and transmission of radio frequency energy that spreads over a very large frequency range, overlapping several frequency bands allocated to radio communication services. The transmitter 2 and the receiver 3 can transmit and receive UWB signals, respectively. A UWB signal is defined as a radio signal with -10 dB bandwidth of at least 500 MHz or a fractional bandwidth greater than 0.2.

FIG. 2 shows the block diagram of the transmitter 2 that transmits a UWB signal.

The transmitter 2 comprises: a pulse generating section 21 which generates a basic UWB signal, a pulse shaping section 22 which shapes the UWB signal generated by the pulse generating section 21 according to certain spectral criteria, a local oscillator 23 which supplies a frequency reference signal to the mixer circuit 24, a mixer circuit

24 which performs frequency conversion on the output signal from the pulse shaping section 22 by using the reference frequency signal supplied from the oscillator 23, a filter

25 for limiting the bandwidth of the frequency-converted signal generated by the mixer circuit 24, a first amplifier

26 which amplifies the output signal from the filter 25, an antenna 27 which radiates the output signal from the first amplifier 26.

The pulse generating section 21 generates a sequence of UWB pulses as a basic UWB signal. A UWB pulse is a signal whose bandwidth is inverse of the pulse duration usually on the order of a nanosecond or a fraction of a nanosecond. The pulse sequence generated by the pulse generating section 21 is sent directly to the pulse shaping section 22.

The pulse shaping section 22 shapes the basic UWB signal generated by the pulse generating section 21 according to certain spectral requirement.

The local oscillator 23 generates a frequency reference signal for frequency conversion in the mixer circuit 24. The frequency of the reference signal may be precisely controlled by an unillustrated PLL (Phase-Locked Loop) circuit or the like. The mixer circuit 24 converts the output signal from the pulse shaping section 22 into a desired frequency band by using the frequency reference signal generated from the local oscillator 23.

The bandpass filter 25 limits the output signal from the mixer circuit 24 within the desired frequency band by removing the unwanted spectral components beyond the desired band. The output signal from the filter 25 is directly fed to the first amplifier 26.

The first amplifier 26 amplifies the output signal from the filter 25 and further modifies the signal in such a way that the signal spectrum is flat within the desired frequency band.

An antenna 27 radiates the output signal generated from the first amplifier 26 as radio signal waves into space which is to be received by the receiver 3 at the point B. Hereinafter, the output signal generated by the antenna 27 is denoted by s (t) .

FIG. 3 shows the block diagram of the receiver 3, which receives the UWB signal, transmitted from the transmitter 2.

The receiver 3 comprises: an antenna 31 which captures the radio signal transmitted from the transmitter 2 in the air, a bandpass filter 32 which removes the unwanted spectral components of the output signal from the antenna 31, a low-noise amplifier (LNA) 33 which amplifies the output signal from the filter 32, a first arrival detection apparatus 34 which estimates the time delay of the first arriving signal component of the output signal from the LNA 33 and, is specified in FIG 4.

The antenna 31 captures the UWB radio signal transmitted from the transmitter 2 in the air, and converts the radio signal into an electrical signal.

The bandpass filter 32 limits the output signal from the antenna 31 within a desired frequency band by removing unwanted spectral components beyond the desired bandwidth.

The LNA 33 amplifies the output signal from the filter

32 in such a manner that amplification of the noise component contained in the signal is controlled under certain level. The amplified signal generated by the LNA 33 is sent to the first arrival detection apparatus 34. Hereinafter, the signal generated by the LNA 33 is denoted by r(t) .

The first arrival detection apparatus 34 estimates the time delay of the first arriving signal component of the output signal from the LNA 33, and is specified in FIG 4.

FIG. 4 shows the block diagram of the first arrival detection apparatus corresponding to the block 34 in the receiver 3, which estimates the time delay of the first arriving signal component of the output signal from the LNA

33 in the receiver 3.

The first arrival detection apparatus comprises: a waveform generation section 44 which generates a template waveform equivalent to the transmit signal s(t) transmitted from the transmitter 2, a correlator 41 which computes the correlation function between the output signal r(t) generated by the LNA 33 in receiver 3 and the template waveform s(t) supplied by the waveform generation section 44, denoted by h(t), an analog-digital converter (ADC) 42 which uniformly samples the correlation output h(t> generated by the correlator 41 into discrete samples, an arithmetic operation section 43 estimates the time delay of the first arriving signal component of the signal r(t) output from the LNA 33 by using the discrete samples generated from the ADC 42.

The waveform generating section 44 generates a template waveform. The template waveform is equivalent to the transmit signal s(t) transmitted from the transmitter 2. The output signal from the waveform generating section 44 is sent to the correlator 41.

The correlator 41 computes a correlation function h(t) between the received signal r(t) output from the LNA 33 in the receiver 3 and the template waveform s(t) generated from the waveform generating section 44. The output signal h(t) from the correlator 41 is an analog signal, and is supplied to the ADC 42.

The ADC 42 uniformly samples the output analog signal h(t) from the correlator 41 into discrete samples, and sends the discrete samples to the arithmetic operation section 43.

The arithmetic operation section 43 estimates the time delay of the first arriving signal component of the received signal r(t) generated by the LNA 33 based on the discrete samples output from the ADC 42 by using an iteration scheme to be discussed next.

The application of the first arrival detection apparatus and method according to this invention is not limited to the UWB system as just described, but can be utilized in any communication system adopting digital sampling.

The first arrival detection scheme adopted in the first arrival detection apparatus of Fig. 4 is presented in detail next, which represents the main contribution of this invention. The corresponding flowchart is shown in Fig. 5.

The first arrival detection scheme according to this invention can greatly improve the estimation accuracy when a first arriving signal component is not dominant among multipath components of a received signal, and the computation complexity is very low. In this invention, an iterative scheme is devised. In each iteration, the present strongest signal component is estimated, and is removed from sample data to be processed in the next iteration. The iteration is terminated when no more such a component above certain threshold can be detected. The smallest delay estimate is taken as the first arrival estimate.

Consider the radio signal s (t) propagating from the transmitter 2 to the receiver 3 is subject to multipath propagation. The received signal r(t) is expressed as

I

where I is the number of total multipath components, Ai and Ti are the amplitude and the time delay for the i-th multipath component, respectively, and n(t) is a white Gaussian noise process with spectral density No.

Our first arrival detection scheme consists of the following eight steps . The description and rationale of each step are presented along with reference to the corresponding components in the flowchart Fig. 5 and the block diagram Fig. 4.

At step SIl in Fig. 5, compute the correlation function between the received signal r(t) and the transmit waveform s(t), which is conducted by the correlator 41 in Fig. 4. The correlation function, denoted by h(v), is given in the following equation

I . ^■ . h{v) = ∑^Ai ' 9(v - Ti) + z(υ), ■ (2)

where g (v) is the autocorrelation function of s(t) as

and z (v) is a noise component as

The noise z (v) is a correlated Gaussian process. Note that the signal waveform s(t) and hence its autocorrelation function g(v) are known at the receiver 3 in advance.

At step S12, uniformly sample the correlation function h(v) at the ADC 42. Let the sampling interval of the ADC 42 be T. Sampling h(v) of equation (2) yields

where tn = to + nT, and to is chosen such that |h(t) | is sufficient small for all t > tN and t < ti. The expression |a| means the absolute value of quantity ^λλa". The noise term z(tn}^/s in the samples can be shown as correlated Gaussian random variables with the zero mean and covariance matrix

FIG. 6 is a graphic illustration of samples of the correlation function, which shows three multiple local maximal points due to three multipath components of the received signal with different delays.

All the arithmetic operations in the following steps constitute an n-th iteration in the iteration scheme for detecting the first arriving signal component of the received signal, and are conducted in the arithmetic operation section 43. Define

def ' tN =^r [^l *2 ' ^• ' *iv] > (7)

h(t_N) ^ [h(h) h(t₂) ^{■ ■ •} h(t_N)f , (8) and

9t_NW = Wi-~ v) g(ti - v) • • • g(t_N - υ)f, (9)

where superscript "T" denotes transpose.

At Step S13, select jn consecutive samples representing the strongest component from the data sequence in the present iteration, which is denoted by h'^11"1' (t_cn) with corresponding time instants t_cn = (ti_n+i ti_n+2 ... tin₊jn)¹¹- The data sequence h'^11"1' (t_cn) is generated at the end of the previous iteration to be shown in equation (13) . In the first iteration, the data sequence is the sample sequence generated at the sampling step S12. The value in and jn are chosen in such a manner that h'^11"1' (t_cn) represents the strongest component and contains less interference from other multipaths . Specifically, jn = 2 or 3 can be utilized. A graphic illustration of the sample selection in the first iteration, i.e., n = 1, is shown in FIG 7A, where two samples h(t±i+i) and h(tii+2) are selected for representing the strongest component in the first iteration.

At Step 14, obtain the delay estimate of the strongest signal component denoted by T^ ' based on the samples h^(n~ ^1] (t_en) selected at the last step, by adopting an existing delay estimation method, e.g., the simplified maximum likelihood method in [4] ([4] Y. Qi and R. Kohno, "Mitigation of sampling-induced errors in delay estimation," Proc. 2005 IEEE International Conference on Ultra-Wideband (2005 ICU) , September, 2005 in Zurich, Switzerland) . In FIG 7A, as an example a delay estimate T^κ ' of the strongest signal component in the first iteration is obtained based on the two selected samples h(tii+i) and h(tii+2).

At Step 15, estimate the amplitude of the strongest signal component. Given the selected samples h^(n-1) (t_cn) with corresponding time instants t_cn = (ti_n+i t_in+2 ... ti_n+jn)^T and the delay estimate T^¹' of the strongest component, which are obtained at the last two steps, the problem of amplitude estimation can be cast into the maximum likelihood (ML)

estimation, which is equivalent to finding A ^• such that the log likelihood function

ffc⁽ⁿ-^1}(t_cn)-ag_tcn(≠^»ψ•V^¹•[T^(t_m)-ag_tcn(f<^»))] is

minimized with respect to a, i.e.,

where Vji is defined in equation (6) representing the noise

statistics, and expression

is defined in equation

(9) representing a noise-free copy of the strongest

component. The ML estimate A,- can be shown as

fft_(*^w)w*.ft_(f<-⁾) ^' _. ^(U> where Wjn is given in form as

with ^(ⁿ-J^m) being a square matrix of order (N-I) obtained by removing the n-th row and the m-th column of VN of equation (6) and |G| being the determinant of matrix G.

At Step S16, check whether a termination criterion is satisfied. The termination criterion is defined by whether the magnitude of the present strongest component, given by

the absolute value of the amplitude ' |/4⁽ⁿ⁾I| , is below certain threshold, or whether no sample data with time instants

.A (γr\ earlier than the time delay estimate T^v ' in the data sequence is available. The threshold can be defined as the noise level in the received signal, i.e., the square root of the noise spectral density. If the termination criterion is true, move to Step S18 which terminates the iteration; otherwise, move to Step S17 and continue another round of iteration.

At Step S17, i.e., when the termination criterion is not satisfied, update the sample sequence, and start a new round iteration, specifically, the (n+l)th iteration, by going back to Step S13. The new (updated) sample sequence,

denoted by

,is produced by first eliminating the data samples with time instants later than the delay

estimate T^ ' from the present data sequence ^ιv V-^¹ ' ' / , which yields a truncated sequence

, and then deducting the strongest component

given by ⁱT(r^W)V ^/ f_rom the truncated sequence as

_Λ ^(»-ⁱ⁾(i^(»-ⁱ⁾,fW) - A_n9t{f{n))(≠% (13)^'

where *(^ " ) ^ C*¹ *^{2 " ' " T} " ' . FIG.7B is a graphic illustration of eliminating the data samples with time instants later than the delay estimate T "(^κ1^J) m the first iteration, which are marked by the shadowed area, FIG. 8A shows the strongest component detected in the first iteration is further removed from the truncated data sequence, which are also marked by the shadowed area, and FIG. 8B represents the resulting updated data sequence prepared for the second iteration n = 2, which is illustrated by the solid line.

At Step S18, i.e., when the termination criterion is satisfied, the iteration is terminated, and the smallest delay estimate with amplitude greater than the threshold is taken as the first arrival estimate.

In this manner, strong multipath components of a received signal and thus their damaging effects on estimation performance are removed sequentially in each iteration until the first arriving signal component is detected. Therefore, a high estimation accuracy can be achieved with a low computational complexity, even when any dominant multipath signal components exist. Industrial Applicability

In this invention, an apparatus and a method for the first arrival detection are provided, which can greatly improve the estimation accuracy especially when the first arriving signal component is not dominant among multipath components of a received signal, and the computation complexity is very low. The method and the apparatus according to this invention can be adopted for precision ranging.

Claims

1. A delay estimation apparatus comprising: correlation means which generates a correlation function based on a received signal and a supplied template waveform;

AD (analog to digital) conversion means which samples said correlation function generated by said correlation means into discrete samples; and arithmetic operation means which estimates delays of multipath components of said received signal based on said discrete samples generated by said AD conversion means, wherein said arithmetic operation means includes an iteration procedure where in each iteration, the time delay and the amplitude of the strongest signal component are estimated based on the present sample sequence, and said sample sequence is updated by deducting the estimated strongest component from said sample sequence; said iteration is terminated when a termination criterion is satisfied.

2. The delay estimation apparatus according to claim 1, wherein in each said iteration, said amplitude estimate of said strongest component is given by the maximum likelihood (ML) solution, and said ML solution is an optimal estimate such that a probability function which summarizes statistics regarding given observations is maximized.

3. The delay estimation apparatus according to claim 1 or 2, which is adopted as a first arrival detection apparatus or wireless ranging apparatus, and said first arrival detection apparatus is to estimate the delay of the first arriving signal component of a received signal in a wireless communication system.

4. The delay estimation apparatus according to claim 1, 2 or 3, which is adopted in a UWB (Ultra Wide Band) communication system.

5. A delay estimation method, comprising: a correlation step at which a correlation function between a received signal and a supplied template waveform is generated; an AD (analog to digital) conversion step at which said correlation function generated at said correlation step is sampled into discrete samples; and an arithmetic operation step at which time delays of multipath components of said received signal are obtained based on said discrete samples generated at said AD conversion step, wherein said arithmetic operation step includes an iteration procedure where in each iteration, the time delay and the amplitude of the strongest signal component are estimated based on the present sample sequence, and said sample sequence is updated by deducting the estimated strongest component from said sample sequence; said iteration is terminated when a termination criterion is satisfied.

6. The delay estimation method according to claim 5, wherein in each said iteration, said amplitude estimate of said strongest component is given by the maximum likelihood (ML) solution, and said ML solution is an optimal estimate such that a probability function which summarizes statistics regarding given observations is maximized.

7. The delay estimation method according to claim 5 or 6, which is adopted as a first arrival detection method or wireless ranging method, and said first arrival detection method is to estimate the time delay of the first arriving signal component of a received signal in a wireless communication system.

8. The delay estimation method according to claim 5, 6 or 7, which is adopted in a UWB (Ultra Wide Band) communication system.