Implementierung der Wikipedia-Gleichung für die DFT

10

Ich schrieb eine einfache Fourier-Transformations-Implementierung und betrachtete die DFT-Gleichung auf Wikipedia als Referenz , als ich bemerkte, dass ich etwas anders machte, und nachdem ich darüber nachgedacht hatte, hatte ich das Gefühl, dass die Wikipedia-Version falsch sein muss, weil es sehr einfach ist, an eine zu denken signalisieren, dass bei einer Fourier-Transformation (mit dieser Gleichung) ein falsches Spektrum zurückgegeben wird: Da die Gleichung das Signal nur einmal um die komplexe Ebene wickelt (aufgrund der mit ), jedes periodische Signal Eine gerade Anzahl von Malen (beim Umwickeln der komplexen Ebene) hat kein Spektrum, da sich die üblichen Peaks (beim Umrunden des Einheitskreises), die während einer DFT auftreten würden, gegenseitig aufheben (wenn eine gerade Anzahl von ihnen auftritt). $n/N$ $0<n<N-1$

Um dies zu überprüfen, habe ich einen Code geschrieben, der das folgende Bild erzeugt, das meine Gedanken zu bestätigen scheint.

"Zeit unter Verwendung der Gleichung" verwendet die Gleichung mit einem Vektor der Zeit (so zum Beispiel die Zeit zu der abgetastet wurde). Es kann in der Funktion unten gefunden werden.

X_{f} = \sum_{n = 0}^{N - 1} x_{n} (\cos (2 π f t_{n}) - i \sin (2 π f t_{n}))

$X_f = \sum_{n=0}^{N-1} x_n (\cos(2\pi f t_n) - i \sin(2\pi f t_n))$

t

$t$

t_{n}

$t_n$

x_{n}

$x_n$ ft

Die oben verlinkte Wikipedia-Gleichung wird hier als Referenz kopiert: Es kann in der Funktion gefunden werden .

X_{f} = \sum_{n = 0}^{N - 1} x_{n} (\cos (2 π f \frac{n}{N}) - i \sin (2 π f \frac{n}{N}))

$X_f = \sum_{n=0}^{N-1} x_n \left(\cos\left(2\pi f \frac{n}{N}\right) - i\sin\left(2\pi f \frac{n}{N}\right)\right)$ ft2

import numpy as np
import matplotlib.pyplot as plt 
plt.style.use('ggplot')

def ft(t, s, fs):
    freq_step = fs / len(s)
    freqs = np.arange(0, fs/2 + freq_step, freq_step)
    S = []
    for freq in freqs:
        real = np.sum(s * np.cos(2*np.pi*freq * t)) 
        compl = np.sum(- s * np.sin(2*np.pi*freq * t)) 
        tmpsum = (real**2 + compl**2) ** 0.5 
        S.append(tmpsum)
    return S, freqs

def ft2(s, fs):  # Using wikipedia equation
    nump=len(s)
    freq_step = fs / nump
    freqs = np.arange(0, fs/2 + freq_step, freq_step)
    S = []
    for i, freq in enumerate(freqs):
        real = np.sum(s * np.cos(2*np.pi*freq * i/nump))
        compl = np.sum(- s * np.sin(2*np.pi*freq * i/nump))
        tmpsum = (real**2 + compl**2) ** 0.5 
        S.append(tmpsum)
    return S, freqs


def main():
    f = 5 
    fs = 100 
    t = np.linspace(0, 2, 200)
    y = np.sin(2*np.pi*f*t) + np.cos(2*np.pi*f*2*t)

    fig = plt.figure()
    ax = fig.add_subplot(311)
    ax.set_title('Signal in time domain')
    ax.set_xlabel('t')
    ax.plot(t, y)

    S, freqs = ft(t, y, fs) 

    ax = fig.add_subplot(312)
    ax.set_xticks(np.arange(0, freqs[-1], 2)) 
    ax.set_title('Time using equation')
    ax.set_xlabel('frequency')
    ax.plot(freqs, S)

    S, freqs = ft2(y, fs) 
    ax = fig.add_subplot(313)
    ax.set_title('Using Wiki equation')
    ax.set_xlabel('frequency')
    ax.set_xticks(np.arange(0, freqs[-1], 2)) 
    ax.plot(freqs, S)

    plt.tight_layout()
    plt.show()

main()

