# Cascaded Multitype Interferences Suppression Method Using Sparse Representation and Array Processing for GNSS Receiver

Authors: Qiang Guo; Liangang Qi
Journal: International Journal of Antennas and Propagation
 (2017)

---

## Abstract

Interference suppression techniques have been intensively studied in nearly two decades due to their importance for maintaining the integrity and functionality of global navigation satellite system (GNSS). However, the interference suppression method applicable for the complex receiving environment in which there are multitype interfering signals has not been considered in most of the researches. To deal with this problem better, a cascaded multitype interferences suppression method using sparse representation and array processing is proposed. In the first stage, according to the sparsity of the narrowband and modulated wideband interference signals, a novel parallel multichannel signal interference suppression method based on matching pursuit (MP) algorithm and a design strategy for the overcomplete dictionary are proposed to mitigate the interferences with sparse features. Then, the minimum power distortionless response (MPDR) beamformer is employed in the second stage to suppress the residuary interferences (such as Gaussian noise interferences). Compared with existing algorithms, the proposed method can not only effectively suppress the interference arriving from the same direction with the desired signal and increase the Degree of Freedom (DoF) of the array antenna, but also introduce no distortion into the navigation signal. The effectiveness of the proposed method is illustrated by theoretical analysis and several simulation results.


---

## Body

## 1. Introduction

The global navigation satellite system (GNSS) has been widely used in military and civilian applications; however, the problems caused by the vulnerability of satellite navigation signals are increasingly serious. Therefore, interference suppression techniques are necessary to ensure the reliability, accuracy, and continuity of GNSS services. According to the characteristics of the GNSS, there are two ways to improve the capability of radio frequency (RF) interference suppression [1]. On the one hand, we can improve the design of navigation satellites to enhance the interference suppression performance of GNSS, such as increasing the signal transmission power, optimizing the structure of the signal; but these methods are too complex, and the cost of time and materials is too huge. On the other hand, we can improve antijamming performance of GNSS receivers. These methods are gaining significant attention due to its effectiveness for interference from multiple, strong interferers plus multipath suppression.The interference suppression techniques for GNSS receivers include time-domain processing, transform-domain processing, spatial processing, and spatial-time processing [1, 2]. The methods based on time-domain and transform-domain processing have been widely studied (e.g., [3, 4]). Although they are effective for suppressing narrowband interference signals, their performance degrades when they deal with wideband interferers such as Gaussian interferers or when the interfering signal changes rapidly in time-domain and frequency domain (e.g., swept continuous wave interference).On the contrary, the interference suppression techniques using an antenna array can effectively suppress both narrowband and wideband interferences regardless of their time and frequency characteristics. One of the most effective space-based processing methods has been referred to as the minimum variance distortionless response (MVDR) beamformer [5]. The MVDR beamformer has a distortionless response for the desired signal while rejecting all interfering signals arriving from other directions. Antenna array processing in GNSS applications has been mostly centered on interference suppression [6]. Reference [7] drew the attention on utilizing minimum power distortionless response (MPDR) beamformer to suppress interfering signals whose power is significantly higher than that of the GPS signals. However, spatial processing methods suffer from hardware complexity, and cannot effectively suppress interference whose direction of arrival (DOA) is close to the GNSS signal. To deal with these problems, techniques employing both time (or frequency) and spatial domain processing have been of great interest since [8] was published. These methods combine spatial and temporal filters to suppress more narrowband interference by increasing the Degree of Freedom (DoF) of the array without physically increasing the number of antenna array elements. Besides the superior advantages of space-time processing, these methods can introduce serious distortion and biases into the GNSS signal and pseudorange measurements [9]. To reduce this distortion, many methods have been proposed, but these methods increase the complexity of the algorithm and reduce the DoF of interference suppression [10, 11].In addition, with the rapid development of jamming technology and the increasingly complex electromagnetic environment, there are multiple types of interferences existing simultaneously rather than a single type of interference in the environment. Although the interference suppression methods mentioned in the prior context improve the performance of GNSS receivers, they still face the following problems when dealing with multiple types of interferences:(1) the cost of hardware or space is huge; (2) the methods employing both time/frequency and spatial domain processing may introduce biases and distortion into the GNSS signals.To solve the above problems, [12, 13] drew the attention on cascaded interference suppression methods based on frequency domain and spatial domain. These methods are “simple cascade structure” of the conventional algorithms, and one of the obvious shortcomings is that when the power of wideband interference is higher than that of the narrowband interference, the interference mitigation methods in the prestage are not able to detect and cancel the narrowband interference.In this paper, a cascaded multitype interferences suppression method using sparse representation and array processing for GNSS receivers is proposed. Firstly, the signal sparse decomposition theory [14] is introduced into array signal processing, which is gaining significant attention and has been successfully applied to many fields, such as clutter and jamming suppression for airborne radar [15] and signal detection [16]. A novel overcomplete dictionary composed of linear frequency modulation atoms is designed. And a parallel multichannel signal interference suppression method based on matching pursuit (MP) algorithm is proposed, which can effectively detect and suppress the narrowband and modulated wideband interferences even when they fall in the other wideband interferences (e.g., Gaussian jammers). Secondly, the MPDR beamformer is employed in the second stage to mitigate the residual interference, which enhances the steering gain of the DOA of interest. Meanwhile, the null gain is set at DOA of interference. Finally, in order to verify the effectiveness of the proposed method, it is compared to the well-known MPDR beamformer [7] and the distortionless space-time processor proposed in [10].


## 2. Signal Model

The signal received by the GNSS receiver is the aggregate of the satellite navigation signal, interfering signals, and the thermal noise. Without loss of generality and for the sake of simplicity, assume that they are independent of each other and there is only one GNSS signal. Considering an arbitrary antenna array withN elements, the complex baseband representation of the received signal can be presented as(1)rN×1=aN×1s+∑i=1KbiN×1ji+nN×1,where bi,  i=1,2,…,K, indicates the steering vector of ith interfering signal and ji,  i=1,2,…,K, is the ith interfering signal. s represents the GNSS signal and n is the receiver white Gaussian noise vector. And a is the steering of the GNSS signal(2)a=ej2π/λdTz1ej2π/λdTz2⋯ej2π/λdTzNT,where λ is the wavelength of the signal; zn,  n=1,2,…,N, is a 3×1 unit vector pointing to the nth antenna element; d is a 3×1 unit vector representing the DOA of the GNSS signal; “·T” denotes transpose.


## 3. The Proposed Method

In the coexistence of multiple types of interfering signals, we can suppress them according to their different characteristics in different dimensions. In view of that, a cascaded multitype interferences suppression method using sparse representation and array processing for GNSS is proposed, and the structure of the proposed method is as shown in Figure1. In the first stage, in order to save the spatial DoF of the antenna array, the received signals are sparsely decomposed to suppress interference signals with sparse features according to the sparse characteristic of narrowband and wideband modulation interfering signals. To make the MP-based sparse decomposition be suitable for multitype interferences suppression scenario, we redesign the overcomplete dictionary in accordance with the characteristics of the interference signal, and the necessary conditions for interfering signals detection are analyzed, especially for the scenario that the energy of the interference signals with sparse feature is smaller than that of the wideband Gauss interferences. Then on the base of these, a parallel multichannel sparse decomposition based on MP and the termination condition is proposed. In the second stage, the MPDR beamformer is employed to suppress Gaussian noise interferences and other residuary interferences by utilizing the spatial DoF of the antenna array.Figure 1
Block diagram of the proposed method.


### 3.1. Signal Sparse Decomposition Based on MP

#### 3.1.1. Matching Pursuit Decomposition

The MP algorithm was introduced to adaptively decompose signals in an overcomplete dictionary when the signal sparse decomposition theory was proposed. And with the flexibility of the redundant dictionary and the adaptability to signals, it has gained more and more attentions. MP is a kind of iterative “greedy” algorithm. At each iteration, the best matching atom that is the most similar to the residual signal is selected and regarded as one of the components of the sparse representation.Letf∈H be the signal to be decomposed, where H is a Hilbert space, and let D be the overcomplete dictionary defined by D=griri∈Γ, where Γ is the parameter set of the atoms and gri=1 is named an atom. And the basic steps of MP are as follows.( 1 ) Choose an atom gr0 from D which best matches the f; that is,(3)f,gr0=supr∈Γf,gr.Then the signal can be decomposed into covariates on the best atom gr0 and the residual; that is,(4)f=f,gr0gr0+R1f.( 2 ) Decompose the residual iteratively, for the (l+1)th iteration(5)Rlf=Rlf,grlgrl+Rl+1f.( 3 ) If termination condition is reached after the L steps decomposition, the signal can be expressed as(6)f=∑l=0L-1Rlf,grlgrl+RLf.Since ∑l=0L-1‍Rlf,grlgrl≫RLf, the signal can be decomposed into a sum of dictionary elements:(7)f≈∑l=0L-1Rlf,grlgrl.Formula (6) and L≪Lf, where Lf is the size of f, represent the key idea of sparse representation. It should be noted that, with the decomposition, namely, as L is increasing, the residual RLf is gradually decreasing, until it disappears.


