Problemy implementacji algorytmów FFT w strukturach FPGA - str. 2 - WOJSKOWA AKADEMIA TECHNICZNA - DSP - FPGA - KORELACJA - ALGORYTMY FFT - IMPLEMENTACJA ALGORYTMU RADIX- - ROBERT KĘDZIERAWSKI - WYDZIAŁ ELEKTRONIKI
Mouser Electronics Poland   Przedstawicielstwo Handlowe Paweł Rutkowski   Amper.pl 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

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:





fot. Spektrum



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.




fot. Spektrum



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%.




fot. Spektrum

Rys. 3a. Schemat organizacji obliczeń DFT dla algorytmu Radix-4 DIT






fot. Spektrum

Rys. 3b. Operacja motylkowa dla algorytmu Radix-4 DIT


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.




fot. Spektrum







fot. Spektrum

Rys. 4. Struktura operacji motylkowej dla algorytmu Split-radix


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.

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