)) simple permettant de faire une analyse fréquentielle sur un signal.
Ximoon :
Presque, mais la version discrète et grandement optimisable appelée "FFT" (transformée de Fourier rapide en français) largement utilisée en traitement du signal numérique.
bref 
(en plus j'ai de fort doute sur la véracité de mon code ^^)
Godzil
:Ximoon :
Presque, mais la version discrète et grandement optimisable appelée "FFT" (transformée de Fourier rapide en français) largement utilisée en traitement du signal numérique.
-able+é non ?
(mais oui c'est déjà optimisé par rapport à une FT de base 
)Lionel Debroux :
Il me semble que Bhuvanesh Bhatt a fait une FFT. Qu'elle soit rapide, par contre, n'est pas sûr.
unsigned char NumberOfBitsNeeded (long PowerOfTwo)
{
for (unsigned char i=0; i<=16; i++) {
if (PowerOfTwo==(1UL<<i)) return i;}
return 0;
}
bool IsPowerOfTwo (long x)
{
if (x<2) return false;
if (!(x&(x-1))) return true;
return false;
}
long ReverseBits (long Index, unsigned char NumBits)
{
long Rev = 0;
for (unsigned char i=0; i<NumBits; i++)
{
Rev = (Rev*2)|(Index&1);
Index = Index/2;
}
return Rev;
}
//bool FFTAudio (long NumSamples, short *RealIn, float *RealOut, float *ImagOut)
bool FFTAudio (long NumSamples, float *RealIn, float *RealOut, float *ImagOut)
{
/* In this case, NumSamples isn't included (since it's always the same),
and the imaginary components are left out since they have no meaning here.
I've use Signles instead of Doubles pretty much everywhere. I think this
makes it faster, but due to type conversion, it actually might not. I should
check, but I haven't.
The imaginary components have no meaning in this application. I just left out
the parts of the calculation that need the imaginary input values (which is a
big speed improvement right there), but we still need output array because
it's used in the calculation. It's static so that it doesn't get reallocated.
*/
unsigned char NumBits;
long i, j, k, n;
long BlockSize, BlockEnd;
float DeltaAngle, DeltaAr;
float Alpha, Beta;
float TR, TI, AR, AI;
/*if ((!IsPowerOfTwo (NumSamples)) || NumSamples<2) {
printf ("Error in procedure Fourier: NumSamples is %ld, which is not a positive integer power of two.\n", NumSamples);
return false;}*/
NumBits = NumberOfBitsNeeded (NumSamples);
for (i=0; i<NumSamples; i++)
{
j = ReverseBits (i, NumBits); //I saved time here by pre-calculating all these values
RealOut [j] = RealIn [i];
ImagOut [j] = 0;
}
BlockEnd = 1; BlockSize = 2;
while (BlockSize<=NumSamples)
{
DeltaAngle = AngleNumerator/BlockSize;
Alpha = sin(0.5*DeltaAngle);
Alpha = 2*Alpha*Alpha;
Beta = sin(DeltaAngle);
i = 0;
while (i<NumSamples)
{
AR = 1; AI = 0;
j = i;
for (n=0; n<BlockEnd; n++)
{
k = j+BlockEnd;
TR = AR*RealOut [k]-AI*ImagOut [k];
TI = AI*RealOut [k]+AR*ImagOut [k];
RealOut [k] = RealOut [j]-TR;
ImagOut [k] = ImagOut [j]-TI;
RealOut [j] = RealOut [j]+TR;
ImagOut [j] = ImagOut [j]+TI;
DeltaAr = Alpha*AR+Beta*AI;
AI = AI-(Alpha*AI-Beta*AR);
AR = AR-DeltaAr;
j++;
}
i += BlockSize;
}
BlockEnd = BlockSize;
BlockSize = BlockSize*2;
}
return true;
}
/*void iDCT (long size, float *data_in, float *data_out)
{
unsigned long i, j;
memset (data_out, 0, sizeof(float)*size);
for (i=0; i<size; i++)
{
for (j=0; j<size; j++)
data_out [i] += data_in [j]*cos(M_PI*(float)j*(((float)i+0.5)/(float)size));
data_out [i] *= 2.0/(float)size;
}
}*/
void iDCT (long size, float *data_in, float *data_out)
{
float *din, *dout, k, s = float(size);
unsigned long i, j;
dout = (float *)memset (data_out, 0, sizeof(float)*size);
for (i=0; i<size; i++)
{
k = (((float)i+0.5)/s);
for (j=0,din = data_in ; j<size; j++)
*dout += *din++ * cos(M_PI*(float)j*k);
*dout++ *= 2.0/(float)size;
}
}
j'ai EXACTEMENT la meme sources, mais en Visual Basic :
Attribute VB_Name = "AudioFFT"
'----------------------------------------------------------------------
' Audio FFT
'----------------------------------------------------------------------
' This code is basically a stripped-down and ironed-out version of
' my VB FFT Library (available on the Deeth website) done entirely
' with digital audio in mind.
' My VB FFT Library (and thusly -- this as well) is heavily based on
' Don Cross's FFT code.
'----------------------------------------------------------------------
' Murphy McCauley (MurphyMc@Concentric.NET) 08/14/99
'----------------------------------------------------------------------
Option Explicit
'These don't change in this program, so I made them constants so they're
'as fast as can be.
Public Const AngleNumerator = 6.283185 ' 2 * Pi = 2 * 3.14159265358979
Public Const NumSamples = 1024
Public Const NumBits = 10
'Used to store pre-calculated values
Private ReversedBits(0 To NumSamples - 1) As Long
Sub DoReverse()
'I pre-calculate all these values. It's a lot faster to just read them from an
'array than it is to calculate 1024 of them every time FFTAudio() gets called.
Dim I As Long
For I = LBound(ReversedBits) To UBound(ReversedBits)
ReversedBits(I) = ReverseBits(I, NumBits)
Next
End Sub
Function ReverseBits(ByVal Index As Long, NumBits As Byte) As Long
Dim I As Byte, Rev As Long
For I = 0 To NumBits - 1
Rev = (Rev * 2) Or (Index And 1)
Index = Index \ 2
Next
ReverseBits = Rev
End Function
Sub FFTAudio(RealIn() As Integer, RealOut() As Single)
'In this case, NumSamples isn't included (since it's always the same),
'and the imaginary components are left out since they have no meaning here.
'I've used Singles instead of Doubles pretty much everywhere. I think this
'makes it faster, but due to type conversion, it actually might not. I should
'check, but I haven't.
'The imaginary components have no meaning in this application. I just left out
'the parts of the calculation that need the imaginary input values (which is a
'big speed improvement right there), but we still need the output array because
'it's used in the calculation. It's static so that it doesn't get reallocated.
Static ImagOut(0 To NumSamples - 1) As Single
'In fact... I declare everything as static! They all get initialized elsewhere,
'and Staticing them saves from wasting time reallocating and takes pressure off
'the heap.
Static I As Long, j As Long, k As Long, n As Long, BlockSize As Long, BlockEnd As Long
Static DeltaAngle As Single, DeltaAr As Single
Static Alpha As Single, Beta As Single
Static TR As Single, TI As Single, AR As Single, AI As Single
For I = 0 To (NumSamples - 1)
j = ReversedBits(I) 'I saved time here by pre-calculating all these values
RealOut(j) = RealIn(I)
ImagOut(j) = 0 'Since this array is static, gotta make sure it's clear
Next
BlockEnd = 1
BlockSize = 2
Do While BlockSize <= NumSamples
DeltaAngle = AngleNumerator / BlockSize
Alpha = Sin(0.5 * DeltaAngle)
Alpha = 2! * Alpha * Alpha
Beta = Sin(DeltaAngle)
I = 0
Do While I < NumSamples
AR = 1!
AI = 0!
j = I
For n = 0 To BlockEnd - 1
k = j + BlockEnd
TR = AR * RealOut(k) - AI * ImagOut(k)
TI = AI * RealOut(k) + AR * ImagOut(k)
RealOut(k) = RealOut(j) - TR
ImagOut(k) = ImagOut(j) - TI
RealOut(j) = RealOut(j) + TR
ImagOut(j) = ImagOut(j) + TI
DeltaAr = Alpha * AR + Beta * AI
AI = AI - (Alpha * AI - Beta * AR)
AR = AR - DeltaAr
j = j + 1
Next
I = I + BlockSize
Loop
BlockEnd = BlockSize
BlockSize = BlockSize * 2
Loop
End Sub
Godzil :
Ok merci. Non pasque la j'ai sous la main un de mes codes utilisant la FFT, mais je ne calcule que les harmoniques d'un signal, mais pas la fréquence fondamentalesbref
(en plus j'ai de fort doute sur la véracité de mon code ^^)
Bref (En fait j'ai besoin de récupérer le taux de certaines fréquences (en gros) dans un échantillon)
ex-Miles
:Godzil :
Ok merci. Non pasque la j'ai sous la main un de mes codes utilisant la FFT, mais je ne calcule que les harmoniques d'un signal, mais pas la fréquence fondamentales
Bref (En fait j'ai besoin de récupérer le taux de certaines fréquences (en gros) dans un échantillon)
Alors il est faux
Comme le dit Pollux, implémente l'algo de Cooley Tukey - sachant que c'est pour des puissances de 2 -, il est super rapide, facile à comprendre à partir du moment où on sait ce qu'est un butterfly.
Si tu es juste en réels, tu peux aussi utiliser l'algo de Bergland qui utilise moins d'espace mémoire et un butterfly modifié, mais c'est pas utile dans les applications non temps-réel ou embarquées.
Si tu dois le faire sur des entiers, il te faudra faire attention, dans la FFT traditionnelle, tu as un coefficient devant l'une des transformation pour que la transformée puis son inverse te donne le résultat de départ, et ce coefficient peut tout mettre en la'air si tu ne fais pas gaffe. Je ne sais plus exactement comment ça s'appelle, j'avais fait ça en stage, mais c'était il y a un an...
vince :
je dois avoir chez moi un TI MAG (pas sur, une revue sur les maths et les caltos de l'époque où j'étais au lycée) avec un exemple de FFT en tibasic... par contre ça sera pas avant le WE du 6 aout...
une seule explication est possible : c'est passé au tri
Godzil :
Non mais si mon algo est bon dans le principe, c'est juste qu'il est fait pour retrouver les harmoniques (2F, 3F & co) et pas la valeur de la fréquence de la fondamentale. Enfin pas tel qu'il est, et il passe par une astuce mathématique.