#### 3.1.2. The Proposed Atoms of the Overcomplete Dictionary

In order to facilitate the analysis, only one single-tone or LFM interfering signal is considered in the formulations below. And assume that there areI wide band Gaussian noise interfering signals. Because the strength of navigation satellite signals is usually very weak, there is no need to be concerned about obtaining signal-free samples. Then, for M snapshots, at the nth antenna, the signal in quadrature I path can be written as(8)xn_IM×1=JM×1+ηM×1,where η is the thermal noise with zero mean and ση variance; J=J1J2⋯Jm⋯JM represents interference signals; and Jm is the mth snapshot data, expressed as(9)Jm=pcos⁡2πkJmT+fJmT+φJ+∑i=0IGimTin which kJ is the linear modulation frequency ratio; fJ represents the fixed frequency; φJ is the phase; m,  m=1,2,…,M represents the number of samples; T is sampling period;p is the energy of the interfering signal; and Gi· is Gaussian interfering signals with zero mean and σi variance.According to the characters of interference signals, select a series of linear frequency modulated signals as atoms in the overcomplete dictionary, which could be expressed as(10)gr=Crcos⁡2πkrmT+frmT+φr,where Cr is the normalized coefficient; kr∈K1,K2, in which K1,K2 represents the search range of the linear modulation frequency ratio;  fr∈f0-B/2,f0+B/2 is fixed frequency parameters and B and  f0 represent the bandwidth and the center frequency of the received signal, respectively; φr∈-π,π is phase parameters. The values of kr,  fr, and φr form the parameter set Γ and are selected at regular intervals according to their respective reasonable ranges and the number of atoms. The more the number of atoms is, the higher the decomposition accuracy is.


#### 3.1.3. Analysis of Interference Detection Performance

The signal to be decomposed contains only one signal that can be sparse in the overcomplete dictionary. Then (8) can be rewritten as(11)xn_IM×1=JsM×1+ℵM×1,where(12)Jsm=pcos⁡2πkJ+fJmT+φJ,ℵm=∑i=0IGimT+ηmT.Then, ℵ can be treated as a Gaussian noise with zero mean and σ variance(13)σ=∑i=0Iσi+ση.The best matching atom is selected according to formula (3)(14)xn_I,gr=Js,gr+ℵ,gr=RJ+Rn.Assume that the closest matching atom, cos⁡2πkJmT+fJmT+φJ, has been known. Then(15)RJΔk,Δf,Δφ=∑m=0M-1pcos⁡2πkJmT+fJmT+φJCrcos⁡2πkJ+ΔkmT+fJ+ΔfmT+φJ+Δφ=12Crp∑m=0M-1cos⁡2πΔkmT+ΔfmT+Δφ+12Crp∑m=0M-1cos⁡2πkJ+ΔkmT+fJ+ΔfmT+φJ+Δφ,where Δk,  Δf, and Δφ represent the linear frequency modulation ration spacing, frequency spacing, and phase spacing, respectively. And since M is large enough, we can suppose that the normalized coefficient of each atom, Cr, is equivalent to each other in the following analysis. In general signal processing, T satisfies the Nyquist sampling theorem or the bandpass sampling theorem and M is large enough, so the latter is much less than the former in the polynomial; then(16)RJΔk,Δf,Δφ≈12Crp∑m=0M-1cos⁡2πΔkmT+ΔfmT+Δφ.In order to further understand the nature ofRJ, it is analyzed in the following three cases.( 1 ) Let Δk=Δφ=0, and kJ=0 and  φJ=0; then(17)Rf=Crp∑m=0M-1cos⁡2πfJ+ΔfmTcos⁡2πfJmT=14Crpsin⁡2π2fJ+ΔfMTsin⁡2π2fJ+ΔfT2sin⁡π2fJ+ΔfTsin⁡2πfJ+ΔfT+sin⁡2πΔfMTsin⁡2πΔfT2sin⁡πΔfTsin⁡πΔfT.Obviously, Rf is a periodic function over Δf, and the period is 1/T. When Δf=m/T or Δf=-m/T-2fJ, the maximum value of Rf can be obtained(18)Rfmax≈14Crpsin⁡2πΔfMTsin⁡2πΔfT2sin⁡πΔfTsin⁡πΔfT≈M2Crp,Δf⟶0.When the sampling rate is 8 times as much as fJ, the relation between Rf and Δf is as shown in Figure 2.Figure 2
Relation betweenRf and Δf.
(a) (b)( 2 ) Let Δk=Δf=0, and kJ=0 and  fJ=0; then(19)Rφ=Crp∑m=0M-1cos⁡2πfJmT+φcos⁡2πfJmT+φ+Δφ=14Crpcos⁡2φ+Δφ-cos⁡4πfJT-2φ-Δφ-cos⁡4MπfJT+2φ+Δφ+cos⁡4M-1πfJT+2φ+Δφ1-cos⁡2πΔφ+M2Crpcos⁡Δφ≈M2Crpcos⁡Δφ,where Rφ is a periodic function over Δφ and the period is 2π. The relation between Rφ and Δφ is as shown in Figure 3. The maximum value of Rφ is(20)Rφmax≈M2Crp.Figure 3
Relation betweenRφ and Δφ.( 3 ) Let Δf=Δφ=0, and fJ=0 and  φJ=0; then(21)Rk=Crp∑m=0M-1cos⁡2πkJ+ΔkmT2cos⁡2πkJmT2=12Crp∑m=0M-1cos⁡2πΔkmT2+12Crp∑m=0M-1cos⁡2π2kJ+ΔkmT2, where Rk is a periodic function over Δk and the period is 1/T2. When the sampling rate is 8 times as much as the center frequency, the relation between Rk and Δk is as shown in Figure 4. The maximum value of Rk is(22)Rkmax≈M2Crp.Figure 4
Relation betweenRk and Δk.
(a) (b)This periodicity ofRk and Rf is caused by the discrete sampling and by bandwidth sampling theorem. It is not difficult to deduce(23)Δf<max2TfJ,1-2TfJ,Δk<1T2.Accordingly, Rk,  Rφ, and Rf do not have periodicity within the range defined by overcomplete dictionary. In other words, RJ does have only maximum value in the search range of the overcomplete dictionary. From the above analysis, it is shown that there is only one best matching atom in the overcomplete dictionary for each sparse representation of the interference signal. And the maximum value of RJ is the inner product of the signal to be decomposed and the best matching atom(24)RJmax≈M2Crp.In addition, since G is the Gauss white noise with zero mean and σ variance, then(25)Rn=Cr∑m=0M-1cos⁡2πkklmT+fflmT+φφlGmT≈CrMσ.Therefore, in order to effectively detect the interfering signal, the number of samples M should satisfy(26)RJmax>Rn;that is,(27)M>4σp.


#### 3.1.4. Design Strategy of the Hierarchical Adaptive Overcomplete Dictionary

Although signal sparse decomposition based on MP has better performance with the increase of the number of atoms in the overcomplete dictionary, the improvement of the performance for such ways is at the cost of the increase of complexity. In order to reduce the amount of computation while maintaining the accuracy, we propose a design strategy of the hierarchical adaptive overcomplete dictionary. In step1, an overcomplete dictionary is generated according to the prior information and the signal is decomposed using MP algorithm. In step 2, the parameters of the best atom obtained in step 1 serve as the new prior information to generate the next level overcomplete dictionary; repeat steps 1 and 2 until the overcomplete dictionary which satisfies the accuracy requirement is obtained.Taking the fixed frequency parameter as an example, assume that the bandwidth of the desired signal is 2 MHz, while the decomposition accuracy is 0.0001 MHz. The number of fixed frequency parameters in the overcomplete dictionary is2×104. However, conduct the three-layer adaptive overcomplete dictionary in the following steps.Step 1.
Decompose the received signal with 0.02 MHZ precision in 2 MHz bandwidth, and get the primary best frequency parameterf1.Step 2.
Generate new frequency parameters dictionary with 0.001 MHz precision at 0.02 MHz bandwidth centered inf1, then decompose the received signal with the new dictionary, and get the best frequency parameter f2.Step 3.
Generate new frequency parameters dictionary with 0.0001 MHz precision at 0.001 MHz bandwidth centered inf2, then decompose the received signal, and get the frequency parameter meeting the accuracy requirements.The total number of fixed frequency parameters in the 3-stage overcomplete dictionary is 130. The computation of the latter is 0.65 percent of the former.


