Raqamli signallarni qayta ishlashda Furye transformatsiyasi

Raqamli signallarni qayta ishlashda Furye transformatsiyasi
Kirish:
Chastotani tahlil qilish signalni qayta ishlashning eng mashhur usullaridan biridir. Bu keyingi filtrlash uchun signalning parchalanishi uchun vosita bo'lib, aslida signal komponentlarini bir-biridan ajratishdir.
Garchi bu ikki dunyo (vaqt va chastota sohasi) chegarasini kesib o'tish jarayonini ilg'or holat deb hisoblash mumkin bo'lsa-da, buni amalga oshirishga arziydi, chunki bu boshqa dunyo bizga yangi imkoniyatlar beradi va ko'p masalalarni soddalashtiradi.
Maqolada Furye transformatsiyasining ta'rifidan boshlab, qisqartirilgan hisoblash algoritmi va Kuli-Tukey tez Furye o'zgarishi usuli bilan yakunlash orqali Diskret Furye transformatsiyasini hisoblashning turli xil versiyalarini amalga oshirish ko'rsatilgan.
Bundan tashqari, u signal spektrida bajariladigan eng oddiy operatsiyalarning ahamiyatini va ularning vaqt sohasiga ta'sirini taqdim etadi.


Signallar:
Signal bitta yoki bir nechta argumentlar funktsiyasi sifatida tavsiflanishi mumkin bo'lgan har qanday jismoniy qiymatning o'zgaruvchanligi sifatida aniqlanishi mumkin. Ushbu maqolada biz bir o'lchovli vaqt funktsiyalari bilan qiziqamiz.
Haqiqiy dunyoda bajarilishi mumkin bo'lgan vaqt funktsiyalari doimiy domenga joylashtiriladi. Biroq, kompyuter fanining rivojlanishi analog signallarni qayta ishlashning kamdan-kam holga kelishiga olib keldi. Raqamli dunyoda signalni qayta ishlash algoritmlarini yaratish, amalga oshirish va sinab ko'rish, keyin analog (elektron) qurilmalarni loyihalash va ishlab chiqish ancha tejamkor.


Uzluksiz domendan diskret domenga:


Analog signalning raqamli tasvirini olish uchun uni diskret-vaqt domeniga aylantirish va kvantlash kerak.
Nyquist-Shannon tanlama teoremasi uzluksiz vaqt signallari va diskret vaqt signallari o'rtasidagi bog'liqlikdir. Ushbu teoremani Whittaker-Nyquist-Kotielnikov-Shannon namuna olish teoremasi deb ham atash mumkin - biz ushbu masala haqida gapiradigan mamlakatga qarab mualliflarning ismlarini tanlash. Bundan yuqori bo'lish uchun biz uni oddiygina namuna olish teoremasi deb ataymiz .
Namuna olish teoremasi diskret-vaqt signalini olish uchun uzluksiz vaqt signalini qanday namuna olish kerakligi haqidagi savolga javob beradi, undan asl (uzluksiz vaqt) signalni tiklashingiz mumkin. Ushbu bayonotga ko'ra, to'g'ri tanlangan diskret-vaqt signalini olish uchun namuna olish chastotasi asl signalda kuzatilishi mumkin bo'lgan eng yuqori chastotadan kamida ikki marta bo'lishi kerak.


Signalning chastota domeniga parchalanishi:


Hammasi 1807 yilda frantsuz matematigi va fizigi Jozef Furye metall plastinkadagi qisman differensial issiqlik tenglamasini yechish uchun trigonometrik qator parchalanishini (hozirgi kunda Furye seriyali usuli deb nomlanadi) joriy qilganida boshlangan. Furyening g'oyasi murakkab davriy funktsiyani eng oddiy tebranish funktsiyalari - sinuslar va kosinuslar yig'indisiga ajratish edi.

Jozef Furye


Agar f(x) funksiya T  davri bilan davriy bo'lsa va [ x ₀ , x ₀ + T ] oraliqda integraliy (uning integrali chekli) bo'lsa , u holda uni qatorga aylantirish mumkin:


