Pipeline Architectures for Radix-2 New Mersenne Number Transform

Omar Nibouche, Said Boussakta, Michael Darnell

    Research output: Contribution to journalArticle

    20 Citations (Scopus)

    Abstract

    Number theoretic transforms which operate in rings or fields of integers and use modular arithmetic operations can perform operations of convolution and correlation very efficiently and without round-off errors; thus, they are well matched to the implementation of digital filters. One such transform is the new Mersenne number transform, which relaxes the rigid relationship between the length of the transform and the wordlength in Fermat and Mersenne number transforms where the kernel is usually equal to a power of two. In this paper, three novel pipeline architectures that implement this transform are presented. The proposed architectures are scalable, parameterized, and can be easily pipelined; they are thus ideally suited to very high speed integrated circuit hardware-description-language (VHDL) descriptions. These architectures process data sequentially and have either one or two inputs and two or four outputs. The different input and output formats have resulted in the proposed architectures having different performances in terms of processing time and area requirements. Furthermore, they give the designer more choices in meeting the requirements of the application being implemented. A field-programmable gate array (FPGA) implementation of the proposed architectures has demonstrated that a throughput rate of up to 6.09 Gbit/s can be achieved for a 1024-sample transform, with samples coded to 31 bits.
    LanguageEnglish
    Pages1668-1680
    JournalIEEE Transactions on Circuits and Systems I: Regular Papers
    Volume56
    Issue number8
    DOIs
    Publication statusPublished - 14 Aug 2009

    Fingerprint

    Computer hardware description languages
    Pipelines
    Mathematical transformations
    Digital filters
    Convolution
    Integrated circuits
    Field programmable gate arrays (FPGA)
    Throughput
    Processing

    Keywords

    • New Mersenne number transform (NMNT)
    • number theoretic transform (NTT)
    • pipeline architectures.

    Cite this

    @article{e10c217a21fb40b090b30ada54bb25c5,
    title = "Pipeline Architectures for Radix-2 New Mersenne Number Transform",
    abstract = "Number theoretic transforms which operate in rings or fields of integers and use modular arithmetic operations can perform operations of convolution and correlation very efficiently and without round-off errors; thus, they are well matched to the implementation of digital filters. One such transform is the new Mersenne number transform, which relaxes the rigid relationship between the length of the transform and the wordlength in Fermat and Mersenne number transforms where the kernel is usually equal to a power of two. In this paper, three novel pipeline architectures that implement this transform are presented. The proposed architectures are scalable, parameterized, and can be easily pipelined; they are thus ideally suited to very high speed integrated circuit hardware-description-language (VHDL) descriptions. These architectures process data sequentially and have either one or two inputs and two or four outputs. The different input and output formats have resulted in the proposed architectures having different performances in terms of processing time and area requirements. Furthermore, they give the designer more choices in meeting the requirements of the application being implemented. A field-programmable gate array (FPGA) implementation of the proposed architectures has demonstrated that a throughput rate of up to 6.09 Gbit/s can be achieved for a 1024-sample transform, with samples coded to 31 bits.",
    keywords = "New Mersenne number transform (NMNT), number theoretic transform (NTT), pipeline architectures.",
    author = "Omar Nibouche and Said Boussakta and Michael Darnell",
    note = "Reference text: [1] C. M. Rader, “Discrete convolutions via Mersenne transforms,” IEEE Trans. Comput., vol. C-21, no. 12, pp. 1269–1273, Dec. 1972. [2] R. C. Agarwal and C. S. Burrus, “Number theoretic transforms to implement fast digital convolution,” Proc. IEEE, vol. 63, no. 4, pp. 550–560, Apr. 1975. [3] R. C. Agarwal and C. S. Burrus, “Fast convolution using Fermat number transform with application to digital filtering,” IEEE Trans. Acoust., Speech, Signal Process., vol. ASSP-22, no. 2, pp. 87–97, Apr. 1974. [4] H. J. Nussbaumer, “Relative evaluation of various number theoretic transforms for digital filtering applications,” IEEE Trans. Acoust., Speech, Signal Process., vol. Vol. ASSP-26, no. 1, pp. 88–93, Feb. 1978. [5] R. Conway, “Modified overlap technique using Fermat and Mersenne transforms,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 53, no. 8, pp. 632–636, Aug. 2006. [6] V. M. Chernov, “Fast algorithm for error-free convolution computation using Mersenne–Lucas codes,” Chaos, Solitons Fractals, vol. 29, no. 2, pp. 372–380, Jul. 2006. [7] S. Gudvangen, “Practical applications of number theoretic transforms,” in Proc. NORSIG, Asker, Norway, Sep. 10–11, 1999, pp. 102–107. [8] R. Kumar, “A fast algorithm for solving a Toeplitz system of equations,” IEEE Trans. Acoust., Speech, Signal Process., vol. ASSP-33, no. 1, pp. 254–267, Feb. 1985. [9] J. J. Hsue and A. E. Yagle, “Fast algorithms for solving Toeplitz systems of equations using number theoretic transforms,” IEEE Trans. Signal Process., vol. 44, no. 1, pp. 89–101, Jun. 1995. [10] T. Lundy and J. V. Buskirk, “A new matrix approach to real FFTs and convolutions of length",
    year = "2009",
    month = "8",
    day = "14",
    doi = "10.1109/TCSI.2008.2008266",
    language = "English",
    volume = "56",
    pages = "1668--1680",
    journal = "IEEE Transactions on Circuits and Systems I: Regular Papers",
    issn = "1549-8328",
    number = "8",

    }

    Pipeline Architectures for Radix-2 New Mersenne Number Transform. / Nibouche, Omar; Boussakta, Said; Darnell, Michael.

    In: IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 56, No. 8, 14.08.2009, p. 1668-1680.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Pipeline Architectures for Radix-2 New Mersenne Number Transform

    AU - Nibouche, Omar

    AU - Boussakta, Said

    AU - Darnell, Michael

    N1 - Reference text: [1] C. M. Rader, “Discrete convolutions via Mersenne transforms,” IEEE Trans. Comput., vol. C-21, no. 12, pp. 1269–1273, Dec. 1972. [2] R. C. Agarwal and C. S. Burrus, “Number theoretic transforms to implement fast digital convolution,” Proc. IEEE, vol. 63, no. 4, pp. 550–560, Apr. 1975. [3] R. C. Agarwal and C. S. Burrus, “Fast convolution using Fermat number transform with application to digital filtering,” IEEE Trans. Acoust., Speech, Signal Process., vol. ASSP-22, no. 2, pp. 87–97, Apr. 1974. [4] H. J. Nussbaumer, “Relative evaluation of various number theoretic transforms for digital filtering applications,” IEEE Trans. Acoust., Speech, Signal Process., vol. Vol. ASSP-26, no. 1, pp. 88–93, Feb. 1978. [5] R. Conway, “Modified overlap technique using Fermat and Mersenne transforms,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 53, no. 8, pp. 632–636, Aug. 2006. [6] V. M. Chernov, “Fast algorithm for error-free convolution computation using Mersenne–Lucas codes,” Chaos, Solitons Fractals, vol. 29, no. 2, pp. 372–380, Jul. 2006. [7] S. Gudvangen, “Practical applications of number theoretic transforms,” in Proc. NORSIG, Asker, Norway, Sep. 10–11, 1999, pp. 102–107. [8] R. Kumar, “A fast algorithm for solving a Toeplitz system of equations,” IEEE Trans. Acoust., Speech, Signal Process., vol. ASSP-33, no. 1, pp. 254–267, Feb. 1985. [9] J. J. Hsue and A. E. Yagle, “Fast algorithms for solving Toeplitz systems of equations using number theoretic transforms,” IEEE Trans. Signal Process., vol. 44, no. 1, pp. 89–101, Jun. 1995. [10] T. Lundy and J. V. Buskirk, “A new matrix approach to real FFTs and convolutions of length

    PY - 2009/8/14

    Y1 - 2009/8/14

    N2 - Number theoretic transforms which operate in rings or fields of integers and use modular arithmetic operations can perform operations of convolution and correlation very efficiently and without round-off errors; thus, they are well matched to the implementation of digital filters. One such transform is the new Mersenne number transform, which relaxes the rigid relationship between the length of the transform and the wordlength in Fermat and Mersenne number transforms where the kernel is usually equal to a power of two. In this paper, three novel pipeline architectures that implement this transform are presented. The proposed architectures are scalable, parameterized, and can be easily pipelined; they are thus ideally suited to very high speed integrated circuit hardware-description-language (VHDL) descriptions. These architectures process data sequentially and have either one or two inputs and two or four outputs. The different input and output formats have resulted in the proposed architectures having different performances in terms of processing time and area requirements. Furthermore, they give the designer more choices in meeting the requirements of the application being implemented. A field-programmable gate array (FPGA) implementation of the proposed architectures has demonstrated that a throughput rate of up to 6.09 Gbit/s can be achieved for a 1024-sample transform, with samples coded to 31 bits.

    AB - Number theoretic transforms which operate in rings or fields of integers and use modular arithmetic operations can perform operations of convolution and correlation very efficiently and without round-off errors; thus, they are well matched to the implementation of digital filters. One such transform is the new Mersenne number transform, which relaxes the rigid relationship between the length of the transform and the wordlength in Fermat and Mersenne number transforms where the kernel is usually equal to a power of two. In this paper, three novel pipeline architectures that implement this transform are presented. The proposed architectures are scalable, parameterized, and can be easily pipelined; they are thus ideally suited to very high speed integrated circuit hardware-description-language (VHDL) descriptions. These architectures process data sequentially and have either one or two inputs and two or four outputs. The different input and output formats have resulted in the proposed architectures having different performances in terms of processing time and area requirements. Furthermore, they give the designer more choices in meeting the requirements of the application being implemented. A field-programmable gate array (FPGA) implementation of the proposed architectures has demonstrated that a throughput rate of up to 6.09 Gbit/s can be achieved for a 1024-sample transform, with samples coded to 31 bits.

    KW - New Mersenne number transform (NMNT)

    KW - number theoretic transform (NTT)

    KW - pipeline architectures.

    U2 - 10.1109/TCSI.2008.2008266

    DO - 10.1109/TCSI.2008.2008266

    M3 - Article

    VL - 56

    SP - 1668

    EP - 1680

    JO - IEEE Transactions on Circuits and Systems I: Regular Papers

    T2 - IEEE Transactions on Circuits and Systems I: Regular Papers

    JF - IEEE Transactions on Circuits and Systems I: Regular Papers

    SN - 1549-8328

    IS - 8

    ER -