Time Delay Estimation Techniques - part 2
19 Oct 2014Introduction
In this article we will look at improving the Time Delay estimation in presense of noise using information of signals coming in from multiple receivers or observing multiple samples intervals of the signal.
Background
Let us consider an array of N receiver ,the signal $x_{m}[n]$ at receiver is given by
\[x\_{m}[n] = s[n]*h[n]+w[n]\]Let us say that by choosing the appropriate delays $\delta_{m}$ we can make all the receivers aligned in time and them summing the time aligned signals together.
The aim of such techniques is to boost SNR of the signal by combining the signals from multiple receivers.
Since the signal is periodic,we can observe multiple instances of the same signal.Again if we are sure that the signals are coherent in sampled intervals we can combine multiple observation of the signal.The aim of such techniques is to boost the SNR of the signal by observing multiple instances of the singal.
Both techniques have the same effect of enhancing the signal and averaging the noise,therby increasing the SNR of the signal.
Reducing Environmental Noise
Mathematically this can be expressed as
\[y[n] = \sum\_{m=1}^{M} x\_{m}[n-\delta\_{m}]\] \[y[n] = \sum\_{m=1}^{M} s\_{m}[n-\delta\_{m} ] + w\_{m}[n]\]The noise due to sensor or amplification process can be assumed to be independent. The noise introduced dues to environment will be same in all the receivers. The noise can be assumed to be sample of stationary white random process.
Let us assume for now that signals are time aligned
We can see that the our signal contains information plus additive noise.Most of region contains just noise and only a small section of the time duration contains the information.
The basic idea is that when we add the signals ,information will get enhanced while the noise will get averaged.In this way we can boost signal strength and achieve higher SNR.
If the noise from independent receivers are considered to uncorrleated. When we add noise components,we are effectively adding two independent gaussian random variables.Thus resultant is also a Gaussian random variable.
The sum of N Gaussian random variables is the Gaussian random variable with the standard deviation \(\sqrt{ \sum\_{i=0}^N\sigma\_{i }^2}\)
Thus if we consider that noise power is same in each of receivers then by adding the signals the resultant noise power is
\[P\_{N}= \sigma^2 N\]However the signal is a deterministic ,the resultant signal power of adding N signals is
$P_{M} = N^2 P_{S} $
Thus the SNR of resultant signal is
\[SNR = \frac{P\_{s}}{P\_{n}} N\]The SNR is boosted by $N$ times.
Let us see if we can observe this via simulations
to generated uncorrelated random sequences,we change the seed every time we generate the random noise.This will simulate condition of noise generated from multiple sensors.
In the first case we observe only the noise signal
Let us observe the variance of sum signal for N={2,4,8 …. 128}
| N | Simulation | Theory |
|---|---|---|
| 2 | 0.14 | 0.14 |
| 4 | 0.20 | 0.2 |
| 8 | 0.28 | 0.28 |
| 16 | 0.39 | 0.4 |
| 32 | 0.56 | 0.56 |
| 64 | 0.78 | 0.8 |
| 128 | 1.144 | 1.13 |
we can see from the table that simulated and theoretical results agrees with each other
we consider the case where $M=4$ independent receivers are used .The signal is corrupted by additive environmental noise of variance $\sigma^2=0.2$
signal strength 1.6 noise power 0.04 Input SNR 40.0 estimated noise power 0.16 estimated signal power 6.4 estimated SNR 40.0 estimated improvement 1.0 emprical signal power 6.56051311603 emprical noise power 0.160339040093 emprical SNR 40.9165048776 emprical SNR improvement 1.02291262194
The empirical results agree with our theoretical analysis. Thought the improvement factor is not very significant
Sensor Noise
The next case comes where we observe signal from the same receiver over N periods.
Again the noise observed at each sample instance $[n]$ is sample of Gaussian random variable since we assume stationary noise process.Thus noise variance is $\sigma^2$.Thus the sum signal will have noise power of $(N * \sigma^2)$
As we add the signals the signal power increases by factor $N^2$.
This comes directly from central limit theorem and law of larger numbers that the sum of N iid samples will approach gaussian distribution.Thus noise variance will be $\sigma^2$.
\[SNR = \frac{P\_{s}}{P\_{n}} {N}\]The SNR is boosted by N Times.
we consider the case where $M=2$ independent receivers are observed over a duration of $N=4$ periods.The signal is corrupted by additive sensor noise of variance $\sigma^2=0.4$
let us consider the case of $N=1$ ,number of periods
signal strength 1.6 noise power 0.16 Input SNR 10.0 estimated noise power 0.32 estimated signal power 6.4 estimated SNR 20.0 estimated improvement 2.0 emprical signal power 7.04582360211 emprical noise power 0.321264927044 emprical SNR 21.931505773 emprical SNR improvement 2.1931505773
Let us consider the case of $N=4$
signal strength 1.6 noise power 0.16 Input SNR 10.0 estimated noise power 1.28 estimated signal power 102.4 estimated SNR 80.0 estimated improvement 8.0 emprical signal power 105.0704936 emprical noise power 1.27294915151 emprical SNR 82.5409981816 emprical SNR improvement 8.25409981816
The empirical estimates again agree with our theoretical analysis. We get a significant improvement in SNR,just by increasing the number of periods of observation.The SNR improves linearly by factor of $N$.
SNR Improvement In Presence of sensor and environmental noise
Let us say that the signal is corrupted by both environmental and receiver noise
There are N receivers .The same environmental noise is observed in each of the receivers. Let us assume that the sequences are time aligned.Each of receivers has uncorrelated noise components. We observe each receiver channel for M periods .
Thus in total we have M*N Signals
Thus total noise power in a single period be considered as $2 \sigma^2$
The environmental noise component which is present in all the sensors cannot be reduced by adding the sensor signals.This component can only be reduced by observing the signal over longer duration
When signals from different receivers are added,the environmental noise power is also amplified along with the signal.This noise power is amplified by a factor $N^2$
Now we have M periods of the signal,Thus noise power after adding M periods of the signal is given by $M*N^2$.
The factor by which total sensor noise power increases by adding all the signals is given by $MN$
Thus the total noise power is given by $M N^2 \sigma_{1}^2 + MN \sigma_{2}^2$
The factor by which total signal power increases by adding all the signals is given by $M^2N^2$
Thus SNR of sum of signals is given by $\frac{M^2N^2 P_{M}}{M N^2 \sigma_{1}^2 + MN \sigma_{2}^2}$
When both variances are same,the SNR Improvement can be expressed as $\frac{2M^2N^2}{N^2M+NM} =\frac {2MN}{N+1}$
we consider the case where $N=2$ independent receivers are observed over a duration of $M=4$ periods.The signal is corrupted by additive environmental and sensor noise of variance $\sigma^2=0.4$
Theoretical improvement by a factor of 5.33
signal strength 1.6 noise power 0.32 Input SNR 5.0 estimated noise power 3.84 estimated signal power 102.4 estimated SNR 26.6666666667 estimated improvement 5.33333333333 emprical signal power 107.678534403 emprical noise power 3.82682954561 emprical SNR 28.1377921644 emprical SNR improvement 5.62755843289
The simulations give a improvement by 5.62
In terms of decibles its improvement of about 25db just by averaging signals.
Also it can be seen that improvement is larger by considering longer duration signals than adding more receivers.
Time Delay Estimation
Given signals form the receviers,time period to analyze signals we compute the SNR for all possible delays between the signals.The delay which gives the maximum SNR is considered to be the time delay between the signals.
In the present article we only consider pairs of signals for analysis.We can perform the delay and sum operation wrt to ideal signal or noisy signal from one of the receivers.
Ideal Signal
In the first method we construct an ideal signal and perform this computation wrt signals obtained from both the receivers.
The ideal signal is not plagued by environmental and sensor noise.When we add ideal and noisy version of the signal,the environmental and sensor noise are averaged.
However the improvement is only between a pair of signals.The environmental signal can only be reduced by a factor of 4.
Let us first consider the case of noise variance of $0.4$ and use a ideal signal to perform the computation
signal strength 1.6 noise power 0.32 Input SNR 5.0 estimated noise power 1.28 estimated signal power 102.4 estimated SNR 80.0 estimated improvement 16.0 emprical signal power 103.442427564 emprical noise power 1.26823592579 emprical SNR 81.5640256366 emprical SNR improvement 16.3128051273 mean delay 5.0 std deviation 0.0
Now the same computation is performed using a signal received from one of the receivers. $MN^2 \sigma_{1}^2 + MN \sigma_{2}^2$ and for N=2 we get $4M \sigma_{1}^2 + 2M \sigma_{2}^2$ and the total signal power increases by $4 M^2$
signal strength 1.6 noise power 0.32 Input SNR 5.0 estimated noise power 3.84 estimated signal power 102.4 estimated SNR 26.6666666667 estimated improvement 5.33333333333 emprical signal power 104.34546039 emprical noise power 3.07193469288 emprical SNR 33.9673433265 emprical SNR improvement 6.79346866529 mean delay 5.0 std deviation 0.0
Improvement factor is greater is the case of using ideal signal.In both the methods since pairwise operations are performed,increasing the number of receivers has not effect on the analysis.
Code
A class TimeDelaySimulator encapsulates all the methods for generating time delayed signals with additive environmental and sensor noise components and computing the statistics.
All the results mentioned in the article can be simulate by executing the script.
def run(self,isignal):
""" main function that generates noisy,time delayed signals
Parameters
--------
isignal : numpy array
ideal signal
Returns
-------
out : numpy array shape=(length,channel,period)
"""
l=len(isignal)
#array for storing signal and noise
signal=numpy.zeros((l,self.nchannels,self.periods));
noise=numpy.zeros((l,self.nchannels,self.periods));
#generate environmental noise for each period and across all channels
for k in range(self.periods):
n=self.GenerateNoise(self.enoise,l)
#simulating environmental noise
for i in range(self.nchannels):
noise[:,i,k]=n;
#for each channel add sensor noise
for k in range(self.nchannels):
#dummpy call to change the random seed
#so that we can generate uncorrelated sensor noise
self.GenerateNoise(self.snoise,l,1)
for i in range(self.periods):
signal[:,k,i]=self.delay(isignal,(k+1)*self.tdelay)+noise[:,k,i]+self.GenerateNoise(self.snoise,l)
#change the seed everytime the function is called
self.seed=int(np.random.uniform(0,1)*10000);
#flag to print the statistics
if self.once==1:
self.once=0;
PS=np.mean(isignal*isignal);
PN=self.enoise*self.enoise+self.snoise*self.snoise;
if self.tde_method==0:
PNT=(self.periods*self.enoise*self.enoise)
PNT=PNT+(self.periods*self.nchannels*self.snoise*self.snoise/self.nchannels)
PST=(self.periods*self.periods)*PS*4
if self.tde_method==1:
PNT=(self.periods*4*self.enoise*self.enoise)
PNT=PNT+(self.periods*2*self.snoise*self.snoise)
PST=(self.periods*self.periods)*PS*4
print "signal strength",PS
print "noise power ",PN
self.SNRI=PS/PN
print "Input SNR ",self.SNRI
print "estimated noise power ",PNT
print "estimated signal power ",PST
self.SNR0=PST/PNT
print "estimated SNR ",self.SNR0
print "estimated improvement ",self.SNR0/self.SNRI
#returns the signal
return signal
A class TimeDelayEstimator encapsulates all the methods for computing the time delay estimation mentioned in the article.
def run(self,signal,isignal,enoise,snoise,method=0):
""" the main function that performs time delay estimation
Parameters
-----------
signal : numpy array shape=(length,channel,periods)
input noisy signals for time delay estimation
isgignal : numpy array shape=(length,)
ideal signal
enoise,snoise : float
environmental and sensor noise standard deviation
method : integer
0 - for pariwise delay sum with ideal signal
1 - pariwise delay sum with noisy signals
Returns
-------
tdelay : numpy integer
estimated time delay
"""
size1=signal.shape;
ch=size1[1];
length=size1[0];
periods=size1[2];
enoise=enoise*enoise;
snoise=snoise*snoise;
PS=np.mean(isignal*isignal);
if method==0:
iloop=ch-1
if method==1:
iloop=ch-1;
#compute the SNR threshold
if method==0:
vnoise=(periods**enoise/4)+(periods*iloop*snoise/iloop);
vsnoise=[-2*vnoise,2*vnoise]
ispower=(periods*periods*PS);
spower=np.mean(signal*signal)*periods*periods
OSNR=(periods*periods*4*PS)+(1*vsnoise);
OSNR=OSNR/(periods*periods)
if method==1:
vnoise=(periods*enoise)+(periods*iloop*snoise);
vsnoise=[-2*vnoise,1*vnoise];
spower=np.mean(signal*signal)*periods*periods
ispower=(periods*periods*iloop*iloop*PS);
OSNR=(periods*periods*4*PS)+vsnoise
OSNR=OSNR/(periods*periods)
#add the signals along periods
s=np.mean(signal,axis=2);
SNR=np.zeros((iloop,length))
for i in range(iloop):
#delay sum operation for various delays
for k in range(length):
if method==0:
su=s[:,0]+self.delay(s[:,i+1],k)
if method==1:
su=s[:,0]+self.delay(s[:,i+1],k)
#apply SNR Thresholding
SNR[i,k]=np.mean(su*su);
if(SNR[i,k] < ;OSNR[0]):
SNR[i,k]=0
#find the index of maximum SNR
m1=np.argmax(SNR,axis=1)
#average all the time delays
if method==0:
tdelay=0;
for i in range(iloop-1):
tdelay=tdelay+abs(m1[0]-m1[i+1])/(i+1)
tdelay=tdelay/(iloop-1)
if method==1:
tdelay=0;
for i in range(iloop):
tdelay=tdelay+((length-(abs(m1[i])+1)))/(i+1);
tdelay=tdelay/iloop;
#return the result
return tdelay
Change the mode from 0-4 to test various algorithms.The parameters like delay and noise can also be changed and the various results mentioned in the article can be generated.
The code can be found in the pyVision github repository https://github.com/pi19404/pyVision
Files
- pySignalProc/TimeDelayEstimation.py