Problemy implementacji algorytmów FFT w strukturach FPGA

Wyniki badań

Badanie wpływu rozmiaru transformaty i długości słowa danych

• Badania przeprowadzono dla trzech rozmiarów transformaty N=4096, N=2048, N=1024 punktów; dla trzech
długości słowa danych Q=12, Q=13, Q=14 bitów oraz współczynnika obrotu WN w formacie Q1.14. Zastosowano
zachowawczy plan skalowania z przesuwanym na kolejne etapy elementem „2”: [1, …, 1, 2], [1, …, 2, 1,], itd.
• Otrzymane charakterystyki współczynnika korelacji widm (rys. 7) i względnego poziomu składowej stałej (rys. 8)
przedstawiono w funkcji numeru etapu, na którym występowało skalowanie przez współczynnik „2”.

• Dla obu użytych miar jakości najlepsze wyniki uzyskuje się w przypadku tej samej pary parametrów algorytmu: N=1024
i Q=14 (ciemnozielona linia). Mniejszej liczbie etapów obliczeń M odpowiada mniejsza liczba operacji mogących powodować nadmiar wyników. Słowa o większej precyzji charakteryzują się mniejszą wartości kwantu, przez co
zmiany wynikające z korekcji formatu i skalowań danych są mniejsze. Zauważalny jest wzrost współczynnika korelacji
przy przesuwaniu elementu „2” w planie skalowania na późniejsze etapy. Otrzymane wyniki są zgodne z oczekiwaniami.

Badanie wpływu korekcji wyniku

• Otrzymane wyniki symulacji dla dwóch możliwych sposobów korekcji wyniku wskazały na wzrost wpływu sposobu korekcji wraz ze spadkiem długości słowa danych. Dla dłuższych formatów słowa wagi bitów pomijanych są małe w porównaniu do wag najstarszych bitów na których zapisany jest wynik.

Badanie wpływu liczby skalowań

Badania wpływu planu skalowania przeprowadzono zmniejszając liczbę skalowań występującą w wektorze zachowawczym. Dla każdej wartości Sn możliwe jest zaprojektowanie skończonej liczby planów skalowania.
• Z przeprowadzonych symulacji, dla badanego sygnału LFM, otrzymano optymalną liczę skalowań równą Sn=7.
Przy takiej liczbie skalowań otrzymano najkorzystniejsze wartości miar użytych do opisu jakościowego.
• Wybór liczby skalowań warunkuje poprawność oraz dokładność wyniku. Mała liczba skalowań może nie zapewnić
poprawności wyniku, zbyt duża powoduje wzrost poziomu składowej stałej oraz spadek dynamiki wyniku wywołany
większą liczbą skalowań.

Optymalny plan skalowania dla badanego sygnału

Wnioski z badań wskazywały na istnienie optymalnego planu skalowania dla badanego typu sygnału. Poszukiwanie optymalnej postaci wektora przypominało metodę blokowego zmiennego przecinka. Kolejne stosowane plany skalowania oraz wyniki uzyskane przy ich zastosowaniu przedstawiono w tabeli 1.


Rezultat otrzymany dla planu skalowania w postaci:
[1,1,1,1,1,0,0,1,1,0] charakteryzuje się największą wartością współczynnika korelacji, najniższym względnym poziomem
składowej stałej oraz dynamiką wyniku na dopuszczalnym poziomie. Uzyskany optymalny plan skalowania zapewnia
największą dokładność otrzymanego wyniku.

Wnioski

Przeprowadzone badania wykazały, że właściwy dobór parametrów transformaty ma istotny wpływ na jej wyniki.
Najważniejszy okazał się plan skalowania, który może powodować:
• całkowite zniekształcenie wyników gdy jest źle zaprojektowany
• ograniczenie dynamiki wyników jeśli jest zachowawczy.
Znalezienie optymalnego planu skalowania wymaga przeprowadzenie badań konkretnego typu sygnału na modelu symulacyjnym transformaty. Zastosowanie modelu postępowania polegającego na badaniach symulacyjnych układu przed jego implementacją w FPGA może być wykorzystane w odniesieniu do implementacji dowolnej złożonej procedury DSP w FPGA.

Literatura

[1] Oppenheim A.V., Schafer R.W.: Cyfrowe przetwarzanie sygnałów, WKŁ, Warszawa 1979
[2] Lyons R. G.: Wprowadzenie do cyfrowego przetwarzania sygnałów, WKŁ, Warszawa 2006
[3] Szabatin J.: Podstawy teorii sygnałów, WKŁ, Warszawa 2003
[4] Zieliński T.P.: Cyfrowe przetwarzanie sygnałów. Od teorii do zastosowań, WKŁ, Warszawa 2005
[5] „Fast Fourier Transform v4.1” specyfikacja IPCore, Xilinx ISE 9.2i
[6] “Fixed Point Arithmetic and Q Format” – http://cnx.org/content/m10919/latest/
[7] Knight W.R., Kaiser A.: “A simple fixed-point error bound for the fast Fourier Transform”, IEEE Xplore
[8] Elterich A., Stammler W.: “Error analysis and resulting structural improvements for fixed point FFTs”, IEEE Xplore
[9] Uzun I.S., Amira A., Bouridane A.: “FPGA implementations of fast Fourier transforms for real-time signal and image processing”, IEEE Xplore
[10] “Overview of Fast Fourier Transform (FFT) Algorithms” – http://cnx.org/content/m12026/latest/
[11] “Decimation-in-Frequency (DIF) Radix-2 FFT” – http://cnx.org/content/m12018/latest/
[12] “Decimation-in-Time (DIT) Radix-2 FFT” – http://cnx.org/content/m12016/latest/
[13] “Radix-4 FFT Algorithms” – http://cnx.org/content/m12027/latest/
[14] “Split-radix FFT Algorithms” – http://cnx.org/content/m12031/latest/
[15] “The Prime Factor Algorithm” – http://cnx.org/content/m12033/latest/
[16] “Power-of-two FFTs” – http://cnx.org/content/m12059/latest/


Robert Kędzierawski
Wojskowa Akademia Techniczna, Wydział Elektroniki