# Low-Complexity-Based RD-MUSIC with Extrapolation for Joint TOA and DOA at Automotive FMCW Radar Systems

Authors: Sangdong Kim; Bongseok Kim; Jonghun Lee
Journal: Journal of Sensors
 (2020)

---

## Abstract

Low-complexity-based reduced-dimension–multiple-signal classification (RD-MUSIC) is proposed with extrapolation for joint time delay of arrivals (TOA) and direction of arrivals (DOA) at automotive frequency-modulated continuous-wave (FMCW) radar systems. When a vehicle is driving on the road, the automotive FMCW radar can estimate the position of multiple other vehicles, because it can estimate multiple parameters, such as TOA and DOA. Over time, the requirement of the accuracy and resolution parameters of automotive FMCW radar is increasing. To accurately estimate the parameters of multiple vehicles, such as range and angle, it is difficult to use a low-resolution algorithm, such as the two-dimensional fast Fourier transform. To improve parameter estimation performance, high-resolution algorithms, such as the 2D-MUSIC, are required. However, the conventional high-resolution methods have a high complexity and, thus, are not applicable to a real-time radar system for a vehicle. Therefore, in this work, a low-complexity RD-MUSIC with extrapolation algorithm is proposed to have a resolution similar to that of a high-resolution algorithm to estimate the position of other vehicles. Compared with conventional low complexity high resolution, in experimental results, the proposed method had better performance.


---

## Body

## 1. Introduction

Frequency-modulated continuous-wave (FMCW) radar systems have many advantages, including lower cost and complexity, over equivalent pulse radar systems [1–3]. For FMCW radar, spatial–temporal parameters, such as multipath time delays of arrivals (TOA) and directions of arrivals (DOA), have been widely studied [4]. These two parameters are useful to estimate the position of moving targets in FMCW radar systems. Especially, a beamforming technique based on phased arrays for vehicle radar sensor systems [5] has been used for smart cruise control, traffic monitoring, and collision avoidance [2, 6, 7]. The FMCW radar has the characteristic that it decreases with the bandwidth corresponding to the frequency of the de-chirped received signal irrespective of the transmitted bandwidth. Therefore, the signal-processing complexity is significantly lower than that of conventional ultrawideband radar. By means of a dechirping method of an FMCW radio frequency (RF) module, the received signals can be transformed into sinusoidal waveforms to acquire TOAs and DOAs information. We can define these sinusoidal signals as beat signals.The resolution parameters of the FMCW radar are estimated through a variety of algorithms, from conventional fast Fourier transform (FFT) to multiple signal classification (MUSIC) algorithms, as vehicle requirements increase. A one-dimensional parameter estimator cannot be used to estimate multiple parameters simultaneously. For this reason, it is necessary to consider a two-dimensional parameter estimator. In the case of a two-dimensional parameter estimator, conventional 2D-FFT has performance degradation for automotive radars requiring high-resolution parameters, such as range and angle. To improve the estimation performance of range and angle parameters jointly, conventional two-dimensional high-resolution algorithms such as two-dimensional estimation of signal parameters via a rotational invariant technique (2D-ESPRIT) and 2D-MUSIC were used to estimate the parameters of multiple targets. Many studies represent the estimation accuracy of the superresolution algorithm is more two or three times than the conventional FFT algorithm. However, due to the high complexity of the high-resolution algorithms, real-time automotive radar has difficulties in applying conventional algorithms. For this reason, various low-complexity-based 2D high-resolution algorithms have been proposed.In [8], this paper proposed a low-complexity super-resolution joint angle and delay estimation algorithm for range-azimuth FMCW radar. The phase shifts in time and arrays are exploited by the temporal and spatial-temporal smoothing technique of the proposed method. The proposed method is designed to estimate the range and angle sequentially without singular value decomposition (SVD) and eigenvalue decomposition (EVD) to reduce the computational burden. In case of complexity, the SVD or EVD to obtain eigenvector and eigenvalue has many computational burdens. In order not to use this SVD or EVD, this paper uses the square-inverse operator to separate signal and noise eigenvalue. However, this method degrades parameter estimation performance. In [9], in order to obtain a high-resolution range profile (HRRP), the high-resolution algorithms are required. This paper also needs low complexity high-resolution algorithm because of applying the real-time system. So, the RELAX algorithm is used in this paper. However, since this paper focuses on the one-dimensional spectrum, it is not suitable for the two-dimensional parameter estimator required in this paper. Another study [10] presented collocated multiple-input multiple-output (MIMO) radar that utilizes a low-complexity ESPRIT-based DOA estimator. To reduce complexity, the fact that the Kronecker product results of transmit and receive steering vectors can be transformed to other steering vectors was used. However, this result has problems in that the DOA estimator is only used for MIMO radar. In [11], a cross-correlation function of a received signal that can find a noise subspace without singular value decomposition (SVD) or eigenvalue decomposition (EVD) was proposed. However, this method can only be used for the two-component uniform linear array (ULA) of an L-shaped array. Therefore, conventional low-complexity 2D high-resolution algorithms still are difficult to apply to automotive radar systems, and there is the limitation of only operating in certain conditions, such as L-shaped ones. In another study [4], a low-complexity algorithm using the combination of DFT and MUSIC was found to have the disadvantage that it is difficult to apply to the trend of increasing range resolution in automotive environments. Therefore, a low-complexity-based dimension RD-MUSIC is proposed with an extrapolation algorithm for joint TOAs and DOAs in automotive FMCW radar systems. In Section 2, the system model is explained. In Section 3, the structure of the conventional 2D-MUSIC estimator is analyzed. In Section 4, the low-complexity-based dimension RD-MUSIC with the extrapolation algorithm for automotive FMCW is proposed. In Section 5, a simulation conducted to assess the estimation results of the proposed algorithm is described. And, the CPU execution time measured in MATLAB is used to evaluate the complexity reduction of the proposed algorithm. In Section 6, the estimation performance of the proposed method assessed through real experiments is discussed. Section 7 concludes this work.


