# PROCESSING OF AUTO AND CROSS-CORRELATIONS OF TWO JOINTLY WSS RANDOM PROCESSES THROUGH VARIOUS TYPES OF WINDOWS IN TIME DOMAIN.

Byline: Ejaz A. Ansari, Saleem Akhtar and Muhammad NadeemABSTRACT: In many situations, transform techniques are quite useful for analyzing the wide sense stationary (WSS) processes through LTI- systems. However, if the input process is not a stationary white noise and is further passed through a(n) exponential, rectangular, triangular and trapezoidal shaped window, then, it becomes difficult to compute auto-correlation and cross-correlation of the output process using transform techniques. Thus, in this paper, we present a very simple and efficient technique in time domain for the computation of auto and cross correlations of the output WSS process through the above windows. First, we develop the relationship of auto and cross correlation of the output signal in terms of auto-correlation of the input deterministic signal and the impulse response of the filter without using the integral definition of the convolution explicitly. Then, we repeat the analysis in terms of two jointly WSS processes, X(t) and Y(t) denote input and output process respectively.

Subsequently, we apply these results and derive the algorithm first for an exponential shaped window and further use it intelligently while processing X(t) through a rectangular (also known as moving average), triangular and trapezoidal shaped windows. Furthermore, we validate our proposed method in case of a moving average window through comparison with the results already reported in the literature. Finally, our proposed technique in time domain can easily be extended to discrete-time signals and discrete-time WSS random processes.

Key Words: Auto correlation, Cross correlation, Fourier Transform, Windows, WSS Processes

1 INTRODUCTION

Both random and stochastic processes are extremely useful for carrying out research in the field of Statistical Digital Signal Processing and Modeling, Detection and Estimation Theory, Digital Image Processing and Advanced Signal Processing for Wireless Communications. There exists plenty of application examples that require the utilization of these processes in certain kind like in the performance analysis of wireless and cognative radio based networks, medical signal and image processing, radar and sonar signal processing, Pattern Recognition, Antenna Array Processing and modern Communication Systems employing coherent receivers [1]-[4].First and second order characteristics of WSS processes are very important for their complete description [3], [4].

The processing of WSS random signals through LTI-systems plays a very useful role in studying the behavior of many wireless communication systems and networks. Filtering does not bring about any change in the stationarity status of the input process and thus both input and output processes become jointly stationary [3], [4]. Frequency response of all the windows discussed in this paper corresponds to the frequency response of a low pass filter. Performing low pass filtering on the WSS input processes removes the noiseA) being added to the process during transmission. Thus, the computation of auto-correlation and cross-correlation of the output process becomes very important for further analysis of the system. In most situations, transform techniques are normally employed for such computations but the analysis becomes difficult and challenging once the input process does not remain a stationary white noise.

We, therefore, need to look for some alternate simple and efficient techniques in time domain that could provide us such computations in a simpler way. In this paper, we, thus present a very simple and elegant method in time domain for computing auto-correlation and cross-correlation of the output process which is usually obtained after processing the input WSS process through the windows. The frequency response of the windows considered in this paper resemble with the frequency response of low pass filters. Different windows discussed in this paper are exponential, moving average (rectangular), triangular and trapezoidal shaped.

This paper is organized as follows: Section 2 describes the computation of cross and auto correlations of the output process in case of deterministic signals and Random processes in continuous domain. Problem statement is formulated in section 3. Section 4 discusses the processing of WSS input process through different types of windows as mentioned above. Validation of the proposed technique is provided in section 5. Finally, we present our conclusions in section 6.

2 Derivation of the Relations for Auto and Cross Correlations in Time Domain

For deterministic real signals Correlation function, Rxy(t) between two deterministic signals x(t) and y(t) may be computed from its definition [5] as Equation (1) is obtained by utilizing the substitution (t + t) = u in the integral definition of Rxy(t). We know that y(u - t) = y{-(t - u)} and using it in eq. (1), Rxy(t) can also be expressed as convolution of x(t) with y(-t). Thus, Rxy(t) = x(t) y(-t) = y(-t) x(t) (2)

where denote analog convolution operation between x(t) and y(-t), Similarly the autocorrelation of the input signal, x(t) can be obtained by replacing y(t) = x(t) in eq. (2) as Rxx(t) = x(t) x(-t) = x(-t) x(t) = Rxx(-t), which follows from eq. (1). This shows that Rxx(t) is an even and real function of time whose Fourier transform is also an even and real function of frequency [6]. When an input signal x(t) is passed through an LTI-system having h(t) as its impulse response, the output, y(t) generated by it may be computed [5] as y(t) = h(t) x(t) = x(t) h(t). We thus, substitute this result in eq. (2) and express the cross correlation between x(t) and y(t) as Rxy(t) = x(t) y(-t) = x(t) {x(-t) h(-t)} ={x(t) x(-t)} h(-t) = Rxx(t) h(-t) = h(-t) Rxx(t) (3) Equation (3) is thus obtained using commutative and associative properties of the convolution.

