Exploring Connections between Sparse Fourier Transform Computation and Decoding of Product Codes Conference Paper uri icon


  • © 2015 IEEE. We show that the recently proposed Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm for computing the Discrete Fourier Transform (DFT) [1] of signals with a sparse DFT is equivalent to iterative hard decision decoding of product codes. This connection is used to derive the thresholds for sparse recovery based on a recent analysis by Justensen [2] for computing thresholds for product codes. We first extend Justesen's analysis to d-dimensional product codes and compute thresholds for the FFAST algorithm based on this. Additionally, this connection also allows us to analyze the performance of the FFAST algorithm under a burst sparsity model in addition to the uniformly random sparsity model which was assumed in prior work [1].

author list (cited authors)

  • Janakiraman, N. T., Emmadi, S., Narayanan, K., & Ramchandran, K.

citation count

  • 0

publication date

  • September 2015