### 1.1. Notation

(.)T and (.)H denote transpose and conjugate transpose, respectively. Operator ⊗ is the Kronecker product, and IL is the L×L identity matrix.


## 1.1. Notation

(.)T and (.)H denote transpose and conjugate transpose, respectively. Operator ⊗ is the Kronecker product, and IL is the L×L identity matrix.


## 2. System Model

This section addresses the system model of the FMCW radar systems. Figure1 shows the TX signal of FMCW radar in terms of change of frequency according to time. As shown in Figure 1, TX frequency linearly increases as the symbol period of FMCW radar, Tsym. Let us denote the initial frequency as fi, and the frequency at a time t is denoted by ft and expressed as [2]:
(1)ft=fi+Bt/Tsymwhere B is the bandwidth of the system. The chirp rate according to time is denoted by μ, i.e., μ=B/Tsym. By employing frequency according to time, the instantaneous phase ϕt for 0≤t<Tsym is expressed into integral term as follows:
(2)ϕt=2π∫0tftdt=2πfit+μt22.Figure 1
TX signal whose frequency varies with time.Consequently, the FMCW radar signalst is expressed as:
(3)st=expjϕt=expj2πfit+μt22for0≤t<Tsym.M targets over Tsym for the mth target for a ULA consisting of K elements are considered and distance between adjacent arrays is set to λ/2, where λ is the carrier frequency’s wavelength as shown in Figure 2. One can represent the received signal in a linear and time-invariant environment at the kth antenna element with the complex amplitude am in previous work [2] such that
(4)ykt=∑m=0M−1a~mst−τmexpjπksinθm+ω~ktwhere a~m is the complex amplitude of the mth target, τm is the TOA, θm defines the DOA, and ω~kt means the kth antenna position’s additive white Gaussian noise (AWGN).Figure 2
Top view and structure of ULA.
(a)
Top view of ULA(b)
Structure of ULAIn the receiver (RX) part by dechirping, the RX signal from targetsykt can multiply with the conjugation of the TX signals st such that
(5)dkt=ykts∗twhere dkt means the kth antenna array’s output results of the dechirping method. The beat signal for the lth chirp and the kth array dl,kt is obtained and expressed as the product of the TOA, Doppler, and DOA terms as follows:
(6)dkt=∑m=1Ma~mexp−j2πfiτm−μτm2/2⏟≡amexp−j2πμτmtexpjπksinθm+s∗tω~kt⏟≡ωkt=∑m=1Mamexp−j2πμτmt⏟TOAexpjπksinθm⏟DOA+ωkt⏟noise.From an analog-to-digital (ADC) converter for Nyquist sampling, where the sampling frequency needed isfs=1/Ts, the digital received signal dkns of dkt can be represented such that
(7)dkns=∑m=0M−1amexp−j2πμτmTsnsexpjπksinθm+ωknswhere ns=0,1,⋯N−1.


