Problemy implementacji algorytmów FFT w strukturach FPGA

Radix-4 [13]

Algorytm radix-4 z podziałem czasowym powstaje z przekształcenia równania N-punktowej dyskretnej transformaty
Fouriera (1) do postaci zawierającej sumę czterech krótszych N/4-punktowych transformat. Podzbiory danych do
tych krótszych transformat są tworzone przez czterokrotne rozrzedzenie sekwencji próbek sygnału x(n), tj. rozrzedzenie sygnału w czasie. Tworzone są cztery podzbiory:

Aby powyższy podział był możliwy, parametr N określający liczbę próbek sygnału wejściowego musi być potęgą
liczby 4. Końcowe równanie algorytmu przedstawiono poniżej.

Graficzną ilustrację metody, na której opiera się algorytm radix-4 (4) przedstawiono na rysunku 3a. a operację motylkową tego algorytmu na rysunku 3b. Algorytm ten wymaga wykonania mniejszej liczby etapów, M=log4(N). Każdy etap to N/4 obliczenia motylkowe, charakteryzujące się trzema mnożeniami i ośmioma sumowaniami liczb zespolonych. Całkowita złożoność obliczeniowa wynosi (3N/8)log2(N) mnożeń i Nlog2N sumowań liczb zespolonych. Spadek liczby mnożeń w stosunku do algorytmu Radix-2 wynosi 25%.


Algorytm Radix-4 z podziałem w częstotliwości charakteryzują się identyczną złożonością obliczeniową. Analogicznie
jak w przypadku algorytmów o podstawie 2, schemat operacji motylkowej dla podziału w częstotliwości jest podobny do
podziału w czasie. Mnożenie przez współczynnik obrotu występuje po operacji sumowania zespolonego.

Split-radix [14]

Algorytm ten łączy własności algorytmu o podstawie 2 i algorytmu o podstawie 4. Struktura takiego algorytmu jest nieregularna. Operacja motylkowa (rys. 4) przyjmuje kształt litery „L”. Nieregularna struktura może utrudnić implementację tego algorytmu w niektórych procesorach. Równanie (5) opisujące algorytm przedstawiono poniżej.


Złożoność obliczeniowa algorytmu wynosi: Nlog2(N) sumowań i (N/3)log2(N) mnożeń liczb zespolonych.

Wybór algorytmu do implementacji

Spośród omówionych algorytmów najbardziej efektywny ze względu na złożoność obliczeniową jest algorytm Radix-4,
ale jego przewaga nad Radix-2 jest niewielka. Oba algorytmy charakteryzują się regularną strukturą ułatwiającą programowanie. Radix-4 ustępuje jednak algorytmowi Radix-2 pod względem elastyczności parametru N oraz charakteryzuje się większą złożonością struktury. Z tych powodów do implementacji w FPGA wybrano algorytm Radix-2 DIF.

Problemy implementacji algorytmu Radix-2 DIF

Implementacja algorytmów FFT w układach FPGA stwarza dwa zasadnicze problemy:
• konieczność stosowania arytmetyki stałoprzecinkowej o ograniczonej długości słowa danych, w układach Virtex jest to 18 bitów,
• złożony i czasochłonny proces diagnostyki programu.
Zastosowanie arytmetyki stałoprzecinkowej powoduje dalsze problemy szczegółowe, tj.:
– możliwość wystąpienia nadmiarów w operacjach arytmetycznych,
– konieczność korekcji formatu słowa po operacjach arytmetycznych.