using System;
namespace TestProject
{
/// <summary>
/// 고속 푸리엔 변환
/// </summary>
public class FFT
{
//////////////////////////////////////////////////////////////////////////////////////////////////// Field
////////////////////////////////////////////////////////////////////////////////////////// Static
//////////////////////////////////////////////////////////////////////////////// Protected
#region Field
/// <summary>
/// 사인 배정도 실수 배열
/// </summary>
/// <remarks>sin(pi / 2), sin(pi / 4), sin(pi / 8) ...</remarks>
protected static double[] _sineDoubleArray = null;
/// <summary>
/// 사인 단정도 실수 배열
/// </summary>
protected static float[] _sineFloatArray = null;
/// <summary>
/// 코사인 배정도 실수 배열
/// </summary>
/// <remarks>cos(pi / 2), cos(pi / 4), cos(pi / 8) ...</remarks>
protected static double[] _cosineDoubleArray = null;
/// <summary>
/// 코사인 단정도 실수 배열
/// </summary>
protected static float[] _cosineFloatArray = null;
/// <summary>
/// 테이블 잠금 객체
/// </summary>
protected static object _tableLock = new object();
#endregion
//////////////////////////////////////////////////////////////////////////////////////////////////// Method
////////////////////////////////////////////////////////////////////////////////////////// Static
//////////////////////////////////////////////////////////////////////////////// Public
// 배정도 실수
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
public static void ComputeForwardFFT(double[] sourceRealArray)
{
ComputeFFT(sourceRealArray, true);
}
#endregion
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray, targetRealArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
public static void ComputeForwardFFT(double[] sourceRealArray, double[] targetRealArray)
{
ComputeFFT(sourceRealArray, targetRealArray, true);
}
#endregion
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeForwardFFT(double[] sourceRealArray, double[] targetRealArray, double[] targetImaginaryArray)
{
ComputeFFT(sourceRealArray, targetRealArray, targetImaginaryArray, true);
}
#endregion
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray, sourceImaginaryArray, targetRealArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
public static void ComputeForwardFFT(float[] sourceRealArray, float[] sourceImaginaryArray, float[] targetRealArray)
{
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, true);
}
#endregion
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeForwardFFT
(
double[] sourceRealArray,
double[] sourceImaginaryArray,
double[] targetRealArray,
double[] targetImaginaryArray
)
{
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, true);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
public static void ComputeInverseFFT(double[] sourceRealArray)
{
ComputeFFT(sourceRealArray, false);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray, targetRealArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
public static void ComputeInverseFFT(double[] sourceRealArray, double[] targetRealArray)
{
ComputeFFT(sourceRealArray, targetRealArray, false);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeInverseFFT(double[] sourceRealArray, double[] targetRealArray, double[] targetImaginaryArray)
{
ComputeFFT(sourceRealArray, targetRealArray, targetImaginaryArray, true);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeInverseFFT
(
double[] sourceRealArray,
double[] sourceImaginaryArray,
double[] targetRealArray,
double[] targetImaginaryArray
)
{
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, false);
}
#endregion
// 단정도 실수
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
public static void ComputeForwardFFT(float[] sourceRealArray)
{
ComputeFFT(sourceRealArray, true);
}
#endregion
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray, targetRealArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
public static void ComputeForwardFFT(float[] sourceRealArray, float[] targetRealArray)
{
ComputeFFT(sourceRealArray, targetRealArray, true);
}
#endregion
#region 순방향 FFT 계산하기 - ComputeForwardFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 순방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeForwardFFT
(
float[] sourceRealArray,
float[] sourceImaginaryArray,
float[] targetRealArray,
float[] targetImaginaryArray
)
{
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, true);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
public static void ComputeInverseFFT(float[] sourceRealArray)
{
ComputeFFT(sourceRealArray, false);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray, targetRealArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
public static void ComputeInverseFFT(float[] sourceRealArray, float[] targetRealArray)
{
ComputeFFT(sourceRealArray, targetRealArray, false);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeInverseFFT(float[] sourceRealArray, float[] targetRealArray, float[] targetImaginaryArray)
{
ComputeFFT(sourceRealArray, targetRealArray, targetImaginaryArray, true);
}
#endregion
#region 역방향 FFT 계산하기 - ComputeInverseFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray)
/// <summary>
/// 역방향 FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
public static void ComputeInverseFFT
(
float[] sourceRealArray,
float[] sourceImaginaryArray,
float[] targetRealArray,
float[] targetImaginaryArray
)
{
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, false);
}
#endregion
//////////////////////////////////////////////////////////////////////////////// Protected
#region 배열 값 설정하기 - SetArrayValue()
/// <summary>
/// 배열 값 설정하기
/// </summary>
protected static void SetArrayValue()
{
if(_sineDoubleArray != null)
{
return;
}
lock(_tableLock)
{
if(_sineDoubleArray != null)
{
return;
}
int size = 20;
double[] sineDoubleArray = new double[size];
float[] sineFloatArray = new float[size];
double[] cosineDoubleArray = new double[size];
float[] cosineFloatArray = new float[size];
double pi = Math.PI;
for(int i = 0; i < size; i++)
{
sineDoubleArray[i] = Math.Sin(pi);
sineFloatArray[i] = (float)(sineDoubleArray[i]);
cosineDoubleArray[i] = Math.Cos(pi);
cosineFloatArray[i] = (float)(cosineDoubleArray[i]);
pi /= 2;
}
_sineFloatArray = sineFloatArray;
_sineDoubleArray = sineDoubleArray;
_cosineFloatArray = cosineFloatArray;
_cosineDoubleArray = cosineDoubleArray;
}
}
#endregion
#region 비트 반전하기 - ReverseBit(value, bitCount)
/// <summary>
/// 비트 반전하기
/// </summary>
/// <param name="value">값</param>
/// <param name="bitCount">비트 수</param>
/// <returns>반전 값</returns>
protected static int ReverseBit(int value, int bitCount)
{
int result = 0;
for(int b = 0; b < bitCount; ++b)
{
result <<= 1;
result |= value & 1;
value >>= 1;
}
return result;
}
#endregion
// 배정도 실수
#region FFT 수행하기 - PerformFFT(sourceRealArray, sourceImaginaryArray, forward)
/// <summary>
/// FFT 수행하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void PerformFFT(double[] sourceRealArray, double[] sourceImaginaryArray, bool forward)
{
int length = sourceRealArray.Length;
double sign = forward ? 1 : -1;
int index = 0;
for(int p = 1; p < length; p <<= 1)
{
int p2 = p << 1;
double sine = sign * _sineDoubleArray[index];
double cosine = _cosineDoubleArray[index++];
double wr = 1.0;
double wi = 0.0;
int j;
for(j = 0; j < p; ++j)
{
int k;
for(k = j; k < length; k += p2)
{
int k2 = k + p;
double tr = (wr * sourceRealArray[k2]) - (wi * sourceImaginaryArray[k2]);
double ti = (wr * sourceImaginaryArray[k2]) + (wi * sourceRealArray[k2]);
sourceRealArray[k2] = sourceRealArray[k] - tr;
sourceImaginaryArray[k2] = sourceImaginaryArray[k] - ti;
sourceRealArray[k] += tr;
sourceImaginaryArray[k] += ti;
}
double nwr = (wr * cosine) - (wi * sine);
double nwi = (wi * cosine) + (wr * sine);
wr = nwr;
wi = nwi;
}
}
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT
(
double[] sourceRealArray,
double[] sourceImaginaryArray,
double[] targetRealArray,
double[] targetImaginaryArray,
bool forward
)
{
SetArrayValue();
int length = sourceRealArray.Length;
int i;
int bitCount = 0;
for(i = 1; i < length; i <<= 1)
{
bitCount++;
}
for(i = 0; i < length; i++)
{
int p = ReverseBit(i, bitCount);
targetRealArray[p] = sourceRealArray[i];
targetImaginaryArray[p] = sourceImaginaryArray[i];
}
PerformFFT(targetRealArray, targetImaginaryArray, forward);
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT(double[] sourceRealArray, bool forward)
{
double[] targetRealArray = new double[sourceRealArray.Length];
double[] sourceImaginaryArray = new double[sourceRealArray.Length];
double[] targetImaginaryArray = new double[sourceRealArray.Length];
for(int i = 0; i < sourceRealArray.Length; i++)
{
sourceImaginaryArray[i] = 0;
}
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward);
for(int i = 0; i < sourceRealArray.Length; i++)
{
targetRealArray[i] = System.Math.Sqrt
(
(targetRealArray[i] * targetRealArray[i]) + (targetImaginaryArray[i] * targetImaginaryArray[i])
);
}
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, targetRealArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT(double[] sourceRealArray, double[] targetRealArray, bool forward)
{
double[] sourceImaginaryArray = new double[sourceRealArray.Length];
double[] targetImaginaryArray = new double[sourceRealArray.Length];
for(int i = 0; i < sourceRealArray.Length; i++)
{
sourceImaginaryArray[i] = 0;
}
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward);
for(int i = 0; i < sourceRealArray.Length; i++)
{
targetRealArray[i] = Math.Sqrt
(
(targetRealArray[i] * targetRealArray[i]) + (targetImaginaryArray[i] * targetImaginaryArray[i])
);
}
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, targetRealArray, targetImaginaryArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT(double[] sourceRealArray, double[] targetRealArray, double[] targetImaginaryArray, bool forward)
{
double[] sourceImaginaryArray = new double[sourceRealArray.Length];
for(int i = 0; i < sourceRealArray.Length; i++)
{
sourceImaginaryArray[i] = 0;
}
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward);
}
#endregion
// 단정도 실수
#region FFT 수행하기 - PerformFFT(sourceRealArray, sourceImaginaryArray, forward)
/// <summary>
/// FFT 수행하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void PerformFFT(float[] sourceRealArray, float[] sourceImaginaryArray, bool forward)
{
int length = sourceRealArray.Length;
float sign = forward ? 1 : -1;
int index = 0;
for(int p = 1; p < length; p <<= 1)
{
int p2 = p << 1;
float sine = sign * _sineFloatArray[index];
float cosine = _cosineFloatArray[index++];
float wr = 1.0f;
float wi = 0.0f;
int j;
for(j = 0; j < p; j++)
{
int k;
for(k = j; k < length; k += p2)
{
int k2 = k + p;
float tr = (wr * sourceRealArray[k2]) - (wi * sourceImaginaryArray[k2]);
float ti = (wr * sourceImaginaryArray[k2]) + (wi * sourceRealArray[k2]);
sourceRealArray[k2] = sourceRealArray[k] - tr;
sourceImaginaryArray[k2] = sourceImaginaryArray[k] - ti;
sourceRealArray[k] += tr;
sourceImaginaryArray[k] += ti;
}
float nwr = (wr * cosine) - (wi * sine);
float nwi = (wi * cosine) + (wr * sine);
wr = nwr;
wi = nwi;
}
}
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소수 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="targetImaginaryArray">타겟 허수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT
(
float[] sourceRealArray,
float[] sourceImaginaryArray,
float[] targetRealArray,
float[] targetImaginaryArray,
bool forward
)
{
SetArrayValue();
int length = sourceRealArray.Length;
int i;
int bitCount = 0;
for(i = 1; i < length; i <<= 1)
{
bitCount++;
}
length = 1 << (bitCount-1);
for(i = 0; i < length; i++)
{
int p = ReverseBit(i, bitCount);
targetRealArray[p] = sourceRealArray[i];
targetImaginaryArray[p] = sourceImaginaryArray[i];
}
PerformFFT(targetRealArray, targetImaginaryArray, forward);
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT(float[] sourceRealArray, bool forward)
{
float[] sourceImaginaryArray = new float[sourceRealArray.Length];
float[] targetRealArray = new float[sourceRealArray.Length];
float[] targetImaginaryArray = new float[sourceRealArray.Length];
for(int i = 0; i < sourceRealArray.Length; i++)
{
sourceImaginaryArray[i] = 0;
}
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward);
for(int i = 0; i < sourceRealArray.Length; i++)
{
targetRealArray[i] = (float)Math.Sqrt
(
(targetRealArray[i] * targetRealArray[i]) + (targetImaginaryArray[i] * targetImaginaryArray[i])
);
}
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, targetRealArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT(float[] sourceRealArray, float[] targetRealArray, bool forward)
{
float[] sourceImaginaryArray = new float[sourceRealArray.Length];
float[] targetImaginaryArray = new float[sourceRealArray.Length];
float[] temporaryRealArray = new float[sourceRealArray.Length];
for(int i = 0; i < sourceRealArray.Length; i++)
{
sourceImaginaryArray[i] = 0;
}
ComputeFFT(sourceRealArray, sourceImaginaryArray, temporaryRealArray, targetImaginaryArray, forward);
for(int i = 0; i < targetRealArray.Length; i++)
{
targetRealArray[i] = (float)Math.Sqrt
(
(temporaryRealArray[i] * temporaryRealArray[i]) + (targetImaginaryArray[i] * targetImaginaryArray[i])
);
}
}
#endregion
#region FFT 계산하기 - ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, forward)
/// <summary>
/// FFT 계산하기
/// </summary>
/// <param name="sourceRealArray">소스 실수 배열</param>
/// <param name="sourceImaginaryArray">소스 허수 배열</param>
/// <param name="targetRealArray">타겟 실수 배열</param>
/// <param name="forward">순방향 여부</param>
protected static void ComputeFFT(float[] sourceRealArray, float[] sourceImaginaryArray, float[] targetRealArray, bool forward)
{
float[] targetImaginaryArray = new float[sourceRealArray.Length];
ComputeFFT(sourceRealArray, sourceImaginaryArray, targetRealArray, targetImaginaryArray, forward);
for(int i = 0; i < sourceRealArray.Length; i++)
{
targetRealArray[i] = (float)Math.Sqrt
(
(targetRealArray[i] * targetRealArray[i]) + (targetImaginaryArray[i] * targetImaginaryArray[i])
);
}
}
#endregion
}
}