#### 3.1.5. The Best Atom Search Strategy for Multichannel Signal

Because the GNSS receiver used in the proposed method is equipped with the array antenna, there are multichannel signals to deal with. If these signals are decomposed independently, the calculation is very great. Fortunately, array signal processing theory demonstrates that there is a potential correlation among the signals of each channel. In particular, they have the same frequency, similar amplitude, and distinct phases. Therefore, we can extend the concept of single channel signal sparse decomposition to the multichannel signal by using the correlation among the signals of each channel. The detailed implementation steps are as follows.Step 1.
Divide the overcomplete dictionary intoN subovercomplete dictionary, and the division principle is expressed as(28)Dn=gr_ngr_n∈Γn,gr_n=Cr_ncos⁡2πkrmT+fr_nmT+φr,where n=1,2,…,N;  N is the number of antenna;(29)fr_n∈n-1NB+f0-B2,n-1NB+f0-B2.Step 2.
EachI signal at nth antenna corresponds to a subdictionary; and use the conventional MP algorithm to select the subbest matching atom, respectively,(30)xn_I,grl_subn=supri_n∈Γnxn_I,gri_n,where xn_I is the I signal vector at nth antenna.Step 3.
Compare the inner products of subbest matching atoms and corresponding signals, and select the global closest matching atomgrl_nkb,fb,φ, which satisfies the following condition:(31)maxxn_I,grl_subn.Step 4.
According to the frequency parameters of the global best matching atom, calculate the unique phase and amplitude parameters of the signals in each channel(32)xn_I,grlkb,fb,φn=supφ∈-π,πxn_I,grlkb,fb,φ.Then, the retrieval interference from the best atom in each channel can be expressed as(33)Jn_I=xn_I,grlkb,fb,φngrlkb,fb,φn.And the I signal in each channel can be written as(34)xn_I=∑l=0L′-1Rlxn_I,grlkb,fb,φngrlkb,fb,φn+Rn_IL′xn_I,where L′ is the number of iterations.


#### 3.1.6. The Terminate Condition of MP

The conventional terminative condition of the MP algorithm is to determine whether the number of iterations or the energy of the residual signal meets the requirements. However, in complicated electromagnetic environment, since the number of signals that can be sparse representation is unknown, the number of iterations cannot be preset; and when the energy of the signals which could be sparse representation is smaller than that of the other interferences, the residual signal energy may have little difference with the original signal energy, so the existing terminative condition is not able to guarantee the effectiveness of the algorithm. Hence, a ratio principle is introduced to judge whether the ratio of inner product of the best matching atom obtained in thel step and the signal to be decomposed to the sum of residual signal meets the threshold. It can be expressed mathematically as(35)Rlxn_I,grlsumRl+1xn_I=ρ,where sum(·) represents the sum function. Formulas (26) and (27) show that when the signal to be decomposed contains the interference signal that can be sparse representation in the overcomplete dictionary, inevitably there is a best matched atom making ρ>1.


#### 3.1.7. Parallel Multichannel Signal Interference Suppression Method Based on MP

Based on the conclusions above, a multichannel signal interference suppression method based on sparse decomposition is proposed. The basic steps are as follows.Step 1.
Algorithm initialization: set up the overcomplete dictionary classification layer, search accuracy, and the threshold value of the termination conditions.Step 2.
Generate the global overcomplete dictionaryD.Step 3.
Use parallel multichannel signal sparse decomposition method to decompose array signals.Step 4.
Judge the accuracy of decomposition; if it reaches the preset accuracy, then take the next step; otherwise, regenerate global overcomplete dictionary according to the information acquired, and iterate to step 3.Step 5.
Shift the phase of the best atoms 90° to get the best atoms of the correspondingQ signal; then the Q signal can be written as(36)xn_Q=∑l=0L′-1Rlxn_Q,grl_Qgrl_Q+Rn_QL′xn_Q.Step 6.
Determine whether the termination condition is met; if not, iterate to step 2; otherwise, take the next step.Step 7.
Output the residual signal of each channel, which can be written as(37)xnR=Rn_IL′xn_I+Rn_QL′xn_Q-1,where n=1,2,…,N.


### 3.2. MPDR Beamformer

In the second stage, by applying the spatial filtering, the beam of receiver antenna arrays is pointed towards the GNSS satellite and away from interferers to protect the GNSS signal and reject interferences. In GNSS applications, MPDR beamformer is one of the powerful approaches available to suppress interfering signals while maintaining desired signals due to its effectiveness for interference suppression without considering the structure and direction of the interfering signals. And the optimization problem for the MPDR beamformer can be expressed as(38)minwwHRN×Nws.t.wHa=1,where w represents the array weight vector; a is defined by formula (2); R is the spatial covariance matrix of the residual signals obtained by stage 1, which can be expressed by(39)R=1MXHX,where X=x1RTx2RT⋯xNRT; “H” denotes conjugate transpose;M is the size of snapshot data. Then the optimal weight vector is(40)wopt=R-1aaHR-1a.


## 3.1. Signal Sparse Decomposition Based on MP

### 3.1.1. Matching Pursuit Decomposition

The MP algorithm was introduced to adaptively decompose signals in an overcomplete dictionary when the signal sparse decomposition theory was proposed. And with the flexibility of the redundant dictionary and the adaptability to signals, it has gained more and more attentions. MP is a kind of iterative “greedy” algorithm. At each iteration, the best matching atom that is the most similar to the residual signal is selected and regarded as one of the components of the sparse representation.Letf∈H be the signal to be decomposed, where H is a Hilbert space, and let D be the overcomplete dictionary defined by D=griri∈Γ, where Γ is the parameter set of the atoms and gri=1 is named an atom. And the basic steps of MP are as follows.( 1 ) Choose an atom gr0 from D which best matches the f; that is,(3)f,gr0=supr∈Γf,gr.Then the signal can be decomposed into covariates on the best atom gr0 and the residual; that is,(4)f=f,gr0gr0+R1f.( 2 ) Decompose the residual iteratively, for the (l+1)th iteration(5)Rlf=Rlf,grlgrl+Rl+1f.( 3 ) If termination condition is reached after the L steps decomposition, the signal can be expressed as(6)f=∑l=0L-1Rlf,grlgrl+RLf.Since ∑l=0L-1‍Rlf,grlgrl≫RLf, the signal can be decomposed into a sum of dictionary elements:(7)f≈∑l=0L-1Rlf,grlgrl.Formula (6) and L≪Lf, where Lf is the size of f, represent the key idea of sparse representation. It should be noted that, with the decomposition, namely, as L is increasing, the residual RLf is gradually decreasing, until it disappears.


### 3.1.2. The Proposed Atoms of the Overcomplete Dictionary

In order to facilitate the analysis, only one single-tone or LFM interfering signal is considered in the formulations below. And assume that there areI wide band Gaussian noise interfering signals. Because the strength of navigation satellite signals is usually very weak, there is no need to be concerned about obtaining signal-free samples. Then, for M snapshots, at the nth antenna, the signal in quadrature I path can be written as(8)xn_IM×1=JM×1+ηM×1,where η is the thermal noise with zero mean and ση variance; J=J1J2⋯Jm⋯JM represents interference signals; and Jm is the mth snapshot data, expressed as(9)Jm=pcos⁡2πkJmT+fJmT+φJ+∑i=0IGimTin which kJ is the linear modulation frequency ratio; fJ represents the fixed frequency; φJ is the phase; m,  m=1,2,…,M represents the number of samples; T is sampling period;p is the energy of the interfering signal; and Gi· is Gaussian interfering signals with zero mean and σi variance.According to the characters of interference signals, select a series of linear frequency modulated signals as atoms in the overcomplete dictionary, which could be expressed as(10)gr=Crcos⁡2πkrmT+frmT+φr,where Cr is the normalized coefficient; kr∈K1,K2, in which K1,K2 represents the search range of the linear modulation frequency ratio;  fr∈f0-B/2,f0+B/2 is fixed frequency parameters and B and  f0 represent the bandwidth and the center frequency of the received signal, respectively; φr∈-π,π is phase parameters. The values of kr,  fr, and φr form the parameter set Γ and are selected at regular intervals according to their respective reasonable ranges and the number of atoms. The more the number of atoms is, the higher the decomposition accuracy is.