Likewise, we may also compute autocorrelation of the output process using eq. (2) as Ryy(t) = y(t) y(-t) = {h(t) x(t)}y(-t) = h(t){x(t)y (-t)} = h(t) Rxy(t) = {h(t) h(-t)} Rxx(t) = Rhh (t) Rxx(t) (4) Where Rhh(t) denote autocorrelation of an LTI- system with h(t) as its impulse response.

B) For two jointly WSS real Random Processes

The auto correlation of a WSS real input random process, X(t) can be defined as [7], RXX(t) = E[X(t+t)X(t)]. Similarly, cross correlation between the input, X(t) and the output Y(t) two real WSS processes can be defined as RXY(t) = E[X(t+t)Y(t)] = E[Y(t)X(t+t)]. The output process, Y(t) obtained after filtering the input pr0cess, X(t) as Using this definition of convolution integral and cross correlation, we may express RXY(t) after following some simplification and manipulation steps as convolution of h(-t) and RXX(t) like eq. (3). Similarly, we may use eq.(5) in the definition of auto correlation of the output process, Y(t) and after doing some simplification and manipulation steps, we can also express RYY(t) as convolution of Rhh(t) and RXX(t) respectively like eq. (4). This shows that auto correlation of the input process, X(t) plays a vital role in determining theA.

Across and auto correlations of the output process, Y(t). C) Computation of RXX(t) from the given input Process The following steps are necessary to compute the autocorrelation function, RXX(t) for t [greater than or equal to] 0. Shift or delay the given process, X(t) towards right by an amount t = t Compute or formulate the product, X(t) with X(t - t) Integrate this product from t = t to t = . This will generate the value of RXX(t) for t [greater than or equal to] 0.

D) Computation of energies present in the input and output Processes

Having determined the autocorrelation of the input and output WSS processes using the steps illustrated in section 2

B) and C) , the computation of energies in their respective process can simply be obtained by setting t = 0 in the expressions of RXX(t) and RYY(t) respectively. There is no need to compute the area bounded by the power spectral densities of the input and output processes over the entire f- axis for this purpose. This is one of the salient features of this algorithm.

E) Transformation of relations derived in eqs.(3)-(4) to frequency domain If the Fourier transforms of auto and cross correlation functions are represented by SXX(f) and SXY(f), then we may consider SXX(f), SYY(f), Shh(f) and H(f) as energy spectral densities present in the input process, output process and the filter and frequency response of the filter respectively. Knowing the fact that convolution operation transforms to simple multiplication operation in the frequency domain, the time domain relations described in eqs. (3)-(4) can easily be transformed to frequency domain as SXY(f) = H(-f) SXX(f) and SYY(f) = Shh(f) SXX(f) (6) where Shh(f) = H(f) x H(-f) = |H(f)|2 as H(-f) = H(f) because h(t) is real.

3 PROBLEM FORMULATION IN FREQUENCY DOMAIN

Consider that h(t) represent the impulse response of a moving average (rectangular) window having duration T sec through which we want to process the input WSS real process X(t). We thus represent mathematically this filter as h(t) = 1/T rect {(t - T/2)/T}.

Its Fourier transform, H(f) using Tables [7] may be computed as, H(f) = 1/T x {T Sinc(fT) exp(jpfT)}= Sinc(fT) exp(jpfT) and H(f) = Sinc(fT) exp(-jpfT), which is also equal to H(-f). The magnitude squared of the frequency response, H(f) is therefore computed as |H(f)|2 = H(f) H(f) = (Sinc2(fT))/T2 = Shh(f) Substitution of these results in eq. (6) reveal that it is indeed difficult to compute the cross and auto correlations of the output WSS real process Y(t) using inverse Fourier transform techniques [7].

4 PROCESSING OF RXX(T) THROUGH VARIOUS LTI- WINDOWS Exponential Window

It is defined as h(t) = e-atu(t) for a (greater than) 0. Consider R+(t) denote that part of RXX(t) which exists for t [greater than or equal to] 0. Autocorrelation of the input WSS process, X(t) can thus be written as RXX(t) = R+(t)u(t) + R-(t)u(-t) as it is real and even. Using eq. (3), we thus compute cross correlation through this window as RXYex(t) = h(-t) RXX(t) = RYXex(-t) and RYXex(t) = h(t) RXX(t) using even symmetry of autocorrelation function. This will yield cross correlation between Y(t) and X(t) and its image across t = 0 axis will generate RXYex(t). We therefore compute the cross correlation between Y(t) and X(t) using the definition of convolution integral as where p(a,t) and q(a,t) represent the results of cross correlation obtained after carrying out integration of eq. (7) for t (less than) 0 and t [greater than or equal to] 0 respectively . We, thus mathematically express cross correlation of Y(t) with X(t) as RYXex(t) = p(a,t)u(-t ) + q(a,t)u(t) for t .

