Transformata Fouriera.pdf

31.01.2008

Zastowowanie transformacji Fouriera w

cyfrowym przetwarzaniu sygnałów

Paweł Tkocz

inf. sem. 5

gr 1

1. Dźwięk cyfrowy

Fala akustyczna jest jednym ze zjawisk fizycznych mających charakter

okresowy. Falę tę reprezentują zmiany ciśnienia w powietrzu, które przy

odpowiednich częstotliwościach stanowią, słyszalny dla ucha ludzkiego, dźwięk.

Poniższy wykres prezentuje fale sinusoidalną. Usłyszymy ją jako jeden

monotonny dźwięk, którego wysokość zależy od okresu fali - im będzie on

krótszy, tym wyższy będzie usłyszany dźwięk.

Zmiany stanu fali są dla komputera całkowicie abstrakcyjne. W naturze

słyszymy dźwięki ciągłe - technika cyfrowa musi jednak opisać ich zmienność w

czasie w postaci liczb. Z pomocą przychodzi tutaj próbkowanie - tworzenie

ciągu wartości chwilowych funkcji pobranych w równych odstępach czasu.

Stopniowe, płynne zmiany stanu fali dźwiękowej zachodzące w czasie są

opisywane przez komputer w drodze pobierania próbek dźwięku w ściśle

ustalonych odstępach czasowych. Jeżeli częstostliwość próbkowania wynosi

1 Hz, to komputer bada stan fali dźwiękowej raz na sekundę. W ten sposób

sygnał z urządzenia analogowego przetwarzany jest na postać cyfrową.

2. Transformacja Fouriera

Transformacja Fouriera umożliwia nam przedstawienie sygnału

zmiennego w czasie w skali częstotliwości. Każdy sygnał analogowy można

przedstawić w postaci składowych sinusoidalnych o odpowiedniej amplitudzie,

fazie i częstotliwości. Dyskretna postać transformacji (DTF), jest stosowana

przy cyfrowej analizie spektrum sygnału t.j. :

● analiza widma sygnału,

● przetwarzanie mowy,

● rozpoznawanie obrazów.

Dyskretna postać transformacji

Jesli znamy wartosci funkcji okresowej f w N równomiernie rozłozonych

na odcinku [0 , a ) punktach, mozemy wyznaczyc przyblizone współczynniki c n

szeregu Fouriera funkcji f . Majac zatem dane N punktów i wartosci funkcji f

w tych punktach:

k = 0 , 1 , · · · ,N − 1, wyznaczyc mozna N przyblizonych

współczynników Fouriera:

Def. Dyskretną trasformatą Fouriera (DFT) ciagu y 0 , y 1 , · · · , y N− 1 nazywamy

ciag

liczbowy Y 0 , Y 1 , · · · , Y N− 1 dany wzorem:

Piszemy:

Przybliżone współczynniki Fouriera mają postać:

Transformata jest odwracalny jest odwracalnym przekształceniem liniowym.

Odwzorowanie odwrotne dane jest wzorem:

Ze względu na złożoność obliczeniową algorytmu DFT – O ( N 2 ) jest on rzadko

implementowany. Do wyznaczenia dyskretnej transfotmaty(oraz transformaty

do niej odwrotnej) używa się algorytmu FFT (Fast Fourier Transformation).

Jego złożoność jest o wiele lepsza i wynosi O ( N log 2 N ).

Główna idea algorytmu FFT

Dowolny wielomian stopnia n-1, gdzie n jest potegą 2

p ( x ) = a 0 + a 1 x 1 + a 2 x 2 + ... + a n- 1 x n+ 1

Da się przedstawić w postaci:

p ( x ) = p parz ( x 2 ) + p nparz ( x 2 )

gdzie:

p parz ( x ) = a 0 + a 2 x 1 + a 4 x 2 + ... + a n- 2 x n/ 2 - 1

p nparz ( x ) = a 1 + a 2 x 1 + a 5 x 2 + ... + a n- 1 x n/ 2 - 1

Wtedy możemy uprościć problem

● z wyznaczenia wartości wielomianu n-tego stopnia p(x) w punktach

w 0 ,w 1 ,...,w n-1

do:

● wyznaczenia wartości dwóch wielomianów stopnia (n/2) w punktach

(w 0 ) 2 ,(w 1 ) 2 ,...,(w n-1 ) 2

Zgodnie z Lematem 3 wartości wielomianów p parz ( x ) i p nparz ( x ) są tylko

wyznaczanew n/ 2 punktach, które są pierwiastkami n/ 2 stopnia z jedynki.

Niech

k = 0, 1, ... , n/2 -1

v = e -i* 2 π /m gdzie m = n/2

v k jest pierwiastkiem stopnia m z jedności

e k = p parz ( v k ) = p parz ( w 2 k ) (z Lematu 2)

d k = p nparz ( v k ) = p nparz ( w 2 k )

Wtedy dla l =k, (czyli dla l = 0, 1,..., n/2-1)

