Dans l'introduction de livres acoustiques et de littérature, nous présenterons des livres auxquels nos représentants de R&D font toujours référence et des articles qui attirent l'attention.
Les liens vers les livres et la littérature introduits sont également publiés, alors veuillez l'utiliser si vous êtes intéressé.
Les liens vers les livres et la littérature introduits sont également publiés, alors veuillez l'utiliser si vous êtes intéressé.
James W. Cooley et John W. Tukey
"Un algorithme pour le calcul de la machine de la série Fourieer complexe"
Mathématiques de calcul
19 (90), pp.297-301, 1965
Doi: https://doi.org/10.1090/S0025-5718-1965-0178586-1
Le document introduit cette fois est un accès gratuit. Cliquez sur "PDF en texte complet" sur la page liée ci-dessus pour télécharger le PDF de la thèse.
Mots-clés: conversion de Fourier à vitesse élevée (FFT), conversion de Fourier discrète (DFT), réponse à l'impulsion finie (FIR)
"Un algorithme pour le calcul de la machine de la série Fourieer complexe"
Mathématiques de calcul
19 (90), pp.297-301, 1965
Doi: https://doi.org/10.1090/S0025-5718-1965-0178586-1
Le document introduit cette fois est un accès gratuit. Cliquez sur "PDF en texte complet" sur la page liée ci-dessus pour télécharger le PDF de la thèse.
Mots-clés: conversion de Fourier à vitesse élevée (FFT), conversion de Fourier discrète (DFT), réponse à l'impulsion finie (FIR)
Connaissez-vous le filtre FIR?
Le FIR signifie une réponse impulsionnelle finie et est appelée une réponse impulsionnelle limitée en japonais. Mathématiquement, la sortie lorsque le signal d'impulsion est entrée dans un système est une réponse impalse, et la réponse impulsive est découpée à un moment fini.
Si vous le comparez avec le son, lorsque vous frappez votre main dans le bain ou le hall (bien que le son lorsque vous frappez votre main n'est pas un signal strictement impulsif) ou lorsque vous frappez votre main devant le microphone de tête factice. la réponse impulsive. La sortie est observée comme une forme d'onde de temps lorsque (entrée) lorsque (entrée) dans l'espace sonore tel qu'un bain et un hall, et la forme du corps humain telles que la tête et les oreilles externes (entrées).
Alors, qu'est-ce qui est délicieux quand vous connaissez le sapin?
En fait, dans un système immuable qui est inévitable, si vous connaissez le FIR, vous pouvez voir la sortie du système pour toute entrée. Si vous le comparez avec le son que vous avez mentionné plus tôt, quel type d'ondes sonores arrivera dans le tympan lorsque vous utilisez l'espace son ).
La raison d'une telle chose est que le signal du son entré dans le système peut être considéré comme une collection de nombreux imaux. En calculant la réponse impulsive à chacune des nombreuses impulsions, vous pouvez calculer la sortie au signal sonore d'entrée en le chevauchant.
Ceci est appelé mathématiquement le pliage et est défini dans la formule suivante. \ begin {aligner *} Y [n] = \ sum_ {k = 0} ^ {n-1} h [k] x [n-k] \ end {align *} Ici, $ h [t] $ est $ n $, et $ x [n] $ et $ y [n] $ sont chaque entrée et sortie. $ h [k] x [n-k] $ est une réponse d'impalice à chaque impulsion, qui est chevauchée par $ \ sum $.
De cette façon, la combinaison d'un FIR à un certain signe sonore est appelée filtre FIR.
Les explications ci-dessus sont assez interrompues, veuillez donc vous référer à des livres spécialisés pour des pièces plus détaillées.
Il est très attrayant de pouvoir reproduire le son dans divers environnements sonores à l'aide d'un filtre FIR, mais il y a un problème.
Autrement dit, le calcul du pliage nécessite une énorme quantité de calcul. Par exemple, supposons qu'il existe des sources sonores et des FIR échantillonnés avec 44100 $ \ Text {HZ} $, et chaque longueur est de $ 1 $ secondes. (En fait, le FIR est souvent plus court de 1 seconde. Pour calculer 1 944 810 000 $ pour 44 100 $ \ fois 44 100 $ pour chevaucher tous. À mesure que le nombre d'échantillons augmente, la quantité de calcul augmente. En ce qui concerne la généralisation, le montant de calcul requis pour plier l'échantillon de $ n $ et le pli de sapin est $ \ mathcal {o} (n ^ 2) $.
Il n'est pas réaliste de calculer cette quantité, même si les ordinateurs modernes (PC) sont devenus des performances élevées. Ces dernières années, des jeux tels que des jeux de tir ont été publiés en plus des images, et des jeux qui reposent sur la direction dans laquelle les sons se présentent dans un espace sonore de trois dimensions ont été publiés. Dans ces jeux, le calcul est effectué pour faire de l'espace sonore à trois dimensions un signal binaural 3D, et vous pouvez en profiter avec des écouteurs. Cependant, ces jeux nécessitent autant que possible les retards sonores en action, il n'y a donc pas de place pour calculer le pliage tel que défini.
Il y a un DFT (transformée de Fourier discrète). La raison pour laquelle DFT apparaît ici est que vous pouvez facilement effectuer des calculs de pliage en utilisant DFT. DFT est défini dans la formule suivante: \ begin {aligner *} A [k] = \ flac {1} {n} \ sum_ {n = 0} ^ {n-1} x [n] w ^ {- nk}, k = 0, 1, \ cdots, n-1 \ end {align *} Cependant, $ x [n] $ et $ a [k] $ voici des nombres complexes, $ w = e ^ \ frac {2 \ pi i} {n} $. Le DFT peut être considéré comme converti en $ x [n] $ dans la zone de temps en données $ n $ dans la zone de fréquence $ a [k] $. Par exemple, il s'agit d'une image de la conversion du signal sonore d'un accord en données sur lesquelles vous avez appuyé sur le clavier. Utilisez l'inverse de Fourier discret suivant pour retourner les données $ a [k] $ dans la zone de fréquence $ a [k] $ $ x [n] $. \ begin {aligner *} x [n] = \ sum_ {k = 0} ^ {n-1} a [k] w ^ {nk} \ end {align *} De plus, si le $ y [n] $ qui apparaissait dans la formule de définition du calcul plié était calculé conformément à la définition de DFT, \ begin {aligner *} 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 {ici,} 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 *} Sera. Cependant, $ y [k], h [k], x [k] $ chacun est $ y [n], h [n], x [n] $ dft et $ x [n] $ en supposant qu'il s'agit d'un signal \ begin {aligner *} x [-l] w ^ {- (- l) k} = x [n-l] w ^ {- (n-l) k} \ end {align *} J'utilise. En d'autres termes, c'est un pliage circulant.
De cette équation, le calcul de pliage, qui nécessitait le montant de calcul de N ^ 2 $ dans la zone de temps, peut être calculé en multipliant la zone de fréquence en multipliant les $ N fois.
Mais il y a un piège ici. Définition DFT \ begin {aligner *} A [k] = \ flac {1} {n} \ sum_ {n = 0} ^ {n-1} x [n] w ^ {- nk}, k = 0,1, \ cdots, n-1 \ end {align *} Si vous regardez attentivement, il y a un calcul de mise en gage $ N $ $ pour un certain $ a [k] $.
$ K $ a $ n $, donc le calcul global est $ n ^ 2 $. En d'autres termes, la quantité de calcul lors de la conversion de la zone de temps et de la région de fréquence par DFT reste la même que le calcul de pliage d'origine. Il semble qu'il ne soit pas inutile d'effectuer le DFT tel qu'il est.
L'introduction est devenue plus longue, mais voici le principal sujet de cette histoire.
L'idée de résoudre le problème que le DFT lui-même est le même que le calcul de pliage d'origine est les algorithmes Cooley et Tukey introduits cette fois.
Il semble que l'algorithme lui-même ait été découvert auparavant avant les papiers Cooley et Tukey, mais à la lumière des réalisations de la propagation au grand public, je présenterai leurs papiers.
Leurs algorithmes sont les suivants. La série complexe de Fourier est déterminée comme suit. (Conformément à leurs articles, la conversion / conversion inverse de Fourier discrète est la même que les séries de Fourier complexes, à l'exception de la différence entre la conjonction constante et complexe.) \ begin {aligner *} x [n] = \ sum_ {k = 0} ^ {n-1} a [k] w ^ {nk}, n = 0,1, \ cdots, n-1 \ end {align *} D'un autre côté, lorsque $ n = r_1 \ TIMES R_2 $ $ $ R_1, R_2 $ existe. \ begin {aligner *} 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 *} Ce faisant, la série originale de Fourier complexe \ begin {aligner *} 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} a [k_1, k_0] w ^ {nk_1 r_2} w ^ {nk_0} \ end {align *} Peut être transformé. De plus, de l'officiel \ begin {aligner *} W ^ {nk_1 r_2} = w ^ {n_0 k_1 r_2} \ end {align *} En utilisant \ begin {aligner *} 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 *} Et peut être divisé en deux étapes.
Dans la première étape, $ r_1 $ est pris pour $ [n_0, k_0] $ n $ des pièces, donc le nombre de calculs est $ (à part le calcul de Riding $ W $). Le nombre de calculs dans la deuxième étape est $ n r_2 $, donc le calcul total est $ n (r_1 + r_2) $.
De plus, lorsqu'il peut être démonté comme $ n = r_1 \ Times R_2 \ Times \ CDOTS \ Times R_M $, le nombre total de calculs est $ 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) $), et dans $ n = r ^ m $, le calcul est $ nr \ log_r n $.
De cette façon, j'ai été impressionné par le fait que le calcul pourrait être réduit par rapport au $ n ^ 2 $ d'origine, j'ai donc introduit un article décrit cet algorithme.
L'endroit où cet algorithme semble étonnant n'est pas seulement la diminution de la quantité de calcul. J'ai été impressionné par les trois points suivants.
Premièrement, à chaque étape, il est indépendant, à l'exception des paramètres qui prennent le contrôle de la somme, il peut donc être calculé en parallèle.
Ensuite, la durée du tableau requise pour enregistrer les données pendant le calcul doit être $ n $. (Au moment de cet article, une calculatrice utilisant des transistors est apparue, donc la quantité de mémoire était si petite que la quantité de mémoire était incomparable. Par conséquent. C'était un gros avantage.
Dans le cas de $ n = 2 ^ M $, les données peuvent être spécifiées avec l'indice Bit $ M $, et pour le calcul de $ L $ Stage $ (1 \ leq l \ leq m) $, $. ) $ 2 $ Il est facile de spécifier un indice de données car deux index avec des bits différents différents sont différents. Personnellement, je pense que c'est le plus beau.
Ce qui précède est le résumé de la thèse. Il s'agit de l'algorithme COOLEY-TUKEY FFT (FFT: Transform Furnière rapide, conversion de Fourier à grande vitesse), une méthode de calcul du DFT à grande vitesse. Jusqu'à présent, de nombreux algorithmes FFT ont été développés, tels que FFT pour les données de valeur réelle et FFT pour les calculatrices de type de mémoire distribuées, dont la plupart sont basées sur des algorithmes FFT Cooley-Tukey.
Beaucoup de bibliothèques FFT actuellement utilisées sont $ n $ $ n $ comme $ n = 2 ^ m $, et le calcul à ce moment est $ \ Mathcal {o} (n \ log_2 n) $. Par exemple, si le nombre de données d'entrée est $ n = 2 ^ {15} = 32 768 $, $ n ^ 2 $ sera 1 073 741 824 $, tandis que $ n log_2 n $ sera de 491 520 $, donc le calcul est dramatique . Vous pouvez voir qu'il a été amélioré.
Le calcul de pliage du filtre FIR décrit au début est la quantité de calcul de $ \ mathcal {o} (n \ log_2 n) $ en utilisant fft, ce qui est très pratique. À l'heure actuelle, les filtres FIR sont utilisés dans divers appareils et applications, tels que l'équipement audio numérique et les jeux informatiques.
Au-delà de l'application que nous utilisons habituellement, une belle théorie est cachée.
Cette fois, nous avons parlé de l'un de ces algorithmes Cooley et Tukey.
η