## 3. Conventional 2D-MUSIC Estimator

The MUSIC algorithm introduced in [12] is a popular superresolution parameter estimation algorithm. The MUSIC algorithm makes use of the signal and noise subspaces of the time-average covariance matrix of the received signal. The conventional 2D-MUSIC estimation algorithm is based on a stacking received data vector such that
(8)Dn=dn,0T,dn,1T,⋯,dn,K−1TTwhere dn,k=dkn,dkn+1,⋯,dkn+L−1T, and L means the parameter of selection for 2≤L<N. Using the stacking received data matrix, the covariance matrix can be estimated as:
(9)R=1N−L∑n=0N−L−1DnDnH.Using covariance matrixR, we should obtain the signal and noise eigenvector to establish the superresolution spectrum. Through EVD, one can obtain the signal subspace matrix Es and noise subspace matrix En by
(10)R=ESENλ00⋯00λ1⋱⋮⋮⋱⋱00⋯0λL−1ES∗EN∗where the signal subspace matrix Es is the eigenvectors corresponding to the M largest eigenvalues of R, and the noise subspace matrix EN is the eigenvectors corresponding to the KL−M smallest eigenvalues of R. The largest M+1 eigenvalues of λ0, …, λM correspond to the M+1 eigenvectors of Es. The other eigenvalues λM+1,⋯,λL−1 correspond to the eigenvectors of En such that λM+1=⋯=λL−1=σ2. The MUSIC algorithm uses the characteristics that the steering vectors aτ and aθ are spanned by the signal subspace and the steering vectors are orthogonal to the columns of noise eigenvectors En such that
(11)ENHaτ⊗aθ=0where aτ and aθ are defined by
(12)aτ=1,exp−jμτTs,⋯,exp−jμτTsN−1T,(13)aθ=1,exp−jπsinθ,⋯,exp−jK−1πsinθT.Using the noise subspace matrixEn, the 2D-MUSIC TOA and DOA spectrum function can be established as
(14)f2D−MUSICτ,θ=1aτ⊗aθHEnEnHaτ⊗aθwhere aτ and aθ are the steering vectors of TOA and DOA, respectively. Here, the M largest peaks of f2D−MUSICτ,θ are taken as the estimates of the TOA and DOA for the automotive targets. For 2D-MUSIC, because a huge 2D search and EVD are needed, it is inefficient because of the high computational cost. In the following sections, a low-complexity-based RD-MUSIC with extrapolation is proposed for joint TOAs and DOAs at automotive FMCW radar systems.


## 4. Proposed Low-Complexity-Based RD-MUSIC with Extrapolation for Joint TOAs and DOAs

