VLSI Circuits for Orthogonal Matching Pursuit Algorithm with Performance Trade-offs

Abstract

The conventional Shannon-Nyquist sampling theory sets the goal for a signal to be sampled at a rate twice the highest frequency component present in the signal. This requires high sampling Analog to Digital Converter (ADC) for measuring high frequency signals like Radio Frequency (RF) signals. Compressed Sensing (CS) is a recently developed sampling paradigm which proves to be an alternative to the Nyquist sampling requirements. CS exploits the sparsity property of signals and enables sparse signals to be acquired and measured at sub-Nyquist rate. CS is achieved by means of two processes, compressive sampling and signal recovery. In the compressive sampling step, random linear measurements are generated from the input signal by some hardware like Analog to Information Converter (AIC) or Random Modulation Pre-Integrator (RMPI). The original signal is recovered from the measurement samples by use of recovery algorithms in the second step. Out of these algorithms Orthogonal Matching Pursuit (OMP) algorithm is very popular and widely used for its moderate complexity and better performance. The major steps of OMP algorithm are Atom Searching (AS) and Least Squares (LS) evaluation. In the AS step, a column is identified from the measurement matrix which is most correlated to the current residual and a least squares problem is solved to find the signal estimate in the LS step. In this work, different Very Large Scale Integration (VLSI) circuits for OMP algorithm are proposed and the performance indices like hardware complexity, recovery speed, power consumption and Recovery Signal to Noise Ratio (RSNR) are estimated to demonstrate the circuit trade-offs. The architectures of OMP algorithm differ in the technique of solving the LS problem. In this work, three different architectures are proposed to implement the OMP algorithm on Field Programmable Gate Array (FPGA) which are termed as architectures 1, 2 and 3. Architecture 1 solves the LS problem using pseudoinverse computation based on QR Decomposition (QRD). Partial QRD is evaluated by modified Gram-Schimdt algorithm. Architecture 2 is an improved version of the previous one and uses same QRD but avoids pseudoinverse computation. Architecture 2 implements a novel Low Power Fast OMP (LPF-OMP) algorithm which is proposed in this work. LPF-OMP algorithm, an improved version of classic OMP algorithm, has high recovery speed compared to other versions of OMP algorithm. QRD based architectures are suitable for low sparse signals where the resource utilization loosely depends on signal sparsity but suffers from low RSNR performance. Architecture 3 solves the LS problem by Gaussian Elimination (GE) to achieve high RSNR performance by keeping other performances within acceptable limit. A novel Incremental Gaussian Elimination (IGE) technique is proposed which efficiently implements GE. In this work, Gaussian test pulses for Radio Detection And Ranging (RADAR) application and multi-tone signals are taken as the input signals to validate the designs. The random measurements from the input signals are taken using the MATLAB-Simulink model of the AIC or RMPI. The proposed designs are targeted to Virtex6 FPGA device to compare with other reported works for K = 256, N = 1024 and Im = 36 where K is the measurement vector length, N is the length of the signal and Im is the maximum number of iterations. Sparsity of RADAR pulses is unknown a priori and thus OMP algorithm can be stopped after maximum number of iterations or when a stopping criteria is fulfilled. A novel stopping criteria is also proposed in this work. Classic OMP can recover an m-sparse signal in Im = m iterations but LPF-OMP may run for extra few iterations for correct recovery. RSNR performance is measured after Im = m = 36 number of iterations for comparison. Original signal reconstruction is also an objective of this research and thus a novel Look Up Table (LUT) based approach is proposed to generate the elements of Gabor dictionary. Reconstruction of the practical signals is demonstrated by implementing the architectures on Artix7 FPGA device. Application Specific Integrated Circuit (ASIC) implementation of OMP algorithm is also attempted in this work as a part of Linear Frequency Modulated Continuous Wave (LFM-CW) RADAR receiver for detection of stationary targets. Two new ASIC realizations are proposed and they are termed as architectures 4 and 5. These architectures implement the LPF-OMP algorithm to achieve fast reconstruction speed and use IGE technique to achieve better RSNR performance. These architectures are modified version of architecture 3 and are implemented for parameters K = 64, N = 256 and Im = 16 using SCL180 nm standard cell library provided by Semi-Conductor Laboratory (SCL) India. OMP implemented on ASIC provides performance advantage over FPGA implementations and the proposed ASIC realizations are hardware efficient compared to other reported ASIC implementations. Improvement of the range solution of the CS based LFM-CW RADAR is also attempted here by using partial Fourier dictionary