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

Article information

J Electromagn Eng Sci. 2021;21(5):399-405
Publication date (electronic) : 2021 November 30
doi : https://doi.org/10.26866/jees.2021.5.r.48
1Korea Electronics Technology Institute (KETI), Seongnam, Korea
2Modem Development Team, Samsung Electronics Co., Hwasung, Korea
3Department of Information and Communication Engineering/Convergence Engineering for Intelligent Drone, Sejong University, Seoul, Korea
4School of Electronics and Information Engineering, Korea Aerospace University, Goyang, Korea
5Department of Smart Drone Convergence, Korea Aerospace University, Goyang, Korea
*Corresponding Author: Yunho Jung (e-mail: yjung@kau.ac.kr)
Received 2020 December 31; Revised 2021 March 3; Accepted 2021 May 10.

Abstract

A pre-processing technique is proposed to reduce the complexity of two-dimensional multiple signal classification (2D-MUSIC) for the joint range and angle estimation of frequency-modulated continuous-wave (FMCW) radar systems. By using the central symmetry of the angle steering vector from a uniform linear array (ULA) antenna and the linearity of the beat signal in the FMCW radar, this pre-processing technique transforms 2D-MUSIC from complex values into real values. To compare the computational complexity of the proposed algorithm with the conventional 2D-MUSIC, we measured the CPU processing time for various numbers of snapshots, and the evaluation results indicated that the 2D-MUSIC with the proposed pre-processing technique is approximately three times faster than the conventional 2D-MUSIC.

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 [13]. 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 [46]. 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

(1) yl(t)=k=1Kakej2π(fcτk+BTτkt)al(θk)+wl(t),

where ak, τ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. fc 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. wl(t) denotes additive white Gaussian noise (AWGN). The sampled signal yn(l,m) of yl(t) can be represented as follows:

(2) yn(l,m)=k=1K(akej2πfcτkbm,n(Rk)al(θk))+wl(l,m),

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). fs denotes the sampling frequency, c the speed of light, and Rk 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

(3) xn=[d¯1,n,,d¯l,n,,d¯L,n]T,

where l,n = [yn(l, 1), K, yn(l, M)]T. The covariance matrix for xn is defined as follows:

(4) R=1Nn=1NxnxnH,

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

(5) R=i=1KλieieiH+i=K+1LMλieieiH=EsΛsEsH+EnΛnEnH,

where λi (λ1 > λ2 > ⋯ > λLM) denotes the i-th eigenvalue and ei the corresponding eigenvector of the matrix R, respectively. Es and En represent the signal subspace and noise subspace of matrix R, respectively. Using the noise subspace En, we can establish the 2D-MUSIC spectrum for joint range and angle estimation, such as

(6) P(R,θ)=[vH(R,θ)EnEnHv(R,θ)]-1,

