2
1 INTRODUCTION
Traditionally, FFT is used to analyze short transient
signal in spectrum domain. The FFT needs long data
blocks to achieve high frequency resolution and
accuracy which is difficult to achieve with short transient
signals. The same case for non-stationary signal, short
data set are required to keep track of time varying
characteristic of the signal (H, Shi, 2013).
To analyze short transient signals with MUSIC method
in hardware, Eigen Value Decomposition (EVD) of a
matrix is an important complex linear algebra algorithm.
Its application varies from radar signal processing to
digital image processing. Many real-time signal
processing require fast EVD computation involving
large matrices. Autocorrelation matrix is constructed
with the short data stream. The autocorrelation matrix is
real symmetric so that it can be computed with Jacobi
method by performing a sequence of orthogonal
similarity updates. Eigenvalues represent the power
characteristic of a signal. The larger number of
processing data samples, the better estimation resolution
is achieved.
Two-sided algorithm for EVD computation (S. Wang, V.
Piuri, and J. E. E. Swartzlander,1997) usually is adopted
because it is suitable for mapping onto regular systolic
array architecture and highly suitable for parallel
computation. A previous study (H. Shi,2013)shows that
processing 4 × 4 matrix has throughput of 100M
sample/sec for a data length of 48 samples. However this
size is not sufficient for the further higher resolution
real-time signal processing, larger architecture required.
The main purpose of this thesis is to develop a new
architecture to extend the dimension of EVD for MUSIC
algorithm, which is fully pipelined processing. The
design based on eigenvector rotation structure. This
paper includes following sections. Section 2 gives
general review of the MUSIC and related theories which
will be used in the rotation method. Section 3 describes
EVD, diagonal, off-diagonal element rotation and data
swapping in details. Ping-Pong method in section 4 is
used to deal with storage issue caused by matrix
boundary data dependency. Section 5 goes inside
processing element, explains its internal structure, data
flow and ID control by FSM. Session 6 and section 7 will
discuss the design verification result with possible
further investigation. Section 8 concludes the whole
simulation information.
2 MUSIC ALGORITHM
2.1 General description
Eigen analysis based methods assume that the signal
consists of sinusoids with back ground white noise. In
MUSIC algorithm, symmetrical matrix with dimension
M×M is formed by apply auto-correction to input signal
samples. Eigen Value Decomposition (EVD) of
symmetrical matrix results separated signal and noise
sub-space values. Corresponding eigenvectors from
signal sub-space orthogonalize with noise sub-space
eigenvectors. Due peaks can be found in the estimator
function:
J
(
)
=
[()]
[()]
(2.0)
For various values yields the strongest frequencies,
where a
(
)
refers to the eigenvectors of signal
sub-space, U
v
is the noise sub-space vectors. Frequency
spectrum can be plot by equation (2.0).
The general procedure to obtain spectrum from input
transient signal (H.Shi,2013) is:
a) Sample input transient signal. Input signal is
sampled to obtain data stream x[n].
b) Buffer sampled data x[0],x[1],…x[M-1]. M is
the dimension of M×M symmetrical matrix.
c) Compute auto-correlation matrix based on M
series buffer data.
d) Eigen-decomposition M × M symmetrical
matrix. Rotation angles are used to composite
eigenvectors matrix.
e) Sub-space classification of signal eigenvectors
and noise eigenvectors.
f) Calculate power spectrum density of MUSIC.
Step d) Eigen-decomposition is the most computation
intensive among the overall procedure. The rest steps are
computed by Matlab, while the Eigen-decomposition is
implemented in FPGA. This paper focuses on FPGA
based design to realize the Eigen-decomposition. In
order to separate noise and signal sub-space in step d),
following steps is needed:
d.1) Jacobi rotation. Given rotation is applied to
diagonal M × M symmetrical matrix and obtain
eigenvectors. Jacobi method is chosen to implement
the Given rotation. Details described in
Section(2.2).
d.2) CORDIC rotation. Jacobi method applies
angle multiplication to realize the Given rotation.
However, angle multiplication cannot be directly
implemented in hardware. Due CORDIC rotation
method is used to transform angle multiplication to
“add and shift” operation in FPGA.Section(2.3,2.4).
A 4×4 symmetrical matrix decomposition base on above
steps have been realized by (H. Shi,2013). This paper
furthermore extends existed 4×4 decomposition core to
higher × 8 dimension to obtain up to eight high
resolution discrete sinosoids. Reuse 4×4 matrix reduces
the design workload. Ping-Pong method (section 4) is