Algoritmo FFT de DFT de 16 puntos
FFT (Transformada Rápida de Fourier) es un caso especial de DFT, que es una operación realizada cuando el número de puntos de operación es una potencia entera de 2 (no lo suficiente se rellena con ceros).
Principio de cálculo y diagrama de flujo de FFT:
Principio: el cálculo de FFT requiere que el número de puntos sea una potencia entera de 2. Si el número de puntos no es suficiente, utilice 0 para completarlo. Por ejemplo, para calcular la FFT de 16 puntos de {2, 3, 5, 8, 4}, debe agregar 11 ceros antes del cálculo. El cálculo de FFT utiliza la operación mariposa. En la operación mariposa, la regla de cambio se deriva de W (N, p), donde N es el número de puntos de cálculo FFT y J es el valor del subíndice.
Cuando L = 1, W(N, p) = W(N, J) = W(2^L, J), donde J = 0
L = 2; Cuando, W(N, p) = W(N, J) = W(2^L, J), donde J = 0, 1;
Cuando L = 3, W(N, p) = W(N, J) = W(2^L, J), donde J = 0, 1, 2, 3;
Entonces, W(N, p) = W(2^L, J), donde J = 0, 1, ..., 2^(L-1)-1
Y porque 2^L = 2^M*2^(L-M) = N*2^ (L-M), donde N es una potencia entera de 2, es decir, N=2^M,
W(N, p) = W(2^L, J) = W(N*2 ^( L-M), J) = W(N, J*2^(M-L))
Entonces, p = J*2^(M-L), donde J = 0, 1, ..., 2 ^ (L-1) -1, cuando el recorrido de J finaliza pero el número de puntos de cálculo no es suficiente para N, J = J 2 ^ L, y luego continúa atravesando hasta que el número de puntos de cálculo llega a N y ya no se repite. .
Diagrama de flujo:
Código de implementación: /*============================= ==========================================? *?Nombre del método: fft? *?Función del método: ¿Calcular la FFT de la matriz, usando la operación de mariposa? *? *?Nombre de la variable:? *yVector?-?Datos originales? *¿Longitud de los datos originales? fftYreal -?¿La parte real después de FFT? *fftYImg?-?¿La parte imaginaria después de FFT? *? *?Valor de retorno: una señal de éxito, si tiene éxito, devuelve verdadero, de lo contrario devuelve falso *======= == ================================================== == ==========*/
?(BOOL)fft: (floatfloat?*)yVector?andOriginalLength: (NSInteger)length?andFFTCount: (NSInteger)N?andFFTReal: (floatfloat ?*)fftYReal?andFFTYImg: (floatfloat?*)fftYImg
{
//? Asegúrese de que el cálculo sea siempre el cálculo de la potencia entera de 2
NSInteger?N1 ?=?[self?nextNumOfPow2:N];
//?Defina el indicador de si la operación FFT es exitosa
BOOL?isFFTOK?=?false ;
///?Determine si el punto de cálculo es una potencia entera de 2
if?(N?!=?N1)
{
//?No 2 a potencias enteras, calcule directamente DFT
isFFTOK?=?[self?dft:yVector?andOriginalLength:length?andFFTCount:N?andFFTReal:fftYReal?andFFTYImg:fftYImg] ;
///?Devolver indicador de éxito
return?isFFTOK;
}
//?Si calculas la potencia entera de dígito 2, use el cálculo FFT, de la siguiente manera
//?Defina variables
float?yVectorN[N1];?//?Datos originales de la operación de N puntos
NSInteger?powOfN?=?log2 (N1); //?N?=?2^powOfN, utilizado para marcar el nivel máximo de operación (expresado como: M en la fórmula)
NSInteger? nivel?=?1; //Número de nivel de operación (número de operaciones), el máximo es powOfN, el valor inicial es la operación de primer nivel (expresada como: L en la fórmula)
NSInteger?lineNum ;//?Número de línea, mariposa dispuesta en orden inverso Número de línea de operación (expresado como: k en la fórmula)
float?inverseOrderY[N1]; //yVector orden inverso x
NSInteger?distanceLine?=?1;?//? Interlineado, operación nivelada, la distancia entre dos nodos de cada mariposa es DistanceLine?=?2^(L-1) (expresado como: B en la fórmula)
NSInteger?p; ///? El orden del factor de rotación, el factor de rotación se expresa como ?W(N,?p), p?=?J*2^(M-L)
NSInteger?J; ///?El orden del factor de rotación, rotar
Los factores se expresan como?W(2^L,?J), J?=?0,?1,?2,...,?2^(L-1)?-?1?=?distanceLine?- ?1
float?realTemp,?imgTemp,?twiddleReal,?twiddleImg,?twiddleTheta,?twiddleTemp?=?PI_x_2/N1;
NSInteger?N_4?=?N1/4 ;
//?Determine si el número de puntos es suficiente para el cálculo de FFT
if?(length?lt;=?N1)
{
/ /?Si N tiene al menos longitud, primero asigne todos los valores a yVector
for?(NSInteger?i?=?0;?i?lt;?length;? i)
{
yVectorN[i]?=?yVector[i];
}
si?(longitud?lt ;?N1)
{
//?If?N?gt;?length? va seguido de ceros
para?(NSInteger?i?= ?longitud;?i?lt;?N1; ?i )
{
yVectorN[i]?=?0.0;
}
}
}
else
{
//?If?N?lt;?length?Interceptar los datos de la longitud correspondiente para la operación
for?(NSInteger?i?=?0;?i?lt;?N1;?i)
{
yVectorN[i]?=?yVector[i];
}
}
//?Llamar al método de orden inverso
[self?inverseOrder:yVectorN?andN:N1?andInverseOrderVector:inverseOrderY] ;
//?Valor inicial
para?(NSInteger?i?=?0;?i?lt ;?N1;?i)
{
fftYReal[i]?=?inverseOrderY[i];
fftYImg[i]?=?0.0;
}
///?Bucle de tres niveles
//?El tercer nivel (el más interno): completa la operación de mariposa del mismo factor de rotación
//?El segundo nivel (medio): Completo El factor de rotación cambia en pasos de 2^nivel
//?El primer nivel (el más externo): Completo Procesos de iteración, es decir , calcular x(k)?=?A0(k), ?A1(k),...,Am(k)?=?X(k)
//?Bucle de primer nivel
mientras?(level?lt;= ?powOfN)
{
distanceLine?=?powf(2,?level?-?1);?// ?Condición inicial?distanceLine?=?2^(nivel- 1)
J?=?0;
NSInteger?pow2_Level?=?distanceLine?*?2;?// ?2^level
NSInteger? pow2_NSubL?=?N1/pow2_Level;//?2^(M-L)
//?Bucle de segundo nivel
mientras ?(J?lt;?distanceLine)
{
p
?=?J?*?pow2_NSubL;
lineNum?=?J;
NSInteger?stepCount?=?0;?//?J recuento de pasos de operación
//?Encuentra el factor de rotación
if?(p==0)
{
twiddleReal?=?1.0;
twiddleImg?=?0.0;
}
else?if?(p?==?N_4)
{
twiddleReal?=?0.0;
twiddleImg?=?-1.0;
}
else
{
//?Calcular θ en la fórmula de Euler
twiddleTheta?=?twiddleTemp?*?p;
//?Calcular las partes real e imaginaria de números complejos
twiddleReal?=?cos(twiddleTheta);
twiddleImg?=?-11?*?sin(twiddleTheta);
}
/ / ?Bucle de tercer nivel
while?(lineNum?lt;?N1)
{
//?Calcular subíndice
NSInteger? footNum?=?lineNum? ?distanceLine;
/*----------------------- --- -------? *?Utilice operaciones con números complejos para calcular los resultados de la operación mariposa para cada fila en cada nivel? N, p)? *?X(k B)?=?X(k)?-?X(k B)*W(N, p)? -----------------------*/
realTemp?=?fftYReal[footNum]?*?twiddleReal?-?fftYImg [footNum] ]?*?twiddleImg;
imgTemp=?fftYReal[footNum]?*?twiddleImg? ?fftYImg[footNum]?*?twiddleReal;
//? y las partes imaginarias se almacenan en la matriz de retorno respectivamente
fftYReal[footNum]?=?fftYReal[lineNum]?-?realTemp;
fftYImg[footNum]=?fftYImg[ lineNum] ?-?imgTemp;
fftYReal[lineNum]?=?fftYReal[lineNum]? ?realTemp;
fftYImg[lineNum]=?fftYImg[lineNum]? p>
stepCount? =?pow2_Level;
//?Cambio de número de línea
lineNum?=?J?stepCount;
}
//?La transformación de orden del factor de rotación logra el efecto de cambiar el factor de rotación
J;
}
//? Agregue uno al nivel de operación
level;
}
isFFTOK?=?true;
return?isFFTOK;
}