Problemy implementacji algorytmów FFT w strukturach FPGA

Metody zapobiegania nadmiarom

Występowanie nadmiarów prowadzi do zniekształcenia wyniku, konieczne jest więc zapobieganie ich powstawaniu.
Jest kilka metod zapobiegania nadmiarom, ale zastosowanie ich wiąże się z utratą dynamiki wyniku i wydłużeniem czasu wykonywania algorytmu lub wzrostem wymagań sprzętowych.
Możliwe jest użycie następujących metod.

• Pełna precyzja (ang. Full-precision unscaled arithmetic), polega ona na rozszerzeniu długości słowa danych o n+1
bitów, gdzie n jest liczbą etapów algorytmu. Wynika to z faktu, iż potencjalnie na każdym etapie może pojawić się
nadmiar. Zapewnia to propagację nadmiaru na starsze bity. Zastosowanie tej metody jest ograniczone możliwościami sprzętowymi.

• Blokowy zmienny przecinek (ang. Block floating-point), polega na wykonywaniu obliczeń transformaty aż do
momentu wystąpienia pierwszego nadmiaru w danym etapie. W takim przypadku wyniki bieżącego etapu są kasowane, następuje powrót do początku bieżącego etapu, skalowanie danych i ponowne obliczenia. Metoda nie nakłada wymogów na długość słowa danych, ale zmniejsza dynamikę wyników proporcjonalnie do liczby skalowań. Każdorazowe wystąpienie nadmiaru powoduje zwiększenie czasu wykonywania algorytmu.

• Skalowanie (ang. Scaled fixed-point), metoda bezwarunkowego skalowania danych przed każdym etapem
obliczeń; polega na podzieleniu danych wejściowych etapu przed jego rozpoczęciem przez założoną wartość, np.: 2, 4,
8, itd. Dla FFT radix-2 będzie to najczęściej dzielenie przez 2 lub 4, a dla radix-4 przez 4 lub 8. Metoda może wprowadzać niepotrzebne dzielenia i zmniejszenie dynamiki wyniku, ale gwarantuje najszybsze wykonanie obliczeń.

Pierwsza metoda jest rzadko stosowana z uwagi na zwiększone zużycie zasobów sprzętowych struktury FPGA. Metoda skalowania danych wymaga zaprojektowania planu skalowania. Wiąże się to z określeniem struktury M-elementowego
wektora poprzez ustalenie liczby skalowań i jej rozkładu na poszczególnych etapach. Strukturę wektora przedstawić
można jako: [NM, …, N2, N1], np.: [1, …, 0, 2]. Elementy wektora wskazują liczbę skalowań na danym etapie a indeks
elementu wektora wskazuje numer etapu. Dla przykładowej struktury wektora element N1=2 oznacza konieczność dwukrotnego skalowania danych przed pierwszym etapem obliczeń (dwukrotne przesunięcie bitowe w prawo równoważne dzieleniu przez 4), a element N2=0 oznacza brak skalowania.

Zastosowanie blokowego zmiennego przecinka nie wymaga planu skalowania. Potrzeba skalowania jest wykrywana automatycznie po wykonaniu każdego kolejnego etapu obliczeń. W ten sposób powstaje optymalny plan skalowania, wiąże się to jednak ze znacznym wzrostem czasu wykonywania algorytmu.

Dobór planu skalowania

Od liczby skalowań zależy dynamika i dokładność otrzymanego wyniku. Metoda blokowego zmiennego przecinka
pozwala wprawdzie na określenie optymalnego planu skalowania, jednak stosowanie jej w systemach czasu
rzeczywistego, pracujących w systemach radiolokacyjnych jest niekorzystne z uwagi na możliwość wydłużenia czasu
wykonania algorytmu. Nadrzędnym zadaniem staje się więc określenie bezwzględnego planu skalowania, optymalnego
pod względem dynamiki i poprawności wyniku. Konieczna zatem jest estymacja przedziału, w którym będzie poszukiwana wartość liczby skalowań Sn. Wartości dopuszczalne

Diagnostyka programu

W układach FPGA czas cyklu diagnostycznego, tj.: przygotowanie programu, załadowanie do FPGA i sprawdzenie
działania jest dużo dłuższy niż w przypadku implementacji algorytmów w klasycznych procesorach. Brak możliwości pracy krokowej utrudnia diagnostykę występujących błędów.

Badania algorytmu

Występowanie przedstawionych problemów wymusza przeprowadzenie dokładnej analizy działania i weryfikacji algorytmu przed jego implementacją w strukturze FPGA. Z uwagi na trudności diagnostyki w środowisku docelowym konieczne staje się przeprowadzenie symulacji algorytmu w środowisku naśladującym działanie układu FPGA. Badania muszą być przeprowadzone dla wszystkich możliwych konfiguracji parametrów algorytmu, tj.: rozmiaru transformaty, długości słowa danych, planu skalowania, sposobu korekcji formatu wyników.

Treść i warunki badań

Badaniu poddano wpływ parametrów algorytmu na poprawność i dynamikę wyników. W celu wykonania badań opracowano program w języku C, w środowisku LabWindows/CVI5.5. Program umożliwiał przybliżenie warunków pracy układu FPGA w zakresie arytmetyki i długości słowa.

Własności programu:
• interfejs graficzny (rys. 5) pozwalający wybrać dowolną konfigurację parametrów,
• rozmiar transformaty: 1024, 2048, 4096 punktów,
• długość słowa danych: 1-14 bitów,
• wybór metody korekcji wyników,
• zliczanie nadmiarów na każdym etapie algorytmu,
• możliwość ustawienia dowolnego planu skalowania,
• możliwość porównania wyników z realizacją zmiennoprzecinkową,
• zapis wyników do pliku.
Do oceny jakościowej wyników otrzymanych w arytmetyce stałoprzecinkowej i porównania ich z realizacją zmiennoprzecinkową użyto następujących miar:
• unormowany współczynnik korelacji widm:

Miara (6) określa podobieństwo otrzymanego widma z realizacją zmiennoprzecinkową. Wartości bliższe jedności świadczą o większym podobieństwie wyniku stałoprzecinkowego do realizacji zmiennoprzecinkowej. Miara (7) charakteryzuje poziom składowej stałej względem maksymalnej wartości w otrzymanym widmie. W przypadku idealnym (brak składowej stałej) przyjmuje ona wartość -∞. Wartości bliższe -∞ wskazują na niższy poziom składowej stałej, a zatem na dokładniejszy wynik. Miara (8) określa stopień wykorzystania dostępnego rozmiaru słowa. Przy jej określaniu wykorzystano właściwość, iż wydłużenie słowa o 1 bit powoduje wzrost dynamiki maksymalnej wartości słowa o 6 dB.




Do badań algorytmu użyto sygnału z liniową modulacją częstotliwości LFM o parametrach: fC=12 MHz, Δf=4 MHz, N=4096, ti=40,95 μs, fs=100 MHz. Sygnał wygenerowano symulacyjnie bez zakłóceń, w postaci liczb rzeczywistych z zakresu -1≤x≤1. Fragment postaci czasowej (ti=5,1 µs) przedstawiono na rysunku 6a, zaś na rysunku 6b – widmo sygnału.