Cet article décrit l'algorithme de variation de Fourier mis en œuvre dans Java. Partagez-le pour votre référence, comme suit:
Le résultat de la variation de Fourier est utilisé pour implémenter Java comme une forme plurielle a + bi
Sans plus tarder, le code d'implémentation est le suivant, un total de deux classes
Code de mise en œuvre de la fonction de changement FFT.Class Fourier Fourier
Package fft.test; / *********************************************************************************** * Compilation: Javac fft.java EXÉCUTION: Java fft n dépendances: complex.java * Compute le fft et inverse fft of a longuement n complexe séquence. Implémentation des os nus * qui fonctionne en temps O (n log n). Notre objectif est d'optimiser la * clarté du code plutôt que des performances. * * Limites ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ***********************************************************************************************. // cas de base if (n == 1) renvoie le nouveau complexe [] {x [0]}; // radix 2 cooley-tukey fft if (n% 2! = 0) {Throw New RuntimeException ("n n'est pas une puissance de 2"); } // fft de même termes complexe [] même = nouveau complexe [n / 2]; pour (int k = 0; k <n / 2; k ++) {même [k] = x [2 * k]; } Complexe [] q = fft (même); // fft de termes impairs complexe [] Odd = même; // Réutiliser le tableau pour (int k = 0; k <n / 2; k ++) {Odd [k] = x [2 * k + 1]; } Complexe [] r = fft (odd); // combiner complexe [] y = nouveau complexe [n]; pour (int k = 0; k <n / 2; k ++) {double kth = -2 * k * math.pi / n; Complexe wk = nouveau complexe (math.cos (kth), math.sin (kth)); y [k] = q [k] .plus (wk.times (r [k])); y [k + n / 2] = q [k] .minus (wk.times (r [k])); } return y; } // Calculez la FFT inverse de x [], en supposant que sa longueur est une puissance de 2 complexe statique public [] ifft (complexe [] x) {int n = x.length; Complexe [] y = nouveau complexe [n]; // Prenez conjugué pour (int i = 0; i <n; i ++) {y [i] = x [i] .Conjugate (); } // calculer Fft Fft y = fft (y); // Prenez à nouveau conjugué pour (int i = 0; i <n; i ++) {y [i] = y [i] .Conjugate (); } // Diviser par n pour (int i = 0; i <n; i ++) {y [i] = y [i] .scale (1.0 / n); } return y; } // calculer la convolution circulaire de X et Y Public Static Complex [] CConvolve (complexe [] x, complexe [] y) {// devrait probablement rejeter X et Y avec 0S afin qu'ils aient la même longueur // et sont des pouvoirs de 2 if (x.length! = y.length) {lancent new RuntimeException ("Dimensions Don't Caccord"); } int n = x.length; // calculer FFT de chaque séquence, évaluer le complexe [] a = fft (x); Complexe [] b = fft (y); // Multiplition ponctuelle, complexe de multiplication de valeur ponctuelle [] C = nouveau complexe [n]; for (int i = 0; i <n; i ++) {c [i] = a [i] .Times (b [i]); } // calculer inverse FFT, retour d'interpolation iffft (c); } // calculer la convolution linéaire du complexe statique publique de X et Y [] Convolution (complexe [] x, complexe [] y) {complexe zéro = nouveau complexe (0, 0); Complexe [] a = nouveau complexe [2 * x.length]; // 2n fois limite, le coefficient d'ordre supérieur est 0. Pour (int i = 0; i <x.length; i ++) a [i] = x [i]; for (int i = x.length; i <2 * x.length; i ++) a [i] = zéro; Complexe [] b = nouveau complexe [2 * y.length]; pour (int i = 0; i <y.length; i ++) b [i] = y [i]; for (int i = y.length; i <2 * y.length; i ++) b [i] = zéro; RETOUR CCONVOLVE (A, B); } // Affichez un tableau de nombres complexes à la sortie standard public static void show (complexe [] x, title de chaîne) {System.out.println (title); System.out.println ("----------------------------------------"); int complexlength = x.length; pour (int i = 0; i <complexlength; i ++) {// complex de sortie // system.out.println (x [i]); // L'amplitude de sortie nécessite * 2 / longueur System.out.println (x [i] .abs () * 2 / complexLength); } System.out.println (); } / ** * Réorganisez les données du tableau dans une puissance de 2 sortie * * @param data * @return * / public static double [] pow2Doublearr (Double [] data) {// créer un nouveau tableau double [] newData = null; int datalngle = data.length; int imnnum = 2; while (sumnum <datalngle) {SUMMUM = SUNMUM * 2; } int addLength = SUNMUM - Datalngle; if (addLength! = 0) {newData = new Double [Sumnum]; System.ArrayCopy (données, 0, newdata, 0, longueur de données); for (int i = datalngle; i <sumnum; i ++) {newData [i] = 0d; }} else {newData = data; } return newdata; } / ** * Deoffset * * @param originalarr * originalarr * originalarr * public static double [] deskew (double [] originalarr) {// Filtre des paramètres incorrects if (originalarr == null || originalarr.length <= 0) {return null; } // définir le tableau cible double [] resarr = new double [originalarr.length]; // Trouvez la somme du tableau double somme = 0d; for (int i = 0; i <originalarr.length; i ++) {sum + = originalarr [i]; } // Trouvez la valeur moyenne du tableau double Aver = sum / originalarr.length; // supprime la valeur de décalage pour (int i = 0; i <originalarr.length; i ++) {resarr [i] = originalarr [i] - Aver; } return resarr; } public static void main (String [] args) {// int n = Integer.parseint (args [0]); Double [] Data = {-0.35668879080953375, -0.6118094913035987, 0.8534269560320435, -0.6699697478438837, 0.35425500561437717, 0,8910250650500561437717, 0,8910250650500561437717, 0,8910250650500561437717, 0,8910250650500561437717, 0,8910250650500561437717, 0,8910250549392, 4377717, 0,8910250549392, -0.025718699518642918, 0,07649691490732002}; // supprimer les données de décalage = Deskew (données); // puissance du nombre de 2 = pow2Doublearr (données); int n = data.length; System.out.println (N + "Numéro dans le tableau N ..."); Complexe [] x = nouveau complexe [n]; // Données originales pour (int i = 0; i <n; i ++) {// x [i] = nouveau complexe (-2 * math.random () + 1, 0); x [i] = nouveau complexe (data [i], 0); } show (x, "x"); // fft du complexe de données d'origine [] y = fft (x); show (y, "y = fft (x)"); // prendre le complexe FFT inverse [] z = ifft (y); show (z, "z = iffft (y)"); // Convolution circulaire de x avec lui-même complexe [] c = cConvolve (x, x); show (c, "c = cConvolve (x, x)"); // Convolution linéaire de x avec lui-même complexe [] d = convolution (x, x); show (d, "d = convolve (x, x)"); }} / *****************************************************************************************. ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0.35425500561437717 0.8910250650549392 * -0.025718699518642918 0.07649691490732002 * * y = fft (x) ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 2.4696418005143532I 1.1395317305034673 * -0.17611092978237974 - 2.4696418005143532I -0.8301420417085572 + * 0,872684066879042I -1.2457766630654419 - 0.7113504894129803i * * z = iffft (y) --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0.8534269560320435 - 2.691607282636124E-17I * -0.669969747843837 + 4.1114763914420734e-17i 0.35425500561437717 * 0,8910250650549392 - 6.887033953004965E-17I -0.025718699518642918 + * 2.691607282636124E-17I 0,07649691490732002 - 1.4396387316837096E-7I * * * C = CCONVOLVE (x) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1.9986455722517509E-16i 1.432390480003344 + 2.636779683484747E-16i * -2.2165857430333684 + 2.2180047699856214E-17i -0.01255525669751989 + * 1.3815636262919812E-17I 1.0230680492494633 - 2.4422465262488753E-16I * * D = Convolve (x, x) --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0.43645117531775324 - 2.78776395788635E-18i * -0.2345048043334932 - 6.907818131459906E-18i -0.5663280251946803 + * 5.829891518914417E-17i 1.2954076913348198 + 1.518836016779236E-16i * -2.212650940696159 + 1.1090023849928107E-17i -0.018407034687857718 - * 1.1306778366296569E-17i 1.023068049249463 - 9.435675069681485E-17I * -1.205924207390114 - 2.983724378680108E-16I 0.796330738580325 + * 2.4967811657742562E-1 0.6732024728888314 - 6.907818131459906E-18I * 0,00836681821649593 + 1.4156564203603091E-16I 0.1369827886685242 + * 1.1179436667055108E-16I620 -0.00393480233720922 + 1.1090023849928107E-17i * 0.005851777990337828 + 2.512241462921638E-17i 1.1102230246251565E-16 - * 1.4986790192807268E-16i ******************************************************************************************************** /Complexe.classe class
Package fft.test; / ************************************************************************************************* * Compilation: Javac Complex.java * Exécution: Java Complex * * Type de données pour les numéros de complexe. * * Le type de données est "immuable", donc une fois que vous avez créé et initialisé * un objet complexe, vous ne pouvez pas le modifier. Le mot-clé "final" * lors de la déclaration RE et IM applique cette règle, ce qui en fait une * erreur de compilation de compilation pour modifier les variables d'instance .re ou .im après * ils ont été initialisés. * *% Java Complex * a = 5.0 + 6.0i * b = -3.0 + 4.0i * re (a) = 5.0 * im (a) = 6.0 * b + a = 2.0 + 10.0i * a - b = 8.0 + 2.0i * a * b = -39.0 + 2.0i * a / b = 0.36 - 1,52i * (a / b) * b = 5.0 + 6.0i * conj (a) = 6 | A | = 7.810249675906654 * Tan (A) = -6.685231390246571E-6 + 1.0000103108981198I * ********************************************************************************************************************************************************. Double final privé re; // la vraie partie privée finale Double IM; // La partie d'imagination // Créer un nouvel objet avec le complexe public réel et imaginaire (Double Real, Double Image) {Re = Real; IM = Imagine; } // renvoie une représentation de chaîne du complexe invoquant l'objet public public string toString () {if (im == 0) return re + ""; if (re == 0) return im + "i"; if (im <0) return re + "-" + (-im) + "i"; return re + "+" + "+ im +" i ";} // return abbs / modulus / magnitude public double abb () {return math.hypot (re, im);} // return angle / phase / argument, normalisé pour être entre -pi et pi Cet objet invoquant un objet DOUBLE = A.re + B. {Complexe a = this; {Rendre le nouveau complexe (re, -im);} // Rendre un nouvel objet complexe dont la valeur est réciproque de ce complexe public réciproque. {Complexe a = this; return a.Times (b.reciprocal ());} // return un nouvel objet complexe dont la valeur est le complexe exponentiel de // ce complexe public exp () {return Complexe (math.sin (re) * math.cosh (im), math.cos (re) * math.sinh (im)); de ce complexe public Tan () {return sin (). Divides ()); (return false. 4.0); B.Plus (a)); / b) * b = "+ a.divides (b) .Times (b)); System.out.println (" conj (a) = "+ a.conjugate (); system.out.println (" | a | = "+ a.abs ()); system.out.println (" tan (a) = "+ a.tan ());}}Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.