qisqaroq ketma-ketliklar uchun DFTlar hisoblab chiqiladi va bu DFT-lardan DFT
olinadi. asl ketma-ketlik quriladi. Ikki (N/2) nuqtali ketma-ketlik uchun kompleks
sonlarni taxminan (N/2)2*2=N2/2 koʻpaytirish talab qilinadi, yaʼni. ko‘paytirish
soni (shuningdek, qo‘shimchalar) taxminan 2 barobar kamayadi. Xuddi shunday,
(N/2)-nuqtali ketma-ketlikning DFT-ni hisoblash o‘rniga, ikkita (N/4)-nuqtali
ketma-ketlikning DFT-ni hisoblash va shu tariqa yana ko‘paytirish va qo‘shish
amallarining kerakli sonini kamaytirish mumkin. Agar N=2
n
, n>0 va butun son
bo‘lsa, u holda DFT hajmini kamaytirish jarayoni faqat 2 nuqtali DFTlar
qolguncha davom ettirilishi mumkin. Bunda DFT ni hisoblash bosqichlarining
umumiy soni n=log2N martaga teng bo‘ladi va N nuqta DFT ni hisoblash uchun
zarur bo‘lgan operatsiyalar soni Nn tartibida bo‘ladi, ya'ni taxminan kamayadi
N
/
log
2
N.
Demak, N=1000 bilan DFTni toʻgʻridan-toʻgʻri hisoblash uchun taxminan
N
2
=10
6
murakkab koʻpaytirish va qoʻshish amallari kerak boʻladi, FFT
algoritmlarini qoʻllashda esa bunday amallar atigi 10
4
ga yaqin, yaʼni. hisoblash
miqdori taxminan ikki darajaga kamayadi.
Turli xil FFT algoritmlari mavjud, masalan, x(nT) kirish ketma-ketligi
namunalarini almashtirishni talab qiluvchi keng qo‘llaniladigan vaqtni qisqartirish
algoritmi va X(k) chiqish ketma-ketligi namunalarini almashtirishni talab qiluvchi
chastotani pasaytirish algoritmi. ). Ikkala FFT algoritmi taxminan Nlog2N
operatsiyalarini (murakkab ko‘paytirish) talab qiladi va ikkala algoritm ham faqat
bitta xotira katakchalari qatori yordamida almashtirish bilan amalga oshirilishi
mumkin.