The proposed estimation algorithm is based on the stacking received data matrix of Eq. (8). The signal subspace matrix Es and the noise subspace matrix En can separate using the EVD of R. The noise subspace matrix En is orthogonal to the actual TOA and DOA steering vector at m−th target. The denominator Vτm,θm of Eq. (11) can be rewritten as
(15)Vτm,θm=aθmHaτm⊗ILHEnEnHaτm⊗ILaθmIt is possible to transform the two dimensions to one dimension through a dimension reduction method, which can separate the TOA and the DOA parameters, by using Eq. (15). The TOAs are first determined by the extrapolation results of the received signal, as in a previous study [12]. In the first antenna element, the indices of the received signal’s extrapolation estimate the TOAs for multiple targets. To achieve extrapolation results, the FFT method is needed as
(16)dFFT,p=d0,0fpwhere fp is the p−th steering vector of FFT for the TOAs, i.e., fp=1,exp–j2πp/L,⋯,exp–j2πL−1p/LT. In practice, however, the finite data length L causes smearing and leakage in the FFT.Therefore, it is necessary to process the next step for the extrapolation algorithm using autoregression (AR). For extrapolation, each chirp signal’s AR parameters can be estimated, and linear prediction with the estimated parameters can be achieved. To estimate AR parameters, the model-based techniques depend on modeling received signald1=d10,d11,⋯,d1L−1T with L in the first antenna as the output of a linear system of a rational system form as follows:
(17)Hz=BzAz=∑k=0hbkz−k1+∑k=1gakz−k.This mathematical model to represent the given received signal by the pole-zero linear model in (17) is called an autoregressive-moving average (ARMA) model. This model is categorized as the ARMA model, AR model, and moving-average (MA) model by the values of h and g. Among these three linear models, the AR model with h=0 is the most widely used approach to model nonwhite random process, because the AR model results in very simple linear equations for the AR parameters [13].Using the AR model in Figure3, the received signal in the first antenna element can be modeled as
(18)d^1n=−∑k=1pakd1n−k+εn.Figure 3
Extrapolation process: (a) received signal, (b) estimated impulse response of the AR process, (c) extrapolated signal, and (d) FFT of extrapolated signal.
(a)(b)(c)(d)In this case, the power spectrumPxz of a pth order AR process is defined as follows:
(19)Pxz=b021+∑k=1pakz−k2where b0 and ak can be estimated from the data and the accuracy of spectrum estimation, P^xz will depend on how accurately the model parameters may be estimated, and εn is the modeling error, which is assumed to be a random noise. Since AR spectrum estimation requires that an all-pole model be found for the process, a variety of techniques may be used to estimate the all-pole parameter ak [14]. The typical method to estimate an AR parameter for estimating distance information is the covariance method [14]. To find the pth order AR parameters a∧1,a∧2,⋯,a∧pT, the covariance method requires a set of linear equations,
(20)cd1,1cd2,1⋯cdp,1cd1,2cd2,2⋯cdp,2⋮⋮⋱⋮cd1,pcd2,p⋯cdp,pa^1a^2⋮a^p=−cd1cd2⋮cdp.The autocorrelation sequencecxk,l is defined as
(21)cdl,k=∑n=pN−1d1n−ld1∗n−k.For distance spectrum estimation using the AR model, the order of the AR processp should be determined by the number of targets M. When the order p is smaller than the number of targets M, the results of the distance spectrum will be smoothed and will have low resolution. When the order p is larger than the number of targets M, the results of the distance spectrum will have spurious peaks. Another method of determining the model order p involves the use of the Akaike Information Criterion (AIC) and Minimum Description Length (MDL) [15, 16]. The optimal modeling order can be selected by changing the model order until the values of the MDL or the AIC are minimized.For the range estimation, a 1D-FFT [2] is performed on the extrapolated chirp signals with the chirp index obtained. The 1D-FFT results of the extrapolated received signal in the first array D0,n=D0n,D0n+1,⋯,D0n+LE−1T are expressed as
(22)D0,0=Wd0,0where d0,0=d00,d01,⋯,d0LE−1T, and LE denotes the number of extrapolated samples. After 1D-FFT is established, the peaks among the distance spectrum I=I1,I2,⋯,IM are detected, and the peak index means the distance results of targets.After the extrapolation in the first antenna element is accomplished among the multiple targets, the TOA index vector is obtained,I=I0,I1,⋯,IM−1, where Im denotes μτmTsL. Therefore, the estimated TOA direction vector for the mth target can be written as:
(23)Tτ^m=1,expjμτ∧mTs,⋯,expjμτ∧mTsL−1T⊗IL.For each target DOA, by substituting the above-estimated vector in Eq. (15), a normal MUSIC estimator at the mth target is obtained such that
(24)fmθ=1SθHQmSθwhere Qm=Tτ∧mHEnEnHTτ^m. After the MUSIC estimation of the mth target and peak detection processing, through the DOA index matrix J=J0,J1,⋯,JM−1 of the multiple targets, the DOA of mth target is accomplished by
(25)θ^m=sin−12JmKwhere sin−1· is the inverse operator of the sine function.Thus, the proposed algorithm TOA and DOA information for vehicle FMCW radar is outlined in Figure4. The major steps of the proposed algorithm are as follows.Step 1.
Construct the spatial–temporal covariance matrixR.Step 2.
Through the EVD ofR, obtain the signal subspace matrix ES and the noise subspace matrix EN, respectively.Step 3.
Through Eq. (15), separate the steering vectors of TOAs and the DOAs, respectively, using reduced dimension.Step 4.
Search forτm through the extrapolation and peak detection of extrapolation results, so one can obtain the M estimated TOA terms of multiple targets, i.e., τ^m for 1≤m≤M.Step 5.
Substitute the estimated TOA direction vector of Eq. (23) in Eq. (15).Step 6.
Search forθm through the MUSIC estimator of Eq. (24) and peak detection, one can find the M estimated DOA terms of multiple targets, i.e., θ^m for 1≤m≤M.Figure 4
Steps of the proposed algorithm.