### 3.1.3. Analysis of Interference Detection Performance

The signal to be decomposed contains only one signal that can be sparse in the overcomplete dictionary. Then (8) can be rewritten as(11)xn_IM×1=JsM×1+ℵM×1,where(12)Jsm=pcos⁡2πkJ+fJmT+φJ,ℵm=∑i=0IGimT+ηmT.Then, ℵ can be treated as a Gaussian noise with zero mean and σ variance(13)σ=∑i=0Iσi+ση.The best matching atom is selected according to formula (3)(14)xn_I,gr=Js,gr+ℵ,gr=RJ+Rn.Assume that the closest matching atom, cos⁡2πkJmT+fJmT+φJ, has been known. Then(15)RJΔk,Δf,Δφ=∑m=0M-1pcos⁡2πkJmT+fJmT+φJCrcos⁡2πkJ+ΔkmT+fJ+ΔfmT+φJ+Δφ=12Crp∑m=0M-1cos⁡2πΔkmT+ΔfmT+Δφ+12Crp∑m=0M-1cos⁡2πkJ+ΔkmT+fJ+ΔfmT+φJ+Δφ,where Δk,  Δf, and Δφ represent the linear frequency modulation ration spacing, frequency spacing, and phase spacing, respectively. And since M is large enough, we can suppose that the normalized coefficient of each atom, Cr, is equivalent to each other in the following analysis. In general signal processing, T satisfies the Nyquist sampling theorem or the bandpass sampling theorem and M is large enough, so the latter is much less than the former in the polynomial; then(16)RJΔk,Δf,Δφ≈12Crp∑m=0M-1cos⁡2πΔkmT+ΔfmT+Δφ.In order to further understand the nature ofRJ, it is analyzed in the following three cases.( 1 ) Let Δk=Δφ=0, and kJ=0 and  φJ=0; then(17)Rf=Crp∑m=0M-1cos⁡2πfJ+ΔfmTcos⁡2πfJmT=14Crpsin⁡2π2fJ+ΔfMTsin⁡2π2fJ+ΔfT2sin⁡π2fJ+ΔfTsin⁡2πfJ+ΔfT+sin⁡2πΔfMTsin⁡2πΔfT2sin⁡πΔfTsin⁡πΔfT.Obviously, Rf is a periodic function over Δf, and the period is 1/T. When Δf=m/T or Δf=-m/T-2fJ, the maximum value of Rf can be obtained(18)Rfmax≈14Crpsin⁡2πΔfMTsin⁡2πΔfT2sin⁡πΔfTsin⁡πΔfT≈M2Crp,Δf⟶0.When the sampling rate is 8 times as much as fJ, the relation between Rf and Δf is as shown in Figure 2.Figure 2
Relation betweenRf and Δf.
(a) (b)( 2 ) Let Δk=Δf=0, and kJ=0 and  fJ=0; then(19)Rφ=Crp∑m=0M-1cos⁡2πfJmT+φcos⁡2πfJmT+φ+Δφ=14Crpcos⁡2φ+Δφ-cos⁡4πfJT-2φ-Δφ-cos⁡4MπfJT+2φ+Δφ+cos⁡4M-1πfJT+2φ+Δφ1-cos⁡2πΔφ+M2Crpcos⁡Δφ≈M2Crpcos⁡Δφ,where Rφ is a periodic function over Δφ and the period is 2π. The relation between Rφ and Δφ is as shown in Figure 3. The maximum value of Rφ is(20)Rφmax≈M2Crp.Figure 3
Relation betweenRφ and Δφ.( 3 ) Let Δf=Δφ=0, and fJ=0 and  φJ=0; then(21)Rk=Crp∑m=0M-1cos⁡2πkJ+ΔkmT2cos⁡2πkJmT2=12Crp∑m=0M-1cos⁡2πΔkmT2+12Crp∑m=0M-1cos⁡2π2kJ+ΔkmT2, where Rk is a periodic function over Δk and the period is 1/T2. When the sampling rate is 8 times as much as the center frequency, the relation between Rk and Δk is as shown in Figure 4. The maximum value of Rk is(22)Rkmax≈M2Crp.Figure 4
Relation betweenRk and Δk.
(a) (b)This periodicity ofRk and Rf is caused by the discrete sampling and by bandwidth sampling theorem. It is not difficult to deduce(23)Δf<max2TfJ,1-2TfJ,Δk<1T2.Accordingly, Rk,  Rφ, and Rf do not have periodicity within the range defined by overcomplete dictionary. In other words, RJ does have only maximum value in the search range of the overcomplete dictionary. From the above analysis, it is shown that there is only one best matching atom in the overcomplete dictionary for each sparse representation of the interference signal. And the maximum value of RJ is the inner product of the signal to be decomposed and the best matching atom(24)RJmax≈M2Crp.In addition, since G is the Gauss white noise with zero mean and σ variance, then(25)Rn=Cr∑m=0M-1cos⁡2πkklmT+fflmT+φφlGmT≈CrMσ.Therefore, in order to effectively detect the interfering signal, the number of samples M should satisfy(26)RJmax>Rn;that is,(27)M>4σp.


### 3.1.4. Design Strategy of the Hierarchical Adaptive Overcomplete Dictionary

Although signal sparse decomposition based on MP has better performance with the increase of the number of atoms in the overcomplete dictionary, the improvement of the performance for such ways is at the cost of the increase of complexity. In order to reduce the amount of computation while maintaining the accuracy, we propose a design strategy of the hierarchical adaptive overcomplete dictionary. In step1, an overcomplete dictionary is generated according to the prior information and the signal is decomposed using MP algorithm. In step 2, the parameters of the best atom obtained in step 1 serve as the new prior information to generate the next level overcomplete dictionary; repeat steps 1 and 2 until the overcomplete dictionary which satisfies the accuracy requirement is obtained.Taking the fixed frequency parameter as an example, assume that the bandwidth of the desired signal is 2 MHz, while the decomposition accuracy is 0.0001 MHz. The number of fixed frequency parameters in the overcomplete dictionary is2×104. However, conduct the three-layer adaptive overcomplete dictionary in the following steps.Step 1.
Decompose the received signal with 0.02 MHZ precision in 2 MHz bandwidth, and get the primary best frequency parameterf1.Step 2.
Generate new frequency parameters dictionary with 0.001 MHz precision at 0.02 MHz bandwidth centered inf1, then decompose the received signal with the new dictionary, and get the best frequency parameter f2.Step 3.
Generate new frequency parameters dictionary with 0.0001 MHz precision at 0.001 MHz bandwidth centered inf2, then decompose the received signal, and get the frequency parameter meeting the accuracy requirements.The total number of fixed frequency parameters in the 3-stage overcomplete dictionary is 130. The computation of the latter is 0.65 percent of the former.


### 3.1.5. The Best Atom Search Strategy for Multichannel Signal

Because the GNSS receiver used in the proposed method is equipped with the array antenna, there are multichannel signals to deal with. If these signals are decomposed independently, the calculation is very great. Fortunately, array signal processing theory demonstrates that there is a potential correlation among the signals of each channel. In particular, they have the same frequency, similar amplitude, and distinct phases. Therefore, we can extend the concept of single channel signal sparse decomposition to the multichannel signal by using the correlation among the signals of each channel. The detailed implementation steps are as follows.Step 1.
Divide the overcomplete dictionary intoN subovercomplete dictionary, and the division principle is expressed as(28)Dn=gr_ngr_n∈Γn,gr_n=Cr_ncos⁡2πkrmT+fr_nmT+φr,where n=1,2,…,N;  N is the number of antenna;(29)fr_n∈n-1NB+f0-B2,n-1NB+f0-B2.Step 2.
EachI signal at nth antenna corresponds to a subdictionary; and use the conventional MP algorithm to select the subbest matching atom, respectively,(30)xn_I,grl_subn=supri_n∈Γnxn_I,gri_n,where xn_I is the I signal vector at nth antenna.Step 3.
Compare the inner products of subbest matching atoms and corresponding signals, and select the global closest matching atomgrl_nkb,fb,φ, which satisfies the following condition:(31)maxxn_I,grl_subn.Step 4.
According to the frequency parameters of the global best matching atom, calculate the unique phase and amplitude parameters of the signals in each channel(32)xn_I,grlkb,fb,φn=supφ∈-π,πxn_I,grlkb,fb,φ.Then, the retrieval interference from the best atom in each channel can be expressed as(33)Jn_I=xn_I,grlkb,fb,φngrlkb,fb,φn.And the I signal in each channel can be written as(34)xn_I=∑l=0L′-1Rlxn_I,grlkb,fb,φngrlkb,fb,φn+Rn_IL′xn_I,where L′ is the number of iterations.


