Methods and apparatus for estimating a time-of-arrival or a distance between two device
A method for estimating a time-of-arrival of a packet received by a receiver includes storing a reference bit-pattern and receiving a plurality of samples in a samples-buffer. In a bit-pattern detector, a matching group of samples having a bit-pattern which matches the reference bit-pattern is identified. In a correlator, a group of three correlation values is determined from the matching group of samples, including a local maximum correlation value, P0, an immediately preceding correlation value, Pm, and an immediately succeeding correlation value Pp. In an estimation unit, a polynomial function f(δ) of the difference, δ, between Pm and Pp is used to estimate a timing offset T frac , between the local maximum correlation value and a correlation peak. The time-of-arrival is estimated from a time of the local maximum correlation value P0, and T frac .
1. A method of estimating a time-of-arrival of a packet received by a receiver, the method comprising:
storing a reference bit-pattern;
receiving a plurality of samples in a samples-buffer;
identifying, in a bit-pattern detector, a matching group of samples having a bit-pattern which matches the reference bit-pattern; and
determining, from the matching group of samples in a correlator, a group of three correlation values, comprising a local maximum correlation value P0, an immediately preceding correlation value Pm, and an immediately succeeding correlation value Pp;
using a polynomial function f(δ) of a difference, δ, between Pm and Pp to estimate, in an estimation unit, a timing offset T frac , between the local maximum correlation value P0 and a correlation peak; and
estimating the time-of-arrival from a time of the local maximum correlation value P0, and T frac.
2. The method of claim 1 , wherein the polynomial function f(δ) is a cubic of the form:
f(δ)=k 1 ·δ+k 2 ·δ 2 k 3 ·δ 3 and the coefficients k 1 , k 2 and k 3 are dependent on the reference bit-pattern.
3. The method of claim 2 , wherein the coefficients k 1 , k 2 and k 3 are dependent on the reference bit-pattern by a vector, C, wherein
C =[ cnt 010 ,cnt 011 ,cnt 111 ]
wherein, applying an extended bit-pattern consisting of the reference bit-pattern both preceded and followed by a single bit of preselected polarity,
cnt 010 is a number of bits in the extended bit-pattern having an opposite polarity to both its immediate neighbours,
cnt 011 is a number of bits in the extended bit-pattern having an opposite polarity to just one of its immediate neighbours, and
cnt 111 is a number of bits in the extended bit-pattern having an opposite polarity to neither of its immediate neighbours;
wherein the coefficients relate to C through a transformation matrix Γ, having dimensions (3·n)×3 and defined through
[ k 1 ,k 2 ,k 3 ]=[ cnt 010 ,cnt 011 ,cnt 111 ,cnt 010 2 ,cnt 011 2 ,cnt 111 2 . . . cnt 010 n ,cnt 011 n ,cnt 111 n ]*Γ.
4. The method of claim 3 , wherein n=3.
5. The method of claim 1 further comprising determining a time-stamp, t TS , for the time-of-arrival from a reference time, t D , of the bit-pattern detection, t 0 , a refinement t P0 corresponding to the difference between the reference time of the detected bit-pattern and the corresponding reference time of the local maximum correlation value, and T frac , according to:
t TS =t D +t P0 +T frac .
6. The method of claim 5 further comprising estimating a distance between the receiver and a transmitter from which the packet is received, based on the time-stamp.
7. The method of claim 1 , wherein the received packet is modulated according to a Gaussian Frequency Shift Key (GFSK) modulation scheme.
8. The method of claim 7 wherein a bit-rate of the GFSK is 1 MHz, and the received packet is sampled at 4 MHz sampling rate.
9. The method of claim 1 , wherein the receiver is a Bluetooth receiver.
10. A time-stamp module comprising:
a samples buffer;
storage circuitry configured to store a reference bit-pattern;
a bit-pattern detector comprising a relatively low-precision correlator, configured to identify a set of samples having a bit-pattern which matches the reference bit-pattern;
a relatively high-precision correlator configured to determine, from the set of samples, a group of three correlation values, comprising a local maximum correlation value P0, an immediately preceding correlation value Pm, and an immediately succeeding correlation value Pp; and
an estimation unit configured to use a polynomial function f(δ) of a difference, δ, between Pm and Pp to estimate a timing offset between a timing of the local maximum correlation value P0 and a correlation peak.
11. A time-stamp module as claimed in claim 10 , wherein the polynomial function f(δ) is a cubic of the form:
f(δ)=k 1 ·δ+k 2 ·δ 2 k 3 ·δ 3 and the coefficients k 1 , k 2 and k 3 are dependent on the reference bit-pattern.
12. A time-stamp module as claimed in claim 11 wherein the coefficients k 1 , k 2 and k 3 are dependent on the reference bit-pattern by a vector, C, wherein
C =[ cnt 010 ,cnt 011 ,cnt 111 ]
wherein, applying an extended bit-pattern consisting of the reference bit-pattern both preceded and followed by a single bit of preselected polarity,
cnt 010 is a number of bits in the extended bit-pattern having an opposite polarity to both its immediate neighbours,
cnt 011 is a number of bits in the extended bit-pattern having an opposite polarity to just one of its immediate neighbours, and
cnt 111 is a number of bits in the extended bit-pattern having an opposite polarity to neither of its immediate neighbours,
wherein the coefficients relate to C through a transformation matrix Γ, having dimensions (3·n)×3 and defined through
[ k 1 ,k 2 ,k 3 ]=[ cnt 010 ,cnt 011 ,cnt 111 ,cnt 010 2 ,cnt 011 2 ,cnt 111 2 . . . cnt 010 n ,cnt 011 n ,cnt 111 n ]*Γ.
13. A time-stamp module as claimed in claim 10 , wherein the time-stamp module is further configured to estimate a distance between a receiver comprising the time-stamp module and a transmitter from which a packet is received, based on the time-offset, a local time of the local maximum correlation value, and a process time.
14. A transceiver comprising the time-stamp module as claimed in claim 10 , and further comprising a Gaussian Frequency Shift Key (GFSK) modulator and a GFSK demodulator coupled to the time-stamp module.
15. A transceiver as claimed in claim 14 comprising a Bluetooth transceiver.
16. A digital signal processor for a transceiver comprising:
a samples buffer;
a memory configured to store a reference bit-pattern;
a relatively low-precision correlator, configured to identify a set of samples having a bit-pattern which matches the reference bit-pattern;
a relatively high-precision correlator configured to determine, from the set of samples, a group of three correlation values, comprising a local maximum correlation value P0, an immediately preceding correlation value Pm, and an immediately succeeding correlation value Pp, and
an estimation unit configured to estimate a timing offset between a timing of the local maximum correlation value P0 and a correlation peak, using Pm and Pp.
17. A digital signal processor according to claim 16 , wherein the estimation unit is configured to use a polynomial function of a difference between Pm and Pp to estimate the timing offset.