where v(R, θ) = [a1(θ), …, aL(θ)] ⊗ [b1(R), …, bM(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:

(7) q1,m(m)=[yn(L2,m),yn(L2-1,m),,yn(1,m)]
(8) q2,m(m)=[yn(L2+1,m),yn(L2+2,m),,yn(L,m)]

After performing the operations of y1,n(m) and y2,n(m) using q1,n and q2,n, an (L × 1)-dimensional vector yn can be expressed as follows:

(9) y1,n(m)=(q1,n(m)+q2,n(m))/2,
(10) y2,n(m)=(q1,n(m)-q2,n(m))/2j,
(11) yn(m)=[y1,n(m),y2,n(m)]T=A·S·b+w,

where

(12) S=diag[α1ej2πfcτ1,,αkej2πfcτk],,αKej2πfcτK,
(13) αk=αke(L-1)πdλsin θk

and b=[bm,n(R1),⋯,bm,n(RK)]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:

(14) A(l,k)={cos(π(dλ)(2l-1)sin θk),when 0<lL2cos(π(dλ)(2l-1-L)sin θk),when L2<lL

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

(15) Y1,n=[yn(M2),yn(M2-1),,yn(1)]
(16) Y2,n=[yn(M2+1),yn(M2+2),,yn(M)]

Assuming Z1,n = (Y2,n+Y1,n)/2 and Z2,n = (Y2,nY1,n)/2j, the (L × M)-dimensional matrix Zn is determined as follows:

(17) Zn=[Z1,n,Z2,n]=A·Sn·B+Wn,

where

(18) Sn=diag[α1sn,1,,αksn,k,,αKsn,K],
(19) sn,k=ej2π(fcτk+BT(Rkc)(M+2n-3)fs)

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

(20) B(k,m)={cos((2m-1)2πBcTfsRk),when 0<mM2sin((2m-1-M)2πBcTfsRk),when M2<mM

Consequently, yn(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:

(21) Zn(l,m)=k=1Ksn,kbm(Rk)al(θk)+w(l,m),

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 Wn. Taking the real part of Zn(l,m) can be expressed as follows:

(22) Re(Zn(l,m))=k=1Ksn,kbm(Rk)al(θk)+Re(w(l,m)),

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:

(23) v(R,θ)=[a1(θ),,aL(θ)]T[b1(R),,bL(R)]T

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, as and rs are the angle and range resolutions, respectively. Rmax 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.

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 (R1, θ1) = (50 m, 20°) and (R2, θ2) = (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. 25 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.

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.

Acknowledgments

This work was supported by the Technology Innovation Program (No. 10080619), funded by the Ministry of Trade, Industry and Energy (MOTIE, Korea), and CAD tools were supported by IDEC.

References

1. Manokhin GO, Erdyneev ZT, Geltser AA, Monastyrev EA. MUSIC-based algorithm for range-azimuth FMCW radar data processing without estimating number of targets. In : Proceedings of 2015 IEEE 15th Mediterranean Microwave Symposium (MMS); Lecce, Italy; 2015; p. 1–4.
2. Saponara S, Neri B. Radar sensor signal acquisition and 3D FFT processing for smart mobility surveillance systems. In : Proceedings of 2016 IEEE Sensors Applications Symposium (SAS); Catania, Italy; 2016; p. 1–6.
3. Zhang K, Ma P, Zhang J. DOA estimation algorithm based on FFT in switch antenna array. In : Proceedings of 2011 IEEE CIE International Conference on Radar; Chengdu, China; 2011; p. 1425–1428.
4. Belfiori F, van Rossum W, Hoogeboom P. Application of 2D MUSIC algorithm to range-azimuth FMCW radar data. In : Proceedings of 2012 9th European Radar Conference; Amsterdam, Netherlands; 2012; :242–245.
5. Zhao E, Zhang F, Zhang D, Pan S. Three-dimensional multiple signal classification (3D-MUSIC) for super-resolution FMCW radar detection. In : Proceedings of 2019 IEEE MTT-S International Wireless Symposium (IWS); Guangzhou, China; 2019; p. 1–3.
6. Li YC, Choi B, Chong JW, Oh D. 3D target localization of modified 3D MUSIC for a triple-channel K-band radar. Sensors 18(5)article no. 1634. 2018; https://doi.org/10.3390/s18051634 .
7. Zhang X, Xu L, Xu L, Xu D. Direction of departure (DOD) and direction of arrival (DOA) estimation in MIMO radar with reduced-dimension MUSIC. IEEE Communications Letters 14(12):1161–1163. 2010;
8. Zhang D, Zhang Y, Zheng G, Feng C, Tang J. Improved DOA estimation algorithm for co-prime linear arrays using root-MUSIC algorithm. Electronics Letters 53(18):1277–1279. 2017;
9. Rangarao KV, Venkatanarasimhan S. gold-MUSIC: a variation on MUSIC to accurately determine peaks of the spectrum. IEEE Transactions on Antennas and Propagation 61(4):2263–2268. 2013;
10. Huang K, Sha J, Shi W, Wang Z. An efficient FPGA implementation for 2-D MUSIC algorithm. Circuits, Systems, and Signal Processing 35(5):1795–1805. 2016;
11. Huarng KC, Yeh CC. A unitary transformation method for angle-of-arrival estimation. IEEE Transactions on Signal Processing 39(4):975–977. 1991;
12. Renbiao W. A novel universal preprocessing approach for high-resolution direction-of-arrival estimation. Journal of Electronics (China) 10(3):249–254. 1993;
13. Xu D, Liu Z, Qi X, Xu Y, Zeng Y. A FPGA-based implementation of MUSIC for centrosymmetric circular array. In : Proceedings of 2008 9th International Conference on Signal Processing. Beijing, China; 2008; p. 490–493.
14. Kim M, Ichige K, Arai H. Design of Jacobi EVD processor based on CORDIC for DOA estimation with MUSIC algorithm. IEICE Transactions on Communications 85(12):2648–2655. 2002;
15. Kim S, Ju Y, Lee J. A low-complexity joint TOAs and AOAs parameter estimator using dimension reduction for FMCW radar systems. Elektronika ir Elektrotechnika 24(4):59–63. 2018;
16. Xia M, Su W, Gu H, Dai Z, Li W, Yang J. Low-complexity range and angle two-dimensional gold-MUSIC for multi-carrier frequency MIMO radar. Electronics Letters 54(18):1088–1089. 2018;
17. Guo YD, Zhang YS, Tong NN. Beamspace ESPRIT algorithm for bistatic MIMO radar. Electronics Letters 47(15):876–878. 2011;

Biography

Yongchul Jung received B.S., M.S. and Ph.D. degrees from the School of Electronics and Information Engineering, Korea Aerospace University, Goyang, South Korea, in 2015, 2017, and 2021, respectively. He is currently a senior researcher with Korea Electronics Technology Institute (KETI), Seongnam, Korea. His research interests include the signal processing algorithm and system-on-chip (SoC) implementation for the radar signal processing system.

Seunghyeok Lee received B.S. and M.S. degrees from the School of Electronics and Information Engineering, Korea Aerospace University, Goyang, South Korea, in 2018 and 2020, respectively. He is currently an engineer with Samsung Company Ltd., Hwasung, Korea. His research interests include the signal processing algorithm and system-on-chip (SoC) implementation for the wireless communication system.

Seongjoo Lee received his B.S., M.S., and Ph.D. degrees in Department of Electrical and Electronic Engineering from Yonsei University, Seoul, Korea, in 1993, 1998, and 2002, respectively. From 2002 to 2003, he was a senior research Engineer with the IT SOC Research Center and the ASIC Research Center, Yonsei University. From 2003 to 2005, he was a senior engineer with the Core Tech Sector, Visual Display Division, Samsung Electronics Company Ltd., Suwon, South Korea. He was a research professor with the IT Center and the IT SoC Research Center, Yonsei University, from 2005 to 2006. He is currently a professor with the Department of Information and Communication Engineering, Sejong University, Seoul. His current research interests include system-on-chip (SoC) design for wireless communication systems, RADAR and Li-DAR signal processing, and SoC design for image signal processing.

Yunho Jung received B.S., M.S., and Ph.D. degrees in electrical and electronic engineering from Yonsei University, Seoul, South Korea, in 1998, 2000, and 2005, respectively. From 2005 to 2007, he was a Senior Engineer with the Communication Research Center, Wireless Device Solution Team, Telecommunication Network Division, Samsung Electronics Company Ltd., Suwon, South Korea. From 2007 to 2008, he was a research professor with the Institute of TMS Information Technology, Yonsei University. He is currently a professor with the School of Electronics and Information Engineering, Korea Aerospace University, Goyang, South Korea. His current research interests include the signal processing algorithm and system-on-chip (SoC) implementation for radar, wireless communication, and image processing systems.

Article information Continued

Fig. 1

Pseudo code of proposed pre-processing.

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.

Table 1

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

Process Multiplication Addition Division tan−1 cos sin exp
Calculation of pre-processing
 Conventional 0 0 0 0 0 0
 Proposed 0 4MLN 0 0 0 0
Covariance matrix calculation
 Conventional 4NL2M2 (3N−1)L2M2 0 0 0 0
 Proposed NL2M2 (N−1)L2M2 0 0 0 0
Eigenvalue decomposition (Jacobi method)
 Conventional 8QL3M3 8Q(LM−1)L2M2+Q 2Q 2Q Q Q
 Proposed 2QL3M3 2Q(LM−1)L2M2+Q Q Q Q 0
MUSIC spectrum search
 Conventional (4LM + 2)(LMK)(180/as)(Rmax/rs) (2(LM − 1)(LMK) + 2LMK − 1)(180/as)(Rmax/rs) 0 0 0 0
 Proposed (LM + 1)(LMK)(180/as)(Rmax/rs) ((LM − 1)(LMK) + (LMK − 1))(180/as)(Rmax/rs) 0 0 0 0

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)

Snapshots (N)

100 300 500 700 900
Conventional 2D-MUSIC algorithms 2D-MUSIC 19.50 20.57 21.06 22.18 23.05
RD-MUSIC 1.93 2.04 2.10 2.22 2.30
2D-gold MUSIC 1.30 1.37 1.40 1.48 1.54
2D-MUSICs with the proposed pre-processing 2D-MUSIC 6.82 (65.0) 7.13 (65.3) 7.58 (64.0) 7.60 (65.7) 8.03(65.2)
RD-MUSIC 0.62 (67.9) 0.66 (67.6) 0.71 (66.2) 0.73 (67.1) 0.77 (66.5)
2D-gold MUSIC 0.43 (66.9) 0.45 (67.2) 0.47 (66.4) 0.49 (66.9) 0.51 (66.9)

Numbers in parentheses indicate a reduction rate (%).