Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Fast Fourier Transforms » Algorithms for Data with Restrictions

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to high-performance computing. First popularized by two American scientists in 1965, the […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Algorithms for Data with Restrictions

Module by: C. Sidney Burrus. E-mail the author

Algorithms for Real Data

Many applications involve processing real data. It is inefficient to simply use a complex FFT on real data because arithmetic would be performed on the zero imaginary parts of the input, and, because of symmetries, output values would be calculated that are redundant. There are several approaches to developing special algorithms or to modifying complex algorithms for real data.

There are two methods which use a complex FFT in a special way to increase efficiency [4], [14]. The first method uses a length-N complex FFT to compute two length-N real FFTs by putting the two real data sequences into the real and the imaginary parts of the input to a complex FFT. Because transforms of real data have even real parts and odd imaginary parts, it is possible to separate the transforms of the two inputs with 2N-4 extra additions. This method requires, however, that two inputs be available at the same time.

The second method [14] uses the fact that the last stage of a decimation-in-time radix-2 FFT combines two independent transforms of length N/2 to compute a length-N transform. If the data are real, the two half length transforms are calculated by the method described above and the last stage is carried out to calculate the total length-N FFT of the real data. It should be noted that the half-length FFT does not have to be calculated by a radix-2 FFT. In fact, it should be calculated by the most efficient complex-data algorithm possible, such as the SRFFT or the PFA. The separation of the two half-length transforms and the computation of the last stage requires N-6N-6 real multiplications and (5/2)N-6(5/2)N-6 real additions [14].

It is possible to derive more efficient real-data algorithms directly rather than using a complex FFT. The basic idea is from Bergland [1], [2] and Sande [12] which, at each stage, uses the symmetries of a constant radix Cooley-Tukey FFT to minimize arithmetic and storage. In the usual derivation [10] of the radix-2 FFT, the length-N transform is written as the combination of the length-N/2 DFT of the even indexed data and the length-N/2 DFT of the odd indexed data. If the input to each half-length DFT is real, the output will have Hermitian symmetry. Hence the output of each stage can be arranged so that the results of that stage stores the complex DFT with the real part located where half of the DFT would have gone, and the imaginary part located where the conjugate would have gone. This removes most of the redundant calculations and storage but slightly complicates the addressing. The resulting butterfly structure for this algorithm [14] resembles that for the fast Hartley transform [13]. The complete algorithm has one half the number of multiplications and N-2 fewer than half the additions of the basic complex FFT. Applying this approach to the split-radix FFT gives a particularly interesting algorithm [5], [14], [6].

Special versions of both the PFA and WFTA can also be developed for real data. Because the operations in the stages of the PFA can be commuted, it is possible to move the combination of the transform of the real part of the input and imaginary part to the last stage. Because the imaginary part of the input is zero, half of the algorithm is simply omitted. This results in the number of multiplications required for the real transform being exactly half of that required for complex data and the number of additions being about N less than half that required for the complex case because adding a pure real number to a pure imaginary number does not require an actual addition. Unfortunately, the indexing and data transfer becomes somewhat more complicated [9], [14]. A similar approach can be taken with the WFTA [9], [14], [11].

Special Algorithms for input Data that is mostly Zero, for Calculating only a few Outputs, or where the Sampling is not Uniform

In some cases, most of the data to be transformed are zero. It is clearly wasteful to do arithmetic on that zero data. Another special case is when only a few DFT values are needed. It is likewise wasteful to calculate outputs that are not needed. We use a process called “pruning" to remove the unneeded operations.

In other cases, the data are non-uniform sampling of a continuous time signal [3].

Algorithms for Approximate DFTs

There are applications where approximations to the DFT are all that is needed.[7], [8]

References

  1. Bergland, G. D. (1968, October). A Fast Fourier Transform Algorithm for Real-Valued Series. Comm. ACM, 11(10), 703-710.
  2. Bergland, G. D. (1969, June). A Radix-8 Fast Fourier Transform Subroutine for Real-Valued Series. IEEE Trans. on Audio an Electrocoustics, 17, 138-144.
  3. Bagchi, S. and Mitra, S. (1999). The Nonuniform Discrete Fourier Transform and Its Applications in Signal Processing. Boston: Kluwer Academic.
  4. Brigham, E. Oran. (1988). The Fast Fourier Transform and Its Applications. [Expansion of the 1974 book]. Englewood Cliffs, NJ: Prentice-Hall.
  5. Duhamel, P. (1986, April). Implementation of `Split-Radix' FFT Algorithms for Complex, Real, and Real-Symmetric Data. [A shorter version appeared in the ICASSP-85 Proceedings, p. 20.6, March 1985]. IEEE Trans. on ASSP, 34, 285–295.
  6. Duhamel, P. and Vetterli, M. (1986, April). Cyclic Convolution of Real Sequences: Hartley versus Fourier and New Schemes. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP-86), 6.5.
  7. Guo, Haitao and Burrus, C. Sidney. (1996, August 6–9). Approximate FFT via the Discrete Wavelet Transform. In Proceedings of SPIE Conference 2825. Denver
  8. Guo, Haitao and Burrus, C. Sidney. (1997, April 21–24). Wavelet Transform Based Fast Approximate Fourier Transform. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 3, p. III:1973–1976). IEEE ICASSP-97, Munich
  9. Heideman, M. T. and Johnson, H. W. and Burrus, C. S. (1984, March). Prime Factor FFT Algorithms for Real–Valued Series. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (p. 28A.7.1–4). San Diego, CA
  10. Oppenheim, A. V. and Schafer, R. W. (1999). Discrete-Time Signal Processing. (Second). [Earlier editions in 1975 and 1989]. Englewood Cliffs, NJ: Prentice-Hall.
  11. Parsons, T. W. (1979, August). A Winograd-Fourier Transform Algorithm for Real-Valued Data. IEEE Trans. on ASSP, 27, 398-402.
  12. Sande, G. (1970, March). Fast Fourier Transform - A Gobally Complex Algorithm with Locally Real Implementations. Proc. 4th Annual Princeton Conference on Information Sciences and Systems, 136-142.
  13. Sorensen, H. V. and Jones, D. L. and Burrus, C. S. and Heideman, M. T. (1985, October). On Computing the Discrete Hartley Transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 33(5), 1231–1238.
  14. Sorensen, H. V. and Jones, D. L. and Heideman, M. T. and Burrus, C. S. (1987, June). Real Valued Fast Fourier Transform Algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(6), 849–863.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks