4-Amaliyot Diskret va tez Furye o’zgartirishi algoritmlari

---

4-Amaliyot 
Diskret va tez Furye o’zgartirishi algoritmlari
Analog signallarni tahlil qilishda bo'lgani kabi, 
diskret signallar
 ham vaqt va chastota sohalarida 
ifodalanishi mumkin. Hozirgi vaqtda diskret signalni qayta ishlash ko'pincha chastotalar 
domenida amalga oshiriladi, bu raqamli uskunalar hajmi va ishlov berish vaqtining sezilarli 
darajada qisqarishi bilan bog'liq. 
 
  
Spektral zichlikka
 ega bo'lgan davomiylikka ega bo'lgan analog impuls signali diskret ishlovga 
duchor bo'lsin (9.16-rasm, a, b). Nazariy jihatdan, 
signal delta funktsiyalarining
 davriy ketma-
ketligi 
bilan tanlanadi
 deb taxmin qilish mumkin. 
 
 
 

 
 
, 

(9,35) 
bu erda 
Kotelnikov teoremasiga
 mos keladigan kerakli namunalar soni . 
 
 
 
(9.32) dagi yig'indi chegaralarini 0 dan 
ga o'rniga qo'yib, formulalar hajmini 
soddalashtirish va kamaytirish uchun bu erda va pastda almashtiring
, biz diskret 
signalning ifodasini yozamiz (9.16-rasm, f).
... 
(9,36) 
(9.36) formulaga asoslanib, ushbu diskret signalning spektri chastota o'qi bo'ylab davriy 
tuzilishga ega degan xulosaga kelishimiz mumkin (9.16-rasm, d). 
Diskret signalni
 davriy 
ravishda interval bilan aqliy ravishda davom ettiramiz (9.16-rasm, e). 

 

Rasm.9.16. DFT chiqishi uchun grafiklar: 

a, b - analog signal va uning spektri; c, d - diskret signal va uning spektri; d - diskret signalning 
davriy ketma-ketligi; e - signalning DFT
, . 
Davriy uzluksiz signallarni ko'rsatishga o'xshash 

---

, bu yerda th garmonikaning kompleks amplitudasi . Diskret funktsiyani 
kompleks Furye qatorida
 kengaytirish mumkin : 

 
 
, 

(9,37) 
qaerda bo'ladi 
Masal tezligi signali
 . 

 
 
Ushbu qatorning koeffitsientlari 

... 
(9,38) 
Koeffitsientlarni aniqlash uchun biz quyidagilarni bajaramiz. (9.36) formulasini (9.38) ga 
almashtiring va parametrni almashtiring . Biz o'lchamsiz o'zgaruvchini kiritamiz va 
yozamiz 
... 
Delta funktsiyalarining filtrlash xususiyatidan foydalanib, biz topamiz 
... 
(9,39) 
Bu diskret deb ataladi 
konvertatsiya Fourier
 (DFT). 
Diskret Furye konvertatsiyasi
 asosan analog 
signalning berilgan diskret namunalaridan spektrning harmonik komponentlarini hisoblash 
algoritmidir , bu ishlov berish vaqtini sezilarli darajada kamaytiradi. Koeffitsientlar 
modullarining odatiy ko'rinishi shaklda ko'rsatilgan. 9.16, e. 
 

 

Ta'rifdan kelib chiqadigan bir qator DFT xususiyatlarini ta'kidlash kerak (9.39). 

Diskret 1. 
o'zgartirmoq Fourier
 lineerlik xususiyati bor: chiziqli kombinatsiyasi 
alohida 
signallari
 kalınlığıyla bir chiziqli kombinatsiyasi mos. 
 

 
  

2. Koeffitsient - signalning barcha diskret namunalarining 
o'rtacha qiymati
 (DC 
komponenti). 

 
  

... 

---

3. Turli koeffitsientlar soni signalning davomiyligi uchun namunalar soniga teng ; da 
koeffitsienti . 
9.2-misol. To'rtta namunada berilgan birlik amplitudasining diskretlashtirilgan to'rtburchak 
impulsining DFT koeffitsientlarini aniqlang . 
Yechim. Umumiy formuladan (9.39) foydalanib, biz birinchi beshta DFT koeffitsientini 
hisoblaymiz: ; 
; 
; ... 
DFT nazariyasini o'rganishda aniq savol tug'iladi: ma'lum DFT koeffitsientlaridan uzluksiz 
signalning mos yozuvlar qiymatlarini hisoblash mumkinmi? 
Davriy signallarga
 o'xshatib 
, biz 
murakkab Furye seriyasi bilan
 namunalarning berilgan davriy ketma-ketligini ifodalaymiz . 
(7.25) bilan almashtirish , va qator atamalar cheklangan soni jamlanadi hisobga olgan holda, biz 
yozish 

 

 

 
... 
(9.40) 
Bu munosabat teskari 
diskret
 Furye 
konvertatsiyasi
 (IDFT) algoritmini belgilaydi . Formulalar 
(9,39) va (9.40) oldinga va teskari o'xshashlarning 
o'zgarishlar Fourier
 uzluksiz uzatish 
uchun. 
 

 
  

(9.39) ifoda shuni ko'rsatadiki, N namunali signal ketma-ketligining bir DFT koeffitsientini 
aniqlash uchun 
kompleks songa
 va bir xil miqdordagi qo'shimchalarga taxminan N ko'paytirish 
amalini bajarish va barcha koeffitsientlarni, hisob-kitoblar miqdorini topish kerak. bo'ladi . 
Xususan, milliondan ortiq ko'paytirish va qo'shimchalarni amalga oshirish kerak bo'lganda . 
Agar qayta ishlangan massivlarning uzunligi ming birlikdan oshsa, u holda 
real vaqt rejimida
 
diskret spektral signallarni qayta ishlash yuqori unumli hisoblash tizimlarini talab 
qiladi. 
 

 
  

---

9.17-rasm. Ketma-ketlikni ikkita kichik ketma-ketlikka bo'lish: a - kiritish; b - juft raqamlar 
bilan; c - toq raqamlar bilan 
Tez Furye transformatsiyasi
 (FFT) operatsiyalar sonini sezilarli darajada kamaytirish uchun 
DFT koeffitsientlarini kichikroq operatsiyalarda hisoblash imkonini beradi. FFT 
diskret signal
 
namunalarining berilgan ketma-ketligini bir nechta oraliq ketma-ketliklarga bo'lish tamoyiliga 
asoslanadi . Buning uchun N namunalar soni omillarga bo'linadi (masalan, ). Keyin bu oraliq 
ketma-ketliklarning spektrlari aniqlanadi va ular orqali butun signalning spektri topiladi. Ushbu 
to'plamlarning tarkibi, soni va tartibiga qarab siz turli xil FFT algoritmlarini yaratishingiz 
mumkin. Raqamli texnologiyada ikkita quvvat (4, 8, 16 va boshqalar) bo'lgan N qiymatli signal 
ketma-ketligini qayta ishlash qulay. Bu kirish namunasi ketma-ketligini pastki ketma-ketliklarga 
bir nechta bo'linish imkonini beradi. 
 

 

Juft 

sonli
 namunalarga ega 
bo'lgan diskret signalning
 DFT ni hisoblash talab qilinsin (9.17-
rasm, a) va ; - 
bir butun son
 . 
 
 
 
 

 
 
Kiritish ketma-ketligini juft va toq sonli va har biridagi a'zolar sonining yarmiga teng bo'lgan 

ikkita kichik ketma-ketlik ko'rinishida tasvirlaymiz (9.17-rasm, b, v) :; ; ... 
Biz juft va toq sonli ketma-ketliklar uchun DFT koeffitsientlarini alohida yozamiz: 
... 
(9,41) 
Kirish ketma-ketligining natijaviy DFT koeffitsientlari parametrlar va ikkita yangi kiritilgan 
kichik ketma-ketliklar bilan ifodalanishi mumkin . Tahlil (9.41) shuni ko'rsatadiki, 0 dan 0 
gacha bo'lgan namuna raqamlari oralig'ida kirish ketma-ketligining DFT nisbati bilan 
aniqlanadi: 

---

, . 
(9,42) 
Juft va toq ketma-ketliklarning DFT davriy bo'lgani uchun, nuqta bilan , keyin ; 
... 
(9.42) formulada ko'rsatkichli omilni yozamiz , ya'ni. DFT uchun quyidagi 
shaklda: 
Oxirgi ikkita ifodani hisobga olgan holda, biz dan gacha raqamlari bo'lgan namunalar uchun 
kirish ketma-ketligining DFT koeffitsientlarini topamiz : 
, . 
(9,43) 
(9.42) va (9.43) munosabatlari FFT yordamida koeffitsientlarni hisoblash algoritmlarini to'liq 
aniqlaydi. E'tibor bering, bu algoritmlardagi ko'rsatkichli faza omillari toq pastki ketma-ketlikni 
juftlikka nisbatan siljitish ta'sirini hisobga oladi.Hisoblash sonini yanada kamaytirish uchun juft 
va toq pastki ketma-ketliklar ham ikkita oraliq qismga bo'linadi. Ajratish eng oddiy ikki 
elementli ketma-ketliklar olinmaguncha davom ettiriladi. Eng oddiy juftlik namunalari 
ma'lumotlarining DFT ni aniqlab, biz to'rt elementli, sakkiz elementli va shunga o'xshash 
keyingi ketma-ketliklarning DFT ni hisoblashimiz mumkin. Juft va toq pastki ketma-
ketliklarning DFT-larini birlashtirganda, raqamlarning tegishli qiymatlarini va ularga 
almashtirib (9.42) va (9.43) algoritmlari qo'llaniladi . 
Ko'rinib turibdiki, (9.41) formulalar bo'yicha hisob-kitoblar ko'paytirish operatsiyalarini talab 
qilmaydi, (9.41) da faqat 
murakkab sonlarni
 qo'shish va 
