Eksperymenty z FPGA (13). Dyskretna transformata Fouriera

Rozpisaliśmy transformatę Fouriera o długości N, na dwie transformaty o połowę mniejszej długości. Teraz musimy wykonać pewne działania na współczynnikach, a następnie policzyć jedną transformatę dla współczynników parzystych, a drugą dla nieparzystych. W pierwszej, współczynniki wejściowe są po prostu sumą, lecz przygotowanie danych dla drugiej jest bardziej skomplikowane – najpierw liczymy różnice, a następnie musimy pomnożyć przez współczynnik, co w języku angielskim nosi nazwę „twiddle factor”. Schematycznie pokazuje to rysunek 7.