Offensichtlich ist es eher unwahrscheinlich, dass ich zufällig einen Fehler auf einer so hochkarätigen Wiki-Seite gefunden hätte. Aber ich kann keinen Fehler in dem sehen, was ich getan habe?

fourier-transform Nimitz14
quelle

Um ein tieferes Verständnis der Bedeutung einer DFT zu erhalten, empfehle ich Ihnen, meine ersten beiden Blog-Artikel zu lesen: "Die exponentielle Natur des komplexen Einheitskreises" ( dsprelated.com/showarticle/754.php ) und "DFT Graphical Interpretation: Centroids" of Weighted Roots of Unity "( dsprelated.com/showarticle/768.php ).

Cedron Dawg

Danke, ich werde einen Blick darauf werfen. Ich bin ehrlich gesagt sehr überrascht über die Aufmerksamkeit, die dies erhielt, wenn alles auf einen sehr dummen Fehler in meinem Code zurückzuführen ist.

Nimitz14

Ich bin auch überrascht. Das kontinuierliche gegen das diskrete Ding ist jedoch eine große Sache. In meinem Blog dreht sich alles um den diskreten Fall ohne Bezug auf den fortlaufenden Fall, der sich davon unterscheidet, den diskreten Fall als Stichprobenversion des fortlaufenden Falls zu lehren.

Cedron Dawg

16

Du hast einen Fehler ft2. Sie erhöhen iund freqzusammen. So soll Ihre Summierung nicht funktionieren. Ich habe herumgespielt, um es zu reparieren, aber es wurde chaotisch. Ich beschloss, es aus einer diskreten Perspektive neu zu schreiben, anstatt zu versuchen, die fortlaufende Terminologie zu verwenden. In der DFT spielt die Abtastrate keine Rolle. Entscheidend ist, wie viele Proben verwendet werden ( N). Die Bin-Nummern ( k) entsprechen dann der Frequenz in Einheiten von Zyklen pro Frame. Ich habe versucht, Ihren Code so intakt wie möglich zu halten, damit er für Sie leicht verständlich bleibt. Ich habe auch die DFT-Berechnungsschleifen entfaltet, um hoffentlich ihre Natur ein bisschen besser zu enthüllen.

Hoffe das hilft.

Ced

importiere numpy als np
importiere matplotlib.pyplot als plt 

def ft (t, s, fs):
    freq_step = fs / len (s)
    freqs = np.arange (0, fs / 2, freq_step)
    S = []
    für freq in freqs:
        real = np.sum (s * np.cos (2 * np.pi * freq * t)) 
        compl = np.sum (- s * np.sin (2 * np.pi * freq * t)) 
        tmpsum = (real ** 2 + compl ** 2) ** 0,5 
        S.append (tmpsum)
    return S, freqs

def ft3 (s, N): # Effizientere Form der Wikipedia-Gleichung

    S = []

    Scheibe = 0,0
    Faserband = 2 * np.pi / float (N) 

    für k im Bereich (N / 2):

        sum_real = 0.0    
        sum_imag = 0.0
        Winkel = 0,0
        für n im Bereich (N):
            sum_real + = s [n] * np.cos (Winkel)
            sum_imag + = -s [n] * np.sin (Winkel)
            Winkel + = Scheibe

        Scheibe + = Splitter
        tmpsum = (sum_real ** 2 + sum_imag ** 2) ** 0,5 
        S.append (tmpsum)

    kehrt zurück

def ft4 (s, N): # Verwenden der Wikipedia-Gleichung

    S = []

    für k im Bereich (N / 2):

        sum_real = 0.0    
        sum_imag = 0.0
        für n im Bereich (N):
            sum_real + = s [n] * np.cos (2 * np.pi * k * n / float (N))
            sum_imag + = -s [n] * np.sin (2 * np.pi * k * n / float (N))

        tmpsum = (sum_real ** 2 + sum_imag ** 2) ** 0,5 
        S.append (tmpsum)

    kehrt zurück

def ft5 (s, N): # Roots of Unity Weighted Sum

    Faserband = 2 * np.pi / float (N) 

    root_real = np.zeros (N)
    root_imag = np.zeros (N)

    Winkel = 0,0
    für r im Bereich (N):
        root_real [r] = np.cos (Winkel)
        root_imag [r] = -np.sin (Winkel)
        Winkel + = Faserband

    S = []

    für k im Bereich (N / 2):

        sum_real = 0.0    
        sum_imag = 0.0
        r = 0

        für n im Bereich (N):
            sum_real + = s [n] * root_real [r]
            sum_imag + = s [n] * root_imag [r]
            r + = k
            wenn r> = N: r - = N.

        tmpsum = np.sqrt (sum_real * sum_real + sum_imag * sum_imag)
        S.append (tmpsum)

    kehrt zurück

