Frage zur diskreten Fourier-Transformation (nicht FFT)

[Manfred M. (bittbeisser)]

Ich habe jetzt meine Hardcover Ausgabe des DSP-Guides bekommen und 
experimentiere gerade mit den einfachen Beispielen von DFT und IDFT (in 
dem Buch als table 8-1 und 8-2). Natürlich habe ich das erstmal in C 
übersetzt.

Eine wichtige Sache habe ich aber noch nicht verstanden bzw. in dem Buch 
nicht gefunden.

Ist es richtig, dass die Anzahl der Eingangssamples immer eine gerade 
Zahl sein muss? Bei allen Beispielen ist das so, aber es wird (bisher) 
nirgends explizit erwähnt. In einem ordentlichen Programm müsste ich bei 
den Eingabedaten diese Bedingung ggf. ja überprüfen.

[C Programmierer (Gast)]

Nein, die Anzahl der Samples kann auch ungerade sein.

[Manfred M. (bittbeisser)]

Das habe ich befürchtet und dadurch bekomme ich ein Problem.

Wie viele komplexe Ergebniswerte bekomme ich dann? Es heisst ja (N/2)+1 
aber es gibt keine halben Abtastwerte.

[C Programmierer (Gast)]

Dann hast du eine andere Formel als ich und als wikipedia.

Aus n Abtastwerten kommen n Frequenzen raus. Aber vielleicht benutzt du 
eine spezielle DFT, die ausschließlich für reelle Eingangswerte 
funktioniert?

Sofern die Abtastwerte reell sind (was ja in der Regel der Fall ist), 
kann man nach der DFT N/2-1 bzw. (N-1)/2 Frequenzenpaare wiederum 
zusammenfassen, da die DFT sowohl Amplituden für negative als auch für 
positive Frequenzen ausspuckt.

[Manfred M. (bittbeisser)]

Der Autor (die Quelle hatte ich ja bereits angegeben) erwähnt 
tatsächlich, dass die komplexe DFT in einem späteren Kapitel behandelt 
wird.

Aber ich glaube ich habe jetzt des Rätsels Lösung gefunden. Es ist 
tatsächlich (N/2)+1. Aber es muss eine Integer Division sein. Ich habe 
die Berechnung einfach mal weiter laufen lassen, um zu sehen was 
passiert. Und man sieht tatsächlich, wie das Spektrum fortgesetzt wird:

Betragswerte skaliert!
:~/prog/filter$ ./dft_f
N = 31
  0:     0.47140     7.07100     0.00000
  1:     0.51919     7.33666     2.61246
  2:     0.71264     8.42349     6.58128
  3:     1.45407    12.64651    17.77043
  4:    10.07158   -53.55034  -141.26443
  5:     1.13306    -2.27744   -16.84266
  6:     0.61587     0.65742    -9.21465
  7:     0.43384     1.67193    -6.28917
  8:     0.34266     2.16888    -4.65981
  9:     0.28902     2.45424    -3.57364
 10:     0.25460     2.63297    -2.76624
 11:     0.23148     2.75024    -2.11944
 12:     0.21576     2.82963    -1.57083
 13:     0.20523     2.88088    -1.08490
 14:     0.19874     2.91227    -0.63709
 15:     0.19565     2.92717    -0.21015 << letzter Wert
 16:     0.19565     2.92717     0.21015 << 
 17:     0.19874     2.91227     0.63709
 18:     0.20523     2.88088     1.08490
 19:     0.21576     2.82963     1.57083
 20:     0.23148     2.75024     2.11944
 21:     0.25460     2.63297     2.76624
----
:~/prog/filter$ ./dft_f
N = 32
  0:     0.00000    -0.00000     0.00000
  1:     0.00000     0.00000    -0.00000
  2:     0.00000    -0.00000    -0.00000
  3:     0.00000     0.00000    -0.00000
  4:     9.99995     0.00000  -159.99923
  5:     0.00000     0.00000     0.00000
  6:     0.00000     0.00000     0.00000
  7:     0.00000     0.00000    -0.00000
  8:     0.00000     0.00000     0.00000
  9:     0.00000    -0.00000     0.00000
 10:     0.00000    -0.00000     0.00000
 11:     0.00000    -0.00000     0.00000
 12:     0.00005     0.00000     0.00077 < 3*f wg. 0.707 bei Eingabe
 13:     0.00000     0.00000     0.00000
 14:     0.00000     0.00000    -0.00000
 15:     0.00000    -0.00000    -0.00000
 16:     0.00000     0.00000    -0.00000 << letzter Wert & Symmetrieachse
 17:     0.00000     0.00000     0.00000
 18:     0.00000    -0.00000     0.00000
 19:     0.00000     0.00000     0.00000
 20:     0.00005     0.00000    -0.00077
 21:     0.00000    -0.00000    -0.00000
----

Die Eingangswerte sind 32 Samples, die genau 4 Sinusschwingungen 
ergeben, was dann bei 31 Samples natürlich nicht mehr passt.

[C Programmierer (Gast)]

Ich kann das nicht richtig nachvollziehen. Was genau sind die einzelnen 
Spalten der Tabellen?

Machen wir doch mal eine einfache Probe, ob du das gleiche rausbekommst 
wie ich nach dem zusammenfügen von positiven und negativen Frequenzen:

x = [2 3 -4]

X = [1 2,5-i*6,06 2,5+i*6,06]

XReal = [0,33 1,67-i*4,04]

x[k] = 0,33 + 4,37 * cos(2*pi*k/3-1,18)

[Manfred M. (bittbeisser)]

Ich bin leider noch nicht soweit, das ich den Test jetzt komplett 
nachvollziehen kann. Aber der Reihe nach.

Die Spalten sind:
  Index des  Ausgabewertes
  Betrag (skaliert mit Anzahl Ausgabewerte)
  Realteil
  Imaginärteil

Der verwendete Algorithmus ist von hier: 
http://www.dspguide.com/ch8/6.htm (TABLE 8-2).

Die Testwerte habe ich jetzt mal eingegeben. Es sind gewisse 
Ähnlichkeiten im Ergebnis erkennbar, aber ich bin nicht sicher ob Du das 
auch so siehst.

  0:     1.00000     1.00000     0.00000
  1:     6.55744     2.50000    -6.06218

(diesmal ohne Skalierung)

[C Programmierer (Gast)]

Deine DFT Formel scheint einfach nach der Hälfte der errechneten Werte 
abzubrechen. Warum auch nicht, wenn die andere Hälfte die konjugiert 
komplexen Zahlen von bereits berechneten Ergebnissen sind...

Um jetzt auf das Signal x wieder zu kommen, musst du anscheinend von 
allen Zeilen außer der ersten den Real- und Imaginärteil jeweils mit 2 
multiplizieren und alle Zeilen, inklusive der ersten durch die Anzahl 
teilen.

Dann erhälst du die gleichen Werte wie in meinem XReal Array und kannst 
daraus schließlich den Test mit der / den cos-Funktion(en) machen, ob 
das ursprüngliche x Array aus dem errechneten Spektrum wieder 
herauskommt.