f( x ) =a02+∑n = 1∞(an⋅ c o s (2 n pTx ) +bn⋅ s i n (2 n pTx ) )f(x)=a02+∑n=1∞(an⋅cos(2npTx)+bn⋅sin(2npTx))
qayerda
an=2T∫x0+ Tx0f( x ) ⋅ c o s (2 n pTx ) dxbn=2T∫x0+ Tx0f( x ) ⋅ s i n (2 n pTx ) dx
Diskret Furye transformatsiyasi:
Ta'rif:
Furye seriyasini Furye transformatsiyasining avlodi deb atash mumkin, bu raqamli signallar (Discrete
Furier Transform) bo'lsa, quyidagi formula bilan tavsiflanadi:
X( k ) =1N∑n = 0N− 1x ( n ) ⋅e− j2 pNk nX(k)=1N∑n=0N−1x(n)⋅e−j2pNkn
Furye konvertatsiyasi teskari bo'lib, biz vaqt domeniga hisoblash orqali qaytishimiz mumkin:


X ( n ) =∑k = 0N− 1X( k ) ⋅ej2 pNk nx(n)=∑k=0N−1X(k)⋅ej2pNkn


Ba'zi belgilarda biz N ga bo'lish teskari hisob-kitobga o'tkazilishini kuzatishimiz mumkin - agar biz N ga bo'linishni to'g'ridan - to'g'ri va teskari Furye konvertatsiyasida qo'llamasak, bu hisobni buzmaydi .
To'g'ridan-to'g'ri va teskari Diskret Furye transformatsiyasini amalga oshirish quyida ko'rsatilgan.
Kichraytirish ▲
///

/// Calculates Discrete Fourier Transform of given digital signal x
///

///
Signal x samples values

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


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


for (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;

}

return X;
}


///

/// Calculates inverse Discrete Fourier Transform of given spectrum X
///

///
Spectrum complex values

/// Signal samples in time domain
public Double[] iDFT(Complex[] X)
{
int N = X.Length; // Number of spectrum elements
Double[] x = new Double[N];
for (int n = 0; n < N; n++)

Complex sum = 0;

for (int k = 0; k < N; k++)
{
sum += X[k] * Complex.Exp(Complex.ImaginaryOne * 2 * Math.PI * (k * n) / Convert.ToDouble(N));
}
x[n] = sum.Real; // As a result we expect only real values (if our calculations are correct imaginary values should be equal or close to zero)
}


return x;
}
Teskari Furye transformatsiyasining kodini amalga oshirishda ko'pincha xatolik uning kattalik qiymatidan foydalanib, murakkab qiymatni realga o'tkazishdir - bunday holatda biz | x(n) | x(n) o‘rniga .


Ta'rif bo'yicha hisoblangan Diskret Furye transformatsiyasining amaliy misoli:
Algoritmni tekshirish uchun ikkita sinus to'lqin yig'indisi bo'lgan signal yarataylik:
x1( n ) = s i n ( 0,02 pn )x1(n)=sin(0,02pn)
x2( n ) = 0,25 ⋅ s i n ( 0,2 pn )x2(n)=0,25⋅sin(0,2pn)
X ₁ (n) bilan asl signalni va x ₂ ( n)  bilan buzilish signalini (shovqin) belgilang. Bu signallarning yig'indisi x(n) = x ₁ (n) + x ₂ (n)  bu holda buzilgan signaldir.


x ( n ) =x1( n ) +x2( n )x(n)=x1(n)+x2(n)
n = 0 , 1 ,. _ . . , 100n=0,1,...,100



1-rasm. Asl va buzilish signallari

2-rasm. Signallar yig'indisi (buzilgan signal)


Biz signalimizni ikkita sinus to'lqinlar yig'indisidan yaratganimizda, Furye teoremasiga ko'ra, biz f ₁  va f ₂ chastotalari atrofida to'plangan chastota tasvirini, shuningdek, f ₁  va - f ₂ ning qarama-qarshi tomonlarini olishimiz kerak .

3-rasm. Buzilgan singalning amplitudali spektri.


Agar Furye teoremasi to'g'ri bo'lsa, buzilish signalidan kelib chiqqan spektr chiziqlarini olib tashlash orqali biz asl signalni olishimiz kerak.



4-rasm. Uzilish chastotasi olib tashlangan spektr va uning teskari DFT natijasi


4-rasmda ko'rib turganimizdek, chiqish signalimiz asl signalga yaqin va buzilishlar raqamli operatsiyalar natijasida paydo bo'lgan qo'shimcha chiziqlar tufayli yuzaga keladi. Keling, ularning barchasini olib tashlaymiz va faqat ikkita asosiy chiziqni qoldiramiz.