### 3.1.6. The Terminate Condition of MP

The conventional terminative condition of the MP algorithm is to determine whether the number of iterations or the energy of the residual signal meets the requirements. However, in complicated electromagnetic environment, since the number of signals that can be sparse representation is unknown, the number of iterations cannot be preset; and when the energy of the signals which could be sparse representation is smaller than that of the other interferences, the residual signal energy may have little difference with the original signal energy, so the existing terminative condition is not able to guarantee the effectiveness of the algorithm. Hence, a ratio principle is introduced to judge whether the ratio of inner product of the best matching atom obtained in thel step and the signal to be decomposed to the sum of residual signal meets the threshold. It can be expressed mathematically as(35)Rlxn_I,grlsumRl+1xn_I=ρ,where sum(·) represents the sum function. Formulas (26) and (27) show that when the signal to be decomposed contains the interference signal that can be sparse representation in the overcomplete dictionary, inevitably there is a best matched atom making ρ>1.


### 3.1.7. Parallel Multichannel Signal Interference Suppression Method Based on MP

Based on the conclusions above, a multichannel signal interference suppression method based on sparse decomposition is proposed. The basic steps are as follows.Step 1.
Algorithm initialization: set up the overcomplete dictionary classification layer, search accuracy, and the threshold value of the termination conditions.Step 2.
Generate the global overcomplete dictionaryD.Step 3.
Use parallel multichannel signal sparse decomposition method to decompose array signals.Step 4.
Judge the accuracy of decomposition; if it reaches the preset accuracy, then take the next step; otherwise, regenerate global overcomplete dictionary according to the information acquired, and iterate to step 3.Step 5.
Shift the phase of the best atoms 90° to get the best atoms of the correspondingQ signal; then the Q signal can be written as(36)xn_Q=∑l=0L′-1Rlxn_Q,grl_Qgrl_Q+Rn_QL′xn_Q.Step 6.
Determine whether the termination condition is met; if not, iterate to step 2; otherwise, take the next step.Step 7.
Output the residual signal of each channel, which can be written as(37)xnR=Rn_IL′xn_I+Rn_QL′xn_Q-1,where n=1,2,…,N.


## 3.1.1. Matching Pursuit Decomposition

The MP algorithm was introduced to adaptively decompose signals in an overcomplete dictionary when the signal sparse decomposition theory was proposed. And with the flexibility of the redundant dictionary and the adaptability to signals, it has gained more and more attentions. MP is a kind of iterative “greedy” algorithm. At each iteration, the best matching atom that is the most similar to the residual signal is selected and regarded as one of the components of the sparse representation.Letf∈H be the signal to be decomposed, where H is a Hilbert space, and let D be the overcomplete dictionary defined by D=griri∈Γ, where Γ is the parameter set of the atoms and gri=1 is named an atom. And the basic steps of MP are as follows.( 1 ) Choose an atom gr0 from D which best matches the f; that is,(3)f,gr0=supr∈Γf,gr.Then the signal can be decomposed into covariates on the best atom gr0 and the residual; that is,(4)f=f,gr0gr0+R1f.( 2 ) Decompose the residual iteratively, for the (l+1)th iteration(5)Rlf=Rlf,grlgrl+Rl+1f.( 3 ) If termination condition is reached after the L steps decomposition, the signal can be expressed as(6)f=∑l=0L-1Rlf,grlgrl+RLf.Since ∑l=0L-1‍Rlf,grlgrl≫RLf, the signal can be decomposed into a sum of dictionary elements:(7)f≈∑l=0L-1Rlf,grlgrl.Formula (6) and L≪Lf, where Lf is the size of f, represent the key idea of sparse representation. It should be noted that, with the decomposition, namely, as L is increasing, the residual RLf is gradually decreasing, until it disappears.


## 3.1.2. The Proposed Atoms of the Overcomplete Dictionary

In order to facilitate the analysis, only one single-tone or LFM interfering signal is considered in the formulations below. And assume that there areI wide band Gaussian noise interfering signals. Because the strength of navigation satellite signals is usually very weak, there is no need to be concerned about obtaining signal-free samples. Then, for M snapshots, at the nth antenna, the signal in quadrature I path can be written as(8)xn_IM×1=JM×1+ηM×1,where η is the thermal noise with zero mean and ση variance; J=J1J2⋯Jm⋯JM represents interference signals; and Jm is the mth snapshot data, expressed as(9)Jm=pcos⁡2πkJmT+fJmT+φJ+∑i=0IGimTin which kJ is the linear modulation frequency ratio; fJ represents the fixed frequency; φJ is the phase; m,  m=1,2,…,M represents the number of samples; T is sampling period;p is the energy of the interfering signal; and Gi· is Gaussian interfering signals with zero mean and σi variance.According to the characters of interference signals, select a series of linear frequency modulated signals as atoms in the overcomplete dictionary, which could be expressed as(10)gr=Crcos⁡2πkrmT+frmT+φr,where Cr is the normalized coefficient; kr∈K1,K2, in which K1,K2 represents the search range of the linear modulation frequency ratio;  fr∈f0-B/2,f0+B/2 is fixed frequency parameters and B and  f0 represent the bandwidth and the center frequency of the received signal, respectively; φr∈-π,π is phase parameters. The values of kr,  fr, and φr form the parameter set Γ and are selected at regular intervals according to their respective reasonable ranges and the number of atoms. The more the number of atoms is, the higher the decomposition accuracy is.


## 3.1.3. Analysis of Interference Detection Performance

The signal to be decomposed contains only one signal that can be sparse in the overcomplete dictionary. Then (8) can be rewritten as(11)xn_IM×1=JsM×1+ℵM×1,where(12)Jsm=pcos⁡2πkJ+fJmT+φJ,ℵm=∑i=0IGimT+ηmT.Then, ℵ can be treated as a Gaussian noise with zero mean and σ variance(13)σ=∑i=0Iσi+ση.The best matching atom is selected according to formula (3)(14)xn_I,gr=Js,gr+ℵ,gr=RJ+Rn.Assume that the closest matching atom, cos⁡2πkJmT+fJmT+φJ, has been known. Then(15)RJΔk,Δf,Δφ=∑m=0M-1pcos⁡2πkJmT+fJmT+φJCrcos⁡2πkJ+ΔkmT+fJ+ΔfmT+φJ+Δφ=12Crp∑m=0M-1cos⁡2πΔkmT+ΔfmT+Δφ+12Crp∑m=0M-1cos⁡2πkJ+ΔkmT+fJ+ΔfmT+φJ+Δφ,where Δk,  Δf, and Δφ represent the linear frequency modulation ration spacing, frequency spacing, and phase spacing, respectively. And since M is large enough, we can suppose that the normalized coefficient of each atom, Cr, is equivalent to each other in the following analysis. In general signal processing, T satisfies the Nyquist sampling theorem or the bandpass sampling theorem and M is large enough, so the latter is much less than the former in the polynomial; then(16)RJΔk,Δf,Δφ≈12Crp∑m=0M-1cos⁡2πΔkmT+ΔfmT+Δφ.In order to further understand the nature ofRJ, it is analyzed in the following three cases.( 1 ) Let Δk=Δφ=0, and kJ=0 and  φJ=0; then(17)Rf=Crp∑m=0M-1cos⁡2πfJ+ΔfmTcos⁡2πfJmT=14Crpsin⁡2π2fJ+ΔfMTsin⁡2π2fJ+ΔfT2sin⁡π2fJ+ΔfTsin⁡2πfJ+ΔfT+sin⁡2πΔfMTsin⁡2πΔfT2sin⁡πΔfTsin⁡πΔfT.Obviously, Rf is a periodic function over Δf, and the period is 1/T. When Δf=m/T or Δf=-m/T-2fJ, the maximum value of Rf can be obtained(18)Rfmax≈14Crpsin⁡2πΔfMTsin⁡2πΔfT2sin⁡πΔfTsin⁡πΔfT≈M2Crp,Δf⟶0.When the sampling rate is 8 times as much as fJ, the relation between Rf and Δf is as shown in Figure 2.Figure 2
Relation betweenRf and Δf.
(a) (b)( 2 ) Let Δk=Δf=0, and kJ=0 and  fJ=0; then(19)Rφ=Crp∑m=0M-1cos⁡2πfJmT+φcos⁡2πfJmT+φ+Δφ=14Crpcos⁡2φ+Δφ-cos⁡4πfJT-2φ-Δφ-cos⁡4MπfJT+2φ+Δφ+cos⁡4M-1πfJT+2φ+Δφ1-cos⁡2πΔφ+M2Crpcos⁡Δφ≈M2Crpcos⁡Δφ,where Rφ is a periodic function over Δφ and the period is 2π. The relation between Rφ and Δφ is as shown in Figure 3. The maximum value of Rφ is(20)Rφmax≈M2Crp.Figure 3
Relation betweenRφ and Δφ.( 3 ) Let Δf=Δφ=0, and fJ=0 and  φJ=0; then(21)Rk=Crp∑m=0M-1cos⁡2πkJ+ΔkmT2cos⁡2πkJmT2=12Crp∑m=0M-1cos⁡2πΔkmT2+12Crp∑m=0M-1cos⁡2π2kJ+ΔkmT2, where Rk is a periodic function over Δk and the period is 1/T2. When the sampling rate is 8 times as much as the center frequency, the relation between Rk and Δk is as shown in Figure 4. The maximum value of Rk is(22)Rkmax≈M2Crp.Figure 4
Relation betweenRk and Δk.
(a) (b)This periodicity ofRk and Rf is caused by the discrete sampling and by bandwidth sampling theorem. It is not difficult to deduce(23)Δf<max2TfJ,1-2TfJ,Δk<1T2.Accordingly, Rk,  Rφ, and Rf do not have periodicity within the range defined by overcomplete dictionary. In other words, RJ does have only maximum value in the search range of the overcomplete dictionary. From the above analysis, it is shown that there is only one best matching atom in the overcomplete dictionary for each sparse representation of the interference signal. And the maximum value of RJ is the inner product of the signal to be decomposed and the best matching atom(24)RJmax≈M2Crp.In addition, since G is the Gauss white noise with zero mean and σ variance, then(25)Rn=Cr∑m=0M-1cos⁡2πkklmT+fflmT+φφlGmT≈CrMσ.Therefore, in order to effectively detect the interfering signal, the number of samples M should satisfy(26)RJmax>Rn;that is,(27)M>4σp.


