Field of the invention

[0001] The present invention is related to the field of detecting tones below the original noise floor in non-uniform undersampled signals, in particular signals where sampling is intentionally or by nature non-uniform, such as radio, seismic, medical signals.

Background of the invention

[0002] In the future many cognitive radio networks may rely on spectrum sensing to monitor and coordinate the instantaneous use of the spectrum. Indeed, the utilization of the radio spectrum by licensed and unlicensed wireless systems, e.g., TV broadcasting, cellular systems, wireless local area networks, etc ... is reported to be actually quite low. Specifically, the instantaneous usage of many frequency bands is very irregular. This has triggered the idea of reusing the unused portions of the spectrum by secondary users in an opportunistic way with cognitive radios (CR). For CR to be able to reuse unused frequency bands, spectrum sensing is a necessity. Since large bands of several GHz may have to be sensed in the near future, sampling at the Nyquist rate can be prohibitive. Fortunately, because the spectrum is largely under-utilized, the signal to be sensed is sparse in the frequency domain. Compressive sensing (CS) exploits this sparsity.

[0003] In many applications, such as medical, seismic, earth science, astronomy, instrumentation, it is desirable or even unavoidable to reduce the number of samples taken from the input signal without changing its characteristics. If the number of samples taken is reduced below the Nyquist rate, aliasing occurs and perfect reconstruction is no longer possible. However, if the sampling instants are not taken at a constant rate or in other words if the sampling instants do not lie on a regular grid, it is still possible to reduce or completely avoid aliasing. Perfect signal reconstruction is even possible under certain conditions, one of them stating that the average sampling rate must be higher than the so-called Landau-Nyquist rate (i.e. twice the sum of the bandwidths of all signals) and the sampling instants must be chosen in a special way, which is a challenging problem. Hence, non-uniform random sampling is usually applied. However, doing so creates significant leakage in the spectral estimate of the signal, resulting in a degraded SNR.

[0004] When an undersampled signal must be reconstructed, the framework of compressive sensing (CS) can be used. The central results of CS state that a sparse undersampled signal can be recovered by solving a convex (and rather complex) program. However, for sensing or detection perfect reconstruction is not necessary. What is needed, is a spectrum estimate sufficiently reliable to decide correctly about the presence or absence of signals. In the case of detection for example, the goal is rather to detect the presence of all signal components with a reasonable probability of detection and probability of false alarm.

[0005] Regarding notational conventions, normal Latin characters are used for time-domain signals (a) and tilde characters for frequency-domain signals ( a_ ), vectors and matrices are denoted by a single and double under-bar, respectively, ( a and A ). The superscripts ^T and ^H denote the matrix transpose and complex conjugate transpose, respectively (A ^7" and A ^H ). The superscript ^ is used to

(A ^r )

indicate the pseudo-inverse — .

[0006] Some background information on non-uniform sampling is now provided. Given a continuous-time signal x _c (t), sampling is achieved by element-wise multiplication with a sampling function s(t) which is a series of Dirac pulses, yielding the sampled signal x _s (t), and its frequency- domain counterpart X _s f) :

.' .' f ; = y xc(t)6(t- kTs)

(i)

In the case of non-uniform sampling, when sampling occurs at times t _s (k) = t _k that do not lie on a regular grid, the time and frequency-domain representations of the signal are: s —

(4)

[0007] The familiar form of the spectrum in (2) shows that the main spectrum is replicated at every integer multiples of the sampling rate F _s = 1/T _S . On the contrary, nothing can be said about the (non-)periodicity of the spectrum of a non-uniformly sampled signal as given in (4). The Power Spectral Density (PSD) of a non-uniformly sampled sequence contains both attenuated replicas and frequency leakage. However, if the observation time is long enough and the time instants t _k are sufficiently random, all spectral replicas disappear. [0008] In order to illustrate the difference between conventional DFT-based spectral estimation and the non-uniform sub-Nyquist DFT better, an extended DFT for non-uniform undersampled signals is defined as follows:

X(n) = -^= J ff(tfc)e- ^i¾r i ^tft K£ ^Fff

N N

n =— m— - - ^■ fM—— 1

(5)

Equation (5) simplifies to the conventional uniform, Nyquist sampled DFT (U-DFT) when m = 1 and t _k = kTs. Uniform undersampling, corresponding to an extended uniform DFT (U-eDFT), is achieved when m > 1 and t _k = kT _s , and non-uniform undersampling, corresponding to a non-uniform extended DFT (NU-eDFT), when m > 1 and t _k ≠ kT _s . In the case of NU-eDFT the average sampling rate _{S av} is equal to F _s = 1/T _S .