ayirish mavjud
 . Massivni kichik kichik 
ketma-ketliklarga bo'lishda turli hisobotlar uchun faqat (9.42) va (9.43) algoritmlardagi 
ko'paytirish amallarini hisobga olish kerak . Birinchi bo'limda ushbu operatsiyalar soni . Har bir 
keyingi bo'linish uchun bir xil miqdordagi operatsiyalar talab qilinadi. Shunday qilib, (7.30), 
(7.31) formulalardagi pastki ketma- ketliklar soni ikki barobar ortadi va eng katta son ikki 
baravar kamayadi . 
 

FFT algoritmlari yordamida N namunalar ketma-ketligining DFT koeffitsientlarini hisoblash 
taxminan ko'paytirish operatsiyalarini talab qiladi . FFT algoritmlari DFT algoritmlariga 
nisbatan amallar sonini bir marta kamaytiradi . Masalan, hisoblar soni bilan bizda bor va 
operatsiyalar sonining kamayishi . Kirish signali namunalarining juda katta massivlari bilan 
ishlov berish tezligidagi o'sish bir necha mingga yetishi 
mumkin. 
Shunday qilib, FFT algoritmlari komponentlardan birini eksponensial omilga ko'paytirish orqali 
qo'shish va ayirish operatsiyalarini bajaradi . FFT uchun asosiy bo'lgan ushbu operatsiyani 
raqamli texnologiyada "kapalak" deb ataladigan signal grafigi bilan ifodalash juda qulay. 

---

Ko'rib chiqilgan usul bo'yicha FFT (u namunalarni vaqt bo'yicha yo'q qilish usuli deb ataladi), 
qoida tariqasida, quyidagi tartibda amalga oshiriladi. Birinchidan, qayta ishlash tartibi uzatish 
istalgan namunalar olish , u asl ketma elementlarini diyadik teskari permütasyonda ijro , . 
Buning uchun elementlarning tartib raqamlari ikkilik kodda yoziladi va bitlarning tartibi teskari 
bo'ladi. Elementlarning yangi tartibi raqamlarning inversiyasidan keyin olingan raqamlar bilan 
aniqlanadi. 
N = 4 uchun misol 
u (l) 
u (k) 
0 → 
00 → 00 → 
0 → 
1 → 
01 → 10 → 
2 → 
2 → 
10 → 01 → 
1 → 
3 → 
11 → 11 → 
3 → 
Elementlarning joylashish tartibi:
. Shundan so'ng ular buni qilishadi. Hisob-
kitoblarning birinchi bosqichida "yangi" ketma-ketlikning
ikki nuqtali DFT- si ushbu 
ketma-ketlikning elementlarini juftlashtirish orqali aniqlanadi . Ikkinchi bosqichda, ikkita nuqta 
DFT dan, ushbu usulning.Ushbu
va 
bazaviy operatsiyasi yordamida 
to'rtta nuqtali DFO’ olinadi (pastga qarang). Keyin to'rt nuqtali DFO’lar sakkiz nuqtalilarga 
birlashtiriladi va hokazo.
Asosiy operatsiyalar va ikkita kirish raqamlari A va B ikkita chiqish raqamlari X va Y ishlab 
chiqarish uchun qanday birlashtirilganligini ko'rsating. Vaqt asosidagi yupqalash usulida, 
rasmda ko'rsatilgan "kapalak" bilan ifodalanadi. 9.18. Yuqoriga o'q B ga ko'paytirishni 
ko'rsatadi. 
Rasm.9.18. FTO’ algoritmini amalga oshirishda kapalak operatsiyasi 
Ikki nuqta DFO’
hisoblash va chiqish raqamlari X va Y ko'paytirish operatsiyalari
, 
holda belgilangan bo'lsa , 
9.3-misol. N = 4 uchun vaqt bo'yicha qisqartirishli BDNFni hisoblash uchun graf tuzamiz (9.19-
rasm). 

---

Rasm.9.19. N = 4 uchun FTO’ni hisoblash grafi 
hisobga , olganda quydagi ko'rsatilgan grafni olamiz
Shaklda. 9.20 N = 8 uchun vaqtni kamaytirishli FDTO’ ni hisoblash grafigini ko'rsatadi. 
Rasm.9.20. N = 8 bilan FTO’ ni hisoblash uchun grafik