Algorithms and pipeline architectures for 2-D FFT and FFT-like transforms

Omar Nibouche, Said Boussakta, Michael Darnell, Mohammed Benaissa

    Research output: Contribution to journalArticle

    8 Citations (Scopus)

    Abstract

    In this paper, efficient pipeline architectures that implement the 2-D FFT are presented. Based on the Vector Radix approach, the new structures alleviate the use of memory banks and the transposition of data of the row–column technique. Architectures for Vector Radix 2 × 2 algorithm and for a modified Vector Radix 4 × 4, called Vector Radix 2^2 × 2^2 algorithm, which has been devised and constructed from Vector Radix 2×2, are presented. These architectures can also be built from their 1-D counterparts. Thus, generic and parameterised architectures can be described using a hardware description language to implement both 1-D and 2-D FFTs. A comparison with row–column FFT architectures has shown that the proposed architectures can achieve a 50% reduction in complex multipliers usage. Furthermore, the suggested architectures are suitable to implement FFT like transforms if the right type of arithmetic components is selected. In particular, they can be modified in order to implement Number Theoretic Transforms. In this case, a saving of up to 66% of registers and 50% of adders requirements of similar work in the literature can be achieved.
    LanguageEnglish
    Pages1072-1086
    JournalDigital Signal Processing
    Volume20
    Issue number4
    DOIs
    Publication statusPublished - Jul 2010

    Fingerprint

    Fast Fourier transforms
    Pipelines
    Computer hardware description languages
    Adders
    Mathematical transformations
    Data storage equipment

    Cite this

    Nibouche, Omar ; Boussakta, Said ; Darnell, Michael ; Benaissa, Mohammed. / Algorithms and pipeline architectures for 2-D FFT and FFT-like transforms. 2010 ; Vol. 20, No. 4. pp. 1072-1086.
    @article{dd62619a74d54b4fb0738301b44befa2,
    title = "Algorithms and pipeline architectures for 2-D FFT and FFT-like transforms",
    abstract = "In this paper, efficient pipeline architectures that implement the 2-D FFT are presented. Based on the Vector Radix approach, the new structures alleviate the use of memory banks and the transposition of data of the row–column technique. Architectures for Vector Radix 2 × 2 algorithm and for a modified Vector Radix 4 × 4, called Vector Radix 2^2 × 2^2 algorithm, which has been devised and constructed from Vector Radix 2×2, are presented. These architectures can also be built from their 1-D counterparts. Thus, generic and parameterised architectures can be described using a hardware description language to implement both 1-D and 2-D FFTs. A comparison with row–column FFT architectures has shown that the proposed architectures can achieve a 50{\%} reduction in complex multipliers usage. Furthermore, the suggested architectures are suitable to implement FFT like transforms if the right type of arithmetic components is selected. In particular, they can be modified in order to implement Number Theoretic Transforms. In this case, a saving of up to 66{\%} of registers and 50{\%} of adders requirements of similar work in the literature can be achieved.",
    author = "Omar Nibouche and Said Boussakta and Michael Darnell and Mohammed Benaissa",
    year = "2010",
    month = "7",
    doi = "10.1016/j.dsp.2009.10.028",
    language = "English",
    volume = "20",
    pages = "1072--1086",
    number = "4",

    }

    Algorithms and pipeline architectures for 2-D FFT and FFT-like transforms. / Nibouche, Omar; Boussakta, Said; Darnell, Michael; Benaissa, Mohammed.

    Vol. 20, No. 4, 07.2010, p. 1072-1086.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Algorithms and pipeline architectures for 2-D FFT and FFT-like transforms

    AU - Nibouche, Omar

    AU - Boussakta, Said

    AU - Darnell, Michael

    AU - Benaissa, Mohammed

    PY - 2010/7

    Y1 - 2010/7

    N2 - In this paper, efficient pipeline architectures that implement the 2-D FFT are presented. Based on the Vector Radix approach, the new structures alleviate the use of memory banks and the transposition of data of the row–column technique. Architectures for Vector Radix 2 × 2 algorithm and for a modified Vector Radix 4 × 4, called Vector Radix 2^2 × 2^2 algorithm, which has been devised and constructed from Vector Radix 2×2, are presented. These architectures can also be built from their 1-D counterparts. Thus, generic and parameterised architectures can be described using a hardware description language to implement both 1-D and 2-D FFTs. A comparison with row–column FFT architectures has shown that the proposed architectures can achieve a 50% reduction in complex multipliers usage. Furthermore, the suggested architectures are suitable to implement FFT like transforms if the right type of arithmetic components is selected. In particular, they can be modified in order to implement Number Theoretic Transforms. In this case, a saving of up to 66% of registers and 50% of adders requirements of similar work in the literature can be achieved.

    AB - In this paper, efficient pipeline architectures that implement the 2-D FFT are presented. Based on the Vector Radix approach, the new structures alleviate the use of memory banks and the transposition of data of the row–column technique. Architectures for Vector Radix 2 × 2 algorithm and for a modified Vector Radix 4 × 4, called Vector Radix 2^2 × 2^2 algorithm, which has been devised and constructed from Vector Radix 2×2, are presented. These architectures can also be built from their 1-D counterparts. Thus, generic and parameterised architectures can be described using a hardware description language to implement both 1-D and 2-D FFTs. A comparison with row–column FFT architectures has shown that the proposed architectures can achieve a 50% reduction in complex multipliers usage. Furthermore, the suggested architectures are suitable to implement FFT like transforms if the right type of arithmetic components is selected. In particular, they can be modified in order to implement Number Theoretic Transforms. In this case, a saving of up to 66% of registers and 50% of adders requirements of similar work in the literature can be achieved.

    U2 - 10.1016/j.dsp.2009.10.028

    DO - 10.1016/j.dsp.2009.10.028

    M3 - Article

    VL - 20

    SP - 1072

    EP - 1086

    IS - 4

    ER -