To access the full text documents, please follow this link: http://hdl.handle.net/2117/12876

Radix-R FFT and IFFT factorizations for parallel implementation
Marti Puig, Pere; Reig Bolano, Ramon; Parisi Baradad, Vicenç
Universitat Politècnica de Catalunya. Departament d'Enginyeria Electrònica; Universitat Politècnica de Catalunya. AHA - Arquitectures Hardware Avançades
Two radix-R regular interconnection pattern families of factorizations for both the FFT and the IFFT -also known as parallel or Pease factorizations- are reformulated and presented. Number R is any power of 2 and N, the size of the transform, any power of R. The first radix-2 parallel FFT algorithm -one of the two known radix-2 topologies- was proposed by Pease. Other authors extended the Pease parallel algorithm to different radix and other particular solutions were also reported. The presented families of factorizations for both the FFT and the IFFT are derived from the well-known Cooley-Tukey factorizations, first, for the radix-2 case, and then, for the general radix-R case. Here we present the complete set of parallel algorithms, that is, algorithms with equal interconnection pattern stage-to-stage topology. In this paper the parallel factorizations are derived by using a unified notation based on the use of the Kronecker product and the even-odd permutation matrix to form the rest of permutation matrices. The radix-R generalization is done in a very simple way. It is shown that, both FFT and IFFT share interconnection pattern solutions. This view tries to contribute to the knowledge of fast parallel algorithms for the case of FFT and IFFT but it can be easily applied to other discrete transforms.
Peer Reviewed
Àrees temàtiques de la UPC::Enginyeria electrònica i telecomunicacions::Processament del senyal
Àrees temàtiques de la UPC::Informàtica
Fourier transformations--Data processing
Parallel algorithms
Fourier, Transformacions de
Algorismes paral·lels
Tractament del senyal -- Matemàtica
Tractament del senyal -- Tècniques digitals
Processament en paral·lel (Ordinadors)
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Reig Bolano, Ramon; Marti Puig, Pere; Lombarte, A.; Soria Pérez, José Antonio; Parisi Baradad, Vicenç
Reig Bolano, Ramon; Marti Puig, Pere; Solé-Casals, Jordi; Zaiats, Vladimir; Parisi Baradad, Vicenç
Reig Bolano, Ramon; Marti Puig, Pere; Gallego, Esteve; Masferrer, Gerard; Lombarte, A.; Ferrer Arnau, Luis Jorge; Parisi Baradad, Vicenç
Ferrer Arnau, Luis Jorge; Parisi Baradad, Vicenç; Reig Bolano, Ramon; Marti Puig, Pere; Manjabacas, A.
 

Coordination

 

Supporters