Low-Complexity 2D-MUSIC for Joint Range and Angle Estimation of Frequency Modulated Continuous-Wave Radar

Article information

Abstract

I. Introduction

In frequency-modulated continuous-wave (FMCW) radar systems, multiple signal classification (MUSIC) has been extensively used for estimating the angle of multiple targets with high resolution [1–3]. Recently, as a method for more accurate target detection, two-dimensional (2D)-MUSIC for joint range and angle estimation has been studied for FMCW radar systems [4–6]. However, the complexity of 2D-MUSIC increases exponentially compared to that of one-dimensional (1D)-MUSIC for angle estimation [7, 8]. To reduce the complexity of 2D-MUSIC, 2D-gold-MUSIC was proposed in [9, 10]. On the basis of 1D-gold-MUSIC, 2D-gold-MUSIC can reduce complexity by searching only a portion of the 2D-MUSIC spectrum [9]. Nevertheless, the complexity of 2D-gold-MUSIC still remains because all operations are performed with complex values.

To transform 1D-MUSIC from complex values into real values, various methods have been proposed. The unitary MUSIC algorithm for a centrosymmetric antenna array was proposed in [11], which can convert the complex covariance matrix and complex steering vector into a real matrix and real vector through unitary transformation. In [12, 13], a more effective pre-processing technique was proposed with less computational overhead than unitary MUSIC by using the angle phases of the incident signal as the central symmetry. This pre-processing converts the complex angle steering vector into real vectors. However, the range steering vector is still complex when this technique is applied to 2D-MUSIC.

In this paper, we propose a novel pre-processing technique that can transform complex range and angle steering vectors into real vectors for 2D-MUSIC. The simulation results indicate that the performance is the same as that of the conventional 2D-MUSIC, and the computational complexity can be significantly reduced. The remainder of this paper is organized as follows. In the estimation model, the 2D-MUSIC algorithm is briefly described. We then propose the pre-processing algorithm for 2D-MUSIC and show the simulation results to compare them with conventional 2D-MUSIC. Finally, the conclusion is presented.

II. Estimation Model

In the time domain, the FMCW radar’s beat signal at the l-th antenna (l ∈ {1,2,..,L}, where L denotes the number of antennas) is expressed as

where a_k, τ_k, and θ_k denote the complex amplitude, time delay, and angle of the k-th target (k ∈ {1,2,..,K}, where K is the number of targets), respectively. f_c denotes the carrier frequency. B and T denote the sweep bandwidth and time for one chirp, respectively. al (θk)=ej2πdλ(l-1)sin θk denotes the l-th element of the angle steering vector in the uniform linear array (ULA) antenna, where λ represents the wavelength and d the distance between antenna elements. w_l(t) denotes additive white Gaussian noise (AWGN). The sampled signal y_n(l,m) of y_l(t) can be represented as follows:

where bm,n (Rk)=ej4πBT(Rkc)m+n-2fs enotes the m-th element in the n-th snapshot of the range steering vector (m ∈ {1,…,M} and n ∈ {1,…,N}, where M is the number of samples and N is the number of snapshots, respectively). f_s denotes the sampling frequency, c the speed of light, and R_k defines the range of the k-th target.

The first step of 2D-MUSIC for joint range and angle estimation is to vectorize the received signal such that

where d̄_l,n = [y_n(l, 1), K, y_n(l, M)]^T. The covariance matrix for x_n is defined as follows:

where (·)^H denotes the Hermitian transpose. The corresponding eigenvalue decomposition is as follows:

where λ_i (λ₁ > λ₂ > ⋯ > λ_LM) denotes the i-th eigenvalue and e_i the corresponding eigenvector of the matrix R, respectively. E_s and E_n represent the signal subspace and noise subspace of matrix R, respectively. Using the noise subspace E_n, we can establish the 2D-MUSIC spectrum for joint range and angle estimation, such as

where v(R, θ) = [a₁(θ), …, a_L(θ)] ⊗ [b₁(R), …, b_M(R)], and ⊗ denotes the Kronecker product. P(R,θ) has peaks at the localization of targets through a 2D search.

III. Proposed Pre-processing Technique

To reduce the computational complexity of 2D-MUSIC for joint range and angle, we propose a pre-processing technique that can make a 2D-MUSIC algorithm based on real values. The number of ULA antennas and the number of time-axis samples are assumed to be even. Before the vectorization of Eq. (3), two vectors are formed as follows:

After performing the operations of y_1,n(m) and y_2,n(m) using q_1,n and q_2,n, an (L × 1)-dimensional vector y_n can be expressed as follows:

where

and b=[b_m,n(R₁),⋯,b_m,n(R_K)]^T. w represents an (L×1)-dimensional AWGN vector because the addition and subtraction between AWGN is still AWGN. The (l, k)-th element in matrix A, A(l, k), is determined as follows:

The next step is to form the (L×M/2)-dimensional matrices Y_1,n and Y_2,n as follows:

Assuming Z_1,n = (Y_2,n+Y_1,n)/2 and Z_2,n = (Y_2,n−Y_1,n)/2j, the (L × M)-dimensional matrix Z_n is determined as follows:

where

W_n is also an AWGN matrix. The (k,m)-th element of the matrix B, B(k, m) is determined as follows:

Consequently, y_n(l,m) in (2) can be transformed into a signal with a real-valued steering vector by using the proposed pre-processing technique and can be expressed as follows:

where al′ (θk) denotes the (l,k)-th element of the matrix A, bm′ (Rk) the (k,m)-th element of the matrix B, and wn′ (l,m) the (l,m)-th element of the matrix W_n. Taking the real part of Z_n(l,m) can be expressed as follows:

where sn,k′ is determined by Re(al′)*Re (sn,k)-Im( al′)*Im(sn,k). As in Eq. (2), al′ (θk) becomes the l-th element ofthe new angle steering vector, and bm′ (Rk) becomes the k-th element of the new range steering vector for 2D-MUSIC, respectively. Accordingly, the steering vector for the 2D-MUSIC spectrum can be defined as follows:

Therefore, using the proposed pre-processing technique and taking only the real part, 2D-MUSIC can be transformed from a complex value to a real value. Through a similar process, the proposed pre-processing technique can be applied to 2D-gold-MUSIC or 3D-MUSIC for the estimation of range, azimuth angle, and elevation angle. Fig. 1 also shows the pseudo code of proposed pre-processing.

Fig. 1

Pseudo code of proposed pre-processing.

We proposed a pre-processing algorithm to reduce the complexity of the computation of the 2D-MUSIC algorithm. Also, the proposed pre-processing algorithm can be applied to any 2D-MUSIC algorithm. Therefore Table 1 presents the comparison results for the computational complexity of the conventional 2D-MUSIC and the proposed 2D-MUSIC. It is assumed that eigenvalue decomposition is performed by the Jacobi method [14], where Q is the number of iterations. In the spectrum search process, a_s and r_s are the angle and range resolutions, respectively. R_max denotes the maximum range. As shown in Table 1, the proposed 2D-MUSIC reduces the multiplications by about four times and the additions by about three times in the calculation of the covariance matrix. In addition, both multiplications and additions are reduced by about four times in the eigenvalue decomposition. Moreover, the division and arctangent operations are reduced by two times. In the process of the MUSIC spectrum search, multiplications and additions are reduced by about four times and two times, respectively.

Table 1

Computational complexity comparison of the conventional 2D-MUSIC and the proposed 2D-MUSIC

IV. Simulation Results

To evaluate the performance of the proposed pre-processing technique for 2D-MUSIC, we assume that there are two uncorrelated stationary targets located at (R₁, θ₁) = (50 m, 20°) and (R₂, θ₂) = (70 m, 60°). There are four or eight receiving antennas, and the number of snapshots is 64, 96, and 128. The range and angle resolution are 0.1 m and 0.1°, respectively. Figs. 2–5 illustrate the variations of the azimuth angle and range estimation root mean square error (RMSE) with signal-to-noise ratio (SNR), respectively, where 1,000 Monte Carlo simulations were performed. In addition, Fig. 6 shows a spatial spectrum when SNR is set to 15 dB.

Fig. 2

RMSE of azimuth angle estimation from 1,000 Monte Carlo simulations for two targets (M = 64, L = 4, K = 2, Q = 1,000).

Fig. 3

RMSE of range estimation from 1,000 Monte Carlo simulations for two targets (M = 64, L = 4, K = 2, Q = 1,000).

Fig. 4

RMSE of azimuth angle estimation from 1,000 Monte Carlo simulations for two targets (M = 64, L = 8, K = 2, Q = 1,000).

Fig. 5

RMSE of range estimation from 1,000 Monte Carlo simulations for two targets (M = 64, L = 8, K = 2, Q = 1,000).

Fig. 6

Spatial spectrum of proposed preprocessing.

As mentioned in Section III, the proposed pre-processing techniques can be applied to various 2D-MUSIC algorithms and can reduce the computational complexity. Table 2 shows the evaluation results for the runtime, which corresponds to the computational complexity between the existing 2D-MUSIC algorithms and 2D-MUSICs with the proposed pre-processing technique. Basic 2D-MUSIC, 2D-gold-MUSIC [15], and reduced-dimension (RD)-MUSIC [16] algorithms are considered for evaluation. The timeit in MATLAB instructions can be used to calculate the runtime as in [17], and the runtime is analyzed against the number of snapshots. We can observe from Table 2 that the runtime of the basic 2D-MUSIC using the proposed pre-processing technique is reduced by a maximum of 65.7% compared to the case without pre-processing. In addition, the runtimes of the 2D-gold-MUSIC and RD-MUSIC with the proposed pre-processing technique are reduced by a maximum 67.2% and 67.9%, respectively.

Table 2

Runtime of the conventional 2D-MUSIC algorithms and 2D-MUSICs with the proposed pre-processing technique according to number of snapshots (M = 64, L = 4, K = 2, Q = 1,000) (unit: second)

V. Conclusion

In this paper, we propose a novel pre-processing technique to reduce the complexity of the 2D-MUSIC algorithm for the joint range and angle estimation of FMCW radar systems. Using the proposed pre-processing technique, we can transform all complex vectors into real vectors. The simulation results indicate that the runtime of 2D-MUSIC using the proposed pre-processing technique is reduced by approximately three times compared with that of conventional 2D-MUSIC. Because the proposed pre-processing can reduce the computational complexity significantly, it is expected that 2D-MUSIC can be implemented in real-time.

Article information Continued