[0009] The different properties of these DFTs are illustrated with an example. A signal is generated consisting of six complex exponentials at different frequencies within the interval [—m _j ^{m —} l] _< ^w ' ^TN AT? = 4 (see Fig. la). The tone magnitudes and frequencies and all DFTs plotted in Fig.lb-d. Fig. lb shows the conventional U-DFT having a frequency range limited to [— F _s /2 , F _s /2] and aliased frequencies outside this range. The U-eDFT in Fig.lc does not provide any additional information. Rather, the aliased spectrum of Fig. lb is repeated AT? = 4 times. The NU-eDFT as per (5) is plotted in Fig.ld and shows that the aliasing is indeed eliminated and that the amplitudes of the peaks (labels a'-f) are only approximately correct, i.e. they are not exact. In addition, there is a significant amount of frequency leakage. This phenomenon is one of the most severe limitations of non-uniform sub-Nyquist sampling because it can mask weak signals in the PSD of a signal.

[0010] The time (x) and frequency (x) domain representation of a signal consisting of the sum of M complex exponentials (each defined by their complex amplitude w, and frequency fa) and additive complex white Gaussian noise of variance σ% can be expressed after sampling as:

where t is the (JV x l) time vector [t ₀ ^■■■ t _N _ ₁ ], f is the (mN x 1) frequency vector

