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].

name of conference

  • 2015 53rd Annual Allerton Conference on Communication, Control and Computing (Allerton)

published proceedings

  • 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)

author list (cited authors)

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

citation count

  • 1

complete list of authors

  • Janakiraman, Nagaraj Thenkarai||Emmadi, Santosh||Narayanan, Krishna||Ramchandran, Kannan

publication date

  • September 2015