Raqamli signallarni qayta ishlashda Furye transformatsiyasi

Kichikroq, asosiy "kapalaklar"gacha bo'lgan ketma-ket parchalanish bosqichlari faqat N ning 2 kuchi deb taxmin qilingan holda amalga oshirilishi mumkin .


Amalda tez Furye o'zgarishi:


To'g'ri namunalar soni
Signalni qayta ishlashning eng oson yo'li 2 quvvatga ega bo'lgan namunalar soniga ega, shunchaki etishmayotgan nol namunalarini to'ldiring. Signal tuzilishiga qarab, qo'shimchalar o'ng qo'l, chap qo'l yoki ikkala tomon sifatida amalga oshirilishi mumkin.



13-rasm. 2-rasmdan to'ldirilgan signal

Namunalarni saralash:

Tegishli juftlikdagi ketma-ket signal namunalarini ulash uchun biz dastlabki tartiblash algoritmlaridan foydalanamiz. Biroq, FFT algoritmi saralanmagan namunalarda, saralash operatsiyasi (xuddi shunday) spektr namunalarida ham amalga oshirilishi mumkin.

Spektr analizatorlarining apparat vositalarida va past darajadagi dasturlash tillarida namunalarni saralash ancha oson, chunki operatsiya indeks namunasining binar ko'rinishidagi bitlarni oddiy inversiyaga asoslangan.

N = 8 signalimizda biz quyidagilarni ko'rishimiz mumkin :

x ( 0 )x ( 1 )x ( 2 )x ( 3 )x ( 4 )x ( 5 )x ( 6 )x ( 7 )000001010011100101110111→→→→→→→→000100010110001101011111x ( 0 )x ( 4 )x ( 2 )x ( 6 )x ( 1 )x ( 5 )x ( 3 )x ( 7 )

Umumiy holda usulni amalga oshirish:

Kichraytirish ▲

///

/// Input data sorting using bit reversal method
///

///
Original input signal samples

/// Sorted signal samples

public Double[] FFTDataSort(Double[] x)
{
int N = x.Length; // signal length

if (Math.Log(N, 2) % 1 != 0)

{
throw new Exception("Number of samples in signal must be power of 2");
}

Double[] y = new Double[N]; // output (sorted) vector

int BitsCount = (int)Math.Log(N, 2); // maximum number of bits in index binary representation

for (int n = 0; n < N; n++)

{
string bin = Convert.ToString(n, 2).PadLeft(BitsCount, '0'); // index binary representation
StringBuilder reflection = new StringBuilder(new string('0', bin.Length));

for (int i = 0; i < bin.Length; i++)

{
reflection[bin.Length - i - 1] = bin[i]; // binary reflection
}

int number = Convert.ToInt32(reflection.ToString(),2); // new index

y[number] = x[n];

}

return y;

}
Biroq, bu operatsiya indeks raqamini ikkilik shaklga o'zgartirmasdan ancha tezroq bajarilishi mumkin:

Kichraytirish ▲

///

/// Input data sorting using index shift method
///

///
Original input signal samples

/// Sorted signal samples

public Double[] FFTDataSort2(Double[] x)
{
int N = x.Length; // signal length

if (Math.Log(N, 2) % 1 != 0)

{
throw new Exception("Number of samples in signal must be power of 2");
}

int m = 1; // original index

for (int n = 0; n < N - 1; n++) // n - new index

{
if (n < m)
{
Double T = x[m-1];
x[m-1] = x[n];
x[n] = T;
}

int s = N / 2; // shift operator

while (s < m)

{
m = m - s;
s = s / 2;
}

m = m + s;

}

return x;

}

14-rasm. Saralangan signal namunalari (2-rasmdagi signal o'ng tomonda to'ldirilgan)

Fast Fourier Transfom algoritmi
FFT algoritmini amalga oshirish quyida ko'rsatilgan.

Kichraytirish ▲

///

/// Calculates forward Fast Fourier Transform of given digital signal x
///

///
Signal x samples values

/// Fourier Transform of signal x

public Complex[] FFT(Double[] x)
{
int N = x.Length; // Number of samples

if (Math.Log(N, 2) % 1 != 0)

{
throw new Exception("Number of samples in signal must be power of 2");
}
Complex[] X = new Complex[N]; // Signal specturm

// Rewrite real signal values to calculated spectrum

for (int i = 0; i < N; i++)
{
X[i] = new Complex(x[i], 0);
}

int S = (int)Math.Log(N, 2); // Number of calculation stages

for (int s = 1; s < S + 1; s++) // s - stage number

{
int BW = (int)Math.Pow(2, s - 1); // the width of butterfly
int Blocks = (int)(Convert.ToDouble(N) / Math.Pow(2, s)); // Number of blocks in stage
int BFlyBlocks = (int)Math.Pow(2, s - 1); // Number of butterflies in block
int BlocksDist = (int)Math.Pow(2, s); // Distnace between blocks

Complex W = Complex.Exp(-Complex.ImaginaryOne * 2 * Math.PI / Math.Pow(2, s)); // Fourier Transform kernel

for (int b = 1; b < Blocks + 1; b++)

{
for (int m = 1; m < BFlyBlocks + 1; m++)
{
int itop = (b - 1) * BlocksDist + m; // top butterfly index
int ibottom = itop + BW; // bottom butterfly index

Complex Xtop = X[itop-1]; // top element -> X(k)

Complex Xbottom = X[ibottom-1] * Complex.Pow(W, m - 1); // bottom element -> X(k + N/2)

// Butterfly final calculation

X[itop-1] = Xtop + Xbottom;
X[ibottom-1] = Xtop - Xbottom;
}
}
}

// Spectrum scaling

for (int i = 0; i < N; i++)
{
X[i] = X[i] / Convert.ToDouble(N);
}
return X;
}

15-rasm. FFT - Saralangan namunalar bilan signalning amplituda spektri (14-rasmdan)



16-rasm. FFT - Saralangan namunalar bilan siljitilgan signalning amplituda spektri (14-rasmdan):
Teskari tez Furye konvertatsiyasi oldinga FFT usulini kichik o'zgartirish orqali amalga oshirilishi mumkin:

Kichraytirish ▲

///

/// Calculates inverse Fast Fourier Transform of given spectrum
///

///
Spectrum values

/// Signal samples

public Double[] iFFT(Complex[] X)
{
int N = X.Length; // Number of samples
Double[] x = new Double[N];
int E = (int)Math.Log(N, 2);

for (int e = 1; e < E + 1; e++)

{
int SM = (int)Math.Pow(2, e - 1);
int LB = (int)(Convert.ToDouble(N) / Math.Pow(2, e));
int LMB = (int)Math.Pow(2, e - 1);
int OMB = (int)Math.Pow(2, e);

Complex W = Complex.Exp(Complex.ImaginaryOne * 2 * Math.PI / Math.Pow(2, e)); // changed sign - our minor change

for (int b = 1; b < LB + 1; b++)

{
for (int m = 1; m < LMB + 1; m++)
{
int g = (b - 1) * OMB + m;
int d = g + SM;

Complex xgora = X[g - 1];

Complex xdol = X[d - 1] * Complex.Pow(W, m - 1);

X[g - 1] = xgora + xdol;

X[d - 1] = xgora - xdol;
}
}
}

for (int i = 0; i < N; i++)

{
x[i] = X[i].Real;
}

return x;

}

17-rasm. 15-rasmdagi spektrdan teskari Fast Furier Transform yordamida signal tiklandi.
Ko'rinib turibdiki, qo'shimcha nol namunalari bilan to'ldirilgan signal spektrga ta'sir qilmaydi - 15 va 16 raqamlarda qo'shimcha chiziqlarni ko'rish mumkin. Shunga qaramay, biz ularni keyingi hisob-kitoblar uchun saqlaganimizda, biz asl signalni tiklashimiz mumkin.

Biroq, keling, biz hali ham signalni shovqindan ajratib, uni FFT usullaridan foydalanib tiklashimiz mumkinligini ko'rib chiqaylik.

Birinchidan, bezovtalanishga shubha qilingan chiziqlarni olib tashlang:

18-rasm. Filtrlangan signal spektri
Ikkinchidan, teskari FFTni hisoblang