y l = p ( w k ) = p parz ( w 2 k ) + w k p nparz ( w 2 k ) = e k + w k d k

Dla dla l = n/ 2 + k , (czyli dla l = n/ 2 – 1,...,n-1)

y l = p (w n/ 2+k ) = p parz ( w 2 k w n ) + w n/ 2+ k p nparz ( w 2 k w n ) = p parz ( w 2 k ) - w k p nparz ( w 2 k ) =

= e k – w k d k

ponieważ:

w n = e - 2 πi =1

w n/2 = -1 (z Lematu 1)

Łatwo zauważyć, że dla n=1

l = 0

y 0 = w 0 l a 0 = a 0

Algorytm FFT

Mając dane {a 0 , a 1 , a 2 , ... , a n- 1 } mamy wyznaczyć {y 0 , y 1 , y 2 ,..., y n- 1 }

Zakładamy, że n jest potęgą 2

Algorytm:

FFT ( n, a 0 , a 1 , a 2 , a 3 , ... , a n- 1 )

{

if ( n == 1) return a 0 ;

w = e - 2 π i/n;

( e 0 , e 1 , e 2 , e 3 ,..., e n/ 2 - 1 ) = FFT ( n/ 2, a 0 , a 2 , a 4 , a 6 ,..., a n- 2 );

( d 0 , d 1 , d 2 , d 3 ,..., d n/ 2 - 1 ) = FFT ( n/ 2, a 1 , a 3 , a 5 , a 7 ,..., a n- 1 );

for k = 0 to n/ 2-1

{

y k = e k + w k d k ;

y k + n/ 2 = e k – w k d k

};

return ( y 1 , y 2 , y 3 ,..., y n- 1 );

}

Dzięki istnieniu takiego algorytmu, możliwe stało się cyfrowe

przetwarzanie sygnałów za pomocą procesorów DSP np. usuwanie szumów :

Stosując szybką transformatę Fouriera przekształcamy dzwięk do zapisu

częstotliwościowego.Usuwamy sygnały o nieporządanych częstotliwościach i

stosujemy transformatę odwrotną.

3. Wykorzystanie transformacji Fouriera dla procesorów DSP

Procesory sygnałowe DSP (Digital Signal Processors) są niezwykle

wydajnymi układami przeznaczonymi do stosowania w rozwiązaniach

wymagających dużej mocy obliczeniowej i dużej szybkości działania.

Stosowane są przeważnie w systemach czasu rzeczywistego do przetwarzania

sygnałów analogowych (np. dźwięku, obrazu, temperatury, ciśnienia itp.) na

postać cyfrową oraz obróbce tak otrzymanych wyników. Szczególnym polem

zastosowań są aplikacje, w których wykonuje się dużą liczbę działań

matematycznych (dodawanie, odejmowanie, mnożenie i dzielenie - w tym

operacje zmiennoprzecinkowe), które to wykonywane są w bardzo krótkim

czasie. Zalety te zapewnia specjalna architektura układów, kładąca nacisk na

łatwy dostęp do pamięci RAM, szybkie przetworniki ADC, wysoką częstotliwość

zegara (do 600 MHz), krótki czas wykonywania instrukcji itp.

Przykładowe rodziny procesorów sygnałowych firmy Analog Devices:

● BlackFin to nazwa rodziny procesorów stałoprzecinkowych , które łączą

cechyprocesorów DSP oraz RISC. Układy te zawierają po dwa 16-bitowe

układy MAC, dwa 40-bitowe ALU i cztery 8-bitowe ALU przeznaczone do

operacji na danych video. Układy BlackFin dedykowane są do szeroko

rozumianych zastosowań w urządzeniach multimedialnych, w tym także

wszędzie tam, gdzie wymagane jest przetwarzanie numeryczne dużych

ilości danych.

● Procesory DSP z rodziny SHARC (Super Harvard Architecture Computer)

dzięki unikalnej architekturze pamięci, zbudowanej z dwóch dużych bloków

dwubramowej pamięci SRAM, są w stanie sprostać zadaniom wymagającym

wykonywania ciągłych szybkich obliczeń (w tym operacji

zmiennoprzecinkowych).

Dzięki algorytmowi FFT, procesory DSP zaczęły być używane na szeroką

skalę. Wykorzystanie cyfrowego przetwarzanie sygnałow wskazuje na takie

obczary jak: cyfrowe przetwarzanie dźwięku, cyfrowe przetwarzanieobrazów

oraz przetwarzanie mowy. Algorytmy Cyfrowego przetwarzania sygnałów są

niekiedy realizowane przez specjalizowane urządzenia komputerowe, które

korzystają ze specjalizowanych procesorów DSP, pozwalających na

przetwarzanie sygnałów w czasie rzeczywistym (ang. real time signal

processing) . Stosowanie analizy Fouriera, ma miejsce w większości przypadkow

korzystania z danych multimedialnych:

● kompresja pików muzycznych mp3 (layer 2, layer3)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: