Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

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
£12.50
(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
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
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.

References

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

Related content

content/journals/10.1049/iet-spr_20060329
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address