Aufgaben:Aufgabe 5.5: Fast-Fouriertransformation: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID1177__Sig_A_5_5_neu.png|right|FFT-Algorithmus]]
+
[[Datei:P_ID1177__Sig_A_5_5_neu.png|right|frame|FFT-Algorithmus für  $N=8$]]
  
Die Grafik zeigt den Signalflussplan der DFT für $N = 8$. Aus den Zeitkoeffizienten $d(0), ... , d(7)$ werden die dazugehörigen Spektralkoeffizienten $D(0), ... , D(7)$ ermittelt. Für diese gilt mit $0 ≤ μ ≤ 7$:
+
Die Grafik zeigt den Signalflussplan der Fast-Fouriertransformation  $\rm (FFT)$  für  $N = 8$. 
 +
 
 +
Aus den Zeitkoeffizienten  $d(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}, d(7)$  werden die dazugehörigen Spektralkoeffizienten  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  ermittelt. Für diese gilt mit  $0 ≤ μ ≤ 7$:
 
   
 
   
$$D(\mu) =  \frac{1}{N}\cdot \sum_{\nu = 0 }^{N-1}
+
:$$D(\mu) =  \frac{1}{N}\cdot \sum_{\nu = 0 }^{N-1}
  d(\nu) \cdot  {w}^{\nu \hspace{0.03cm} \cdot
+
  d(\nu) \cdot  {w}^{\hspace{0.03cm}\nu \hspace{0.05cm} \cdot
 
  \hspace{0.05cm}\mu}\hspace{0.05cm},$$
 
  \hspace{0.05cm}\mu}\hspace{0.05cm},$$
  
wobei der komplexe Drehfaktor $w = \text{exp}^{\text{j}2\pi /N}$ zu verwenden ist, also $w = \text{exp}^{\text{j}\pi /4}$ für $N = 8$.
+
wobei der komplexe Drehfaktor  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot
 +
\hspace{0.05cm}2\pi /N}$  zu verwenden ist, also  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot
 +
\hspace{0.05cm}\pi /4}$  für  $N = 8$.
 +
 
 +
*Am Eingang wird die alternierende $±1$–Folge  $\langle\hspace{0.05cm} d(ν)\hspace{0.05cm}\rangle$  angelegt.
 +
*Nach der Bitumkehroperation ergibt sich daraus die Folge  $\langle \hspace{0.05cm}b(\kappa)\hspace{0.05cm}\rangle$.
 +
 
 +
 
 +
Es gilt  $b(κ) = d(ν)$, wenn man  $ν$  als Dualzahl darstellt und die resultierenden drei Bit als  $κ$  in umgekehrter Reihenfolge geschrieben werden. Beispielsweise
 +
* folgt aus  $ν = 1$  $($binär  $001)$  die Position  $κ = 4$  $($binär  $100)$,
 +
* verbleibt  $d(2)$  an der gleichen Position  $2$  $($binär  $010)$.
 +
 
 +
 
 +
Der eigentliche FFT–Algorithmus geschieht für das Beispiel  $N = 8$  in  $\log_2 N = 3$  Stufen, die mit  $L = 1$,  $L =2$  und  $L = 3$  bezeichnet werden.  Weiter gilt:
 +
* In jeder Stufe sind vier Basisoperationen – so genannte '''Butterflies''' – durchzuführen.
 +
* Die Werte am Ausgang der ersten Stufe werden in dieser Aufgabe mit&nbsp; $X(0),\hspace{0.03cm}\text{...} \hspace{0.1cm} , X(7)$&nbsp; bezeichnet, <br>die der zweiten mit&nbsp; $Y(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}  , Y(7)$.
 +
* Nach der dritten und letzten Stufe sind alle Werte noch durch&nbsp; $N$&nbsp; zu dividieren.&nbsp; Hier liegt dann das endgültige Ergebnis&nbsp; $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}  , D(7)$&nbsp; vor.
 +
 
  
