Finding the Interference
Karunhen-Loeve Transform as an Instrument to Detect Weak RF Signals
GNSS signals, like other RF signals in general, are exposed to interference and jamming. In GNSS however, the problem is far more challenging and difficult to solve. The low signal power on the ground resulting from the large distance the satellite signals have travelled make them particularly sensitive to interference, even if the power levels of the interfering signals are modest. This column discusses a mathematical tool — the Karhunen-Loève Transform — that can help detect interfering signals with power levels similar to or even lower than those usually received on earth from GNSS satellites today.
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:
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 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
. . .
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
. . .
Example 2: Narrowband Signal Detection
. . .
Example 3: Wideband Signal 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
. . .
BAM-KLT: A Step Closer to Fast KLT
. . .
BAM-KLT and Wideband Signals
. . .
BAM-KLT and Chirp Signal Detection
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.
Copyright © 2017 Gibbons Media & Research LLC, all rights reserved.