Dyskretna transformata Fouriera
Dyskretna transformata Fouriera
Discrete Fourier Transform  DFT
Fourierowskie przedstawienie
ciągów o skończonej długości
(lub ciągów okresowych dla próbek w jednym okresie)
Discrete Fourier Transform - DFT
Discrete Fourier Transform - DFT
Definicja DFT dla skończonego ciągu x(n) o długości N
j�
0 d" n d" N -1
próbek dla i jego DTFT , jest to
X (e )
j�
równomiernie spróbkowana transformata wzdłuż
X (e )
0 d" � d" 2Ą �k = 2Ąk/ N
osi �, w przedziale w punktach
dla .
0 d" k d" N -1
(1)
Definicja DFT
0 d" k d" N -1
dla .
2
Interpretacja
Interpretacja
Ciąg x(n) o skończonej długości N traktowany jako ciąg okresowy
xN(n) o okresie N, który w ramach jednego okresu jest identyczny
z ciągiem o skończonej długości (pomijamy na razie wycinanie
fragmentu sygnału  tzw. okienkowanie, gdy xN(n) = x(n)wN(n) ).
W przeciwieństwie do szeregu Fouriera okresowej funkcji ciągłej x(t) = fT (t)
"
"
"
"
fT (t) = Ł Fk exp(jk�0t), gdzie �0 = 2Ą / T
(2a)
k = -"
"
"
"
T
(2b)
Fk = 1/T +" fT (t) exp(-jk�0t)dt ,
0
szereg Fouriera ciągu (szeregu) okresowego ma tylko N różnych
zespolonych wyrazów wykładniczych, gdyż
k-ta dyskretna harmoniczna jest okresowa z okresem N
e j(2Ą/�)kn = e j(2Ą/�) (k+rN)n
3
Rozważmy wyrażenie exp(-jk�0t)dt we wzorze (2b) na
współczynniki Fouriera rozkładu funkcji w przedziale T dla
przypadku czasu dyskretnego, tzn. t = nTs i dt=Ts .
k�0tćłt=nTs = knTs 2Ą /T = knTs 2Ą / NTs = 2Ą kn / N
Wtedy całka (2b) , przy podstawieniu dt =Ts i T = NTs
przechodzi w szereg (1).
T
�!
�!
�!
�!
Fk = 1/T +" fT (t) exp(-jk�0t)dt
0
4
Uwagi
Uwagi
" X(k) nazywamy dyskretną transformatą Fouriera
skończonego ciągu x(n) o długości N próbek (wyrazów).
" X(k) również długość N próbek w dziedzinie dyskretnej
pulsacji (częstotliwości).
WN = e- j2Ą / N
" Stosując notację DFT można zapisać
w postaci
N -1
k
(3)
X[k] = x[n]WNn, 0 d" k d" N -1
"
n=0
Próbek widma jest tyle, ile próbek sygnału. Zespolone, czy to 2 razy więcej?
5
DTFT
6
Odwrotna transformata DFT - IDFT
Odwrotna transformata DFT - IDFT
Odwrotne przekształcenie do DFT dane jest wzorem
N -1
1
-kn
(4)
x[n] = X[k]WN , 0 d" n d" N -1
"
N
k=0
Aby wykazać słuszność wzoru (4) (chodzi też o współczynnik N) wykonamy
WNn
DFT postaci (4). W tym celu pomnóżmy obustronnie (4) przez
0 d" n d" N -1
dla i zsumujmy dla .
7
Otrzymamy
N -1 N -1 N -1
�ł �ł
1
-kn
�ł �ł
x[n]WNn = X[k]WN �łWNn
" " "
�ł
N
�ł łł
n=0 n=0 k=0
N -1N -1
1
-
= X[k]WN(k- )n
" "
N
n=0 k=0
N -1N -1
1
-
= X[k]WN(k- )n
" "
N
k=0 n=0
?
8
Wykorzystując zależność
N -1
r całkowite
for k - = rN,
N,
- ńł
WN(k- )n =
"
�ł
0, otherwise
ół
n=0
otrzymujemy, że prawa strona poprzedniej równości wynosi
X [ ]
(wybierając k = l z przedziałów i ),
0 d" k d" N -1
N -1
a zatem
x[n]WNn = X [ ]
"
n=0
co jest poprawną zależnością na DFT ciągu x(n) otrzymanego z (4).
9
6
1,5
3
1
itd.
4
0 2, 6 0, 4
itd.
7 5
N = 8
2 3, 7
k - l = 3 k - l = - 6
(ujemne, w prawo 3/2 Ą)
(dodatnie, w lewo co � Ą )
WN = e- j2Ą / N
N -1
r całkowite
for k - = rN,
N,
- ńł
WN(k- )n =
"
�ł
0, otherwise
ół
10
n=0
Interpretacja sygnału w czasie przez DFT
Interpretacja sygnału w czasie przez DFT
11
Okresowość widma DFT
Okresowość widma DFT
12
Przyczyna okresowości DFT
Przyczyna okresowości DFT
Dla jakich pulsacji w całym przedziale t"(-" ," ) zachodzi exp(j�1t)=exp(j�2t)?
Tylko dla �2 = �1 , co nie wymusza okresowości widma sygnału ciągłego w czasie.
Dla jakich pulsacji (liczb k) dla całkowitych n w całym przedziale
n"(-" ," ) zachodzi exp(j2Ąk1n/N)=exp(j2Ąk2n/N)?
Dla wszystkich k2 = k1 + rN , gdzie r" C, co powoduje okresowości widma
dyskretnego dla sygnału dyskretnego w czasie (szeregu, ciągu próbek czasowych).
Dla jakich pulsacji ciągłych i dla całkowitych n w całym przedziale
n"(-" ," ) zachodzi exp(j�1nTs)= exp(j�2nTs)  dotyczy tzw. DTFT ?
Dla wszystkich �2 = �1 + r�s = �1 + r2Ą/Ts , co powoduje okresowość widma
ciągłego dla sygnału dyskretnego w czasie .
Przyczyną okresowości widma jest dyskretyzacja w czasie.
Granice sumowania w DFT -1 - komentarz
Dlaczego?
x(n)
N -1
1
-kn
x[n] = X[k]WN , 0 d" n d" N -1
"
N
k=0
xa(t)
1( N -1)m
-kn
x[n] = X[k]WN , 0 d" n d" N -1
"
m
N
k=0
Przykłady DFT
Przykłady DFT
Dyskretny impuls w zerze  �(n) w skończonym przedziale czasu n
1, n = 0
ńł
x[n] =
�ł
0, 1d" n d" N -1
ół
i jego DFT
N -1
kn 0
X [k] = x[n]WN = x[0]WN =1
"
n=0
dla
0 d" k d" N -1
15
Przykłady DFT cd.
Przykłady DFT cd.
Przesunięty impuls
1, n = m
ńł
y[n] =
�ł
0, 0 d" n d" m -1, m +1d" n d" N -1
ół
i jego DFT
dla
N -1
kn km km
Y[k] = y[n]WN = y[m]WN = WN
"
0 d" k d" N -1
n=0
Dla stałej c widmo X(k) jest zerowe, za wyjątkiem prążka X(0) = Nc,
gdyż& ..
16
Przykłady DFT cd.
Przykłady DFT cd.
Ciąg N próbek cosinusa dla o okresie N/r (r-ta harmoniczna)
dla
0 d" n d" N -1
g[n] = cos(2Ąrn/ N), 0 d" r d" N -1
WN = e- j2Ą/ N
Korzystając ze wzoru Eulera, otrzymamy dla przyjętej notacji
1
j2Ąrn / N
g[n] = (e + e- j2Ąrn / N)
2
17
DFT ciągu g(n) obliczamy zatem jako
N -1
N -1 N -1
1
�ł
kn
-(r-k)n (
G[k] = g[n]WN
= WN + WNr+k)n �ł,
" "
" �ł �ł
2�ł n=0
łł
n=0
n=0
a wykorzystując już poprzednio stosowaną tożsamość
N -1
for k - = rN ,
N ,
- ( k - )n ńł
r całkowite
W =
" �ł
N
0, otherwise
ół
n = 0
otrzymujemy
for k = r
ńł
�łN / 2,
G[k] = for k = N - r
�łN / 2,
�ł
0, otherwise
ół
18
Dla N =16 i r =3 wykresy DTFT (linia ciągła) i DFT (prążki o) są następujące
f=13/16 = 0,812 brak, gdyż& ..
jest natomiast minus 0,1875
f=3/16 = 0,1875
f
0,5
2Ą �
Ą
0 1 2 3 4 ��� N k
N/2
Wykresy są przedstawiane w funkcji znormalizowanej częstotliwości f (przy czym 1= fs),
znormalizowanej pulsacji � (przy czym Ts=1s, �s= 2Ą) lub numerów harmonicznych k .
Najczęściej rysowana jest tylko pierwsza połowa wykresu od 0 łącznie z punktem środkowym.
Jeżeli w okresie obserwacji N nie mieści się całkowita liczba okresów
harmonicznej o okresie L próbek, to pulsacja tej harmonicznej wypada
pomiędzy punktami �k = 2Ą k / N.
W sygnale z rys b) istnieje składowa 12/8 = 1.5
20
DFT w zapisie macierzowym
DFT w zapisie macierzowym
Wyrażenie na wartości transformaty X(k) w postaci definicji (1)
możemy zapisać w postaci macierzowej jako
(5)
X = DNx
gdzie odpowiednie wektory i macierz D są zdefiniowane jako
.....
X = [X [0] X[1] X [N -1]]T
.....
x = [x[0] x[1] x[N -1]]T
21
Dla zapisu (5), przekształcenie
odwrotne (4) możemy zapisać
jako
(6)
x = D-1X
N
gdzie przyjęto oznaczenie
k n 0 1 2 . . . N-1
0
1
1
D-1 = D*
N N
N
.
.
.
N-1
22
Tworzenie macierzy DN z wektorów na kole jednostkowym dla N=8
Skok o kąt 2Ą/N = Ą/4
" obrót w kierunku
ujemnym (w prawo)
dla prostego DFT,
w celu konstrukcji
macierzy DN
" obrót w kierunku
dodatnim (w lewo)
dla odwrotnej DFT,
w celu konstrukcji
macierzy DN-1
23
Tworzenie macierzy DN z wektorów na kole jednostkowym cd.
próbki widma - prążki Próbki sygnału
24
Fast Fourier Transform (FFT)
Fast Fourier Transform (FFT)
Idea wykorzystania cząstkowych wyników mnożenia wartości próbek przez elementy macierzy DN
oraz zależności WN(rN + k) = WNk i WN(N/2 + k) = -WNk wynikających z okresowości WNk .
MOTYLEK
X[5] = x0WN0 + x1W85 + x2W810 + x3W815 + x4W820 + x5W825 + x6W830 + x7W835 =
= x0WN0- x1W81 + x2W82 - x3W83 - x4W80 + x5W81 - x6W82 + x7W83
- - - -
- - - -
- - - -
Próbkowanie transformaty DTFT a oryginał
Próbkowanie transformaty DTFT a oryginał
j�
X (e )
" rozważamy nieograniczony ciąg x(n) i jego DTFT w postaci ,
j�
" próbkujemy w N równomiernie rozłożonych punktach
X (e )
dla otrzymując zbiór próbek
�k = 2Ąk/ N
0 d" k d" N -1
j�k
{X (e )},
�k
" rozważamy otrzymany ciąg jako DFT ciągu czasowego y(n),
" wyznaczając IDFT porównujemy otrzymany ciąg y(n) z oryginalnym
x(n).
26
Skoro
"
j�
X (e ) = x[ ]e- j�
"
(7)
=-"
a zatem
j�k
j2Ąk/ N
Y[k] = X (e ) = X (e )
" "
k
= x[ ]e- j2Ąk / N = x[ ]WN
" "
=-" =-"
i z odwrotnej dyskretnej transformaty IDFT otrzymujemy
N -1
1
-kn
y[n] = Y[k]WN
"
N
k=0
27
czyli
N -1 "
1
k -kn
y[n] = x[ ]WN WN
" "
N
k=0 =-"
" N -1
�ł łł
1
-k(n- )
= x[ ]�ł WN
" "
śł
�łN �ł
=-" k=0
a posługując się tożsamością
N -1
1 1, for r = n + mN
- k ( n - r ) ńł
W =
" �ł
N
0, otherwise
N ół
n = 0
otrzymujemy zależność na y(n) w zależności od oryginału x(n) w postaci
"
(8)
y[n] = x[n + mN], 0 d" n d" N -1
"
m=-"
28
Na podstawie (8) wnosimy, że w wyniku dyskretyzacji
j�
X (e )
ciągłego widma DTFT ciągu x(n)
otrzymujemy w wyniku odwrotnej dyskretnej
transformaty DFT ciąg y(n) będący
nieskończoną sumą poprzesuwanych o okres N
ciągów pierwotnych x(n).
Jest to analog zjawiska próbkowania sygnału x(t),
którego widmo jest sumą poprzesuwanych widm
sygnału analogowego (przypomnienie).
29
Z zależności (8) wynika, że jeżeli ciąg x(n) ma ma skończoną liczbę
wyrazów M mniejszą niż liczba próbek widma N, to wypadkowy ciąg
okresowy
"
(8)
y[n] = x[n + mN], 0 d" n d" N -1
"
m=-"
będzie w ramach każdego okresu N powtórzeniem ciągu nieokresowego
(9)
M d" N
dla i .
y[n] = x[n] 0 d" n d" N -1
W przypadku, gdy M > N zachodzi tzw. time-domain aliasing.
30
Time-domain aliasing - przykład
Time-domain aliasing - przykład
Niech
{x[n]} = {0 1 2 3 4 5}
ę!
j�
X (e ) �k = 2Ąk/ 4
Próbkując DTFT w punktach i stosując
czteropunktową IDFT otrzymujemy sekwencję y(n) w postaci
dla
y[n] = x[n]+ x[n + 4]+ x[n - 4] 0 d" n d" 3
czyli
{y[n]} = {4 6 2 3}
ę!
co przedstawiono schematycznie na kolejnym rysunku
31
n -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
x(n) ...... 0 1 2 3 4 5 .......
x(n-4) 0 1 2 3 4 5
x(n+4) 0 1 2 3 4 5
____________________________________________________
y(n) = Ł kolumn 4 6 2 3 4 6 2 3
Ciąg x(n) nie może być odtworzony z ciągu y(n).
32
Inny przykład
y12(n)
y7(n)
33
Kołowe przesunięcie ciągu  splot kołowy
Kołowe przesunięcie ciągu  splot kołowy
Rozpatrzmy ciąg x(n) o długości N zdefiniowany dla .
0 d" n d" N -1
Próbki dla n < 0 i są równe zeru.
n e" N
Definiujemy kołowe przesunięcie ciągu jako operację modulo N
xc[n] = x[)#n - no*#N ]
(10)
no > 0
(jest to tzw. kołowe przesunięcie ciągu w prawo) otrzymujemy
Dla
x[n - no], for no d" n d" N -1
ńł
xc[n] =
�ł
x[N - no + n], for 0 d" n < no
ół
34
Dla przykładu, dla N = 6
n0 = 1 n0 = 4
x[)#n - 1*#6 ] x[)#n - 4*#6 ]
x[n]
35
Inny przykład dla N = 6 i n0 = -2 (jest to tzw. kołowe przesunięcie ciągu w lewo)
36
Splot liniowy ciągów o długości N-próbek dany jest wzorem
(zakłada się, że poza tym przedziałem ciągi przyjmuję zerowe wartości)
N -1
(11)
yL[n] = g[m]h[n - m], 0 d" n d" 2N - 2
"
m=0
Pytanie: Z czego wynika taka długość splotu liniowego?
Splot kołowy (circular convolution) definiuje się jako
N -1
(12)
yC[n] = g[m]h[)#n - m*#N ], 0 d" n d" N -1
"
m=0
i oznacza symbolem
N
y[n] = g[n] h[n]
37
Przykład splotu kołowego
Niech dane będą czteropunktowe ciągi g(n) i h(n) w postaci
{g[n]} = {1 2 0 1}, {h[n]} = {2 2 1 1}
ę! ę!
2 2
h[n]
g[n]
1 1
n
n
0 1 2 3
0 1 2 3
Splot kołowy o długości N = 4 zapisujemy dla jako
0 d" n d" 3
3
4
yC[n] = g[n] h[n] = g[m]h[)#n - m*#4],
"
m=0
38
a kolejne wartości splotu kołowego wynoszą
3
yC[0] = g[m]h[)#-m*#4]
"
m=0
= g[0]h[0] + g[1]h[3] + g[2]h[2] + g[3]h[1]
= (1� 2) + (2�1) + (0�1) + (1� 2) = 6
3
yC[1] = g[m]h[)#1- m*#4]
"
m=0
= g[0]h[1]+ g[1]h[0]+ g[2]h[3]+ g[3]h[2]
= (1� 2) + (2� 2) + (0�1) + (1�1) = 7
2 2
h[n]
g[n]
1 1
itd.
n
n
39
0 1 2 3
0 1 2 3
Inny przykład
Ostatecznie
yC[n]
N-1
x3[n] =
"x [m]x2[((n - m)) ]
1 N
40
m=0
Jeszcze inny przykład
41
Splot liniowy a kołowy
Splot liniowy a kołowy
Rozpatrzmy ciągi o długości L= N / 2 uzupełnione zerami do długości N
42
Obliczanie splotu kołowego metodą DFT
Obliczanie splotu kołowego metodą DFT
Rozpatrzmy ponownie ciągi g(n) i h(n)
2 2
h[n]
g[n]
1 1
n
n
0 1 2 3
0 1 2 3
oraz ich splot kołowy yC(n) w postaci
m
funkcje
0 1 2 3
n y(n)
g(m) 1 2 0 1
0 h (0-m) 2 1 1 2 6
1 h (1-m) 2 2 1 1 7
2 h (2-m) 1 2 2 1 6
3 h (3-m) 1 1 2 2 5
43
Cykliczny rejestr przesuwający
Czteropunktowe DFT ciągów odpowiednio wynoszą
G[k] = g[0]+ g[1]e- j2Ąk/ 4
+ g[2]e- j4Ąk/ 4 + g[3]e- j6Ąk/ 4
=1+ 2e- jĄk/ 2 + e- j3Ąk/ 2, 0 d" k d" 3
G[0] =1+ 2 +1 = 4,
G[1] =1- j2 + j =1- j,
G[2] =1- 2 -1 = -2,
G[3] =1+ j2 - j =1+ j
44
H[k] = h[0]+ h[1]e- j2Ąk/ 4
+ h[2]e- j4Ąk/ 4 + h[3]e- j6Ąk/ 4
= 2 + 2e- jĄk/ 2 + e- jĄk + e- j3Ąk/ 2, 0 d" k d" 3
H[0] = 2 + 2 +1+1 = 6,
H[1] = 2 - j2 -1+ j =1- j,
H[2] = 2 - 2 +1-1 = 0,
H[3] = 2 + j2 -1- j =1+ j
45
Poprzednie transformaty łatwiej obliczyć używając zapisu macierzowego.
�łg[0]łł
1 1 4
�łG[0]łł
�ł1 1 łł �ł łł
�ł1łł
�ł śł
g[1] 1 - j -1 j 1- j
�łG[1]śł
�ł śł 2 �ł śł
�ł śł
= D4 �łg[2]śł = =
�łG[2]śł
�ł śł 0 �ł śł
1 -1 1 -1 �ł śł - 2
�łg[3]śł
�łG[3]śł
�ł śł�ł �ł �ł śł
�ł1śł
j -1 - j�ł
�ł1 �ł1+ j�ł
�ł �ł
�ł �ł
1 1 6
�łH[0]łł �łh[0]łł
�ł1 1 łł �ł łł
�ł2łł
1 - j -1 j 1- j
�ł H[1]śł
�ł śł 2 �ł śł
�ł śł
= D4 �łh[1]śł = =
�łH[2]śł �łh[2]śł
�ł śł 1 �ł śł
1 -1 1 -1 �ł śł 0
�łH[3]śł �łh[3]śł
�ł śł�ł �ł �ł śł
�ł1śł
j -1 - j�ł
�ł1 �ł1+ j�ł
�ł �ł �ł �ł
46
Iloczyn widm
YC[k] = G[k]H[k], 0 d" k d" 3
wynosi
�łYC[0]łł
�łG[0]H[0]łł
24
�ł łł
�ł śł
�ł śł
YC[1]
G[1]H[1] - j2
�ł śł
= =
�łYC[2]śł
�łG[2]H[2]śł
�ł śł
0
�łY [3]śł
�łG[3]H[3]śł
�ł śł
j2
�ł �ł
�ł �ł
�ł �ł
C
a czteropunktowa odwrotna DFT
47
�łyC[0]łł �łYC[0]łł
�ł śł �ł śł
1
yC[1]
= D*�łYC[1]śł
4
�łyC[2]śł
Y [2]
4
�ł �łYC
yC[3]śł [3]śł
�ł �ł �ł �ł
C
1 1 24
�ł1 1 łł�ł łł
�ł6łł
1
1 j -1 - j - j2
�ł śł�ł śł 7
�ł śł
= =
�ł śł�ł śł 6
1 -1 1 -1 0 �ł śł
4
�ł śł�ł śł
�ł5śł
j j2
�ł �ł
�ł1 - j -1 �ł�ł �ł
48
Splot liniowy wyznaczany metodą DFT
Splot liniowy wyznaczany metodą DFT
" Niech g[n] i h[n] będą ciągami o długościach
odpowiednio N i M próbek
" Splot liniowy ma długość
L = N + M -1
" Zdefiniujmy odpowiednie wydłużone sekwencje
uzupełnione zerami do długości L próbek
g[n], 0 d" n d" N -1
ńł
ge[n] =
�ł
0, N d" n d" L -1
ół
ńłh[n], 0 d" n d" M -1
he[n] =
�ł
0, M d" n d" L -1
ół
49
wtedy
yL[n] = g[n] h[n] = yC[n] = g[n] L h[n]
*
e
e
Zero-padding
g[n]
ge[n]
(N+M-1)-
with
point DFT
Length-N
yL[n]
(M-1) zeros
(N+M-1)-
�
point IDFT
Zero-padding
h[n]
he[n]
(N+M-1)-
with
point DFT
Length-
Length-M
(N +M -1)
(N-1) zeros
Problem  w przypadku liczenia tą metodą funkcji korelacji
należy odpowiednio przyporządkować próbki
z tablicy IDFT odpowiednim wartościom argumentu m
korelacji  wartości dla m e" 0 leżą prawidłowo, dla m< 0 znajdują
się na pozycji (m+L)
(dla splotu wszystkie próbki są prawidłowo ułożone) - przykład.
50
Splot liniowy metodą DFT  przykład
Splot liniowy metodą DFT  przykład
Dane są ciągi x(n) o długości N =2 i y(n) długości M =3.
Ich splot linowy wyznaczony w dziedzinie czasowej o długości L=N+M-1 = 4
przedstawiono poniżej.
m
ciągi
n -2 -1 0 1 2 3 x(n)" y(n)
"
"
"
x (m) 1 1
0 y (0-m) 2 2 1 1
1 y (1-m) 2 2 1 3
2 y (2-m) 2 2 1 4
3 y (3-m) 2 2 1 2
51
Wyznaczmy teraz DFT ciągów g(n) i h(n) uzupełnionych zerami do długości
splotu liniowego L=4 i oznaczonych jako xe(n) i ye(n).
Xe (k)
Ye (k)
52
Splot liniowy (równy kołowemu) wyznaczamy jako
IDFT [Xe(k)Ye(k)]
=
Wartości próbek otrzymanego wektora odpowiadają wartościom splotu liniowego x y.
"
"
"
"
53
Estymator funkcji korelacji wyznaczany metodą DFT
Estymator funkcji korelacji wyznaczany metodą DFT
Definicje korelacji wzajemnej (przypomnienie):
korelacja sygnału x(n) z y(n)
(13a)
Rxy (m) = E[x(n+m) y(n)] = E(x(n) y(n-m)]
korelacja sygnału y(n) z x(n)
(13b)
Ryx (m) = E[y(n+m) x(n)] = E[y(n) x(n-m)]
Zajmiemy się estymatą korelacji w postaci (13b), rzadziej prezentowaną
w podręcznikach, a wykorzystywaną przecież do identyfikacji odpowiedzi
impulsowej układu liniowego przy pobudzeniu szumem białym.
Estymatą odpowiedzi impulsowej g(n) jest wtedy
estymata korelacji wzajemnej
sygnału na wyjściu układu y(n) z sygnałem wejściowym u(n).
54
Estymator funkcji korelacji wyznaczany metodą DFT cd.
Estymator funkcji korelacji wyznaczany metodą DFT cd.
Estymator obciążony korelacji wzajemnej lub skrośnej (13b)
ciągów y(n) z x(n) o długościach równych N próbek dany jest wzorem
N-m-1
1
__
x(n) y(n + m) dla m e" 0 ( y przesuwane w lewo)
Ł
N
n=0
N-1
1
__
dla m < 0 ( y przesuwane w prawo)
x(n) y(n+m)
Ł
N
n=ćłmćł
lub najczęściej
m
y(n) �! y(n)
�!
�!
�!
N-1
'"
'"
'"
'"
1
__
x(n) y(n+m)
Ryx = dla -(N-1) d" m d" (N-1) (14)
Ł
N
n=0
kiedy to zakłada się, że brak próbki y(i + m) dla występującej w sumie (14)
kolejnej próbki x(i) oznacza, że jest ona równa zeru.
55
Bez względu na współczynnik przed sumą w (13)  decydujący o obciążeniu
estymaty, zawsze należy wyznaczyć (2N-1) razy sumę
N-1 N-1
x(n) y(n+m) = y(n) x(n - m) (15)
Cyx(m) =
Ł Ł
n=0 n=0
Wyznaczenie wartości (14) w dziedzinie czasu charakteryzuje się
złożonością obliczeniową O(N2). Wyznaczenie wartości (14) w dziedzinie
widmowej poprzez zastosowanie DFT (a właściwie jej szybkiego algorytmu
Fast Fourier Transform (FFT) obniża złożoność do postaci Nlog2N.
Porównując (15) ze wzorem na splot liniowy (16)
N-1
(16)
y(m) x(m - n)
sL(m) = y(m)" x(m) =
Ł
n=0
otrzymujemy bardzo wygodną obliczeniowo zależność
(17a)
Cyx(m) = y(m)" x(-m)
oraz analogicznie
(17b)
x(m)" y(-m)
Cxy(m) =
56
Obliczenie wartości (16) w dziedzinie widmowej odbywa się według procedury
Cyx(m) = IDFT [Ye(k) Xe*(k)] , (18)
Ye(k)] X* (k)
gdzie i oznaczają odpowiednio DFT uzupełnionego zerami
e
ciągu y(n) i sprzężoną DFT uzupełnionego zerami ciągu x(n), na przykład
jak na rysunku poniżej (uzupełnienie do długości L = M + N  1 = 4)
M =2 L = 4
N =3 L = 4
57
Estymator funkcji korelacji metodą DFT - przykład
Estymator funkcji korelacji metodą DFT - przykład
Estymaty korelacji (14) wyznaczana w dziedzinie czasu wynosi
n
ciągi
przesunięcie
m -2 -1 0 1 2 3
c yx (m)
x (n)
1 1
w prawo -1 y (n-1)
1 2 2 1
bez 0 y (n)
1 2 2 3
w lewo 1 y (n+1)
1 2 2 4
w lewo 2 y (n+2)
1 2 2 2
Natomiast dyskretne transformaty ciągów ye(n) i xe(n) są równe
X* (k)
Ye (k) Xe (k)
e
58
Ostatecznie
IDFT [Ye(k) Xe*(k)]
=
W kolumnie kolejno występują: cyx(0) = 3
cyx(1) = 4
cyx(2) = 2
cyx(-1) = IDFT(L-1) = IDFT(3) = 1 59
DFT iloczynu ciągów  splot kołowy widm DFT
DFT iloczynu ciągów  splot kołowy widm DFT
Rozpatrzmy iloczyn ciągów g(n) i h(n) w postaci
2 2
h[n]
g[n]
1 1
n
n
0 1 2 3
0 1 2 3
i ich iloczyn y(n) = g(n)h(n) , przedstawione w Tab.1
Tab. 1 Wartości próbek ciągów i ich iloczynu
n
0 1 2 3
g(n)
1 2 0 1
h(n)
2 2 1 1
y(n)
2 4 0 1
60
Wyznaczmy splot kołowy uprzednio wyznaczonych widm G(k) i H(k)
zgodnie ze wzorem definiującym splot kołowy widm w postaci
m =N-1
1
__
Y(k) = G(m) H[(k-m)N ] .
Ł
N
m =0
Dla N = 4 otrzymujemy następującą tabelkę wyznaczania splotu
kołowego widm G(k) i H(k) oraz wynik IDFT ze splotu, równy y(n).
61
m
funkcje
0 1 2 3
k Y(k)
G(m) 4 1 - j -2 1 + j
0 H (0-m)|4 6 1 + j 0 1 - j 7
1 H (1-m)|4 1 - j 6 1 + j 0 2 - 3j
2 H (2-m)|4 0 1 - j 6 1 + j -3
3 H (3-m)|4 1 + j 0 1 - j 6 2 + 3j
Transformata odwrotna IDFT z wyniku splotu kołowego widm Y(k) wynosi
Otrzymany wynik równy jest próbkom iloczynu y(n)=g(n)h(n) z tabeli 1.
62
Podstawowe własności DFT
Podstawowe własności DFT
63