Wikipedia:Reference desk/Archives/Computing/2024 August 15

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 15

Fast Fourier transform

In the website there's an example FFT algorithm structure which uses a decomposition into half-size FFTs. Does the 🔝 half-size FFT which consists of x[0], x[2], x[4], x[6] pertain to switching circuit theory which "is the mathematical study of the properties of networks of idealized switches?" Below the example FFT algorithm structure is "a discrete Fourier analysis of a sum of cosine waves at 10, 20, 30, 40 and 50 Hz." Afrazer123 (talk) 22:05, 15 August 2024 (UTC)

For context, this presumably refers to the first picture in the article Fast Fourier transform. And here's Switching circuit theory.  Card Zero  (talk) 03:34, 16 August 2024 (UTC)

In regards to the first picture, there's no relationship between that FFT structure and switching circuit theory "except that both can be characterized and diagrammed as graphs." Afrazer123 (talk) 19:48, 5 September 2024 (UTC)

No, there is no relation between this FFT structure, which is about linear operators on real and complex numbers, and switching circuit theory, which is about digital logic operations (except that both can be characterized and diagrammed as graphs). In the FFT diagram, E(0), E(1), E(2), and E(3) are complex numbers that represent the DFT of the Even-numbered input numbers; similarly O(0)... for the DFT of the odd-numbered inputs. The Ws are complex "weights", numbers that are multiplied by the Os; those products are added to the unmultiplied Es that they are paired with, to make the output complex numbers that represent the DFT of the full input sequence of numbers. Dicklyon (talk) 15:49, 16 August 2024 (UTC)

Thanks for ur reply, especially the part about the Ws being complex "weights" and so on. Also, I read about "[all] known FFT algorithms require O(nlogn) operations" and a colored diagram of the Big O notation which includes a graph of O(nlogn). Afrazer123 (talk) 21:56, 4 September 2024 (UTC)