## 3.1.4. Design Strategy of the Hierarchical Adaptive Overcomplete Dictionary

Although signal sparse decomposition based on MP has better performance with the increase of the number of atoms in the overcomplete dictionary, the improvement of the performance for such ways is at the cost of the increase of complexity. In order to reduce the amount of computation while maintaining the accuracy, we propose a design strategy of the hierarchical adaptive overcomplete dictionary. In step1, an overcomplete dictionary is generated according to the prior information and the signal is decomposed using MP algorithm. In step 2, the parameters of the best atom obtained in step 1 serve as the new prior information to generate the next level overcomplete dictionary; repeat steps 1 and 2 until the overcomplete dictionary which satisfies the accuracy requirement is obtained.Taking the fixed frequency parameter as an example, assume that the bandwidth of the desired signal is 2 MHz, while the decomposition accuracy is 0.0001 MHz. The number of fixed frequency parameters in the overcomplete dictionary is2×104. However, conduct the three-layer adaptive overcomplete dictionary in the following steps.Step 1.
Decompose the received signal with 0.02 MHZ precision in 2 MHz bandwidth, and get the primary best frequency parameterf1.Step 2.
Generate new frequency parameters dictionary with 0.001 MHz precision at 0.02 MHz bandwidth centered inf1, then decompose the received signal with the new dictionary, and get the best frequency parameter f2.Step 3.
Generate new frequency parameters dictionary with 0.0001 MHz precision at 0.001 MHz bandwidth centered inf2, then decompose the received signal, and get the frequency parameter meeting the accuracy requirements.The total number of fixed frequency parameters in the 3-stage overcomplete dictionary is 130. The computation of the latter is 0.65 percent of the former.


## 3.1.5. The Best Atom Search Strategy for Multichannel Signal

Because the GNSS receiver used in the proposed method is equipped with the array antenna, there are multichannel signals to deal with. If these signals are decomposed independently, the calculation is very great. Fortunately, array signal processing theory demonstrates that there is a potential correlation among the signals of each channel. In particular, they have the same frequency, similar amplitude, and distinct phases. Therefore, we can extend the concept of single channel signal sparse decomposition to the multichannel signal by using the correlation among the signals of each channel. The detailed implementation steps are as follows.Step 1.
Divide the overcomplete dictionary intoN subovercomplete dictionary, and the division principle is expressed as(28)Dn=gr_ngr_n∈Γn,gr_n=Cr_ncos⁡2πkrmT+fr_nmT+φr,where n=1,2,…,N;  N is the number of antenna;(29)fr_n∈n-1NB+f0-B2,n-1NB+f0-B2.Step 2.
EachI signal at nth antenna corresponds to a subdictionary; and use the conventional MP algorithm to select the subbest matching atom, respectively,(30)xn_I,grl_subn=supri_n∈Γnxn_I,gri_n,where xn_I is the I signal vector at nth antenna.Step 3.
Compare the inner products of subbest matching atoms and corresponding signals, and select the global closest matching atomgrl_nkb,fb,φ, which satisfies the following condition:(31)maxxn_I,grl_subn.Step 4.
According to the frequency parameters of the global best matching atom, calculate the unique phase and amplitude parameters of the signals in each channel(32)xn_I,grlkb,fb,φn=supφ∈-π,πxn_I,grlkb,fb,φ.Then, the retrieval interference from the best atom in each channel can be expressed as(33)Jn_I=xn_I,grlkb,fb,φngrlkb,fb,φn.And the I signal in each channel can be written as(34)xn_I=∑l=0L′-1Rlxn_I,grlkb,fb,φngrlkb,fb,φn+Rn_IL′xn_I,where L′ is the number of iterations.


## 3.1.6. The Terminate Condition of MP

The conventional terminative condition of the MP algorithm is to determine whether the number of iterations or the energy of the residual signal meets the requirements. However, in complicated electromagnetic environment, since the number of signals that can be sparse representation is unknown, the number of iterations cannot be preset; and when the energy of the signals which could be sparse representation is smaller than that of the other interferences, the residual signal energy may have little difference with the original signal energy, so the existing terminative condition is not able to guarantee the effectiveness of the algorithm. Hence, a ratio principle is introduced to judge whether the ratio of inner product of the best matching atom obtained in thel step and the signal to be decomposed to the sum of residual signal meets the threshold. It can be expressed mathematically as(35)Rlxn_I,grlsumRl+1xn_I=ρ,where sum(·) represents the sum function. Formulas (26) and (27) show that when the signal to be decomposed contains the interference signal that can be sparse representation in the overcomplete dictionary, inevitably there is a best matched atom making ρ>1.


## 3.1.7. Parallel Multichannel Signal Interference Suppression Method Based on MP

Based on the conclusions above, a multichannel signal interference suppression method based on sparse decomposition is proposed. The basic steps are as follows.Step 1.
Algorithm initialization: set up the overcomplete dictionary classification layer, search accuracy, and the threshold value of the termination conditions.Step 2.
Generate the global overcomplete dictionaryD.Step 3.
Use parallel multichannel signal sparse decomposition method to decompose array signals.Step 4.
Judge the accuracy of decomposition; if it reaches the preset accuracy, then take the next step; otherwise, regenerate global overcomplete dictionary according to the information acquired, and iterate to step 3.Step 5.
Shift the phase of the best atoms 90° to get the best atoms of the correspondingQ signal; then the Q signal can be written as(36)xn_Q=∑l=0L′-1Rlxn_Q,grl_Qgrl_Q+Rn_QL′xn_Q.Step 6.
Determine whether the termination condition is met; if not, iterate to step 2; otherwise, take the next step.Step 7.
Output the residual signal of each channel, which can be written as(37)xnR=Rn_IL′xn_I+Rn_QL′xn_Q-1,where n=1,2,…,N.


## 3.2. MPDR Beamformer

In the second stage, by applying the spatial filtering, the beam of receiver antenna arrays is pointed towards the GNSS satellite and away from interferers to protect the GNSS signal and reject interferences. In GNSS applications, MPDR beamformer is one of the powerful approaches available to suppress interfering signals while maintaining desired signals due to its effectiveness for interference suppression without considering the structure and direction of the interfering signals. And the optimization problem for the MPDR beamformer can be expressed as(38)minwwHRN×Nws.t.wHa=1,where w represents the array weight vector; a is defined by formula (2); R is the spatial covariance matrix of the residual signals obtained by stage 1, which can be expressed by(39)R=1MXHX,where X=x1RTx2RT⋯xNRT; “H” denotes conjugate transpose;M is the size of snapshot data. Then the optimal weight vector is(40)wopt=R-1aaHR-1a.