Am Eingang wird die alternierende $±1$–Folge $\langle d(ν)\rangle$ angelegt. Nach der Bitumkehroperation ergibt sich daraus die Folge $\langle b(\kappa)\rangle$.
 
  
Es gilt $b(κ) = d(ν)$, wenn man $ν$ als Dualzahl darstellt und die resultierenden drei Bit als $κ$ in umgekehrter Reihenfolge geschrieben werden. Beispielsweise
 
* folgt aus $ν = 1$ (binär 001) die Position $κ = 4$ (binär 100),
 
* verbleibt $d(2)$ an der gleichen Position $2$ (binär 010).
 
  
 +
''Hinweis:''
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Signaldarstellung/Fast-Fouriertransformation_(FFT)|Fast-Fouriertransformation (FFT)]].
 +
  
Der eigentliche FFT–Algorithmus geschieht für das Beispiel $N = 8$ in $\log_2 N = 3$ Stufen, die mit $L = 1$, $2$ und $3$ bezeichnet werden. Weiter gilt:
 
* In jeder Stufe sind vier Basisoperationen – so genannte ''Butterflies'' – durchzuführen.
 
* Die Werte am Ausgang der ersten Stufe werden in dieser Aufgabe mit $X(0), ... , X(7)$ bezeichnet, die der zweiten mit $Y(0), ... , Y(7)$.
 
* Nach der dritten und letzten Stufe sind alle Werte noch durch $N$ zu dividieren.
 
  
''Hinweise:''
 
*Die Aufgabe gehört zum  Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)|Fast-Fouriertransformation (FFT)]].
 
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 
  
 
===Fragebogen===
 
===Fragebogen===
Zeile 33: Zeile 44:
 
<quiz display=simple>
 
<quiz display=simple>
  
{Berechnen Sie den DFT–Koeffizienten $D(3)$.
+
{Berechnen Sie den DFT–Koeffizienten&nbsp; $D(\mu=3)$.
 
|type="{}"}
 
|type="{}"}
$D(3) =$ { 0. }
+
$D(\mu=3) \ = \ $ { 0. }
  
{Berechnen Sie den DFT–Koeffizienten $D(4)$.
+
{Berechnen Sie den DFT–Koeffizienten&nbsp; $D(\mu=4)$.
 
|type="{}"}
 
|type="{}"}
$D(4) =$ { 1 3% }
+
$D(\mu=4) \ = \ $ { 1 3% }
  
{Ermitteln Sie die Ausgangswerte $X(0), ... , X(7)$ der ersten Stufe. Welche der folgenden Aussagen sind zutreffend?
+
{Ermitteln Sie die Ausgangswerte&nbsp; $X(0)$, ... , $X(7)$&nbsp; der ersten Stufe.&nbsp; Welche der folgenden Aussagen sind zutreffend?
 
|type="[]"}
 
|type="[]"}
- Alle Werte mit geradzahligen Indizes sind gleich $2$.
+
- Alle&nbsp; $X$&ndash;Werte mit geradzahligen Indizes sind gleich&nbsp; $2$.
+ Alle Werte mit ungeradzahligen Indizes sind gleich $0$.
+
+ Alle&nbsp; $X$&ndash;Werte mit ungeradzahligen Indizes sind gleich&nbsp; $0$.
  
{Ermitteln Sie die Ausgangswerte $Y(0), ... , Y(7)$ der zweiten Stufe. Geben Sie zur Kontrolle die Werte $Y(0)$und $Y(4)$ ein.
+
{Ermitteln Sie die Ausgangswerte&nbsp; $Y(0)$, ... , $Y(7)$&nbsp; der zweiten Stufe.&nbsp; Geben Sie zur Kontrolle die Werte&nbsp; $Y(0)$&nbsp; und&nbsp; $Y(4)$&nbsp; ein.
 
|type="{}"}
 
|type="{}"}
$Y(0) =$ { 4 3% }
+
$Y(0) \ = \ $ { 4 3% }
$Y(4) =$ { -4.12--3.88 }
+
$Y(4) \ = \ $ { -4.12--3.88 }
  