19-rasm. Teskari FFT - tiklangan signal:
Uchinchidan, qo'shimcha namunalarni kesib oling



20-rasm. Qo'shimcha namunalarsiz signal.

Oxirida asl (bezovta qilinmagan) signalni filtrlash natijasi bilan solishtiring.

21-rasm. Asl va chiqish signalini taqqoslash (Fast Furier Transform).

Koddan foydalanish:

Ushbu maqolada keltirilgan barcha signallarni qayta ishlash algoritmlari biriktirilgan manba kodida amalga oshiriladi. DiscreteFourierTransform kutubxonasi bilan ishlashni boshlash uchun uning nom maydonini e'lon qilish kifoya:

using DiscreteFourierTransform;

yangi ob'ekt yaratish:

DiscreteFourierTransform.DiscreteFourierTransform dft = new DiscreteFourierTransform.DiscreteFourierTransform();

va chastota domenida raqamli signalni qayta ishlash bilan sarguzashtingizni boshlang.

Kutubxona usullari va ilovalari

Sinov signali:
Bezovta qilingan sinus signali va namunalar indekslari dll fayliga kiritilgan:

Double[] signal = dft.testsignal();

int[] n = dft.testsignalindexes();
Diskret Furye transformatsiyasi.
// --- Discrete Fourier Transform by definition

Complex[] X = dft.DFT(signal); // discrete fourier transform by definition

Double[] A = dft.Amplitude(X); // amplitude spectrum from X

Complex[] Xa = dft.DFT(signal, n); //discrete fourier transform by definition with samples numbers

Double[] signal2 = dft.Shift(signal); // Signal shift method

Complex[] Xb = dft.DFT(signal2); // discrete fourier transform by definition of shifted signal

// Compare Xa and Xb and see if we were correct!

Teskari diskret Furye transformatsiyasi
// --- Inverse Discrete Fourier Transform by definition

Double[] x = dft.iDFT(X); // inverse discrete fourier transform by definition

Double[] xa = dft.iDFT(Xa, n); // inverse discrete fourier transform by definition (with samples numbers)

Double[] xb = dft.iDFT(Xb); // inverse discrete fourier transform by definition of shifted signal

// Compare x, xa and xb. Any other operation needs to be performed at xb to restore original?

Hisoblash sonining kamayishi bilan diskret Furye konvertatsiyasi

// --- Discrete Fourier Transform with reduced number of calculation
Complex[] X2 = dft.DFT2(signal); // discrete fourier transform with reduced number of calculation
Complex[] X2a = dft.DFT2(signal, n); // discrete fourier transform with reduced number of calculation with samples numbers
Complex[] X2b = dft.DFT2(dft.Shift(signal), n); // discrete fourier transform with reduced number of calculation (shifted signal)
Tez Furye o'zgarishi
Nol bilan signal to'plami
// Signal pack with zeros

Double[] signalpack = dft.SignalPackRight(signal); // Complement at right to N = nearest power of 2

Double[] signalpack2 = dft.SignalPackLeft(signal); // Complement at left to N = nearest power of 2

Double[] signalpack3 = dft.SignalPackBoth(signal); // Complement at both sides to N = nearest power of 2

Namunalarni saralash
// Samples sorting

Double[] signal3 = dft.FFTDataSort(signalpack); // using bit reverse

Double[] signal4 = dft.FFTDataSort2(signalpack); // using shift method

// Compare signal3 and signal4 - should be equal!

Tez Furye o'zgarishi
Complex[] X3 = dft.FFT(signal3); // fast fourier transform

Complex[] X3a = dft.FFT(dft.Shift(signal3)); // shifted spectrum - fast fourier transform

Teskari tez Furye konvertatsiyasi
Spektr chiziqlarini saralash
Complex[] X3s = dft.FFTDataSort(X3); // spectrum sort using bit reverse

Complex[] X3as = dft.FFTDataSort2(X3); // spectrum sort using shift method

Teskari tez Furye konvertatsiyasi

Double[] x3 = dft.iFFT(X3s); // inverse fast fourier transform


// ----------------- Compare x3 with signal!!! ---------------