"fft" bu yerga yo'naltiradi. Boshqa ma'lumotlar uchun qarang: fft (aniqlash)

"FFT" bu yerga yo'naltiradi. Boshqa ma'lumotlar uchun qarang: FFT (aniqlash).

Yarim o'lchamli FFTlarga parchalanishdan foydalangan holda FFT algoritm tuzilishiga misol

10, 20, 30, 40 va 50 Gts chastotalarda kosinus to'lqinlar yig'indisining diskret Furye tahlili

Tez Furye konvertatsiyasi (FFT) - ketma-ketlikning diskret Furye konvertatsiyasini (DFT) yoki uning teskarisini (IDFT) hisoblaydigan algoritm. Furye tahlili signalni o'zining asl domenidan (ko'pincha vaqt yoki makon) chastota domenidagi vakillikka aylantiradi va aksincha. DFT qiymatlar ketma-ketligini turli chastotali komponentlarga ajratish yo'li bilan olinadi. Ushbu operatsiya ko'p sohalarda foydalidir, lekin uni to'g'ridan-to'g'ri ta'rifdan hisoblash ko'pincha amaliy bo'lish uchun juda sekin. FFT bunday o'zgarishlarni DFT matritsasini siyrak (asosan nol) omillar ko'paytmasiga ajratish orqali tezda hisoblab chiqadi. Natijada, u N ma'lumotlar hajmidan DFTni hisoblashning murakkabligini kamaytirishga muvaffaq bo'ldi. Tezlikdagi farq juda katta bo'lishi mumkin, ayniqsa N minglab yoki millionlab bo'lishi mumkin bo'lgan uzoq ma'lumotlar to'plamlari uchun. Yaxlitlash xatosi mavjud bo'lganda, ko'plab FFT algoritmlari DFT ta'rifini to'g'ridan-to'g'ri yoki bilvosita baholashdan ko'ra ancha aniqroqdir. Oddiy kompleks-son arifmetikasidan tortib, guruhlar nazariyasi va sonlar nazariyasigacha bo'lgan keng ko'lamli nashr etilgan nazariyalarga asoslangan juda ko'p turli xil FFT algoritmlari mavjud.

Tez Furye o'zgarishlari muhandislik, musiqa, fan va matematikadagi ilovalar uchun keng qo'llaniladi. Asosiy g'oyalar 1965 yilda ommalashgan, biroq ba'zi algoritmlar 1805 yildayoq olingan edi.[1] 1994 yilda Gilbert Strang FFTni "hayotimizdagi eng muhim raqamli algoritm" deb ta'rifladi va u IEEE Computing in Science & Engineering jurnali tomonidan 20-asrning eng yaxshi 10 ta algoritmiga kiritilgan.

Eng mashhur FFT algoritmlari N ning faktorizatsiyasiga bog'liq, ammo barcha N uchun, hatto tub N uchun ham O(N log N) murakkabligi bo'lgan FFTlar mavjud. Ko'pgina FFT algoritmlari faqat N-ibtidoiy ildiz ekanligiga bog'liq. birlikdan iborat va shuning uchun har qanday chekli maydondagi o'xshash o'zgarishlarga, masalan, son-nazariy o'zgarishlarga qo'llanilishi mumkin. Teskari DFT DFT bilan bir xil bo'lgani uchun, lekin ko'rsatkichdagi qarama-qarshi belgi va 1/N faktor bilan har qanday FFT algoritmi unga osongina moslashtirilishi mumkin.

Ta'rif

Kompleks X0,….,Xn-1 murakkab sonlar bo'lsin. DFT formula bilan aniqlanadi

bu yerda 1 ning ibtidoiy N-chi ildizi.

Ushbu ta'rifni baholash to'g'ridan-to'g'ri operatsiyalarni talab qiladi: N ta Xk chiqishi mavjud va har bir chiqish N ta atama yig'indisini talab qiladi. FFT - bu operatsiyalarda bir xil natijalarni hisoblashning har qanday usuli. Ma'lum bo'lgan barcha FFT algoritmlari operatsiyalarni talab qiladi, garchi pastroq murakkablik ballini olish mumkin emasligi haqida ma'lum dalil yo'q.
FFTni tejashni ko'rsatish uchun N=4096 ma'lumot nuqtasi uchun murakkab ko'paytirish va qo'shimchalar sonini ko'rib chiqing. DFT summalarini baholash to'g'ridan-to'g'ri N2 murakkab ko'paytirishni va N (N - 1) murakkab qo'shimchalarni o'z ichiga oladi, ulardan 1 ga ko'paytirish kabi ahamiyatsiz operatsiyalarni yo'q qilish orqali operatsiyalarni saqlash mumkin, taxminan 30 million operatsiya qoladi. Bundan farqli o'laroq, radix-2 Cooley-Tukey algoritmi, N a quvvati 2 uchun, bir xil natijani faqat (N/2)log2(N) murakkab ko'paytirishlar bilan hisoblashi mumkin (yana 1 va shunga o'xshash ko'paytirishlarni soddalashtirishni hisobga olmaganda) va N log2(N) murakkab qo'shimchalar, jami 30 000 ga yaqin operatsiyalar - to'g'ridan-to'g'ri baholashga qaraganda ming baravar kam. Amalda, zamonaviy kompyuterlarning haqiqiy ishlashi odatda arifmetik operatsiyalar tezligidan boshqa omillarga bog'liq va tahlil murakkab mavzudir (masalan, Frigo va Jonson, 2005 ga qarang), ammo umumiy yaxshilanish hali ham saqlanib qolmoqda.
Misollar

Furye transformatsiyasidan keng tarqalgan foydalanish chastota komponentlarini topishdir

shovqinli vaqt domenidagi signalga ko'milgan signal. Namuna olingan ma'lumotlarni ko'rib chiqing

1000 Gts. 0,7 va 120 amplitudali 50 Gts sinusoidni o'z ichiga olgan signal hosil qiling.

1-amplitudali Hz sinusoidi va uni nol o'rtacha tasodifiy shovqin bilan buzadi:
Fs = 1000; % Sampling frequency

T = 1/Fs; % Sample time

L = 1000; % Length of signal

t = (0:L-1)*T; % Time vector

% Sum of a 50 Hz sinusoid and a 120 Hz sinusoid

x = 0.7*sin(2*pi*50*t) + sin(2*pi*120*t);

y = x + 2*randn(size(t)); % Sinusoids plus noise

plot(Fs*t(1:50),y(1:50))

title('Signal Corrupted with Zero-Mean Random Noise')

xlabel('time (milliseconds)')