def main ():

    N = 200
    fs = 100,0

    Zeitschritt = 1,0 / fs
    t = np.arange (0, N * Zeitschritt, Zeitschritt)

    f = 5,0
    y = np.sin (2 * np.pi * f * t) + np.cos (2 * np.pi * f * 2 * t)

    fig = plt.figure ()
    ax = fig.add_subplot (311)
    ax.set_title ('Signal im Zeitbereich')
    ax.set_xlabel ('t')
    ax.plot (t, y)

    S, Freqs = ft (t, y, fs) 

    ax = fig.add_subplot (312)
    ax.set_xticks (np.arange (0, freqs [-1], 2)) 
    ax.set_title ('Zeit mit Gleichung')
    ax.set_xlabel ('Frequenz')
    ax.plot (freqs, S)

    S = ft3 (y, N) 
    ax = fig.add_subplot (313)
    ax.set_title ('Verwenden der Wiki-Gleichung')
    ax.set_xlabel ('Frequenz')
    ax.set_xticks (np.arange (0, freqs [-1], 2)) 
    print len (S), len (freqs)
    ax.plot (freqs, S)

    plt.tight_layout ()
    plt.show ()

Main()

Cedron Dawg
quelle

Übrigens hatten Sie wahrscheinlich Probleme, weil mein Code Python3 annahm;)

Nimitz14

1

@ Nimitz14, keine große Sache. Ich habe die Zahlen mit "float ()" und ein paar ".0" versehen. Ihr Code lief einwandfrei. Das einzige, was ich entfernen musste, war die Anweisung "plt.style.use ('ggplot')".

Cedron Dawg

1

@ Nimitz14, ich habe vergessen zu erwähnen, ich habe dem Code eine ft5-Routine hinzugefügt, die die Wurzeln von Einheitswerten vorberechnet und wirklich zeigt, wie die DFT unter Verwendung der gleichen Wurzeln für jeden Bin berechnet wird.

Cedron Dawg

4

$j$

X [k] = \sum_{n = 0}^{N - 1} x [n] e^{- j 2 π n k / N}

$X[k] = \sum\limits_{n=0}^{N-1} x[n] \, e^{-j 2 \pi nk/N}$

x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] e^{j 2 π n k / N}

$x[n] = \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] \, e^{j 2 \pi nk/N}$

$x[n]$ $X[k]$

X_{k} = \sum_{n = 0}^{N - 1} x_{n} e^{- i 2 π n k / N}

$X_k = \sum\limits_{n=0}^{N-1} x_n \, e^{-i 2 \pi nk/N}$

x_{n} = \frac{1}{N} \sum_{k = 0}^{N - 1} X_{k} e^{i 2 π n k / N}

$x_n = \frac{1}{N} \sum\limits_{k=0}^{N-1} X_k \, e^{i 2 \pi nk/N}$

und das ist das gleiche wie auf der Wikipedia-Seite.

$+$ $-$ $+$ $-$ $\sin(\cdot)$

robert bristow-johnson
quelle

3

Wenn wir i anstelle von j verwenden würden, könnten wir ELI nicht als ICE-Mann bezeichnen. ELJ, der JCE-Mann, hat nicht den gleichen Ring. Die Zivilisation wäre bedroht

1

Elijah der Saftmann?

Robert Bristow-Johnson

@ user28715 Nun, ich bin in diesem Fall aktuell nicht die Quadratwurzel von minus 1 .... youtube.com/watch?v=2yqjMiFUMlA

Peter K.

0

Ich bin darauf zurückgekommen und habe versucht, die diskrete Version abzuleiten, die dazu beigetragen hat, die Dinge sinnvoller zu machen:

$f_k t_n = f(n, k, N)$

$f_k = \frac{f_s}{N}k$ $t_n = \frac{T}{N}n$

$f_s = \frac{N}{T}$

Damit

$f_k t_n = \frac{f_s}{N}k\frac{T}{N}n = \frac{N}{TN}k\frac{T}{N}n = \frac{kn}{N}$

Erledigt!

Nimitz14
quelle

Implementierung der Wikipedia-Gleichung für die DFT

Antworten: