Raqamli signallarni qayta ishlashda Furye transformatsiyasi

// Zero-index element calculation
X[0] = x.Sum() / N;


for (int k = 1; k < N/2 + 1; k++)
{
X[k] = 0;


Efor (int n = 0; n < N; n++)
{
X[k] += x[n] * Complex.Exp(-Complex.ImaginaryOne * 2 * Math.PI * (k * n) / Convert.ToDouble(N));
}

X[k] = X[k] / N;

// Miss additional calculation for center element
if (k != N / 2)
{
X[N - k] = new Complex(X[k].Real, -X[k].Imaginary);
}
}


return X;
}


///

/// Calculates forward Discrete Fourier Transform of given digital signal x with respect to sample numbers and reduced number of multiplications
///

///
Signal x samples values

///
Samples numbers vector

/// Fourier Transform of signal x
public Complex[] DFT2(Double[] x, int[] SamplesNumbers)
{
int N = x.Length; // Number of samples
Complex[] X = new Complex[N];


for (int k = 0; k < N / 2 + 1; k++)
{
X[k] = 0;
Double s1 = SamplesNumbers[k];


for (int n = 0; n < N; n++)
{
Double s2 = SamplesNumbers[n];
X[k] += x[n] * Complex.Exp(-Complex.ImaginaryOne * 2 * Math.PI * (s1 * s2) / Convert.ToDouble(N));
}

X[k] = X[k] / N;

// Miss additional calculation for center element
if (k != N/2)
{
X[N - k - 1] = new Complex(X[k].Real, -X[k].Imaginary);
}
}


return X;
}


Misollar:



9-rasm. 2-rasmdagi signalning amplituda spektri. hisoblash soni kamaytirilgan DFT bilan belgilanadi



10-rasm. 7-rasmdagi signalning amplituda spektri. hisoblash soni kamaytirilgan DFT bilan belgilanadi


Tez Furye o'zgarishi:
Furye transformatsiyasi formulasini quyidagilarga bo'lish mumkin:
X( k ) =1N∑n = 0N− 1x ( n ) ⋅e− j2 pNk n=1N∑n = 0N2− 1x ( 2 n ) ⋅V2 n kN+1N∑n = 0N2− 1x ( 2 n + 1 ) ⋅V( 2 n + 1 ) kNX(k)=1N∑n=0N−1x(n)⋅e−j2pNkn=1N∑n=0N2−1x(2n)⋅VN2nk+1N∑n=0N2−1x(2n+1)⋅VN(2n+1)k
qayerda
V2 n kN=e− j2 pN2 n k=e− j2 pN2n k=Vn kN2VN2nk=e−j2pN2nk=e−j2pN2nk=VN2nk
va
V( 2 n + 1 ) kN=V2 n k + kN=V2 n kN⋅VkN=Vn kN2⋅VkNVN(2n+1)k=VN2nk+k=VN2nk⋅VNk=VN2nk⋅VNk
shuning uchun:
X( k ) =1N∑n = 0N2− 1x ( 2 n ) ⋅Vn kN2+1N⋅VkN∑n = 0N2− 1x ( 2 n + 1 ) ⋅Vn kN2X(k)=1N∑n=0N2−1x(2n)⋅VN2nk+1N⋅VNk∑n=0N2−1x(2n+1)⋅VN2nk
Bu oddiyroq shaklda yozilishi mumkin bo'lgan, juft namunalar uchun bajarilgan hisoblarni toq bo'lganlardan ajratib turadigan:
X( k ) =XE( k ) +VkN⋅XO( k )X(k)=XE(k)+VNk⋅XO(k)

Shunga ko'ra, N = 8 holati uchun oldingi hisob-kitoblarimizga murojaat qilib, quyidagicha yozish mumkin:
X( 0 ) =XE( 0 ) +V08⋅XO( 0 )X( 1 ) =XE( 1 ) +V18⋅XO( 1 )X( 2 ) =XE( 2 ) +V28⋅XO( 2 )X( 3 ) =XE( 3 ) +V38⋅XO( 3 )X( 4 ) =XE( 0 ) +V48⋅XO( 0 ) =XE( 0 ) −V08⋅XO( 0 )X( 5 ) =XE( 1 ) +V58⋅XO( 1 ) =XE( 1 ) −V18⋅XO( 1 )X( 6 ) =XE( 2 ) +V68⋅XO( 2 ) =XE( 2 ) −V28⋅XO( 2 )X( 7 ) =XE( 3 ) +V78⋅XO( 3 ) =XE( 3 ) −V38⋅XO( 3 )X(0)=XE(0)+V80⋅XO(0)X(1)=XE(1)+V81⋅XO(1)X(2)=XE(2)+V82⋅XO(2)X(3)=XE(3)+V83⋅XO(3)X(4)=XE(0)+V84⋅XO(0)=XE(0)−V80⋅XO(0)X(5)=XE(1)+V85⋅XO(1)=XE(1)−V81⋅XO(1)X(6)=XE(2)+V86⋅XO(2)=XE(2)−V82⋅XO(2)X(7)=XE(3)+V87⋅XO(3)=XE(3)−V83⋅XO(3)


grafik sifatida taqdim etilishi mumkin:



11-rasm. DFTning juft va toq namunalarga parchalanishini hisoblash.


E'tibor bering, elementlar:
va


Xuddi shu tarzda hisoblash mumkin: x (0), x (4), x (1) va x (5) elementlari ularning diagrammalarida juft indekslar, x (2), x (6), x (3 ) ) va x (7) toq sonlardir. Ularni tartiblangan juftlikda birlashtirib, yuqoridagi grafiklarni qayta chizish mumkin:

Nihoyat, ushbu misolda:

12-rasm. N = 8 signal uchun Fast Furier Transform ( RADIX-2 ) .


N = 8 signal uchun DFT ta'rifini belgilashda biz 64 ta ko'paytirish amalini bajarishimiz kerak edi, lekin yuqoridagi kuzatishlar tufayli biz ularni atigi 12 ta qildik. Signaldagi namunalar soni qanchalik ko'p bo'lsa, hisob-kitoblar sonining foydasi shunchalik ko'p bo'ladi. FFT algoritmi, chunki N -smaple signali uchun hisob-kitoblar miqdori quyidagicha aniqlanishi mumkin:
N2l og2( N)N2log2(N)
Bunday hisoblashning asosiy elementi "kapalak" deb ataladi:



qayerda
Y( k ) = y( k ) +VkN⋅ y( k +N2)Y( k +N2) = y( k ) −VkN⋅ y( k +N2)Y(k)=y(k)+VNk⋅y(k+N2)Y(k+N2)=y(k)−VNk⋅y(k+N2)