5-rasm. Faqat asosiy chastotali spektr va uning teskari DFT natijasi.


5-rasmdagi chiqish signali mukammal sinus to'lqinga o'xshaydi. Ammo chiqish va asl signal o'rtasidagi kichik farqlarni ko'rsatish uchun quyida taqqoslashga qarang.



6-rasm. Asl va chiqish signalini taqqoslash.


3-rasmda biz hech qanday manfiy qiymatlarni ko'ra olmaymiz, shuning uchun nima uchun hisoblangan spektr ikki f ₁  va f ₂ chastotalar atrofida , shuningdek, uning qarama-qarshi tomonlari - f ₁  va - f ₂ atrofida to'planganligini aytdik ?
Buning sababi, biz kelib chiqishiga simmetrik diapazonda aniqlangan signallarni tahlil qilish uchun foydalanamiz. Agar biz buzilgan x(n) signalimizni quyidagicha belgilasak :
x ( n ) =x1( n ) +x2( n )x(n)=x1(n)+x2(n)
n = - 50 , - 49 , . . . , − 1 , 0 , 1 , . . . , 49 , 50n=−50,−49,...,−1,0,1,...,49,50



7-rasm. O'zgartirilgan signal


va bizning algoritmimizda kichik o'zgarishlarni amalga oshiring:
Kichraytirish ▲
///

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

///
Signal x samples values

///
Samples numbers vector

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


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


Double s1 = SamplesNumbers[k]; // Get sample index


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

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

}
return X;
}


biz quyida ko'rsatilgan amplituda spektrini olamiz.



8-rasm. O'zgartirilgan signalning amplituda spektri


Xuddi shu o'zgarish teskari DFT usulida amalga oshirilishi kerak.
Kichraytirish ▲
///

/// Calculates inverse Discrete Fourier Transform of given spectrum X with respect to sample numbers
///

///
Spectrum complex values

///
Samples numbers vector

/// Signal samples in time domain
public Double[] iDFT(Complex[] X, int[] SamplesNumbers)
{
int N = X.Length; // Number of spectrum elements
Double[] x = new Double[N];


for (int n = 0; n < N; n++)
{
Complex sum = 0;
Double s1 = SamplesNumbers[n]; // Get sample index


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

x[n] = sum.Real; // As a result we expect only real values (if our calculations are correct imaginary values should be equal or close to zero)

}


return x;
}


E'tibor bering, signalni orginaga nosimmetrik holatga o'tkazish orqali biz siljigan spektrni hisobladik:


X( k ) → X( k -N2)X(k)→X(k−N2)


Agar biz dastlabki signalni formuladan foydalanib o'zgartirsak, xuddi shunday ta'sirga erishish mumkin


x ( n ) → ( − 1)n⋅ x ( n )x(n)→(−1)n⋅x(n)


Bunday holda, namunalarning haqiqiy sonini saqlashning hojati yo'q. Buning uchun foydalanish usuli quyida ko'rsatilgan.


///

/// Shifts spectrum by changing original signal before Fourier Transform
///

///
Original signal

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


for (int i = 0; i < N; i++)
{
x[i] = (int)Math.Pow(-1, i) * x[i];
}


return x;
}


Qisqartirilgan hisob-kitoblar bilan diskret Furye konvertatsiyasi:
Keling, diskret Furye transformatsiyasining oldingi ta'rifiga yana qaraylik:


X( k ) =1N∑n = 0N− 1x ( n ) ⋅e− j2 pNk nX(k)=1N∑n=0N−1x(n)⋅e−j2pNkn
W N yordamchi o'zgaruvchi bilan _{belgilang :}
VN=e− j2 pNVN=e−j2pN


Keyin formulamiz shaklni oladi:


X( k ) =1N∑n = 0N− 1x ( n ) ⋅Vk nNX(k)=1N∑n=0N−1x(n)⋅VNkn


Bundan tashqari, agar k = 0 yoki n = 0 bo'lsa, biz quyidagilarni olamiz:


Vk nN= 1VNkn=1


Shunga ko'ra, DTF ning belgilanishi matritsa shaklida yozilishi mumkin:


⎡⎣⎢⎢⎢⎢⎢X[ 0 ]X[ 1 ]⋮X[ N− 1 ]⎤⎦⎥⎥⎥⎥⎥=1N⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢1111⋮11VNV2NV3N⋮VN− 1N1V2NV4NV6N⋮VN− 2N…………⋱…1VN− 1NVN− 2NVN− 3N⋮VN⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⋅⎡⎣⎢⎢⎢⎢⎢x [ 0 ]x [ 1 ]⋮x [ N− 1 ]⎤⎦⎥⎥⎥⎥⎥[X[0]X[1]⋮X[N−1]]=1N[111…11VNVN2…VNN−11VN2VN4…VNN−21VN3VN6…VNN−3⋮⋮⋮⋱⋮1VNN−1VNN−2…VN]⋅[x[0]x[1]⋮x[N−1]]


Bundan kelib chiqadiki, N -namuna signalining Dikret Furye o'zgarishini aniqlash uchun biz N ² ko'paytirish amallarini bajarishimiz va W _N matritsadagi ( N -1) ² koeffitsientlarini aniqlashimiz kerak . Eslatib o'tamiz, ko'paytirish amali protsessorlar uchun eng ko'p vaqt talab qiladigan operatsiyalardan biridir.
W _N  faktoriga qaytaylik va N= 4 ta misol x(n)  signalini ko'rib chiqaylik . X(k) ni hisoblash uchun matritsa koeffitsientlarining qiymatlarini topishimiz kerak:
⎡⎣⎢⎢⎢⎢11111V4V24V341V24V44V241V34V24V4⎤⎦⎥⎥⎥⎥[11111V4V42V431V42V44V421V43V42V4]
Bizda ... bor:
V4=e− jp2= c o s ( -p2) + j ⋅ s i n ( -p2) = c o s (p2) − j ⋅ s i n (p2) = − jV4=e−jp2=cos(−p2)+j⋅sin(−p2)=cos(p2)−j⋅sin(p2)=−j
qayerda
ej s= c o s ( s ) + j ⋅ s i n ( s )ejs=cos(s)+j⋅sin(s)
Eyler formulasi .


Keyingi qiymatlar
V24= − 1V34= jV44= − 1V42=−1V43=jV44=−1


E'tibor bering
V24= −V04V34= −V14V42=−V40V43=−V41


Shunga o'xshash vaziyatni N = 8 uchun ko'rish mumkin:


V18=e− jp4= c o s (p4) − j ⋅ s i n (p4) =2√2( 1 - j ) =1 − j2√V28= (( 1 - j)22) = − jV38= − j ⋅1 − j2√=− 1 − j2√V48=− 1 − j2√⋅1 − j2√= − 1V58= −1 − j2√V68= − (1 − j2√)2= jV78= j ⋅1 − j2√=1 + j2√V88=1 + j2√⋅1 − j2√= 1V81=e−jp4=cos(p4)−j⋅sin(p4)=22(1−j)=1−j2V82=((1−j)22)=−jV83=−j⋅1−j2=−1−j2V84=−1−j2⋅1−j2=−1V85=−1−j2V86=−(1−j2)2=jV87=j⋅1−j2=1+j2V88=1+j2⋅1−j2=1


quyidagilarni ta'minlaydi:
V48= −V08V58= −V18V68= −V28V78= −V38V84=−V80V85=−V81V86=−V82V87=−V83


Umuman olganda, N - namunalar signali uchun biz yozishimiz mumkin:
VzN= −Vz−N2Nz=N2,N2+ 1 ,N2+ 2 , . . . , NVNz=−VNz−N2z=N2,N2+1,N2+2,...,N


Bu kuzatish bizni shunday xulosaga olib keladiki, DFTni aniqlashda biz faqat N/2 - 1 spektral koeffitsientlarni hisoblaymiz, boshqasini esa oldingilaridan olishimiz mumkin - bu spektr simmetriya xossasidir. Ushbu kuzatish tufayli algoritm ichidagi operatsiyalar soni to'rt baravar kamaydi. Agar biz jismoniy signallar, ya'ni haqiqiy qiymatlarga ega bo'lgan signallar bilan shug'ullanadigan bo'lsak, bu kuzatish to'g'ri bo'ladi.
Kichraytirish ▲
///

/// Calculates forward Discrete Fourier Transform of given digital signal x with reduced number of multiplications
///

///
Signal x samples values

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