Area-efficient and scalable solution to real-data fast fourier transform via regularised fast Hartley transform

Area-efficient and scalable solution to real-data fast fourier transform via regularised fast Hartley transform

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Signal Processing — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

A highly parallel hardware solution to the regularised fast Hartley transform (FHT), an algorithm developed only recently for the efficient computation of the discrete Hartley transform (DHT) and hence of the real-data fast Fourier transform (FFT), is discussed. A drawback of conventional FHT algorithms lies in the loss of regularity arising from the need for two types of ‘butterfly’ for catering for fixed-radix formulations. A generic radix-4 double butterfly was therefore developed for the regularised FHT which overcame the problem in an elegant fashion. An architecture for the parallel computation of the generic double butterfly and the resulting regularised FHT is now discussed in some detail; this exploits a single high-performance processing element (PE) which yields an attractive solution, particularly when implemented with field-programmable gate array (FPGA) technology, which is both area-efficient and scalable in terms of transform length. High performance is achieved by having the PE able to process the input/output data sets to the double butterfly in parallel, this in turn implying the need to be able to access simultaneously, and without conflict, both multiple data and multiple twiddle factors, or coefficients, from their respective memories. The resulting area-efficient and scalable single-PE architecture is shown to yield a generic solution to the real-data FFT which is capable of achieving the throughput of the most advanced commercially available solutions for just a fraction of the silicon area and, for new applications, at negligible re-design cost.


    1. 1)
    2. 2)
      • R.N. Bracewell . (1986) The hartley transform.
    3. 3)
      • R.V.L. Hartley . A more symmetrical fourier analysis applied to transmission problems. Proc. IRE , 144 - 150
    4. 4)
      • G. Birkhoff , S. MacLane . (1977) A survey of modern algebra.
    5. 5)
      • P. Duhamel , M. Vetterli . Improved fourier and hartley transform algorithms: application to cyclic convolution of real data. IEEE Trans. ASSP , 6 , 812 - 825
    6. 6)
      • R.E. Blahut . (1985) Fast algorithms for digital signal processing.
    7. 7)
      • R.N. Bracewell . (1978) The fourier transform and its applications.
    8. 8)
      • E.O. Brigham . (1988) The fast fourier transform and its applications.
    9. 9)
      • J.W. Cooley , J.W. Tukey . An algorithm for the machine calculation of complex fourier series. Math. Comput. , 4 , 297 - 301
    10. 10)
      • D.F. Elliott , K. Ramamohan Rao . (1982) Fast transforms: algorithms, analyses, applications.
    11. 11)
      • H.J. Nussbaumer . (1981) Fast fourier transform and convolution algorithms.
    12. 12)
      • A.V. Oppenheim , R.W. Schafer . (1989) Discrete-time signal processing.
    13. 13)
      • L.R. Rabiner , B. Gold . (1975) Theory and application of digital signal processing.
    14. 14)
      • J.H. McClellan , C.M. Rader . (1979) Number theory in digital signal processing.
    15. 15)
      • I. Niven , H.S. Zuckerman . (1966) An introduction to the theory of numbers.
    16. 16)
      • S.G. Akl . (1989) The design and analysis of parallel algorithms.
    17. 17)
      • A.W. Biermann . (1995) Great ideas in computer science.
    18. 18)
      • D. Harel . (1997) Algorithmics: the spirit of computing.
    19. 19)
      • L. Kronsjo . (1985) Computational complexity of sequential and parallel algorithms.
    20. 20)
      • R. Tessier , W. Burleson . Reconfigurable computing for digital signal processing: a survey. J. VLSI Signal Process. , 7 , 7 - 27
    21. 21)
      • J.E. Volder . The CORDIC trigonometric computing technique. IRE Trans. Electron. Comput. , 3 , 330 - 334
    22. 22)
      • RF Engines Ltd: IP Cores – Xilinx FFT Library. Product information sheet available at web site:
    23. 23)
      • Roke Manor Research Ltd: ‘Ultra high speed pipeline FFT core’. Product information sheet available at web site:
    24. 24)
    25. 25)
      • Analog Devices: A low distortion, high accuracy signal generator using the ADSP-218x or ADSP-219x families. 2002, available at web site:
    26. 26)
      • Xilinx: Company and product information available at web site:

Related content

This is a required field
Please enter a valid email address