## 4. Simulation Results and Analysis

In order to verify the effectiveness of the proposed method, three simulations have been conducted. In all simulations, a linear half-wavelength space antenna array with 5 elements has been considered. A navigation signal operates on 1.023 MHz with bandwidth of 2 MHz and C/A code rate of 1.023 MHz, whose incident angle is80∘ and Doppler frequency is 2 KHz. The analog baseband signal with SNR = −20 dB is sampled at 16.328 MHz, and the number of snapshots is cut to 16328 points. The parameters of interference signals are shown in Table 1, and the parameters involved in the proposed algorithm are shown in Table 2. According to the parameters in Table 2, we can obtain the computation complexity of the MP stage for each iteration. And the computational complexities of the proposed method and the conventional algorithm are given in Table 3.Table 1
Interference signals characteristics.
Name Type of interference Center frequency (MHz) Bandwidth (MHz) DOA (°) Linear modulation frequency rate Interference to noise ratio (dB) 1 Narrowband 1.023 0 80 — 32 2 Narrowband 1.04 0 60 — 32 3 Narrowband 0.95 0 70 — 32 4 LFM 1.023 2 110 109 45 5 Wideband Gaussian 1.023 2 20 — 45 6 Wideband Gaussian 1.023 2 100 — 45 7 Wideband Gaussian 1.023 2 150 — 45 8 Wideband Gaussian 1.023 2 40 — 45 9 LFM 1.023 2 80 −109 45Table 2
The parameters involved in the proposed algorithm.
Name of parameter Value Termination threshold 8 Layers of overcomplete dictionary 3 The decomposition accuracy of fixed frequency in the first layer (corresponding range) 0.01 MHz (1.023±1 MHz) The decomposition accuracy of fixed frequency in the second layer (corresponding range) 0.001 MHz (f1±0.01 MHz) The decomposition accuracy of fixed frequency in the third layer (corresponding range) 0.0001 MHz (f2±0.0005 MHz) The decomposition accuracy of phase in the first layer (corresponding range) 0.1π  (-π,π) The decomposition accuracy of phase in the second layer (corresponding range) 0.01π  (φ1±0.05π) The decomposition accuracy of phase in the third layer (corresponding range) 0.001π  (φ1±0.005π) The decomposition accuracy of linear modulation frequency rate in the first layer (corresponding range) 1 0 7  (0±109) The decomposition accuracy of linear modulation frequency rate in the second layer (corresponding range) 1 0 6  (k1±5×106) The decomposition accuracy of linear modulation frequency rate in the third layer (corresponding range) 1 0 5  (k2±5×105)Table 3
Computational complexities of the proposed method and the conventional MP.
Name Layers of overcomplete dictionary Numbers of atoms in overcomplete dictionary Computational complexity of one channel Total computational complexity Conventional MP 1 8 × 1011 O(8 × 1011) O(4 × 1012) The proposed 3 8.06 × 104 O(8.06 × 104) O(4.03 × 105)


### 4.1. Simulation 1

In this simulation, to examine the performance of the parallel multichannel signal interference suppression method based on MP proposed in Section3.1.7 for interference with sparse features detection and suppression, Interferences 1, 2, 4, 5, and 6 are considered. From the analysis of Section 3.1, Interferences 1, 2, and 4 can be detected and canceled by the proposed method. Take the real part (I signal path) of received signal in channel 1, for example, to evaluate the effectiveness of the proposed method.Figures5(a) and 5(b) show the time-domain waveforms and the frequency spectrum obtained from the FFT of the signals, respectively, and they illustrate that the multitone and LFM interfering signals are buried in Gaussian interference signals and cannot be directly detected in both time-domain and frequency domain. Figure 6 shows the relationship between terminate condition and the iteration number of the MP stage. It can be found that the values of ρ in the first three iterations are greater than the termination threshold, and it consists with the simulation conditions. Figure 7 shows the time-domain waveforms of the original interfering signals (Interferences 1, 2, and 4) and the residual signals in theory; Figure 8 shows the time-domain waveforms of the estimated interfering signals and the residual signal by the proposed method. Comparing Figures 7 and 8, it can be shown that the proposed method in this paper can exactly and effectively estimate the interfering signal. And the errors between these two signals can be measured with the normalized mean square error (NMSE), which are shown in Table 4. Accordingly, we can assume that there are not multitone and LFM interfering signals in the residual signal.Table 4
Normalized mean square error (NMSE) of estimated signals.
Name Interference 1 Interference 2 Interference 4 The residual signal NMSE 0.022 0.025 0.001 0.001Figure 5
Characteristic of received signals.
(a) (b)Figure 6
Relationship between terminate condition and the iteration number.Figure 7
Time-domain waveform of original interfering signals.
(a)
Retrieval interference from the first best atom (b)
Retrieval interference from the second best atom (c)
Retrieval interference from the third best atom (d)
The residual signalsFigure 8
Time-domain waveform of estimated interfering signals.
(a)
Retrieval interference from the first best atom (b)
Retrieval interference from the second best atom (c)
Retrieval interference from the third best atom (d)
The residual signals


### 4.2. Simulation 2

In this simulation, the proposed method is compared to the well-known space-only MPDR (S-MPDR) beamformer and three simulation scenarios are considered. In scenario 1, Interferences 3, 4, 5, and 6 are used. In other words, there is not any interfering signals with the same direction as the GNSS signal and the number of interferences is less than that of antenna elements. In scenario 2, Interferences 1, 4, 5, and 6 are adopted. It means that there is one interfering signal with the same direction as the GNSS signal. In scenario 3, Interferences 2, 3, 4, 5, and 6 are used. It implies that the number of interferences is equal to that of antenna elements.The normalized correlation peaks after interference suppression are shown in Figures9–14 for each scenario, which are used to measure the performance of signal acquisition after interference suppression by these two methods. For scenario 1, Figures 9 and 10 show that the two methods can effectively suppress the interferences. However, Figures 11 and 13 show that the MPDR beamformer has failed to capture the GNSS signal for both scenario 2 and scenario 3. Figures 12 and 14 show that the proposed method can effectively suppress the interferences and does not distort the normalized correlation peak of the GNSS signal even there is one interfering signal with the same direction as the GNSS signal and when the number of interference is more than the DoF of the antenna array.Figure 9
Correlation peaks after interference suppression by S-MPDR beamformer for scenario 1.
(a) (b) (c)Figure 10
Correlation peaks after interference suppression by the proposed method for scenario 1.
(a) (b) (c)Figure 11
Correlation peaks after interference suppression by S-MPDR beamformer for scenario 2.
(a) (b) (c)Figure 12
Correlation peaks after interference suppression by the proposed method for scenario 2.
(a) (b) (c)Figure 13
Correlation peaks after interference suppression by S-MPDR beamformer for scenario 3.
(a) (b) (c)Figure 14
Correlation peaks after interference suppression by the proposed method for scenario 3.
(a) (b) (c)


### 4.3. Simulation 3

In this simulation, the proposed method is compared to the well-known space-time MPDR (ST-MPDR) beamformer [7] and the distortionless space-time adaptive processor (DST-MPDR) [10]. The number of time delay taps is 7. And three simulation scenarios are conducted. In scenario 1, Interferences 1, 2, 4, 5, 6, and 7 are considered, which means that there is one single-tone interfering signal with the same direction as the GNSS signal and the number of wideband interferences is less than that of antenna elements. In scenario 2, Interferences 1, 2, 4, 5, 6, 7, and 8 are used. In other words, the number of wideband interferences is more than that of antenna elements. In scenario 3, Interferences 1, 2, 5, 6, 7, and 9 are used. It means that there is one wideband interfering signal with the same direction as the GNSS signal.The normalized correlation peaks after interference suppression by the three methods for each scenario are shown in Figures15–23, which are used to measure the performance of interference suppression. For scenario 1: Figure 15 shows that the space-time MPDR processing method causes the distortion and shift of the correlation peak; Figure 16 shows that although the distortionless space-time adaptive processor introduces code biases into the GNSS signal, it does not distort the correlation peak of the GNSS signal; Figure 17 shows the proposed algorithm does not affect the shape and the position of the correlation peaks. For both scenario 2 and scenario 3: Figures 18 and 19 and Figures 21 and 22 show that space-time MPDR processing and the distortionless space-time adaptive processor fail to suppress the interference and it is failed to capture the GNSS signal; Figures 20 and 23 show that the proposed method is still effective since the modulated wideband can be canceled by sparse decomposition in the first stage.Figure 15
Correlation peaks after interference suppression by ST-MPDR beamformer for scenario 1.
(a) (b) (c)Figure 16
Correlation peaks after interference suppression by DST-MPDR beamformer for scenario 1.
(a) (b) (c)Figure 17
Correlation peaks after interference suppression by the proposed method for scenario 1.
(a) (b) (c)Figure 18
Correlation peaks after interference suppression by ST-MPDR beamformer for scenario 2.
(a) (b) (c)Figure 19
Correlation peaks after interference suppression by DST-MPDR beamformer for scenario 2.
(a) (b) (c)Figure 20
Correlation peaks after interference suppression by the proposed method for scenario 2.
(a) (b) (c)Figure 21
Correlation peaks after interference suppression by ST-MPDR beamformer for scenario 3.
(a) (b) (c)Figure 22
Correlation peaks after interference suppression by DST-MPDR beamformer for scenario 3.
(a) (b) (c)Figure 23
Correlation peaks after interference suppression by the proposed method for scenario 3.
(a) (b) (c)


