In der Einführung von Akustikbüchern und Literatur werden wir Bücher vorstellen, auf die sich unsere F & E -Vertreter immer beziehen, und auf Papiere, die Aufmerksamkeit erregen.
Die Links zu den eingeführten Büchern und Literatur werden ebenfalls veröffentlicht. Bitte verwenden Sie sie, wenn Sie interessiert sind.
Die Links zu den eingeführten Büchern und Literatur werden ebenfalls veröffentlicht. Bitte verwenden Sie sie, wenn Sie interessiert sind.
James W. Cooley und John W. Tukey
"Ein Algorithmus für die Maschinenberechnung der komplexen Fourieer -Serie"
Mathematik der Berechnung
19 (90), S. 297-301, 1965
Doi: https://doi.org/10.1090/S0025-5718-1965-0178586-1
Das diesmal eingeführte Papier ist der freie Zugang. Klicken Sie auf der verknüpften Seite oben auf "Volltext-PDF", um das PDF der Dissertation herunterzuladen.
Schlüsselwörter: Hochgeschwindigkeits -Fourier -Konvertierung (FFT), diskrete Fourier -Konvertierung (DFT), endliche Impulsantwort (FIR)
"Ein Algorithmus für die Maschinenberechnung der komplexen Fourieer -Serie"
Mathematik der Berechnung
19 (90), S. 297-301, 1965
Doi: https://doi.org/10.1090/S0025-5718-1965-0178586-1
Das diesmal eingeführte Papier ist der freie Zugang. Klicken Sie auf der verknüpften Seite oben auf "Volltext-PDF", um das PDF der Dissertation herunterzuladen.
Schlüsselwörter: Hochgeschwindigkeits -Fourier -Konvertierung (FFT), diskrete Fourier -Konvertierung (DFT), endliche Impulsantwort (FIR)
Kennen Sie den FIR -Filter?
FIR steht für eine endliche Impulsreaktion und wird auf Japanisch eine Impulsreaktion mit begrenzter Länge bezeichnet. Mathematisch ist der Ausgang, wenn das Impulssignal in ein System eingegeben wird, eine Impulsesantwort, und die Impulsantwort wird zu einer endlichen Zeit ausgeschnitten.
Wenn Sie es mit Ton vergleichen, wenn Sie Ihre Hand in das Bad oder die Halle schlagen (obwohl das Geräusch beim Schlagen Ihrer Hand kein streng Impulssignal ist) oder wenn Sie Ihre Hand vor dem Dummy -Kopf -Mikrofon schlagen. die Impulsantwort. Die Ausgabe wird als Zeitwellenform beobachtet, wenn (Eingabe) in den Schallraum wie ein Bad und eine Halle und die menschliche Körperform wie den Kopf und die Außenohren (eingegeben) eine Impulsantwort ist.
Also, was ist köstlich, wenn Sie FIR kennen?
Tatsächlich können Sie in einem unveränderlichen System, das unvermeidlich ist, wenn Sie die FIR kennen, die Ausgabe des Systems für jede Eingabe sehen. Wenn Sie ihn mit dem Sound vergleichen, den Sie zuvor erwähnt haben, welche Art von Klangwellen zum Trommelfell gelangen, wenn Sie den Klangraum oder den Dummy Head Tanne verwenden, um Ihren Lieblings -Sound (einzugeben) in den Klangraum (Eingabe in das System ).
Der Grund für so etwas ist, dass das Signal des im System eingegebenen Klangs als Sammlung vieler Impals angesehen werden kann. Durch die Berechnung der Impulsantwort auf jeden der vielen Impulse können Sie den Ausgang zum Eingangsschallsignal berechnen, indem Sie ihn überlappen.
Dies wird mathematisch als Falten bezeichnet und in der folgenden Formel definiert. \ begin {align*} Y [n] = \ sum_ {k = 0}^{n-1} h [k] x [n-k] \ end {align*} Hier ist $ h [t] $ $ n $ und $ x [n] $ und $ y [n] $ sind jeweils Eingabe und Ausgabe. $ h [k] x [n-k] $ ist eine spalte Antwort auf jeden Impuls, der durch $ \ sum $ überlappt wird.
Auf diese Weise wird das Kombinieren einer Tanne mit einem bestimmten Klangzeichen als FIR -Filter bezeichnet.
Die obigen Erklärungen sind ziemlich gebrochen. Weitere detailliertere Teile finden Sie in spezialisierten Büchern.
Es ist sehr attraktiv, den Klang in verschiedenen Klangumgebungen mit einem FIR -Filter reproduzieren zu können, aber es gibt ein Problem.
Das heißt, die Berechnung der Faltung erfordert eine große Berechnung. Angenommen, es gibt Schallquellen und FIRs mit 44.100 $ \ text {Hz} $, und jede Länge beträgt 1 $ $ Sekunden. (Tatsächlich ist FIR oft kürzer als 1 Sekunde.) Bei der Berechnung dieser Faltung gibt es 44.100 US -Dollar quantifizierte Tonsignale und jedes Soundsignal $ 1 $ Impuls -Antwort pro $ eins. Berechnung von 1.944.810.000 USD für 44.100 USD \ mal 44.100 $, um alle zu überschneiden. Mit zunehmender Anzahl der Proben steigt die Berechnung. Bei der Verallgemeinerung beträgt der Berechnungsbetrag, der für das Falten der Stichprobe von $ n $ und die FIR -Faltung erforderlich ist, $ \ mathcal {o} (n^2) $.
Es ist nicht realistisch, diesen Betrag zu berechnen, obwohl die modernen Computer (PCs) zu hoher Leistung geworden sind. In den letzten Jahren wurden zusätzlich zu Bildern Spiele wie Shooting Games veröffentlicht, und Spiele, die auf der Richtung beruhen, in der Geräusche in drei dimensionaler Klangraum erhältlich sind. In diesen Spielen wird die Berechnung durchgeführt, um den dreidimensionalen Schallraum zu einem 3D -binauralen Signal zu machen, und Sie können es mit Kopfhörern genießen. Diese Spiele erfordern jedoch so viel wie mögliche Klangverzögerungen in Aktion. Daher gibt es keinen Raum für die Berechnung des Faltens wie definiert.
Es gibt eine DFT (diskrete Fourier -Transformation). Der Grund, warum DFT hier erscheint, ist, dass Sie mit DFT leicht Faltberechnungen durchführen können. DFT ist in der folgenden Formel definiert: \ begin {align*} A [k] = \ flac {1} {n} \ sum_ {n = 0}^{n-1} x [n] W^{-nk}, k = 0, 1, \ cdots, n-1 \ end {align*} $ X [n] $ und $ a [k] $ hier sind komplexe Zahlen, $ w = e^\ frac {2 \ pi i} {n} $. Der DFT kann als umgewandelt in $ x [n] $ in der Zeitfläche in $ n $ Daten im Frequenzbereich $ A [K] $ umgewandelt werden. Zum Beispiel ist es ein Bild, das das Schallsignal eines Akkords in die Daten, die Sie gedrückt haben, konvertieren. Verwenden Sie das folgende diskrete Fourier Reverse, um Daten $ A [k] $ im Frequenzbereich $ A [K] $ $ x [n] $ zurückzugeben. \ begin {align*} x [n] = \ sum_ {k = 0}^{n-1} a [k] w^{nk} \ end {align*} Wenn die in der Definitionsformel der gefalteten Berechnung erschienene $ y [n] $ in Übereinstimmung mit der Definition von DFT berechnet wurde, wurde er berechnet. \ begin {align*} Y [k] & = \ frac {1} {n} \ sum_ {n = 0}^{n-1} y [n] w^{-nk} \\ & = \ Frac {1} {n} \ sum_ {n = 0}^{n-1} \ sum_ {m = 0}^{n-1} h [m] x [n-m] w^{-nk} \\ & = \ Frac {1} {n} \ sum_ {m = 0}^{n-1} h [m] \ sum_ {n = 0}^{n-1} x [n-m] w^{-nk} \\ & = \ Frac {1} {n} \ sum_ {m = 0}^{n-1} h [m] \ sum_ {l = -m}^{n-m-1} x [l] w^{-((( l+m) k} (\ text {hier,} l = n-m) \\ & = N \ cdot \ frac {1} {n} \ sum_ {m = 0}^{n-1} h [m] w^{-mk} \ sum_ {l = 0}^{n-1} x [L] w^{-lk} \\ & = N \ cdot H [k] x [k] \ end {align*} Wird sein.ただし、 $ y [k], h [k], x [k] $ はそれぞれ $ y [n], h [n], x [n] $ の dft で、また $ x [n] $ は周期的Angenommen, es ist ein Signal \ begin {align*} x [-l] w^{-(-l) k} = x [n-l] w^{-(n-l) k} \ end {align*} Ich benutze. Mit anderen Worten, es ist eine zirkulierende Faltung.
Aus dieser Gleichung kann die Faltungsberechnung, für die der Berechnungsbetrag von $ n^2 $ in der Zeitfläche erforderlich war, berechnet werden, indem die Frequenzfläche durch Multiplizieren der $ n -mal multipliziert werden.
Aber hier gibt es einen Fall. DFTの定義 \ begin {align*} A [k] = \ flac {1} {n} \ sum_ {n = 0}^{n-1} x [n] w^{-nk}, k = 0,1, \ cdots, n-1 \ end {align*} Wenn Sie genau hinschauen, gibt es eine $ N $ $ $ Pawning -Berechnung für eine bestimmte $ a [k] $.
$ K $ hat $ n $, daher beträgt die Gesamtberechnung $ N^2 $. Mit anderen Worten, die Berechnung bei der Umwandlung des Zeitbereichs und des Frequenzbereichs durch DFT bleibt der ursprünglichen Faltungsberechnung gleich. Es scheint, dass es keinen Sinn macht, DFT so auszuführen, wie es ist.
Die Einführung ist länger geworden, aber hier ist das Hauptthema dieser Geschichte.
Die Idee, das Problem zu lösen, dass die DFT selbst die ursprüngliche Faltberechnung entspricht, ist die diesmal eingeführte Cooley- und Tukey -Algorithmen.
Es scheint, dass der Algorithmus selbst zuvor vor den Cooley- und Tukey -Papieren entdeckt wurde, aber angesichts der Erfolge der Ausbreitung auf die Öffentlichkeit werde ich ihre Papiere vorstellen.
Ihre Algorithmen sind wie folgt. Die komplexe Fourier -Serie wird wie folgt bestimmt. (In Übereinstimmung mit ihren Papieren entspricht die diskrete Fourier -Umwandlung / Reverse -Konvertierung mit Ausnahme der Differenz zwischen der konstanten und komplexen Konjunktion.) \ begin {align*} x [n] = \ sum_ {k = 0}^{n-1} a [k] w^{nk}, n = 0,1, \ cdots, n-1 \ end {align*} Andererseits existiert R_2 $, wenn $ n = r_1 \ mal R_2 $ $ $ R_1 vorhanden ist. \ begin {align*} N & N_1 R_1+N_0, N_0 = 0,1, \ CDOTS, R_1-1, N_1 = 0,1, \ cdots, r_2-1 \\ K & = k_2+k_0, k_0 = 0,1, \ cdots, r_2-1, k_1 = 0,1, \ cdots, r_1-1 \ end {align*} Auf diese Weise die ursprüngliche komplexe Fourier -Serie \ begin {align*} x [n] = x [n_1, n_0] & = \ sum_ {k = 0}^{n-1} a [k] w^{nk} \\ & = \ sum_ {k_0 = 0}^{r_2-1} \ sum_ {k_1 = 0}^{r_1-1-1} a [k_1, k_0] w^{nk_1 r_2} w^{nk_0} \ end {align*} Kann transformiert werden. Darüber hinaus vom offiziellen Beamten \ begin {align*} W^{nk_1 r_2} = w^{n_0 k_1 r_2} \ end {align*} Durch Verwendung \ begin {align*} A_1 [n_0, k_0] & = \ sum_ {k_1 = 0}^{r_1-1} a [k_1, k_0] w^{n_0 k_1 r_2} \\ x [n_1, n_0] & = \ sum_ {k_0 = 0}^{r_2-1} _1 [n_0, k_0] w^{(n_1 r_1+n_0) k_0} \ end {align*} Und kann in zwei Stufen unterteilt werden.
In der ersten Phase wird $ R_1 $ für $ [n_0, k_0] $ n $ poies genommen, sodass die Anzahl der Berechnungen $ beträgt (abgesehen von der Berechnung von $ W $). Die Anzahl der Berechnungen in der zweiten Stufe beträgt $ n r_2 $, daher beträgt die Gesamtberechnung $ n (r_1+r_2) $.
Furthermore, when it can be disassembled as $ n = r_1 \ times r_2 \ times \ cdots \ times R_m $, the total number of calculations is $ N (R_1+R_2+\ CDOTS+\ CDOTS+\ CDOTS+\ CDOTS+\ CDOTS+CDOTS+\ CDOTS+ \ Cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ cdots+\ r_m) $) und in $ n = r^m $ ist die Berechnung $ nr \ log_r n $.
Auf diese Weise war ich beeindruckt von der Tatsache, dass die Berechnung aus dem ursprünglichen $ N^2 $ reduziert werden konnte, daher habe ich ein Papier vorgestellt, das diesen Algorithmus beschrieben wurde.
Der Ort, an dem sich dieser Algorithmus erstaunlich anfühlt, ist nicht nur die Abnahme der Berechnung. Ich war beeindruckt von den folgenden drei Punkten.
Erstens ist es in jeder Phase unabhängig, bis auf die Parameter, die die Summe übernehmen, so dass sie parallel berechnet werden kann.
Als nächstes muss die Länge des Arrays, das zum Speichern von Daten während der Berechnung erforderlich ist, $ n $ sein. (Zum Zeitpunkt dieses Papiers trat ein Taschenrechner mit Transistoren auf, sodass die Speichermenge so gering war, dass die Speichermenge unvergleichlich war. Daher war es ein großer Vorteil.
Im Fall von $ n = 2^m $ können die Daten mit dem $ M $ Bit-Index und für die Berechnung von $ l $ Stufe $ (1 \ Leq l \ Leq M) $, $, angegeben werden ) $ 2 Es ist einfach, einen Datenindex anzugeben, da zwei Indizes mit unterschiedlichen Bits unterschiedlich sind. Persönlich finde ich das am schönsten.
Das obige ist die Zusammenfassung der Dissertation. Dies ist der Cooley-Tukey-FFT-Algorithmus (FFT: Fast Fourier-Transformation, Hochgeschwindigkeits-Fourier-Umwandlung), eine Methode zur Berechnung von DFT bei hoher Geschwindigkeit. Bisher wurden viele FFT-Algorithmen entwickelt, z.
Viele der derzeit verwendeten FFT -Bibliotheken sind $ n $ $ n $ als $ n = 2^m $, und die Berechnung zu diesem Zeitpunkt beträgt $ \ mathcal {o} (n \ log_2 n) $. Wenn beispielsweise die Anzahl der Eingabedaten $ n = 2^{15} = 32.768 $ beträgt, beträgt $ n^2 $ 1.073.741.824 $, während $ n log_2 n $ 491.520 $ betragen wird, sodass die Berechnung dramatisch ist Sie können sehen, dass es verbessert wurde.
Die Faltungsberechnung des am Anfang beschriebenen FIR -Filters ist die Berechnung der Berechnung von $ \ mathcal {o} (n \ log_2 n) $ unter Verwendung von FFT, was sehr praktisch ist. Gegenwärtig werden FIR -Filter in verschiedenen Geräten und Anwendungen verwendet, wie z. B. digitale Audiogeräte und Computerspiele.
Abgesehen von der Anwendung, die wir normalerweise verwenden, ist eine schöne Theorie versteckt.
Diesmal sprachen wir über einen von diesen, Cooley und Tukey -Algorithmus.
η
