Problemy implementacji algorytmów FFT w strukturach FPGA - str. 3 - WOJSKOWA AKADEMIA TECHNICZNA - DSP - FPGA - KORELACJA - ALGORYTMY FFT - IMPLEMENTACJA ALGORYTMU RADIX- - ROBERT KĘDZIERAWSKI - WYDZIAŁ ELEKTRONIKI
Farnell, An Avnet Company   Przedstawicielstwo Handlowe Paweł Rutkowski   Phoenix Contact Sp. z o.o.  

Energetyka, Automatyka przemysłowa, Elektrotechnika

Dodaj firmę Ogłoszenia Poleć znajomemu Dodaj artykuł Newsletter RSS
strona główna ARTYKUŁY Telekomunikacja Problemy implementacji algorytmów FFT w strukturach FPGA
drukuj stronę
poleć znajomemu

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





fot. Spektrum




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:




fot. Spektrum



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.




fot. Spektrum

Rys. 5. Panel nastaw parametrów symulacji






fot. Spektrum

Rys. 6a. Fragment postaci czasowej sygnału






fot. Spektrum

Rys. 6b. Widmo sygnału



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.

REKLAMA

Otrzymuj wiadomości z rynku elektrotechniki i informacje o nowościach produktowych bezpośrednio na swój adres e-mail.

Zapisz się
Administratorem danych osobowych jest Media Pakiet Sp. z o.o. z siedzibą w Białymstoku, adres: 15-617 Białystok ul. Nowosielska 50, @: biuro@elektroonline.pl. W Polityce Prywatności Administrator informuje o celu, okresie i podstawach prawnych przetwarzania danych osobowych, a także o prawach jakie przysługują osobom, których przetwarzane dane osobowe dotyczą, podmiotom którym Administrator może powierzyć do przetwarzania dane osobowe, oraz o zasadach zautomatyzowanego przetwarzania danych osobowych.
Komentarze (0)
Dodaj komentarz:  
Twój pseudonim: Zaloguj
Twój komentarz:
dodaj komentarz
Stowarzyszenie Elektryków Polskich
Stowarzyszenie Elektryków Polskich
ul. Świętokrzyska 14, Warszawa
tel.  +48 22 5564-302
fax.  +48 22 5564-301
$nbsp;
REKLAMA
Nasze serwisy:
elektrykapradnietyka.com
przegladelektryczny.pl
rynekelektroniki.pl
automatykairobotyka.pl
budowainfo.pl