Problemy implementacji algorytmów FFT w strukturach FPGA

Omówiono implementacje algorytmów FFT dla przypadku przetwarzania sygnałów radarowych w czasie rzeczywistym. Przedstawiono charakterystyki wybranych algorytmów FFT oraz typowe problemy ich stałoprzecinkowej realizacji. Przeanalizowano rozwiązania stosowane w celu zapobiegania nadmiarom. Przedstawiono wyniki badań wpływu parametrów transformaty na dokładność i dynamikę otrzymanego wyniku. Dla badanego typu sygnału określono optymalną postać planu skalowania.

Istota algorytmów FFT, złożoność obliczeniowa

Wyznaczanie widma sygnału dyskretnego x(n) jest operacją powszechnie wykonywaną w systemach cyfrowego przetwarzania sygnałów. Narzędziem pozwalającym na wykonanie tej operacji jest dyskretna transformata Fouriera (ang. DFT – Discrete Fourier Transform), której równania można zapisać w następującej postaci:

W ogólnym przypadku ciąg x(n) jest ciągiem zespolonym. Wyznaczenie DFT bezpośrednio z zależności (1) wymaga wykonania N2 mnożeń i N(N-1) sumowań liczb zespolonych.
Dla rozmiarów transformaty rzędu 1024-, 2048-punktów liczba operacji jest tak duża, że ten sposób wyznaczania widma jest nie realizowalny, szczególnie w aplikacjach czasu rzeczywistego z wysokimi wymaganiami czasowymi. Jest wiele różnych algorytmów FFT, ale wspólną cechą wszystkich jest znacznie mniejsza złożoność obliczeniowa względem metody bezpośredniej. Pojęcie „złożoność obliczeniowa” oznacza tu liczbę operacji arytmetycznych niezbędnych do realizacji algorytmu. Nie obejmuje ona operacji związanych z organizacją obliczeń, nie informuje więc o pełnej czasochłonności obliczeń. W przypadku wykonywania FFT przez klasyczne mikroprocesory, szczególnie starszego typu, operacje związane z organizacją programu zajmowały pomijalnie krótki czas względem operacji arytmetycznych. Sytuacja zmienia się w przypadku implementacji FFT w układach FPGA, które każdą operacje wykonują w identycznym czasie. Szczególnego znaczenia nabiera więc dobór najbardziej efektywnego algorytmu, również pod względem łatwości programowania.

Dla 1024-punktowej transformaty metoda bezpośrednia wymaga 1024^2=1048576 operacji arytmetycznych, zaś 2•(512)^2=524288. Liczba koniecznych do wykonania operacji arytmetycznych spada o połowę w stosunku do metody bezpośredniej. Zysk ten jest jednak zmniejszany poprzez występowanie operacji łączenia widm. Rekursywne dokonywanie podziałów i obliczanie krótszych DFT prowadzi do uzyskania dwupunktowych DFT i znacznej redukcji złożoności obliczeniowej. Końcowy schemat organizacji obliczeń wynikający z rekursywnych podziałów DFT pokazano na rysunku 1a.

Klasyfikacja algorytmów FFT [15,16]

Klasyfikacji algorytmów FFT można dokonać ze względu na kilka własności. Głównym kryterium podziału jest długość ciągu wejściowego N. Wyróżnia się algorytmy Cooley’a – Tuckey’a i algorytmy „Prime Factor”. Pierwsza grupa to algorytmy, dla których rozmiar transformaty jest całkowitą potęgą liczby 2, tzn. N=2M. Druga obejmuje algorytmy, gdzie rozmiar transformaty nie jest potęgą liczby 2 i da się przedstawić jako iloczyn liczb pierwszych. Klasyfikację algorytmów można również przeprowadzić ze względu na podstawę (ang. radix) podziału. Otrzymuje się wtedy algorytmy o podstawie 2 (radix-2), o podstawie 4 (radix-4), o podstawie 8 (radix-8), itd. Algorytmy można sklasyfikować również ze względu na dziedzinę podziału, wyróżnia się wtedy algorytmy z podziałem w czasie DIT (ang. Decimation In Time) oraz z podziałem w częstotliwości DIF (ang. Decimation In Frequency).

Charakterystyka algorytmów FFT

Wspomniany rekursywny podział obliczeń, w przypadku Radix-2, prowadzi do schematu obliczeń, takiego jak na rysunku 1a. Dla większej podstawy podziału powstają bardziej złożone schematy. Każdy algorytm wykonywany jest w określonej liczbie etapów: M=logPN, gdzie p jest podstawą algorytmu. Elementarna operacja algorytmu określana jest jako operacja motylkowa. Algorytmy FFT zmieniają uporządkowanie danych wyjściowych względem danych wejściowych: radix-2 wprowadza tzw. bit reverse w indeksie próbek, a radix- 4 digit reverse.

Radix-2 z podziałem w czasie DIT [12]

Algorytm radix-2 z podziałem czasowym powstaje z przekształcenia równania dyskretnej transformaty Fouriera (1) do
postaci zawierającej sumę dwóch transformat:
• pierwszej, obliczonej dla parzyście indeksowanych elementów wejściowej sekwencji danych (parzystych próbek sygnału wejściowego),
• drugiej, dla nieparzystych próbek sygnału wejściowego.
Przekształcone w ten sposób równanie przedstawiono poniżej.

Graficzny schemat obliczeń reprezentujący powyższe równania dla N=8 pokazano na rysunku 2a.


Dane wejściowe (rys. 2) są uporządkowane w naturalnej kolejności a dane wyjściowe w odwrotnej kolejności bitów w indeksie. Pojedyncza operacja motylkowa (rys. 2b), jest podobna do operacji motylkowej algorytmu z podziałem w czasie (rys. 1b). Obejmuje ona dwa sumowania liczb zespolonych i jedno mnożenie. Liczba etapów określona jest wyrażeniem M=log2N, na każdym etapie wykonuje się N/2 operacje motylkowe. Całkowita złożoność obliczeniowa
wynosi: Nlog2N sumowań oraz (N/2)log2N mnożeń liczb zespolonych.

Korekcja formatu wyników operacji arytmetycznych

Wynikiem stałoprzecinkowych operacji arytmetycznych są liczby o długości większej niż dane wejściowe. Wynik mnożenia jest sumą długości czynników mnożenia, np.: mnożenie p-bitowej próbki i b-bitowego współczynnika, generuje wynik o długości p+b bitów. Z uwagi na ograniczoną długość słowa stosuje się korekcję długości wyniku, zazwyczaj do wartości p. Korekcji można dokonać poprzez obcięcie lub zaokrąglenie mniej znaczących bitów.
Wynik sumowania dwóch p-bitowych próbek nie wymaga korekcji, ale może przekroczyć maksymalną wartość dającą się zapisać na p bitach, tzn. może powstać nadmiar.
Wynik sumowania dwóch p-bitowych próbek nie wymaga korekcji, ale może przekroczyć maksymalną wartość dającą się zapisać na p bitach, tzn. może powstać nadmiar.

Wykonywanie korekcji wyników mnożenia wiąże się z wprowadzaniem błędu, który jest zależny:
• od sposobu wykonania korekcji,
• od wartości, jakie reprezentują sobą liczby stałoprzecinkowe: ułamki, liczby całkowite,
• od sposobu reprezentacji liczb ujemnych: uzupełnienie do dwóch, uzupełnienie do jedności, notacja znak-moduł.