# Simplified Welch Algorithm for Spectrum Monitoring
## 2 Fourier Transform and Welch Algorithm
### Welch's Method  
The main usage of the Fourier transform is to get the frequency samples of an input signal. For a discrete signal, the FFT can be applied to a certain number of samples or, depending on the sampling frequency, a certain amount of time of the signal. Represented spectrum in DFT is limited to half of the sampling frequency. This method is widely used, but the problem is the ambient noise and limitation due to the finite number of samples in the input window. The situation of signals that travel in communication channels is even worse. They experience channel with additive white Gaussian noise (AWGN). Depending on the travelling method and the distance between transmitter and receiver, the noise level may cover the signal and make it harder for the receiver to extract the PSD with acceptable details. In noisy situations, spectrum monitoring requires more and more data time samples for the correct estimation of the frequency components. The Welch algorithm [18; 19] is a nonparametric method to estimate the PSD and it makes the frequency spectrum smoother than the raw FFT output. Let us consider that the FFT is calculated over the entire duration of the signal. In the Welch algorithm, instead of processing the FFT over the entire time domain, the signal is separated in windows with the same size. Window size affects the clarity of the result by cutting frequencies with periods larger than the window. Windowing is taking a sample of a larger dataset and tapering the signal at the edges of each interval. This makes the signal smoother without sharp transitions that can disturb the frequency spectrum representation [11]. There are different types of windowing sequence like Hamming and Blackman, which affect the result differently. Each window overlaps the adjacent windows by a certain factor, which can be as much as 50% of the total window size. Overlapping helps to reduce the loss of information because of the tapering and display a more reliable periodogram. The Fourier transform is calculated on each interval, and the value is squared. This results in a modified periodogram value that is the base of the PSD calculation. Finally, the average of all periodograms are calculated as PSD estimation. Averaging enhances the SNR and it is optimal for spectrum monitoring. The issue with the Welch algorithm is that the frequency resolution is reduced compared to the FFT. Let us consider a discrete time signal \(s\) with \(N\) samples:  
\[s=x[1],\ x[2],\ \ldots,\ x[N] \tag{3}\]The signal can be separated in \(K\) smaller intervals with \(M\) length and \(V\) overlapping:  
\[ \begin{array}{c}1:s_{1}=x[1],\ x[2],\ \ \ldots,\ x[M]\\ 2:s_{2}=x[M-V+1],\ x[M-V+2],\ \ldots,\ x[2M-V]\\ \ldots\\ K:s_{K}=x[(K-1)M-(K-1)V+1],\ \ldots,\ x[KM-(K-1)V]\end{array}  \tag{4}\]  
where \(s_{i}=\ \{s_{i}[1],s_{i}[2],\ \ldots s_{i}[M]\}\) represents the \(i\)th window and \(K\) is number of the involved window in the PSD calculation. The DFT is calculated for each window:  
\[S_{i}[v]=\ \sum_{m=1}^{M}s_{1}[m]\cdot w[m]\exp\left(\frac{-2\pi jmv}{N_{F}} \right)\ 1\leq v\leq N_{F} \tag{5}\]  
where \(w=\ \{w[1],w[2],\ldots w[M]\}\) is the windowing vector, \(N_{F}\) is the DFT size, and \(S_{i}=\ \{S_{i}[1],S_{i}[2],\ \ldots S_{i}[N_{F}]\}\) represent the vector of frequency samples of \(i\)th input window. Periodogram values are squared of the absolute value of the DFT samples:  
\[P_{i}[v]=\ \frac{1}{C}\ |S_{i}[v]|^{2}\ 1\leq v\leq N_{F} \tag{6}\]  
where \(C\) is normalization factor:  
\[C=\sum_{m=1}^{M}w^{2}[m] \tag{7}\]  
Calculated periodogram values from different windows are averaged and the Power Spectral Density estimate is obtained:  
\[PSD(v)=\ \frac{1}{K}\sum_{i=1}^{K}P_{i}[v]\ 1\leq v\leq N_{F} \tag{8}\]  
The number of packets involved in averaging directly affects the estimated \(PSD\) in different ways. First, as more packets are involved, estimation uses more past data and a smoother spectrum is obtained. In other words, average order \(K\) is controlling the dependency on the past.