Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Fast Fourier Transforms » Factoring the Signal Processing Operators

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.
 

Factoring the Signal Processing Operators

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

A third approach to removing redundancy in an algorithm is to express the algorithm as an operator and then factor that operator into sparse factors. This approach is used by Tolimieri [4], [5], Egner [3], Selesnick, Elliott [2] and others. It is presented in a more general form in DFT and FFT: An Algebraic View The operators may be in the form of a matrix or a tensor operator.

The FFT from Factoring the DFT Operator

The definition of the DFT in Multidimensional Index Mapping: Equation 1 can written as a matrix-vector operation by C=WXC=WX which, for N=8N=8 is

C ( 0 ) C ( 1 ) C ( 2 ) C ( 3 ) C ( 4 ) C ( 5 ) C ( 6 ) C ( 7 ) = W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 1 W 2 W 3 W 4 W 5 W 6 W 7 W 0 W 2 W 4 W 6 W 8 W 10 W 12 W 14 W 0 W 3 W 6 W 9 W 12 W 15 W 18 W 21 W 0 W 4 W 8 W 12 W 16 W 20 W 24 W 28 W 0 W 5 W 10 W 15 W 20 W 25 W 30 W 35 W 0 W 6 W 12 W 18 W 24 W 30 W 36 W 42 W 0 W 7 W 14 W 21 W 28 W 35 W 42 W 49 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) C ( 0 ) C ( 1 ) C ( 2 ) C ( 3 ) C ( 4 ) C ( 5 ) C ( 6 ) C ( 7 ) = W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 1 W 2 W 3 W 4 W 5 W 6 W 7 W 0 W 2 W 4 W 6 W 8 W 10 W 12 W 14 W 0 W 3 W 6 W 9 W 12 W 15 W 18 W 21 W 0 W 4 W 8 W 12 W 16 W 20 W 24 W 28 W 0 W 5 W 10 W 15 W 20 W 25 W 30 W 35 W 0 W 6 W 12 W 18 W 24 W 30 W 36 W 42 W 0 W 7 W 14 W 21 W 28 W 35 W 42 W 49 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )
(1)

which clearly requires N2=64N2=64 complex multiplications and N(N-1)N(N-1) additions. A factorization of the DFT operator, WW, gives W=F1F2F3W=F1F2F3 and C=F1F2F3XC=F1F2F3X or, expanded,

C ( 0 ) C ( 4 ) C ( 2 ) C ( 6 ) C ( 1 ) C ( 5 ) C ( 3 ) C ( 7 ) = 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 W 0 0 - W 2 0 0 0 0 0 0 W 0 0 - W 2 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 W 0 0 - W 0 0 0 0 0 0 0 W 2 0 - W 2 C ( 0 ) C ( 4 ) C ( 2 ) C ( 6 ) C ( 1 ) C ( 5 ) C ( 3 ) C ( 7 ) = 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 W 0 0 - W 2 0 0 0 0 0 0 W 0 0 - W 2 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 W 0 0 - W 0 0 0 0 0 0 0 W 2 0 - W 2
(2)
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 W 0 0 0 0 - W 0 0 0 0 0 W 1 0 0 0 - W 1 0 0 0 0 W 2 0 0 0 - W 2 0 0 0 0 W 3 0 0 0 - W 3 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 W 0 0 0 0 - W 0 0 0 0 0 W 1 0 0 0 - W 1 0 0 0 0 W 2 0 0 0 - W 2 0 0 0 0 W 3 0 0 0 - W 3 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )
(3)

where the FiFi matrices are sparse. Note that each has 16 (or 2N2N) non-zero terms and F2F2 and F3F3 have 8 (or NN) non-unity terms. If N=2MN=2M, then the number of factors is log(N)=Mlog(N)=M. In another form with the twiddle factors separated so as to count the complex multiplications we have

C ( 0 ) C ( 4 ) C ( 2 ) C ( 6 ) C ( 1 ) C ( 5 ) C ( 3 ) C ( 7 ) = 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 C ( 0 ) C ( 4 ) C ( 2 ) C ( 6 ) C ( 1 ) C ( 5 ) C ( 3 ) C ( 7 ) = 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 - 1
(4)
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 W 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 W 2 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 - 1 0 0 0 0 0 0 1 0 - 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 - 1 0 0 0 0 0 0 1 0 - 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 W 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 W 2 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 - 1 0 0 0 0 0 0 1 0 - 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 - 1 0 0 0 0 0 0 1 0 - 1
(5)
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 W 1 0 0 0 0 0 0 0 0 W 2 0 0 0 0 0 0 0 0 W 3 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 - 1 0 0 0 0 1 0 0 0 - 1 0 0 0 0 1 0 0 0 - 1 0 0 0 0 1 0 0 0 - 1 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 W 1 0 0 0 0 0 0 0 0 W 2 0 0 0 0 0 0 0 0 W 3 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 - 1 0 0 0 0 1 0 0 0 - 1 0 0 0 0 1 0 0 0 - 1 0 0 0 0 1 0 0 0 - 1 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )
(6)

which is in the form C=A1M1A2M2A3XC=A1M1A2M2A3X described by the index map. A1A1, A2A2, and A3A3 each represents 8 additions, or, in general, NN additions. M1M1 and M2M2 each represent 4 (or N/2N/2) multiplications.

This is a very interesting result showing that implementing the DFT using the factored form requires considerably less arithmetic than the single factor definition. Indeed, the form of the formula that Cooley and Tukey derived showing that the amount of arithmetic required by the FFT is on the order of Nlog(N)Nlog(N) can be seen from the factored operator formulation.

Much of the theory of the FFT can be developed using operator factoring and it has some advantages for implementation of parallel and vector computer architectures. The eigenspace approach is somewhat of the same type [1].

Algebraic Theory of Signal Processing Algorithms

A very general structure for all kinds of algorithms can be generalized from the approach of operators and operator decomposition. This is developed as “Algebraic Theory of Signal Processing" discussed in the module DFT and FFT: An Algebraic View by Püschel and others [3].

References

  1. Beard, James K. (2003). The FFT in the 21st Century: Eigenspace Processing. Boston: Kluwer.
  2. Elliott, Douglas F. (Ed.). (1987). Handbook of Digital Signal Processing. [Chapter 7 on FFT by Elliott]. San Diego, CA: Academic Press.
  3. Egner, Sebastian and Püschel, Markus. (2001). Automatic Generation of Fast Discrete Signal Transforms. IEEE Transactions on Signal Processing, 49(9), 1992–202.
  4. Tolimieri, Richard and An, Myoung and Lu, Chao. (1989, 1997). Algorithms for Discrete Fourier Transform and Convolution. (second). New York: Springer-Verlag.
  5. Tolimieri, Richard and An, Myoung and Lu, Chao. (1993, 1997). Mathematics of Multidimensional Fourier Transform Algorithms. (second). New York: Springer-Verlag.

Collection Navigation

Content actions

Download module as:

PDF | 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