pyVision
A Machine Learning and Signal Processing toolbox

Download .zip Download.tar.gz View on GitHub


Time Delay Estimation Techniques - part 2

Introduction

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
blog comments powered by Disqus