## 5. Simulation Results and Complexity Analysis

A MATLAB simulation was performed to verify the estimation results of the proposed algorithm compared with the conventional 2D-MUSIC. In this section, the proposed algorithm and 2D-MUSIC are only analyzed, because other algorithms are not based spectrum. A snapshot of the time delay–angle map is represented in the case of one target and two targets. In this section, the parameters are set as shown in Table1. It was assumed that a 24-GHz RF module of an FMCW radar with one transmitting channel and two receiving channels is used to obtain the simulation results.Table 1
Simulation parameters for AWGN channel.
ParameterValueChange rate of chirp, μ3.125×1012Sampling interval,Ts200 nsSymbol duration,Tsym80μsFor the simulation, as presented in Figure5, a single target was placed at R=6.75m and θ=15°. As in Figure 5, the proposed algorithm estimates similar angle and time delay results compared with the conventional algorithm.Figure 5
Time-angle map results withK=2 for single target: (a) the conventional 2D-MUSIC and (b) the proposed RD-MUSIC with extrapolation.
(a)(b)Figure6 shows a simulation snapshot of two targets in an AWGN channel. Two different targets were placed at R1,θ1=5.25m,8° and R2,θ2=6.75m,15°. Because this result is similar to that in Figure 5, the proposed algorithm and the conventional algorithm obtain similar angles and time delay results correctly.Figure 6
Time-angle map results withK=2 for two targets: (a) the conventional 2D-MUSIC and (b) the proposed RD-MUSIC with extrapolation.
(a)(b)In root mean squared error (RMSE), the proposed algorithm is analyzed for the RMSE of the estimated TOA and DOA compared to other algorithms. We compare the RMSE of the ideal RELAX and ESPRIT algorithm with RMSE of the proposed estimator in TOA and DOA. In Figures7(a) and 7(b), two targets were placed at R1,θ1=15.0m,5° and R2,θ2=16.5m,9°. Two different targets are located at a greater distance interval than the distance resolution. Because the distance interval is greater than distance resolution, the RMSE results of all algorithm have similar results. In Figures 7(c) and 7(d), two targets were placed at R1,θ1=15.0m,5° and R2,θ2=15.4m,12°. Two different targets are located at lower distance interval than the distance resolution. Since the distance interval is lower than distance resolution, the RMSE results of MUSIC, RELAX, and the proposed algorithm have similar results while that of FFT has low performance.Figure 7
RMSE simulation results (a) TOA, (b) DOA ofR1,θ1=15.0m,5° and R2,θ2=16.5m,9°, (c) TOA, and (d) DOA of R1,θ1=15.0m,5° and R2,θ2=15.4m,12°.
(a)(b)(c)(d)For complexity, the proposed algorithm, 2D-MUSIC, and 2D-FFT are analyzed. The computational complexity of the algorithms is consisted of the primary multiplication operation. The 2D-MUSIC and 2D-FFT use full search to detect target for the ranges and angles, whereas the proposed algorithm requires the memory-efficient search to estimate multiple parameters. In case of 2D-FFT method,K times N-point FFT for distance estimation and N times K-point FFT for angle estimation are accomplished. The required number of multiplication operation of 2D-FFT is described by (28). And, the algorithm part that does not require SVD is only the FFT. The 2D-MUSIC algorithm’s complexity is composed of autocorrelation matrix, EVD, and spectrum generation by the orthogonality in (27). In case of the proposed algorithm, 1D-extrapolation and RD-MUSIC for range and angle are performed in (26). Here, n denotes the number of spectrum samples of the MUSIC algorithm. When the complexity of the proposed structure in (26) is compared with that of the 2D-MUSIC in (27), the proposed structure has a complexity of the n, while the 2D-MUSIC is composed of n2.
(26)Cproposed=3NM−M2+N−LN2K2+N3K3+nN2K+N2NK−M+N2(27)C2D‐MUSIC=MN2K2+N3K3+n2NKNK−M+NK−M(28)C2D‐FFT=KNlog2N+NKlog2KThe complexity of the proposed algorithm is verified by measuring the CPU execution time in MATLAB. Figure8 shows the measured CPU time based on the number of time samples N. With K=2, the complexity of the proposed method is at least 50 times lower than that of the conventional 2D-MUSIC algorithm. The proposed method dramatically reduces the complexity burden by applying a reduced dimension method compared with the conventional 2D-MUSIC algorithm while providing similar performance to the 2D MUSIC algorithm. 2D-FFT do not analyze because 2D-FFT’s complexity is much lower than other algorithms.Figure 8
MATLAB CPU execution time for the conventional 2D-MUSIC and the proposed algorithm withK=2.


