Fast Decoding and Hardware Design for Binary-Input Compressive Sensing
Authors:
- 16 October 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Emerging and Selected Topics in Circuits and Systems
- Vol. 2 (3) , 591-603
Abstract
Binary-input compressive sensing (BiCS) has recently been applied to wireless communications as a modulated coding scheme for seamless rate adaptation. Different from conventional channel codes which generate binary symbols with logical-OR (XOR) operations, BiCS generates multilevel symbols through weighted sum operation. Although BiCS can be decoded by message passing, it needs to compute the convolution of probability functions in each iteration. The high decoding complexity has prevented the technique from being applied to practical use. In this paper, we propose a fast BiCS decoding algorithm and its corresponding partial-parallel hardware design. In this algorithm, we first build lookup tables to solve the computationally intensive problem of convolution. Through these tables, we successfully convert the convolution of probabilities into the polynomial of some exponential terms. This key step allows us to use log-likelihood ratio as message in message passing decoding and a fast algorithm is developed by approximate computing. We further design a partial-parallel hardware decoder. To avoid memory collision, we propose a multilevel cyclic-shift approach to generate the CS measurement matrix. We design horizontal unit processors with the proposed tables for iterative computing. Our analyses show that the proposed fast algorithm can reduce multiplications by nearly 90%. The decoding speed of our field-programmable gate array design reaches the range of communication rate in modern wireless networks.Keywords
This publication has 55 references indexed in Scilit:
- Message-passing algorithms for compressed sensingProceedings of the National Academy of Sciences, 2009
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- Efficient and Robust Compressed Sensing Using Optimized Expander GraphsIEEE Transactions on Information Theory, 2009
- Subspace Pursuit for Compressive Sensing Signal ReconstructionIEEE Transactions on Information Theory, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Analysis on Rate-Distortion Performance of Compressive Sensing for Binary Sparse Source2009
- Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed SensingSIAM Journal on Imaging Sciences, 2008
- Exact Reconstruction of Sparse Signals via Nonconvex MinimizationIEEE Signal Processing Letters, 2007
- Efficient Compressive Sensing with Deterministic Guarantees Using Expander Graphs2007
- Sudocodes ߝ Fast Measurement and Reconstruction of Sparse Signals2006