Finally, RXYex(t) is simply obtained by taking the image of RYXex(t) aound t = 0 axis. The auto correlation (RYYex(t)) of the output process Y(t) can also be obtained in a similar manner using eq. (4) by replacing RXX(t) with RXYex(t) in eq. (7). Moving Average (Rectangular) Window The input-output relation between X(t) and Y(t) in case of moving average (rectangular) window may be expressed as [4]

The impulse response f(t) of the moving average window can be computed by substituting X(t) = (Delta)(t) in eq. (8) and is thus given by f(t) = 1/T rect{(t - T/2)/T}.This can also be written in terms of unit step and its time delayed functions as, f(t) = 1/T{u(t) - u(t - T)} which can further be expressed where h(t) = e-atu(t). We now compute the cross correlation of Y(t) with X(t) in case of moving average window using eq. (3) as We have used eqs. (7), (9) and linearity property of the window in deriving eq. (10). We need to take the limit of the result within brackets in eq. (10) when a - 0 and further divide its amplitude by the width, T of the moving average window. Finally, RXYma(t) is simply obtained by taking the image of RYXma(t) around t = 0 axis. The auto correlation (RYYma(t)) of the output process Y(t) in this case can also be obtained in a similar manner using eq. (4) by replacing RXX(t) with RXYma(t) in eq. (10).

Hence, to compute cross and auto correlation of Y(t) through a moving average window we propose the following algorithm in the form of distinctive steps as: Steps of the proposed Algorithm i) Find RXX(t) from the knowledge of X(t) using the above three steps described in section 2 (C) ii) the convolution of h(t) with R (t) using eq. (7) iii) Delay the result of step ii) by t = T sec iv) Subtract the result of step iii) from the result of step ii) v) Evaluate the limit of the result obtained in step iv) when a - 0 vi) Scale down the amplitude of the result obtained in step v) by T. This will yield RYXma(t) vii) Take the mirror image of this result obtained at t = 0 axis viii) First replace Rxx (t) with RXYma(t) and repeat steps i) - vii) to compute the auto correlation of the output process Y(t) B.

Triangular Window with width 2T and unity height we know from [5] that a triangular shaped window, (Delta)(t) of width 2T can easily be generated by convolving two rectangular shaped windows of unity height having the same width equal to T. Thus we formulate the relation among them as, (Delta)(t) = (Tf(t)) (Tf(t)) = T2 x {f(t) f(t)}. where f(t) represent an impulse response of a moving average window.

The processing of X(t) through this window will provide us cross correlation of Y(t) using eq. (3) as Equation (11) shows that cross and auto correlation functions of Y(t) can be obtained by applying the proposed algorithm twice first on RXX(t) and then on RYX(Delta) respectively. Finally, scale up the amplitude of the result by T . C. Trapezoidal Window with width, W = T1 + T2 and height, h = T1 Likewise, a trapezoidal shaped window, trap(t) of width, W and height T1 can also be formulated by convolving two widths. We therefore, develop the relation among them as [5], trap(t) = f1(t) f2(t), where fi(t) = u(t) - u(t - Ti), i [?] (1, 2) and T2 (greater than) T1.

The processing of X(t) through this window using eq.(3) will provide us cross correlation of Y(t) as Here, again we notice from eq. (12) that cross and auto correlation functions of Y(t) can be obtained by applying the proposed algorithm twice first on RXX(t) and then on RYXtrap(t) respectively. Finally, sca le up the amplitude of the result by T1T2.

5 VALIDATION OF THE PROPOSED ALGORITHM USING THE LITERATURE

To validate our proposed algorithm, we'll reduce the cross correlation result of Y(t) through a moving average filter, f(t) in frequency domain which is already available in the literature [3, 7]. Thus, it is given by using eq. (3) as RYX(t) = f(t) RXX(t) = RXY(-t). This relation maps to frequency domain using Fourier transform properties as SYX(f) = F(f) x SXX(f) = SXY(-f) = (SXY(f)), where denote complex conjugation of energy spectral density (ESD) and F(f) represent the Fourier transform of a moving average window/filter which is computed using time shift property of Fourier transform and its tables as, F(f) = 1/T x {TSinc(fT) x exp(-jpfT)} = Sinc(fT) x exp(-jpfT) . The proposed algorithm developed from eqs. (9) and (10) is presented in section 4 (B). We just need to show that the representation of eq. (9) in frequency domain indeed represents the Fourier Transform of the moving average filter as mentioned above.