## 4.1. Simulation 1

In this simulation, to examine the performance of the parallel multichannel signal interference suppression method based on MP proposed in Section3.1.7 for interference with sparse features detection and suppression, Interferences 1, 2, 4, 5, and 6 are considered. From the analysis of Section 3.1, Interferences 1, 2, and 4 can be detected and canceled by the proposed method. Take the real part (I signal path) of received signal in channel 1, for example, to evaluate the effectiveness of the proposed method.Figures5(a) and 5(b) show the time-domain waveforms and the frequency spectrum obtained from the FFT of the signals, respectively, and they illustrate that the multitone and LFM interfering signals are buried in Gaussian interference signals and cannot be directly detected in both time-domain and frequency domain. Figure 6 shows the relationship between terminate condition and the iteration number of the MP stage. It can be found that the values of ρ in the first three iterations are greater than the termination threshold, and it consists with the simulation conditions. Figure 7 shows the time-domain waveforms of the original interfering signals (Interferences 1, 2, and 4) and the residual signals in theory; Figure 8 shows the time-domain waveforms of the estimated interfering signals and the residual signal by the proposed method. Comparing Figures 7 and 8, it can be shown that the proposed method in this paper can exactly and effectively estimate the interfering signal. And the errors between these two signals can be measured with the normalized mean square error (NMSE), which are shown in Table 4. Accordingly, we can assume that there are not multitone and LFM interfering signals in the residual signal.Table 4
Normalized mean square error (NMSE) of estimated signals.
Name Interference 1 Interference 2 Interference 4 The residual signal NMSE 0.022 0.025 0.001 0.001Figure 5
Characteristic of received signals.
(a) (b)Figure 6
Relationship between terminate condition and the iteration number.Figure 7
Time-domain waveform of original interfering signals.
(a)
Retrieval interference from the first best atom (b)
Retrieval interference from the second best atom (c)
Retrieval interference from the third best atom (d)
The residual signalsFigure 8
Time-domain waveform of estimated interfering signals.
(a)
Retrieval interference from the first best atom (b)
Retrieval interference from the second best atom (c)
Retrieval interference from the third best atom (d)
The residual signals


## 4.2. Simulation 2

In this simulation, the proposed method is compared to the well-known space-only MPDR (S-MPDR) beamformer and three simulation scenarios are considered. In scenario 1, Interferences 3, 4, 5, and 6 are used. In other words, there is not any interfering signals with the same direction as the GNSS signal and the number of interferences is less than that of antenna elements. In scenario 2, Interferences 1, 4, 5, and 6 are adopted. It means that there is one interfering signal with the same direction as the GNSS signal. In scenario 3, Interferences 2, 3, 4, 5, and 6 are used. It implies that the number of interferences is equal to that of antenna elements.The normalized correlation peaks after interference suppression are shown in Figures9–14 for each scenario, which are used to measure the performance of signal acquisition after interference suppression by these two methods. For scenario 1, Figures 9 and 10 show that the two methods can effectively suppress the interferences. However, Figures 11 and 13 show that the MPDR beamformer has failed to capture the GNSS signal for both scenario 2 and scenario 3. Figures 12 and 14 show that the proposed method can effectively suppress the interferences and does not distort the normalized correlation peak of the GNSS signal even there is one interfering signal with the same direction as the GNSS signal and when the number of interference is more than the DoF of the antenna array.Figure 9
Correlation peaks after interference suppression by S-MPDR beamformer for scenario 1.
(a) (b) (c)Figure 10
Correlation peaks after interference suppression by the proposed method for scenario 1.
(a) (b) (c)Figure 11
Correlation peaks after interference suppression by S-MPDR beamformer for scenario 2.
(a) (b) (c)Figure 12
Correlation peaks after interference suppression by the proposed method for scenario 2.
(a) (b) (c)Figure 13
Correlation peaks after interference suppression by S-MPDR beamformer for scenario 3.
(a) (b) (c)Figure 14
Correlation peaks after interference suppression by the proposed method for scenario 3.
(a) (b) (c)


## 4.3. Simulation 3

In this simulation, the proposed method is compared to the well-known space-time MPDR (ST-MPDR) beamformer [7] and the distortionless space-time adaptive processor (DST-MPDR) [10]. The number of time delay taps is 7. And three simulation scenarios are conducted. In scenario 1, Interferences 1, 2, 4, 5, 6, and 7 are considered, which means that there is one single-tone interfering signal with the same direction as the GNSS signal and the number of wideband interferences is less than that of antenna elements. In scenario 2, Interferences 1, 2, 4, 5, 6, 7, and 8 are used. In other words, the number of wideband interferences is more than that of antenna elements. In scenario 3, Interferences 1, 2, 5, 6, 7, and 9 are used. It means that there is one wideband interfering signal with the same direction as the GNSS signal.The normalized correlation peaks after interference suppression by the three methods for each scenario are shown in Figures15–23, which are used to measure the performance of interference suppression. For scenario 1: Figure 15 shows that the space-time MPDR processing method causes the distortion and shift of the correlation peak; Figure 16 shows that although the distortionless space-time adaptive processor introduces code biases into the GNSS signal, it does not distort the correlation peak of the GNSS signal; Figure 17 shows the proposed algorithm does not affect the shape and the position of the correlation peaks. For both scenario 2 and scenario 3: Figures 18 and 19 and Figures 21 and 22 show that space-time MPDR processing and the distortionless space-time adaptive processor fail to suppress the interference and it is failed to capture the GNSS signal; Figures 20 and 23 show that the proposed method is still effective since the modulated wideband can be canceled by sparse decomposition in the first stage.Figure 15
Correlation peaks after interference suppression by ST-MPDR beamformer for scenario 1.
(a) (b) (c)Figure 16
Correlation peaks after interference suppression by DST-MPDR beamformer for scenario 1.
(a) (b) (c)Figure 17
Correlation peaks after interference suppression by the proposed method for scenario 1.
(a) (b) (c)Figure 18
Correlation peaks after interference suppression by ST-MPDR beamformer for scenario 2.
(a) (b) (c)Figure 19
Correlation peaks after interference suppression by DST-MPDR beamformer for scenario 2.
(a) (b) (c)Figure 20
Correlation peaks after interference suppression by the proposed method for scenario 2.
(a) (b) (c)Figure 21
Correlation peaks after interference suppression by ST-MPDR beamformer for scenario 3.
(a) (b) (c)Figure 22
Correlation peaks after interference suppression by DST-MPDR beamformer for scenario 3.
(a) (b) (c)Figure 23
Correlation peaks after interference suppression by the proposed method for scenario 3.
(a) (b) (c)


## 5. Conclusion

Based on the sparsity of the interfering signals and the advantage of the spatial processing, a novel cascaded multitype interferences suppression method using sparse representation and array processing is proposed and examined in this paper. Firstly, the parallel multichannel signal interference suppression method based on MP is proposed, which can save the spatial DoF of the antenna array by effectively detecting and canceling the narrowband and modulated wideband interference even when they vanish into the Gaussian interferences. Then, the MPDR beamformer is employed to suppress the residuary interferences (such as Gaussian noise interferences) by utilizing the spatial DoF of the antenna array. Numerical simulations show that the proposed method not only can suppress more interferences, but also does not affect the shape and position of the correlation peaks. Compared with the space-only MPDR beamformer, space-time MPDR beamformer, and the distortionless space-time adaptive processor, the proposed method is able to deal with multitypes interferences more effectively and can suppress the interference with the same direction as the desired signal. Therefore, the proposed method is able to effectively improve the interference suppression ability of GNSS receiver while reducing the cost of space and hardware.



---

*Source: 9832197-2017-01-30.xml*