## 6. Experiments

In various experiments, the estimation results of the proposed method were evaluated in an anechoic chamber located at Daegu Gyeongbuk Institute of Science and Technology (DGIST) in South Korea. Using one TX channel and two received (RX) channels, an FMCW RF module was made with a 24-GHz carrier frequency. The transmitter involved an oscillator with 26 MHz, a frequency synthesizer, and a voltage-controlled oscillator. From the frequency synthesizer, an FMCW TX signal was produced for the 200-MHz bandwidth in the range of 24.05–24.25 GHz. The receiver consisted of two high-pass filters, two low-pass filters, two low-noise amplifiers (LNAs), and two mixers. The noise figures of the receiver and the LNA were 8 and 14 dB, respectively. The gain was set to 2.5 dB. By the mixer, the RF signal was changed to an intermediate-frequency signal as the beat signal. The developed 24-GHz FMCW RF module is shown in Figure9 [2].Figure 9
Implemented FMCW RF module [2].To avoid an undesired reflected signal, the experiment was conducted in an anechoic chamber. For the experiments, a single target was placed atR=7.2m and θ=0°. The experimental results of the time-angle map were estimated, as given in Figure 10. As shown in Figure 10, the proposed method and the conventional method estimated similar angles and time delays correctly, but the proposed algorithm had a lower complexity load than 2D-MUSIC.Figure 10
Experimental results of (a) the conventional 2D-MUSIC and (b) the proposed RD-MUSIC with extrapolation.
(a)(b)


## 7. Conclusions

A low-complexity-based RD-MUSIC with extrapolation for joint TOAs and DOAs at automotive FMCW radar systems was proposed. The proposed method considerably reduces the complexity of using RD-MUSIC to reduce the dimensions from two dimensions to one dimension for the automotive FMCW radar system. The proposed method solves the low-complexity problem by using the extrapolation method instead of 1D-MUSIC in the range estimation.The simulation results showed that 2D-MUSIC and the proposed algorithm have similar estimation performance, while the complexity of the proposed method is at least 50 times lower than that of the conventional 2D-MUSIC algorithm withK=2. Experimental analyses showed that the proposed algorithm provided a similar performance compared with 2D-MUSIC. Therefore, the proposed method is applicable to automotive radar because of its low complexity for parameter estimation.



---

*Source: 7342385-2020-06-28.xml*