Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe’s Galileo Operations and Evolution.
Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe’s Galileo Operations and Evolution.
The signal-processing methods currently used to detect interfering signals have reached their practical limits and have little more to offer in dealing with problem of very weak signal detection. The most popular of these include:
- the Fast Fourier Transform (FFT), which directly transforms a signal into its spectral representation
- the Short Time Fourier Transform (STFT), based on the Fourier Transform (FT), which gives information about frequency and time of the signal
- the Wigner-Ville probability distribution, which also provides frequency and time information.
This column presents a very competitive alternative to FT, namely the Karhunen-Loève Transform (KLT). In contrast to the FT, the KLT offers a solution to problems that are today still intractable.
The KLT has indeed been proposed for applications to process the signals collected by astronomers worldwide in the framework of the SETI program (Search for Extra Terrestrial Intelligence). In a 2010 paper (cited in the Additional Resources section at the end of this column), Dr. Claudio Maccone presented his most recent discoveries concerning the KLT theory and its application to the detection of very weak signals hidden in noise. He also presented an example of the successful detection of an unknown sinusoidal signal with a signal-to-noise ratio (SNR) of as low as -23 decibels. He concluded that an even lower SNR could be mastered by the KLT.
Following the ideas of the SETI scientists, this column will first discuss the advantages and limitations of the KLT, especially with respect to its application to detect typical interferences of GNSS signals. After providing some theoretical insight into the KLT approach, we will present examples of a successful detection of a very weak wideband signal, including a performance comparison of the KLT to the FFT, the STFT, and the Wigner-Ville methods.
KLT: Worth Our Attention
The KLT was not chosen for weak signal detection by accident. Several factors explain why KLT could be an appropriate mathematical tool for that purpose. As the Fourier Transform is of paramount importance in signal processing nowadays, this article uses it as the reference transform against which the KLT properties are compared.
The main advantages of the KLT compared to the FT are the following:
1. The KLT works equally well for narrowband and wideband signals, while the FT is optimized for narrowband signals only. This feature makes the KLT more adjustable to bandwidths characteristic for GNSS signals.
2. Both transforms decompose the signal using a set of base functions. When comparing these functions, one notices that the KLT is a more flexible transform, because its basis functions can be of any form. This results in a better decomposition of the signal. The FT is very limited here because its basis functions are strictly limited to sines and cosines.
3. The KLT merges deterministic and stochastic analyses of the signal, which is a very powerful attribute not found in other methods. Although the set of KLT basis functions is deterministic, it does also provide information on the stochastic nature of the signal, rather characterizing an expectation of the power of the basis functions than their exact value. Consequently the KLT grades the basis functions with respect to their probable power contribution thus allowing one to efficiently distinguish the signal from the noise. This implies that, when using the KLT, the processed signal can be filtered by keeping only the most interesting, non-stochastic part and omitting the rest, which is then defined as background noise. On the other hand, when using FT an exact power value can be determined to each sine and cosine, this being the only parameter defining the signal.
4. Finally, according to experiments performed by Maccone and presented in the previously cited paper, the KLT is able to detect much weaker signals than the FT. Although this capability still must be confirmed by practical applications, it could have an enormous influence in the future.
In spite of its significant advantages, the KLT has not replaced FTs yet. In particular, associated complexity and, thus, the computational burden still speak against KLT and in fact favor classical FFT. The Fourier Transform has its fast, numerical implementation called Fast Fourier Transform with a complexity of O(n*log(n)) (i.e. n*log(n) addition/multiplication operations on data of length n). The complexity of the numerical implementation of the KLT is much higher — O(n2).
The underlying reason for this difference is that the FFT uses a predefined set of orthogonal functions (sines and cosines), whereas the KLT looks for the best representation of the orthogonal function for each individual signal …
KLT and FFT – Analogies and Differences
The Karhunen-Loève Transform and the Fourier Transform have many analogies but also important differences. To gain further insight into the mathematical characteristics of each of them, let us compare the equations for the Fourier series of a deterministic periodic signal x(t) and its analogous KL expansion of a stochastic process of the signal X(t) are compared.
. . .
But the most revolutionary aspect of the KL expansion is still to come.
Unlike the FT, the coefficients Zn of the KL expansion of a stochastic process X(t) are pure random variables. In contrast to an and bn of the Fourier series, the KL coefficients reflect the stochastic nature of the data under analysis.
. . .
During simulations for which results are presented later in this article, discrete signals were processed and the length of the autocorrelation was finite. Under these conditions, the eigenvalues of a noise-only signal converge to one and are equal to one on average.
. . .
This theoretical introduction leads us to the practical part. Our purpose here was to investigate the capabilities of the KLT as applied to weak signal detection, especially those that can be harmful to GNSS signals on the receiver side and are to be detected from far distance.
In order to gain better insight into the detection capabilities offered by the various well-known methodologies, we tested them using the same input data. We structured the tests in three stages. The first example demonstrates how the KLT decomposes a signal and identifies the eigenvalues and eigenfunctions of the data. Next, a narrowband, single sinusoidal signal was selected to check the performance of the KLT.
The final example addresses the wideband signal detection capabilities of the various approaches. We carried out the last exercise (or stage) for two kinds of signals: a BPSK (binary phase shift keying) modulated signal, representing a stationary signal to reveal the KLT’s limitations on wideband signals (Example 3) and a wideband chirp, which represents Example 4 and enabled the testing of the KLT’s behavior in the presence of a non-stationary signal.
Example 1: Decomposition of the Signal
This simple example shows how the decomposition of a signal X(t) is performed using the KLT. The decomposition starts with the computation of the linear autocorrelation function of the received signal. The next step is to build an autocorrelation Toeplitz matrix and use equation (7) to solve a set of linear equations. The result of this equation is the set of eigenvalues and their corresponding eigenfunctions.
. . .
Example 2: Narrowband Signal Detection
Having illustrated the decomposition of a simple signal in low noise environment using the KLT, the next step is to investigate the limits of the KLT technique to detect signals in very strong noise environment. In the following test the KLT performance is compared also against that of an FFT. Note that only one eigenfunction is used to estimate the signal.
. . .
Example 3: Wideband Signal Detection
The previous example showed that the KLT performs better than the FFT in narrowband signal detection. Next, the KLT is applied to wideband signals. A BPSK-modulated signal serves as the sample signal for detection.
. . .
In the following sections, we present the results of applying KLT, STFT, and Wigner-Ville methods to detect a hidden BPSK signal with an SNR level of -12 decibels. For each method two plots are presented. The first shows the spectrogram of the processed signal, and the second plot shows the power spectrum estimation obtained by averaging the spectrogram.
KLT . . .
STFT . . .
Wigner-Ville . . .
Example 4: Chirp Signal Detection
We also analyzed a chirp signal with a wide frequency boundary. This type of signal was chosen to enable us to evaluate the performance of KLT in detecting a dynamic, non-stationary signal.
. . .
BAM-KLT: A Step Closer to Fast KLT
Again, the biggest drawback of the KLT is its complexity and the resulting high computational burden. As with the Fourier Transform, however, which become popular when its fast implementation (the FFT) became available, the KLT has the potential to experience a similar boost if a fast KLT implementation is discovered.
. . .
BAM-KLT and Wideband Signals
Because very promising results of single-tone detection in a strong noise were presented in Maccone’s paper, we thought it worthwhile to test the detection capabilities of BAM-KLT for wideband signals. The following results are based on identical test conditions as in the previous tests for estimation of a wideband signal spectrum. First the results of hidden BPSK(1) signal detection are presented, followed by the detection of a chirp.
. . .
BAM-KLT and Chirp Signal Detection
BAM-KLT shows a much better performance when it comes to chirp signals. But it is, of course, still not as good as the original KLT. From the spectrogram it can be seen that the chirp was detected successfully. Nonetheless, a very strong DC component appears in the spectrum, which could make the detection of a low-frequency signal impossible. One can say that the BAM-KLT is already powerful enough to detect narrowband signals, excluding low-frequency signals, which are buried by strong DC component observed in the plots.
Conclusions
This article shows that the KLT technique has very high potential and can outperform the classical signal detection methods that are used today. The KLT is equally capable of detecting both narrowband and wideband signals, which deserves close attention if we think of future applications in the field of GNSS.
The simulations presented here indicate that this transform allows us to detect more feeble signals than FFT, STFT, and Wigner-Ville methods can. The main strength of the KLT is its natural feature of adapting to the characteristics of the processed signal. As a result, it allows the filtering of a non-stochastic signal from noise.
The KLT is also more flexible and configurable than other known methodologies. This permits the user to directly control the level of filtering. The remarkable detection capabilities of KLT, however, must be paid for by a high computational burden.
BAM-KLT, which shows excellent detection performance when applied to pure sinusoidal functions, is capable of significantly reducing the computational load. Therefore, some analogies between the BAM-KLT and the FFT can be drawn. Indeed, the introduction of the FFT made it possible to exploit the Fourier Transform in a numerically efficient way.
A similar future could be expected for the BAM-KLT. However, before BAM-KLT or a closely related methodology can be efficiently applied, the spectrum of detectable signals needs to be significantly enlarged. This article shows that the BAM-KLT is not yet capable of unambiguously detecting wideband signals such as BPSKs appearing as noise or interference in a GNSS-like signal. So, further research work needs to be invested in this area. One potential starting point could be to identify relations between the signals to be detected, the windowing function, and the number of characteristic eigenvalues.
In summary, we can say that the KLT is a very high-performing mathematical tool and could prove to be of great value for the detection of feeble interfering signals. However, the method still needs further development in order to become faster, more efficient, and easier to use.
Future work on this topic could be to explore the limitations of the KLT in wideband signal detection, in order to get a better idea of the full capabilities of KLT in regards to wideband signals in general. Another promising work would be to reduce the complexity of a KLT implementation. Here the BAM-KLT approach already offers a promising step towards a competitive signal analysis method that meets the needs of the scientific community.
For the complete story, including figures, graphs, and images, please download the PDF of the article, above.
Acknowledgment
I would like to thank my supervisor Dr. José-Ángel Ávila-Rodríguez who encouraged me to write this article and for his advice and support during this project. I also want to thank my colleagues from the ESA European GNSS Evolution Program: Jan Speidel, Stefan Wallner, and Pierre Crucis, whose comments and ideas helped me to improve the quality of this article.
Additional Resources
[1] Heinzel, G., and A. Rüdiger and R. Schilling, “Spectrum and spectral density estimation by the Discrete Fourier transform (DFT), including a comprehensive list of window functions and some new at-top windows,” Max-Planck-Institut für Gravitationsphysik (Albert-Einstein-Institut) Teilinstitut Hannover, February 15, 2002
[2] Maccone, C., “The KLT (Karhunen–Loeve Transform) to extend SETI searches to broad-band and extremely feeble signals,” Acta Astronautica (2010), doi:10.1016/j.actaastro.2010.05.002