[— m/2 ^••• m/2 — (1/2ΛΠ] and F is the (rectangular) NU-eDFT matrix. 1

F =—= =e ^{^i(2} ¾ > fmiV x N)

~ ^{/W '} (8)

[0011] One now wants to detect the presence of all signal components with a reasonable probability of detection and probability of false alarm. Fig.2 illustrates the NU-eDFT for a signal consisting of 10 tones and shows that a simple peak search on the magnitude will detect only the strong peaks (labels 1 to 6), and not the weaker tones, i.e the tones buried in the noise-like leakage.

[0012] A well-known leakage reduction technique to overcome this problem is called matching pursuit, which relies on peak excision. This solution is briefly revised here. In order to allow detection of weaker tones, i.e. peaks with lower amplitude, the stronger peaks together with the leakage they create, are to be removed. The rationale for this is that stronger tones contribute the most to the leakage. Hence, once their frequency and complex amplitude is estimated, each tone can be eliminated from the received signal and the search for lower magnitude tones can continue.

[0013] First, the strongest peak p ₁ in the frequency spectrum is detected/selected, which provides an estimate of its frequency f _x and complex amplitude w ₁ . The contribution of this tone to the global signal is expressed in the time-domain as: p — Witi ^■ · — Wi'y

(9)

The signal after the first excision is described by:

- £J

- ^l - -i (lo)

ί = F_■ (x— p _i ) = x— F_■ p _i which shows that the excision can be performed in either the time or frequency domain. This process can then be repeated with the second strongest peak and so on until some convergence criterion is met. In this method the estimation of both the frequency fj and the complex amplitude wj is performed in the frequency domain. Due to frequency domain estimate of the complex amplitude wj, the estimation can be degraded because of the leakage generated by all the other signals on the currently detected peak.

[0014] Hence, there is a need for a technique wherein this drawback is overcome.

Summary of the invention

[0015] It is an object of embodiments of the present invention to provide for a method and system for detection of tones below the original noise floor in non-uniformly undersampled signals, whereby the problem of degradation of the estimation due to leakage is reduced. [0016] The above objective is accomplished by the solution according to the present invention.

[0017] In a first aspect the invention relates to a method for detecting tones in a received signal, said signal being non-uniformly sampled at a rate below the Nyquist frequency. The method comprises the steps of :

- determining a peak in the frequency spectrum of the received signal,

- estimating the frequency of the peak,

- estimating the complex amplitude of the peak by solving an optimization problem wherein frequency leakage due to the peak at the estimated frequency is minimized,

- eliminating from the received signal the tone with the estimated frequency and complex amplitude corresponding to the peak, yielding a modified received signal with reduced frequency leakage.

[0018] The proposed method indeed counters the frequency leakage problem by estimating the complex amplitude of the peak via an optimisation method wherein the frequency leakage due to the peak at the estimated frequency is minimized. After eliminating the frequency tone with estimated frequency and complex amplitude, the frequency leakage is therefore reduced. The optimization problem is preferably solved using a least-squares method.

[0019] In a preferred embodiment also at least one neighbouring frequency of the estimated peak frequency is taken into account in the optimization problem.

[0020] Preferably the method steps are repeated on the modified received signal, whereby in each iteration one or more peaks of the remaining, modified received signal are estimated and subsequently eliminated, thereby further reducing the frequency leakage effect. Advantageously, in such embodiment the method steps are performed iteratively until at least one convergence criterion is met. In one embodiment the at least one convergence criterion compares leakage power before and after the step of eliminating said tone is performed. In an alternative embodiment the at least one convergence criterion compares the power at the peak to the power in the rest of the frequency spectrum. Both options can be combined in a further embodiment.

[0021] In a preferred embodiment more than one peak is processed in a single iteration.

[0022] In another embodiment the step of eliminating is performed only if a given condition is met. The elimination is then performed only if it contributes in reaching an improved overall solution.

[0023] In a second aspect the invention relates to a device for detecting tones in a received signal, said signal being non-uniformly sampled at a rate below the Nyquist frequency. The device comprises

- means for determining a peak in the frequency spectrum of the received signal, - estimation means arranged for estimating the frequency of the peak and for estimating the complex amplitude of the peak by solving an optimization problem wherein frequency leakage due to the peak at the estimated frequency is minimized, and

- excision means for eliminating from the received signal the tone with the estimated frequency and complex amplitude corresponding to the peak, yielding a reduced received signal.

[0024] In a preferred embodiment the device is further arranged for executing a convergence test.

[0025] For purposes of summarizing the invention and the advantages achieved over the prior art, certain objects and advantages of the invention have been described herein above. Of course, it is to be understood that not necessarily all such objects or advantages may be achieved in accordance with any particular embodiment of the invention. Thus, for example, those skilled in the art will recognize that the invention may be embodied or carried out in a manner that achieves or optimizes one advantage or group of advantages as taught herein without necessarily achieving other objects or advantages as may be taught or suggested herein.

[0026] The above and other aspects of the invention will be apparent from and elucidated with reference to the embodiment(s) described hereinafter.

Brief description of the drawings

[0027] The invention will now be described further, by way of example, with reference to the accompanying drawings, wherein like reference numerals refer to like elements in the various figures.

[0028] Fig.l(A-D) illustrate the problems of tone detection when using uniform DFT (U-DFT), extended uniform DFT (U-eDFT) and non-uniform extended DFT (NU-eDFT).

[0029] Fig.2 illustrates the problem of detection of tones below the original noise floor when using NU-eDFT.

[0030] Fig.3 illustrates a block diagram of the tone detection system according to an embodiment of the invention.

[0031] Fig.4 represents a flowchart of the tone detection system according to another embodiment of the present disclosure.

[0032] Fig.5 illustrates performance curves for a first scenario.

[0033] Fig.6 illustrates performance curves for a second scenario.

[0034] Fig.7 illustrates performance curves for a second scenario.

Detailed description of illustrative embodiments [0035] The present invention will be described with respect to particular embodiments and with reference to certain drawings but the invention is not limited thereto but only by the claims.

[0036] Furthermore, the terms first, second and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a sequence, either temporally, spatially, in ranking or in any other manner. It is to be understood that the terms so used are interchangeable under appropriate circumstances and that the embodiments of the invention described herein are capable of operation in other sequences than described or illustrated herein.

[0037] It is to be noticed that the term "comprising", used in the claims, should not be interpreted as being restricted to the means listed thereafter; it does not exclude other elements or steps. It is thus to be interpreted as specifying the presence of the stated features, integers, steps or components as referred to, but does not preclude the presence or addition of one or more other features, integers, steps or components, or groups thereof. Thus, the scope of the expression "a device comprising means A and B" should not be limited to devices consisting only of components A and B. It means that with respect to the present invention, the only relevant components of the device are A and B.

[0038] Reference throughout this specification to "one embodiment" or "an embodiment" means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, appearances of the phrases "in one embodiment" or "in an embodiment" in various places throughout this specification are not necessarily all referring to the same embodiment, but may. Furthermore, the particular features, structures or characteristics may be combined in any suitable manner, as would be apparent to one of ordinary skill in the art from this disclosure, in one or more embodiments.

[0039] Similarly it should be appreciated that in the description of exemplary embodiments of the invention, various features of the invention are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure and aiding in the understanding of one or more of the various inventive aspects. This method of disclosure, however, is not to be interpreted as reflecting an intention that the claimed invention requires more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive aspects lie in less than all features of a single foregoing disclosed embodiment. Thus, the claims following the detailed description are hereby expressly incorporated into this detailed description, with each claim standing on its own as a separate embodiment of this invention.

[0040] Furthermore, while some embodiments described herein include some but not other features included in other embodiments, combinations of features of different embodiments are meant to be within the scope of the invention, and form different embodiments, as would be understood by those in the art. For example, in the following claims, any of the claimed embodiments can be used in any combination.

[0041] It should be noted that the use of particular terminology when describing certain features or aspects of the invention should not be taken to imply that the terminology is being redefined herein to be restricted to include any specific characteristics of the features or aspects of the invention with which that terminology is associated.

[0042] In the description provided herein, numerous specific details are set forth. However, it is understood that embodiments of the invention may be practiced without these specific details. In other instances, well-known methods, structures and techniques have not been shown in detail in order not to obscure an understanding of this description.

[0043] The invention relates to a solution for signal sensing below the original noise-like leakage in non-uniformly undersampled signals, in particular signals where sampling is intentionally or by nature non-uniform, such as, but not limited to radio, seismic, medical signals and the like. The disclosed implementation includes excision entirely in the frequency domain and ways to reduce gradually frequency leakage thereby making signal detection below the original noise floor possible. Although the present description mainly refers to tone detection, it may be noted that the present disclosure may also find application in signal reconstruction.

[0044] Fig.3 shows a block diagram illustrating an embodiment of the proposed solution for tone detection below the original noise floor in non-uniform undersampled signals. In case the received signal is a time-domain signal, the system advantageously comprises a time to frequency convertor for generating a frequency spectrum by applying a non-uniform extended Discrete Fourier Transform (NU-eDFT). The system is arranged for iteratively excising peaks, i.e. frequency components, in the frequency spectrum. The system as shown in Fig.3 further comprises a peak selector for selecting one or more peaks, a complex amplitude estimator for estimating the complex amplitude of the selected peak(s), e.g. via a least-squares method, such that the impact of the leakage is minimized. In this way the detection of weaker signals, signals below the original noise floor, is made possible. An excision unit for performing the peak excision, i.e. the actual elimination of the peak, is shown as well in Fig.3. The peak excision process is controlled by a convergence unit, wherein the peak excision is performed until one or more convergence criteria are met. The tone detection system outputs the complex frequency and optimal complex amplitude of the excised peaks, thereby yielding sensing information. [0045] Fig.4 shows a flowchart illustrating an embodiment of the proposed method for tone detection below the original noise floor in non-uniform undersampled signals. The method comprises the (optional) step of generating a frequency spectrum, preferably by applying a non-uniform extended Discrete Fourier Transform (NU-eDFT), after which peaks, i.e. frequency components in the spectrum, are iteratively excised. For performing the peak excision further a step of selecting one or more peaks may be carried out, next one or more complex amplitudes of the selected peaks are estimated, optionally via a least-squares method such that the impact of the leakage is minimized. In that way the detection of weaker signals, signals below the original noise floor, is made possible. Then the actual peak excision, i.e. the elimination of the peak(s) processed in that iteration, is performed. The peak excision is repeated until one or more convergence criteria are met.

[0046] In one embodiment of the present invention the estimation of the complex amplitude wj is performed by minimizing a least-squares criterion. Assuming that the frequency f _x is correct, the leakage L ₁ after excision of the first tone is

= (x - u¾« ) ^H · H · (x— w _t y ) .

(12)

where denotes the contribution of the first tone to the global signal expressed in the time domain and G_ = F_ ^H■ A ^H■ A - F_ and A is an identity matrix except for some zeros at the indices corresponding to the frequency f _x and its close neighbouring frequencies (e.g. three frequency bins at each side). Those zeros avoid the peak due to p ₁ in the estimation of the leakage caused by p ₁ itself.

The complex amplitude w that minimizes the leakage given f _lt is the value of w for which the derivative of L ₁ is zero :

The optimal value of w ₁ follows directly:

This process is then repeated with the second strongest peak and so on until one or more convergence criteria are met (see below). [0047] In another embodiment joint estimation is applied of the complex amplitude of multiple tones in a single operation if several peaks are detected/selected at once. The method developed above is then augmented with one dimension to handle multiple tones, where the excision of Q tones is given as

p = Y · w

- = - (is)

where Y_ is a matrix whose q ^th column is a complex exponential at frequency f _q and w is a vector containing the corresponding Q complex amplitude w _q . The optimization problem can then be written as tii = arg mm ί · ⁽ _ Y w) · (i ¹ w_ ^{H ■} Y_ ^H J }

„ ._ ^> _ _ (16) where G_ = F_ ^H■ A ^H■ A ^■ F_ as for the single tone case but A is an identity matrix except for some zeros at the Q indices corresponding to the frequencies f _q and their close neighboring frequencies. The solution is obtained by setting all partial derivatives to zero

( L ) = 0.

ow

(17)

Solving (17) yields (18)

which is a generalization of (14). This process is then repeated with a second group of peaks and so on until one or more convergence criteria are met.

[0048] In order to avoid false detections and false alarms, the tone detection scheme can be provided with one or more convergence criteria performed e.g. after each iteration. Two preferred convergence criteria to use are the following.

[0049] One option relates to a convergence criterion defined as a "leakage reduction" criterion, wherein the leakage power before and after an excision is measured. As long as the excision reduces the leakage power, the iterative process can continue. Otherwise, the last peak detection (which would result in a bad excision) is not used for excision and the process is halted. This test mostly avoids wrong detections after several peaks have been eliminated.

[0050] Another possible test relates to a convergence criterion defined as a "peak quality" criterion, wherein the ratio of the power of the currently detected strongest peak to the power of the rest of the spectrum is estimated. This criterion is useful for terminating the iterations but also to avoid starting new iterations when noise only is present. [0051] To illustrate the benefit in terms of performance of the proposed solution for spectrum sensing with non-uniform undersampling over the prior art technique of matching pursuit (where no measures are taken at all with respect to frequency leakage), some simulations have been carried out. Three scenarios are considered. A first scenario corresponds to the detection of a few narrowband signals. Ten tones are assumed and m = 4. In a second scenario there are three broadband signals, each 10 tones wide and again m = 4. This corresponds to sensing modulated signals with moderate bandwidth, with a low spectrum usage. In a third scenario three signal are considered, each two tones wide, and three signals, each 20 tones wide, again with m=4. This corresponds to the sensing of a more 'crowded' environment with a mix of narrowband and broadband modulated signals.

[0052] The results for the three scenarios are shown in Figs 5, 6 and 7. Note that what in the figures is called 'method 1', corresponds to the prior art technique of matching pursuit, while 'method 2' denotes a solution according to the invention whereby a single tone is excised per iteration and 'method 3' a solution according to the invention whereby multiple tones are excised per iteration. The figures highlight the superior performance of the methods of the invention wherein the frequency leakage is minimized (hence, 'method 2' and 'method 3'). When the number of signals increases, the detection probability of matching pursuit ('method ) starts to saturate because it does not cope well with the leakage. It can also be observed that, due to the convergence criteria, the level of false detections for all methods is kept to a small value.

[0053] A method to perform spectrum sensing on non-uniformly under-sampled signals has been disclosed in this invention. The non-uniform sampling is useful for suppressing the frequency domain aliasing that normally comes along with under-sampling. In order to deal with frequency leakage that masks weaker signals, a method for frequency excision is presented that reduces the impact of this leakage. The simulation results shown above illustrate that the proposed method is applicable to tones, narrowband and wideband signals and mixtures thereof. Hence, it is useful for a wide range of spectrum sensing scenarios. This technique is especially attractive for wide F band sensing with a fast ADC that is driven much below the Nyquist rate to save power.

[0054] While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. The foregoing description details certain embodiments of the invention. It will be appreciated, however, that no matter how detailed the foregoing appears in text, the invention may be practiced in many ways. The invention is not limited to the disclosed embodiments. [0055] Other variations to the disclosed embodiments can be understood and effected by those skilled in the art in practicing the claimed invention, from a study of the drawings, the disclosure and the appended claims. In the claims, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. A single processor or other unit may fulfil the functions of several items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage. A computer program may be stored/distributed on a suitable medium, such as an optical storage medium or a solid-state medium supplied together with or as part of other hardware, but may also be distributed in other forms, such as via the Internet or other wired or wireless telecommunication systems. Any reference signs in the claims should not be construed as limiting the scope.