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

abstract

• 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)

authors

• Narayanan, Krishna

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

• 2

complete list of authors

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

publication date

• January 2015

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• n2474-0195ISSN  Journal

Digital Object Identifier (DOI)

• 10.1109/allerton.2015.7447167

International Standard Book Number (ISBN) 13

• 9781509018239

start page

• 1366

end page

• 1373

URL

• http://dx.doi.org/10.1109/allerton.2015.7447167