Thus, using Linearity and Time Shift property of Fourier Transform, we express our eq. (9) as where H(f) represent the Fourier Transform of an exponential window defined in section 4(A) and from Tables, it is given by H(f) = 1 / (a + j2pf). We rewrite F(f) by taking H(f) common as Equation (14) represents the Fourier transform of the moving average window which was found above. In deriving eq. (14), we have first taken exp(-jpfT) common and then have utilized the Euler's identity. Finally, we have taken the limit of H(f) when a tends to zero in its result and have utilized the definition of sinc(x) = sin(px) / (px). We thus, conclude that the proposed algorithm for processing any WSS input process, X(t) in time domain through exponential, moving average, triangular and trapezoidal shaped windows is therefore validated.

6 CONCULUSIONS

In this paper, we discussed and presented a very simple, elegant and efficient technique in time domain for computing the cross and auto correlations of two jointly WSS processes through various types of windows also known as Low Pass Filtering (LPF) of the input Process. First, we processed the input WSS process through an exponential window and after words utilized it intelligently for processing the input WSS process through the moving average, triangular and trapezoidal shaped windows. Finally, we did the validation of the proposed algorithm by processing input WSS process through an exponential shaped window and further verifying the result for the moving average filter (by making a - 0 ) through the use of Literature. The worst case time complexity of the proposed algorithm is O(N) which is better than the worst case time complexities of the conventional convolution performed in time and freque techniques.

One significant feature of the proposed algorithm is that it can easily be extended to process discrete-time WSS processes through discrete version of these windows without using the time domain convolution and z- Transform techniques which is in fact a great achievement.

ACKNOWLEDGMENT

We are extremely grateful to the Department of Electrical Engineering of COMSATS Institute of Information Technology (CIIT) for carrying out this work. Moreover, we are also thankful to the anonymous reviewers for their valuable suggestions towards the improvement with respect to the quality of the paper.

REFERENCES

1. M. H. Hayes, Statistical Digital Signal Processing and Modeling, John Wiley and Sons, Inc., 2004.

2. A. V. Oppenheim, R. W. Schafer and J. R. Buck, Discrete-time Signal Processing, Pearson edition, 2nd edition, 1994.

3. J. G. Proakis and M. Dimitris, Digital Signal Processing, (Principles, Algorithms and Applications), Pearson son edition, 4 edition, 2011.

4. M. H. Hayes, Digital Signal Processing, Tata McGraw-Hill, 2005.

5. A. B. Carlson, P. B. Crilly and J. C. Rutledge, Communication Systems. 4 2002, New York, NY 10020. Edition, McGraw Hill,

6. S. K. Mitra, Digital Signal Processing, Tata McGraw- Hill, 3rd edition, 2006.

7. A. V. Oppenheim, A. S. Willsky with S. H. Nawab, Signals and Systems, 2nd edition, Prentice Hall, New Delhi, India, 2004.

8. Hwei P. Hsu, Schaum's Outlines on Signals and Systems, 3rd Edition, Tata McGraw Hill, New Delhi, 2004.

9. Simon Haykin and Barry Van Veen, Signals and Systems, 2nd Edition, John Wiley and sons, 2007.

10. A. L. Garcia, Probability and Random Processes for Electrical Engineering. 2nd Edition, Addison Wesley Publishing Company Inc., 1994.

11. A. Papoulis and S. U. Pillai, Probability, Random Variables and Stochastic Processes. 4th Edition, Tata McGraw Hill, India, 2002.

12. Ansari, E. A. and Rajatheva,N., Performing Low Pass Filtering through Different Types of Windows in Linear Time. International Conference on Information Science, Signal Processing and its Applications (ISSPA 2010), Kuala Lumpur, Malaysia, May 10-13, 2010.

Department of Electrical Engineering, COMSATS Institute of Information Technology, 1.5 km Defense Road, off Raiwind Road, 53700, Lahore, Pakistan {dransari1, sakhtar2, munadeem3{@ciitlahore.edu.pk} corresponding author's email: {dransari@ciitlahore.edu.pk}

Printer friendly Cite/link Email Feedback | |

Author: | Ansari, Ejaz A.; Akhtar, Saleem; Nadeem, Muhammad |
---|---|

Publication: | Science International |

Article Type: | Report |

Date: | Dec 31, 2013 |

Words: | 3372 |

Previous Article: | A CASE STUDY OF EFFORT ESTIMATION IN AGILE SOFTWARE DEVELOPMENT USING USE CASE POINTS. |

Next Article: | CONVENTIONAL AND ISLAMIC ANOMALIES IN KARACHI STOCK EXCHANGE. |

Topics: |