{Berechnen Sie alle $N$ Spektralwerte $D(\mu)$, insbesondere
+
{Berechnen Sie alle&nbsp; $N$&nbsp; Spektralwerte&nbsp; $D(\mu)$, insbesondere
 
|type="{}"}
 
|type="{}"}
$D(\mu = 4) =$ { 4 3% }
+
$D(\mu = 3) \ = \ $ { 0. 3% }
$D(\mu \neq 4) =$ { 0. }
+
$D(\mu = 4) \ = \ $ { 1 }
  
{Welche Spektralkoeffizienten würden sich für $d(ν = 4) = 1$ und $d(ν \neq 4) = 0$ ergeben? Geben Sie zur Kontrolle die Werte $D(3)$ und $D(4)$ ein:
+
{Welche Spektralkoeffizienten würden sich für&nbsp; $d(ν = 4) = 1$&nbsp; und&nbsp; $d(ν \neq 4) = 0$&nbsp; ergeben? <br>Geben Sie zur Kontrolle die Werte&nbsp; $D(\mu=3)$&nbsp; und&nbsp; $D(\mu=4)$&nbsp; ein.
 
|type="{}"}
 
|type="{}"}
$D(\mu = 3) =$ { -1.03--0.97 }
+
$D(\mu = 3) \ = \ $ { -1.03--0.97 }
$D(\mu = 4) =$ { 1 3% }
+
$D(\mu = 4) \ = \ $ { 1 3% }
  
  
Zeile 67: Zeile 78:
  
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.''' Entsprechend der auf dem Angabenblatt gegebenen allgemeinen DFT–Gleichung gilt mit $w = \text{exp}(–\text{j}\pi /4)$ unter Berücksichtigung der alternierenden Zeitkoeffizienten:
+
'''(1)'''&nbsp; Entsprechend der auf dem Angabenblatt gegebenen allgemeinen DFT–Gleichung gilt mit&nbsp; $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot
 +
\hspace{0.05cm}\pi /4}$&nbsp; unter Berücksichtigung der alternierenden Zeitkoeffizienten:
 
   
 
   
$$\begin{align*}8 \cdot D(3) & =    w^0 - w^3 + w^6- w^9+ w^{12}- w^{15}+ w^{18}-
+
:$$8 \cdot D(3) =    w^0 - w^3 + w^6- w^9+ w^{12}- w^{15}+ w^{18}-
w^{21} \\ & =    w^0 - w^3 + w^2- w^1+ w^{4}- w^{7}+ w^{6}-
+
w^{21} =    w^0 - w^3 + w^2- w^1+ w^{4}- w^{7}+ w^{6}-
w^{5}\hspace{0.05cm}.\end{align*}$$
+
w^{5}\hspace{0.05cm}.$$
  
Hierbei ist berücksichtigt, dass aufgrund der Periodizität $w_9 = w_1$, $w_{12} = w_4$, $w_{15} = w_7$, $w_{18} = w_2$ und $w_{21} = w_5$ ist. Nach Umsortieren gilt in gleicher Weise
+
*Hierbei ist berücksichtigt, dass aufgrund der Periodizität&nbsp; $w_9 = w_1$,&nbsp; $w_{12} = w_4$,&nbsp; $w_{15} = w_7$,&nbsp; $w_{18} = w_2$&nbsp; und&nbsp; $w_{21} = w_5$&nbsp; ist.  
 +
*Nach Umsortieren gilt in gleicher Weise:
 
   
 
   
$$\begin{align*} 8 \cdot D(3) & =  (w^0 + w^4) - (w^1 + w^5)+ (w^2 + w^6) - (w^3 + w^7) = \\
+
:$$8 \cdot D(3) =  (w^0 + w^4) - (w^1 + w^5)+ (w^2 + w^6) - (w^3 + w^7) =  (1 + w + w^2+ w^3) \cdot (w^0 + w^4)\hspace{0.05cm}.$$
& =  (1 + w + w^2+ w^3) \cdot (w^0 + w^4)\hspace{0.05cm}.\end{align*}$$
+
 
 +
*Wegen&nbsp; $w_0 = 1$&nbsp; und&nbsp; $w_4 = \text{e}^{-\text{j}\pi } = \hspace{0.08cm} - \hspace{-0.08cm}1$&nbsp; erhält man somit&nbsp; $\underline {D(\mu=3) = 0}$.
  
Wegen $w_0 = 1$ und $w_4 = \text{exp}(–\text{j} \cdot \pi) = –1$ erhält man somit $D$(3) = 0.
 
  
'''2.''' In analoger Weise zu 1) ergibt sich nun:
+
'''(2)'''&nbsp; In analoger Weise zur Teilaufgabe&nbsp; '''(1)'''&nbsp; ergibt sich nun:
 
   
 
   
$$\begin{align*} 8 \cdot D(4) & =    w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+
+
:$$ 8 \cdot D(4) =    w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+
w^{24}- w^{28}= \\ & =  4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm}
+
w^{24}- w^{28}=  4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm}
\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(4) = 1}\hspace{0.05cm}.\end{align*}$$
+
\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(\mu=4) = 1}\hspace{0.05cm}.$$
 +
 
  
[[Datei:P_ID1178__Sig_A_5_5c_neu.png|250px|right|Beispiel für den FFT-Algorithmus (ML zu Aufgabe A5.5)]]
+
[[Datei:P_ID1178__Sig_A_5_5c_neu.png|right|frame|Beispiel für den FFT-Algorithmus]]
 +
'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
*Der Term&nbsp; $w^0 = 1$&nbsp; muss nicht berücksichtigt werden.
 +
*Alle Ausgangswerte mit ungeraden Indizes sind durch die Subtraktion zweier identischer Eingangswerte Null.
 +
*Die erste Aussage trifft nicht zu: &nbsp; Es gilt&nbsp; $X(0) = X(2) = +2$&nbsp; und&nbsp; $X(4) = X(6) = - 2$.  
  
'''3.''' Der Term $w_0$ = 1 muss nicht berücksichtigt werden. Alle Ausgangswerte mit ungeraden Indizes sind somit durch die Subtraktion zweier identischer Eingangswerte gleich 0.
 
Die erste Aussage trifft dagegen nicht zu: Es gilt $X$(0) = $X$(2) = +2 und $X$(4) = $X$(6) = –2  ⇒  Lösungsvorschlag 2.
 
  
  
'''4.''' Auf die Multiplikation mit $w_2$ = –j kann verzichtet werden, da im Signalflussplan die entsprechenden Eingangsgrößen 0 sind.
+
'''(4)'''&nbsp; Auf die Multiplikation mit&nbsp; $w^{2} = -{\rm j}$&nbsp; kann verzichtet werden, da im Signalflussplan die entsprechenden Eingangsgrößen Null sind.
Man erhält somit $Y$(0) = 4 und $Y$(4) = –4. Alle anderen Werte sind 0.  
+
*Man erhält somit&nbsp; $Y(0) \;\underline{= 4}$&nbsp; und&nbsp; $Y(4) \;\underline{= - \hspace{-0.03cm}4}$.
 +
*Alle anderen Werte sind Null.  
  
  
'''5.''' Wegen $Y$(5) = $Y$(6) =$Y$(7) = 0 spielen auch in der dritten Stufe die Multiplikationen mit $w$, $w_2$ und $w_3$ keine Rolle. Alle Spektralkoeffizienten $D(\mu)$ ergeben sich zu 0 mit Ausnahme von
+
 
 +
'''(5)'''&nbsp; Wegen&nbsp; $Y(5) = Y(6) =Y(7) = 0$&nbsp; spielen auch in der dritten Stufe die Multiplikationen mit&nbsp; $w$,&nbsp; $w^2$&nbsp; und&nbsp; $w^3$&nbsp; keine Rolle.&nbsp; Alle Spektralkoeffizienten&nbsp; $D(\mu)$&nbsp; ergeben sich deshalb zu Null mit Ausnahme von
 
   
 
   
$$\hspace{0.15 cm}\underline{D(4)} =  {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1}
+
:$$\hspace{0.15 cm}\underline{D(\mu= 4)} =  {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1}
 +
\hspace{0.05cm},$$
 +
:$$\hspace{0.15 cm}\underline{D(\mu =3)} =  D(\mu \ne 4) \hspace{0.15 cm}\underline{= 0}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Dieses Ergebnis stimmt mit den Ergebnissen aus 1) und 2) überein.  
+
Dieses Ergebnis stimmt mit den Ergebnissen aus&nbsp; '''(1)'''&nbsp; und&nbsp; '''(2)'''&nbsp; überein.
 +
 
 +
 
 +
 
 +
'''(6)'''&nbsp; Nachdem sowohl die Zeitkoeffizienten&nbsp; $d(ν)$&nbsp; als auch alle Spektralkoeffizienten&nbsp; $D(\mu)$&nbsp; rein reell sind, besteht kein Unterschied zwischen der FFT und der IFFT.
 +
*Das bedeutet gleichzeitig:&nbsp; Die Eingangs– und Ausgangswerte können vertauscht werden.
  
'''6.''' Nachdem sowohl die Zeitkoeffizienten $d(ν)$ als auch alle Spektralkoeffizienten $D(\mu)$ rein reell sind, besteht kein Unterschied zwischen der FFT und der IFFT. Das bedeutet gleichzeitig: die Eingangs– und Ausgangswerte können vertauscht werden.
+
*Die Teilaufgabe&nbsp; '''(5)'''&nbsp; hat das folgende Ergebnis geliefert:
Die Teilaufgabe 5) hat das folgende Ergebnis geliefert:
 
 
   
 
   
$$d({\rm gerades}\hspace{0.15cm}\nu) =  +1, \hspace{0.2cm}d({\rm
+
:$$d({\rm gerades}\hspace{0.15cm}\nu) =  +1, \hspace{0.2cm}d({\rm
ungerades}\hspace{0.15cm}\nu)=  -1 \hspace{0.3cm} \Rightarrow
+
ungerades}\hspace{0.15cm}\nu)=  -1$$
 +
:$$\Rightarrow
 
\hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$
 
\hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$
  
Durch Vertauschen der Eingangs– und Ausgangswerte kommt man zur Aufgabenstellung von (6):
+
*Durch Vertauschen der Eingangs– und Ausgangswerte kommt man zur Aufgabenstellung&nbsp; '''(6)''':
 
   
 
   
$$d(\nu = 4)= 1, \hspace{0.2cm}d(\nu \ne 4)= 0 \hspace{0.3cm}
+
:$$d(\nu = 4)= 1, \hspace{0.2cm}d(\nu \ne 4)= 0 \hspace{0.3cm}
 
\Rightarrow \hspace{0.3cm}D({\rm gerades}\hspace{0.15cm}\mu) = +1,
 
\Rightarrow \hspace{0.3cm}D({\rm gerades}\hspace{0.15cm}\mu) = +1,
 
\hspace{0.2cm}D({\rm ungerades}\hspace{0.15cm}\mu)=  -1
 
\hspace{0.2cm}D({\rm ungerades}\hspace{0.15cm}\mu)=  -1
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Insbesondere würde sich $D$(3) = –1 und D(4) = +1 ergeben.
+
*Insbesondere ergibt sich sich&nbsp; $D(\mu=3) \; \underline{= -1}$&nbsp; und&nbsp; $D(\mu=4) \; \underline{= +1}$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
 
__NOEDITSECTION__
 
__NOEDITSECTION__
[[Category:Aufgaben zu Signaldarstellung|^5. Zeit- und frequenzdisktrete Signaldarstellung^]]
+
[[Category:Aufgaben zu Signaldarstellung|^5. Zeit- und frequenzdiskrete Signaldarstellung^]]

Aktuelle Version vom 21. Mai 2021, 17:03 Uhr

FFT-Algorithmus für  $N=8$

Die Grafik zeigt den Signalflussplan der Fast-Fouriertransformation  $\rm (FFT)$  für  $N = 8$. 

Aus den Zeitkoeffizienten  $d(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}, d(7)$  werden die dazugehörigen Spektralkoeffizienten  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  ermittelt. Für diese gilt mit  $0 ≤ μ ≤ 7$:

$$D(\mu) = \frac{1}{N}\cdot \sum_{\nu = 0 }^{N-1} d(\nu) \cdot {w}^{\hspace{0.03cm}\nu \hspace{0.05cm} \cdot \hspace{0.05cm}\mu}\hspace{0.05cm},$$

wobei der komplexe Drehfaktor  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot \hspace{0.05cm}2\pi /N}$  zu verwenden ist, also  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot \hspace{0.05cm}\pi /4}$  für  $N = 8$.

  • Am Eingang wird die alternierende $±1$–Folge  $\langle\hspace{0.05cm} d(ν)\hspace{0.05cm}\rangle$  angelegt.
  • Nach der Bitumkehroperation ergibt sich daraus die Folge  $\langle \hspace{0.05cm}b(\kappa)\hspace{0.05cm}\rangle$.


Es gilt  $b(κ) = d(ν)$, wenn man  $ν$  als Dualzahl darstellt und die resultierenden drei Bit als  $κ$  in umgekehrter Reihenfolge geschrieben werden. Beispielsweise

  • folgt aus  $ν = 1$  $($binär  $001)$  die Position  $κ = 4$  $($binär  $100)$,
  • verbleibt  $d(2)$  an der gleichen Position  $2$  $($binär  $010)$.


Der eigentliche FFT–Algorithmus geschieht für das Beispiel  $N = 8$  in  $\log_2 N = 3$  Stufen, die mit  $L = 1$,  $L =2$  und  $L = 3$  bezeichnet werden.  Weiter gilt:

  • In jeder Stufe sind vier Basisoperationen – so genannte Butterflies – durchzuführen.
  • Die Werte am Ausgang der ersten Stufe werden in dieser Aufgabe mit  $X(0),\hspace{0.03cm}\text{...} \hspace{0.1cm} , X(7)$  bezeichnet,
    die der zweiten mit  $Y(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , Y(7)$.
  • Nach der dritten und letzten Stufe sind alle Werte noch durch  $N$  zu dividieren.  Hier liegt dann das endgültige Ergebnis  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  vor.



Hinweis:



Fragebogen

1

Berechnen Sie den DFT–Koeffizienten  $D(\mu=3)$.

$D(\mu=3) \ = \ $

2

Berechnen Sie den DFT–Koeffizienten  $D(\mu=4)$.

$D(\mu=4) \ = \ $

3

Ermitteln Sie die Ausgangswerte  $X(0)$, ... , $X(7)$  der ersten Stufe.  Welche der folgenden Aussagen sind zutreffend?

Alle  $X$–Werte mit geradzahligen Indizes sind gleich  $2$.
Alle  $X$–Werte mit ungeradzahligen Indizes sind gleich  $0$.

4

Ermitteln Sie die Ausgangswerte  $Y(0)$, ... , $Y(7)$  der zweiten Stufe.  Geben Sie zur Kontrolle die Werte  $Y(0)$  und  $Y(4)$  ein.

$Y(0) \ = \ $

$Y(4) \ = \ $

5

Berechnen Sie alle  $N$  Spektralwerte  $D(\mu)$, insbesondere

$D(\mu = 3) \ = \ $

$D(\mu = 4) \ = \ $

6

Welche Spektralkoeffizienten würden sich für  $d(ν = 4) = 1$  und  $d(ν \neq 4) = 0$  ergeben?
Geben Sie zur Kontrolle die Werte  $D(\mu=3)$  und  $D(\mu=4)$  ein.

$D(\mu = 3) \ = \ $

$D(\mu = 4) \ = \ $


Musterlösung

(1)  Entsprechend der auf dem Angabenblatt gegebenen allgemeinen DFT–Gleichung gilt mit  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot \hspace{0.05cm}\pi /4}$  unter Berücksichtigung der alternierenden Zeitkoeffizienten:

$$8 \cdot D(3) = w^0 - w^3 + w^6- w^9+ w^{12}- w^{15}+ w^{18}- w^{21} = w^0 - w^3 + w^2- w^1+ w^{4}- w^{7}+ w^{6}- w^{5}\hspace{0.05cm}.$$
  • Hierbei ist berücksichtigt, dass aufgrund der Periodizität  $w_9 = w_1$,  $w_{12} = w_4$,  $w_{15} = w_7$,  $w_{18} = w_2$  und  $w_{21} = w_5$  ist.
  • Nach Umsortieren gilt in gleicher Weise:
$$8 \cdot D(3) = (w^0 + w^4) - (w^1 + w^5)+ (w^2 + w^6) - (w^3 + w^7) = (1 + w + w^2+ w^3) \cdot (w^0 + w^4)\hspace{0.05cm}.$$
  • Wegen  $w_0 = 1$  und  $w_4 = \text{e}^{-\text{j}\pi } = \hspace{0.08cm} - \hspace{-0.08cm}1$  erhält man somit  $\underline {D(\mu=3) = 0}$.


(2)  In analoger Weise zur Teilaufgabe  (1)  ergibt sich nun:

$$ 8 \cdot D(4) = w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+ w^{24}- w^{28}= 4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(\mu=4) = 1}\hspace{0.05cm}.$$


Beispiel für den FFT-Algorithmus

(3)  Richtig ist der Lösungsvorschlag 2:

  • Der Term  $w^0 = 1$  muss nicht berücksichtigt werden.
  • Alle Ausgangswerte mit ungeraden Indizes sind durch die Subtraktion zweier identischer Eingangswerte Null.
  • Die erste Aussage trifft nicht zu:   Es gilt  $X(0) = X(2) = +2$  und  $X(4) = X(6) = - 2$.


(4)  Auf die Multiplikation mit  $w^{2} = -{\rm j}$  kann verzichtet werden, da im Signalflussplan die entsprechenden Eingangsgrößen Null sind.

  • Man erhält somit  $Y(0) \;\underline{= 4}$  und  $Y(4) \;\underline{= - \hspace{-0.03cm}4}$.
  • Alle anderen Werte sind Null.


(5)  Wegen  $Y(5) = Y(6) =Y(7) = 0$  spielen auch in der dritten Stufe die Multiplikationen mit  $w$,  $w^2$  und  $w^3$  keine Rolle.  Alle Spektralkoeffizienten  $D(\mu)$  ergeben sich deshalb zu Null mit Ausnahme von

$$\hspace{0.15 cm}\underline{D(\mu= 4)} = {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1} \hspace{0.05cm},$$
$$\hspace{0.15 cm}\underline{D(\mu =3)} = D(\mu \ne 4) \hspace{0.15 cm}\underline{= 0} \hspace{0.05cm}.$$

Dieses Ergebnis stimmt mit den Ergebnissen aus  (1)  und  (2)  überein.


(6)  Nachdem sowohl die Zeitkoeffizienten  $d(ν)$  als auch alle Spektralkoeffizienten  $D(\mu)$  rein reell sind, besteht kein Unterschied zwischen der FFT und der IFFT.

  • Das bedeutet gleichzeitig:  Die Eingangs– und Ausgangswerte können vertauscht werden.
  • Die Teilaufgabe  (5)  hat das folgende Ergebnis geliefert:
$$d({\rm gerades}\hspace{0.15cm}\nu) = +1, \hspace{0.2cm}d({\rm ungerades}\hspace{0.15cm}\nu)= -1$$
$$\Rightarrow \hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$
  • Durch Vertauschen der Eingangs– und Ausgangswerte kommt man zur Aufgabenstellung  (6):
$$d(\nu = 4)= 1, \hspace{0.2cm}d(\nu \ne 4)= 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}D({\rm gerades}\hspace{0.15cm}\mu) = +1, \hspace{0.2cm}D({\rm ungerades}\hspace{0.15cm}\mu)= -1 \hspace{0.05cm}.$$
  • Insbesondere ergibt sich sich  $D(\mu=3) \; \underline{= -1}$  und  $D(\mu=4) \; \underline{= +1}$.