Radix-R WHT-FFT with Identical Stage-to-Stage Interconnection Pattern

Qianjian XING  Feng YU  Xiaobo YIN  Bei ZHAO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.5   pp.1125-1129
Publication Date: 2014/05/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1125
Type of Manuscript: LETTER
Category: Digital Signal Processing
Kronecker product,  fast Walsh-Fourier transform (FWFT),  butterfly structure,  sparse matrix factorization,  

Full Text: PDF>>
Buy this Article

In this letter, we present a radix-R regular interconnection pattern family of factorizations for the WHT-FFT with identical stage-to-stage interconnection pattern in a unified form, where R is any power of 2. This family of algorithms has identical sparse matrix factorization in each stage and can be implemented in a merged butterfly structure, which conduce to regular and efficient memory managing scalable to high radices. And in each stage, the butterflies with same twiddle factor set are aggregated together, which can reduce the twiddle factor evaluations or accesses to the lookup table. The kinds of factorization can also be extended to FFT, WHT and SCHT with identical stage-to-stage interconnection pattern.