O’zbekiston aloqa va axborotlashtirish qo’mita toshkent axborot texnologiyalari universiteti
2.2. Diskret kosinus almashtirish(DKA) va teskari DKA
Download 1.31 Mb. Pdf ko'rish
|
signallarga spektrial ishlov berishning tezkor algoritmlarining dasturiy kompleksini yaratish
- Bu sahifa navigatsiya:
- 2.3. Uolsh almashtirsh
- 2.4. Adamar almashtirish
- III-BOB. SIGNALLARGA SPEKTRIAL ISHLOV BERISHNING TEZKOR ALGORITMLARINI DASTURIY VOSITASINI YARATISH
|
22
Diskret kosinus almashtirishlardan korrelatsiya va svertka (o‘ram)ni hisoblashni tezlashtirishda va spektr tahlilida foydalaniladi.
Bundan tashqari, bu usullardan ma’lumotlarni siqish, misol uchun ovozni (tovush) yoki tasvirni uzatish, elektrokardiogramma va elektroensenogramma kabi tibbiyot signallarini yozish uchun foydalaniladi.
Shuningdek, DKAdan tasvir va nusha (shablon)larni tanishda ham foydalaniladi. Buning natijasida signallarni uzatish uchun kodlashda talab etiladigan «bit»lar soni kamayadi, bu signal uzatish tezligini oshiradi.
Bu esa nisbatan tor polosali aloqa linyalaridan foydalanish imkoniyatini keltirib chiqaradi, shuningdek, nusxa (shablon)larni tanishni osonlashtiradi (bu axborot hajmi kamaytirilishi hisobiga ro‘y beradi).
DKAning ushbu xususiyatlari uni signallarni siqish nuqtai nazaridan samaradarligini bildiradi, bu signal energiyasining past chastotalarda to‘planishi natijasida ro‘y beradi. Bundan tashqari, hisoblashlarning soddaligi va o‘rtacha kvadratik xatolikning kichik (minimal) bo‘lishini taminlaydi [9,15,17].
Yuqoridagi fikrlar Fur’e diskret kosinus almashtirishdan (FDKA) foydalanishni taqazo etadi. Umuman olganda, FDKA Fur’e diskret almashtirishning xaqiqiy qismidan iborat, chunki Fur’e qatori haqiqiy va juft qismi faqat kosinusoidal tashkil etuvchilardan iborat bo‘lib, misol uchun kuchlanishning diskret qiymatlaridan foydalanilganda ma’lumotlar haqiqiy bo‘ladi, ularni ikki marta ko‘p qilish uchun ularga aks tashkil etuvchilarni qo‘shish kerak bo‘ladi. (2.13) formulaga asosan FDA quyidagi ko‘rinishda bo‘ladi:
1 0 2 . 1 ,...,
1 , 0 , N n N ink n N k e x k X
Ushbu almashtirishning haqiqiy qismi DKA ni anglatadi:
1 0 . 1 ,...,
1 , 0 , 2 cos Re N n n c N k N n k x k X k X (2.16) Bu DKA ning bir xususiy ko‘rinishi. DKAning umumiy ko‘rinishi quyidagicha aniqlanadi: 23
1 0 1 0 . 1 ,...,
1 , 0 , 2 1 2 cos
1 2 2 cos 1
n n N n n c N k N n k x N N k n k x N k X (2.17) 2.3. Uolsh almashtirsh
Hozirgacha ko‘rib chiqilgan almashtirishlar sinus va kosinus funksiyalariga asoslangan edi. Imrulsga o‘xshash +1 va +1 ga asoslangan almashtirish nisbatan oson va tez xisoblash imkoniyatini beradi. Bundan tashqari, bunday almashtirishlar uzluksizligi buzilgan signallarni ifodalashda ancha qulay xisoblanadi, misol uchun, tasvir signallarini almashtirishda. Shu bilan birga ular uzluksiz signallarni ifodalashda ancha noqulay bo‘lib, ular fazalari bo‘yicha moslikni taminlamaydi, bu signal spektrining buzilishiga va natijada signal shaklining buzilishiga olib keladi. Shuning uchun Uolsh almashtirishidan, odatda tasvir signallariga ishlov (astronomiya va spektroskopiya)da signallarni kodlash va filtrlashda foydalaniladi. Fur’e diskret almashtirishi garmonik sinusoidal va kosinusoidal tashkil etuvchilar orqali ifodalanganidek, Uolsh diskret almashtirishi (UDA) Uolsh funksiyalari deb ataluvchi to‘g‘ri to‘rtburchakli o‘rovchili garmonik signallar to‘plami orqali ifodalashga asoslangan. Ammo to‘g‘riburchakli imrulslar uchun ularning takrorlanish chastotasi nomalum bo‘lgani uchun analog signal uchun foydalaniladigan «ketma-ketlik» atamasidan foydalaniladi. «Ketma-ketlik»-bu vaqt birligida nolni kesib o‘tishlar sonining yarmiga teng bo‘ladi. 3-rasmda 8
gacha bo‘lgan tartibdagi Uolsh funksiyalari kattalashtirish tartibida ko‘rsatilgan. Bu ko‘rinishni Uolsh bo‘yicha tartibga keltirilgan funksiya deb ataladi. Davomiylik vaqti
ga
va tartibi n ga teng Uolsh funksiyasi quyidagicha belgilanadi
[10].
3-rasmdan ko‘rinadiki, xudi Fur’e qatorida toq va juft sinusoidal va kosinusoidal funksiyalar bir biriga teng bo‘lganidek, Uolsh funksiyasida ham bir xil sonli toq va juft funksiyalar bo‘ladi. Uolsh
k W A L , 2 juft funksiyalari t k CAL , ko‘rinishida ifodalanadi va 24
t k WAL , 1 2 toq funksiyalari
k CAL , 1 2 ko‘rinishida ifodalanadi, bunda k=1,2…,N/2-1 .
3-rasm.
Uolshning 8 8
tartibli almashtirishi matritsasi uchun uning ketma-ket kattalashishi 7
gacha tartibga keltirilgan funksiyalari
Har qanday
t S signalni Uolsh funksiyalari majmua (jamlama)lariga yoyish mumkin (xudi Fure qatoriga yoygandek):
1 2 1 1 2 1 0 , , , , N i N j i i t j CAL b i t SAL a t o WAL a t S (2.18) Bunda
va
i b - qator koeffitsientlari.
Har qanday ikkita Uolsh funksiyasi uchun quyidagi ifoda kuchga ega:
1 0 , , , , , N t m n o m n N t n WAL t m WAL
Yani, Uolsh funksiyalari o‘zaro ortogonal [15]. Uolsh almashtirishi uchun to‘g‘ri va teskari almashtirishlarni tadbiq etish mumkin:
1 0 . 1 ,..., 1 , 0 , , 1 N i k N k i k WAL N X (2.19)
1 0 . 1 ,...,
1 , 0 , ,
i k i N k i k WAL X x (2.20)
Agar
N 1 ko‘paytmani e’tiborga olinmasa, teskari almashtirish to‘g‘ri almashtirish bilan bir xil va
1 , t k WAL bo‘ladi. Shuning uchun «shakl» lar juftlarini matritsalarni raqamli usul (usul) asosida ko‘paytirish natijasida topish mumkin. Ammo faza xaqidagi 25
axborot yo‘qligi uchun UDA tez korrelatsiya (korrelatsiya oralig‘i kichik) larni va o‘ramlarni hisoblash uchun yaroqsiz.
(2.17) tezlik UDA k -tsrsh elementini diskret signal har bir elementi i x ni
k ketma-ketligi Uolsh funksiyasiga ko‘paytirishi va k ning hamma qiymatlari uchun qo‘shish orqali olish mumkin 1 ,..., 1 , 0
k ning hamma elementlari uchun uni matritsa ko‘rinishida yozish mumkin:
i k W x X , (2.21) Bunda 1 2 1 0 ...
i x x x x x -ma’lumotlar ketma-ketligi.
1 , 1 2 , 1 1 , 1 1 , 1 12 11 1 , 0 02 01 ...
. .......... .......... ...
... N N N N N N ki W W W W W W W W W W
-Uolsh almashtirishi matritsasi, 1 ... 1 2 1 0
X X X X X N I UDA matritsasi tashkil etuvchilari.
Alohida ta’kidlaymiz, ki W -bu
N N tartibli matritsa, bunda N berilgan nuqtalar soni, ya’ni diskret signal nuqtalari. Agar
berilgan nuqtalar soni bo‘lsa, u holda Uolsh funksiyasining dastlabki
ta tartibga keltirilganlarini ko‘rib chiqish kerak bo‘ladi. Ularning har biri
marta diskretizatsiyalanadi, bunda
matritsaning k -qatori k komponenta ketma-ketligining N ta diskret qiymatlariga to‘g‘ri keladi [11,12].
Adamar almashtirishi yoki Uolsh- Adamar almashtirishi bu ham mazmunan Uolsh almashtirishi bo‘lib, faqat boshqa tartibdagi Uolsh funksiyalari va boshqa almashtirish matritsasi qatoridir. Bunday o‘rin almashtirishlar natijasida olinadigan Adamar matritsasi, ikkinchi tartibli matritsaning massiv ostini o‘z ichiga oladi. 4-rasmda Adamarning 8 8
tartibli matritsasi ko‘rsatilgan bo‘lib, u H 8 ko‘rinishida belgilanadi. Uni matritslar orqali yozish mumkin: 26
1 1 1 1 2 H va
1 1 1 1 2 H .
Adamarning har qanday N 2 tartibli matritsasini H 2 dan rekursiv shaklda olish mumkin, ya’ni H H H H H N N N N N 2 (2.30) Bu rekursivlik xossasidan Uolsh funksiyasini Adamar tomonidan aniqlangan tartibda joylashtirish natijasida olingan Uolsh-Adamar tez almashtirishini UDA ga nisbatan ancha katta.
4-rasm. Adamarning 8 8
tartibli almashtirish matritsasi
Tezlik bilan hisoblash mumkin. tartibda jaylashgan Uolsh (yoki tabiiy tartibda joylashgan) funksiyasi 5-rasmda ko‘rsatilgan.
5-rasm. Adamar 4 4 tartibli almashtirish matritssi uchun diskretizatsiyalash vaqtini ko‘rsatuvchi 7
gacha Adamar tartibida joylashgan Uolsh funksiyasi
27
TEZKOR ALGORITMLARINI DASTURIY VOSITASINI YARATISH 3.1. Signallarga raqamli ishlov berishning tezkor hisoblash algoritmlari Fur’e diskret almashtirishdan foydalanib katta davomiylikka ega impulslar ketma – ketligiga ishlov kata hajmdagi arifmetik amallar (ko‘paytirish, qo‘shish vak kechiktirish) ni real vaqt oralig‘ida bajarish talab etiladi.
Hozirda katta tezlikda arifmetik amallarni bajaruvchi maxsus signal protsessorlari mavjudligiga qaramasdan katta hajmdagi signallarga raqamli ishlov berishni real vaqt davomida bajarishda qiyinchiliklar mavjud.
Misol uchun n x ketma – ketlik uchun 3 10
N bo‘lgan holat uchun Fure diskret almashtirishini
1 0 2 N n N jnk e n x k G , bunda 1 ,...,
2 , 1 , 0 N k
(3.1) formula orqali aniqlashda va
kompleks kattalik bo‘lganda,
2 10 1
ta kompleks ko‘paytirish va 6 10 1 N N ta kompleks qo‘shish amallarini bajarish kerak bo‘ladi.
Fur’e tezkor almashtirishi (FTA) dan foydalanish asosida bajariladigan arifmetik amallar sonini bir necha tartibli keskin kamaytirish mumkin.
FTAning asosi bir o‘lchovli sonlar massivini ko‘p o‘lchamli bilan almashtirish tashkil etadi. Bir o‘lchamli sonlar massisvini ko‘p sonliga aylantirishning bir necha uullari, ya’ni TFAning bir necha algoritmlari mavjud.
Ushbu FTA algortmlaridan birini ko‘rib chiqamiz. N nuqtali n x ketma – ketlik uchun FTA ni aniqlaymiz. Buning uchun
2 deb hisoblaymiz. N nuqtali n x ketma – ketlik ikki
/ N nuqtali juf
1 va toq n x 2 ketma – ketliklariga ajratiladi. 28
, 1 2 ,..., 1 , 0 , 2 1 N n n x n x
(3.2)
, 1 2 ,...,
1 , 0 , 2 1 N n n x n x
(3.3)
N nuqtali
n x ketma – ketlikning FTA quyidagicha aniqlanadi:
, 1 2 2 1 2 1 2 / 0 2 1 2 / 0 1 0 2 1 0 2 k n N N n nk N N n N toq n n N j N juft n n N j W n x W n x e n x e n x k G
(3.4)
bunda, 2 / / 2 2 / 2 2 N N j N j N W e e W
(3.5) (2.18) ifodani (2.19) ni e’tiborga olgan holda quyidagi shaklga keltiramiz:
nk N N n k N nk N N n W n x W W n x k G 2 / 1 2 / 0 2 2 / 1 2 / 0 1
(3.6) yoki
, 2 1 k G W k G k G k N
(3.7) bunda
k G 1 va k G 2 mos ravishda n x 1 va n x 2 ketma – ketliklarning 2 / N
nuqtali FDA ga teng. (3.7) ifoda
nuqtali FDA ni
1 va 2 / 2
k G nuqtali FDA lari yig‘indisi shakliga aniqlash mumkin.
Agar 2 / N nutali FDA ni oddiy usulda hisoblanganda, N nuqtali FDA ni aniqlash uchun N N 2 / 2 ta kompleks ko‘paytirish amalini bajarish kerak bo‘ladi. N katta bo‘lganda, ya’ni 2 / 2 / 2 / 2 2 2 N N N N N bo‘lgan holat uchun
k G ni aniqlashda bajariladigan ko‘paytirish amallari soni taxminan 2 marta kamayadi.
k G ni
1 0
k lar uchun aniqlash kerakligini va
1 , k G 2 larni esa 1 2 / 0
k uchun aniqlash kerakligini e’tiborga olib, (3.8) ifoda 2 /
k uchun aniqlanadi: 29
k G W k G k G k N 2 1 , agar 1 2 / 0 N k ,
(3.8)
Bunda k G 1 va k G 2 lar har 2 /
davrda k tadan takrorlanishi e’tiborga olingan. Yuqorida keltirilgan FTA algoritmini yo‘naltirilgan graflar yordamida tushuntirish uchun (6-rasm) sakkiz nuqtali FTA ni ikkita to‘rt nuqtali graflardan foydalanish usuli tasvirlangan [9,15].
Dastlab, kirishdagi n x ketma-ketligi ikkita
1 -juft va n x 2 -toq ketma-ketlikka bo‘laklangan bo‘lib, ular uchun
k G 1 va k G 2 lar aniqlanadi. So‘ngra (3.9) ifodaga asoslanib
k G aniqlanadi. O‘z navbatida har bir
1 va n x 2 ketma-ketliklar ikkiga bo‘linib, to‘rtta ikki nuqtali ketma-ketliklarni hosil qilish mumkin. (3.6) va (3.7) ifodalarni e’tiborga olib, 2
nuqtali FDA ikkita 4
nuqtali FDA kombinatsiyalari shakliga keltirishi mumkin:
k B W k A k G k N 2 1 , (3.10) yoki
k B W k A k G k N 2 1 , (3.11) Bunda,
k A N k , 1 2 0 va 4
k B nuqtali n x 1 ning juft va toq FDAlari. Misol: Berilgan qo’yidagi ketma ketlik 2 , 1 , 2 , 3 , 1 , 1 , 2 , 1 ] [ m X signal
qiymatlarini Diskret Fur’e almashtirish koeffisentlarini hisoblashning Tezkor Fur’e almashtirish algoritmidan foydalanish. 6-rasm. Sakkiz nuqtali FTA ni ikkita to‘rt nuqtali graflardan foydalanish usuli
30
Sakkiz nuqtali Fur’e tezkor almashtirishning 1-bosqichini qarab chiqamiz. x 1 (l)=x(l)+x(l+4) l=0,3 x 1 (l)=x(l-4)-x(l) l=4,7 x 1 (0)=x(0)+x(4) = 1+3=4 x 1 (4)=x(0)-x(4) = 1-3= -2 x 1
1 (5)=x(1)-x(5) = 2-2=0 x 1
1 (6)=x(2)-x(6) = 1-1=0 x 1
1 (7)=x(3)-x(7) = 1-2= -1 2.Bosqich ketma ket yaqinlashish usuli(iteratsiya)ni grafigini qurish. x 2 (0)=x 1 (0)+x 1 (2) = 4+2=6 x 2 (4)=x
1 (4)+x
1 (6) = 4+2=6 x 2
1 (1)+x
1 (3) = 4+3=7 x 2 (5)=x
1 (5)+x
1 (7) = 0-1=-1 x 2
1 (0)-x
1 (2) = 4-2=2 x 2 (6)=x
1 (4)-x
1 (6) = -2-0=-2 x 2
1 (1)-x
1 (3) = 4+2=6 x 2 (7)=x
1 (5)-x
1 (7) = 0+1=1 3.
x 3 (0)=x 2 (0)+x 2 (1) = 6+7=13 x 3 (4)=x
2 (4)+x
2 (5) = -2-1=-3 x 3
2 (0)-x
2 (1) = 6-7= -1 x 3 (5)=x
2 (4)-x
2 (5) =-2+1=-1 x 3
2 (2)+x
2 (3) = 2+1=3 x 3 (6)=x
2 (6)+x
2 (7) = -2+1=-1 x 3
2 (2)-x
2 (3) = 2-1=1 x 3 (7)=x
2 (6)-x
2 (7) = -2-1=-3 4. Bosqich ketma ket yaqinlashish usuli(iteratsiya)ni grafigini qurish. C x (0)=13/8; C x (1)=-3/8; C x (2)=3/8; C x (3)=-1/8; C x
x (5)=-1/8; C x
x (7)=-3/8;
X 0 1/8 2/8
3/8 1/2
5/8 6/8
7/8 Y 1 2 1 1 3 2 1 2 C x 13/8 -3/8
3/8 -1/8
-1/8 -1/8
1/8 -3/8
Qayta 1 2 1 3/2
3 2 1 3/2 xatolik
0 0 0 0.5 0 0 0 0.5
1- Jadval. Tezkor Fur’e almashtirish algoritmni bo’yicha olingan qiymatlar 31
Tezkor Uolsh-Adamar almashtirish algoritmi. Bizga ma’lumki Tezkor Fur’e almashtirish diskret Fur’e almashtirishning effektiv hisoblash algoritmi bo’lgani kabi, tezkor Uolsh – Adamar almashtirish ham Uolsh-Adamar almashtirishning tezkor algoritmidir. N=8 ga teng bo’lgan matrisani bo’laklash algoritmi yordamida tezkor Uolash-Adamar almashtirishni ko’rib chiqamiz. ) 12
3 ( ), 3 ( * ) 3 ( * 8 1 ) 3 ( X H С h x
bu erda
C spektr ko’ffisentlari. (3.12) ifodani qo’yidagi ko’rinishga keltiramiz. ) 7 ( ) 6 ( ) 5 ( ) 4 ( ) 3 ( ) 2 ( ) 1 ( ) 0 ( * ) 2 ( ) 2 ( ) 2 ( ) 2 ( * 8 1 ) 7 ( ) 6 ( ) 5 ( ) 4 ( ) 3 ( ) 2 ( ) 1 ( ) 0 (
X X X X X X X H H H H C C C C C C C С h h h h x x x x x x x x (3.13) (3.13) ifodani ko’rinishni qo’yidagi 2 ta shaklga keltiramiz. ) 3
) 2 ( ) 1 ( ) 0 ( * ) 2 ( * 8 1 ) 3 ( ) 2 ( ) 1 ( ) 0 ( 1 1 1 1
X X X H C C C С h x x x x (3.14) ) 7 ( ) 6 ( ) 5 ( ) 4 ( * ) 2 ( * 8 1 ) 7 ( ) 6 ( ) 5 ( ) 4 ( 1 1 1 1
X X X H C C C С h x x x x (3.15) Bu erdan qo’yidagi ifodani keltirib chiqamiz. x 1 (l)=x(l)+x(4+l), l=0,1,2,3; (3.16) x 1 (l)=x(l-4)-x(l), l=4,5,6,7; (3.17) va (3.18) ifodalarni ketma ket qo’shish va ayirish natijasida tezkor Uolsh – Adamar almashtirish algoritmining grafigini qo’ramiz (7-rasm).
32
8-rasm. Tezkor Uolsh-Adamar almashtirish grafi N=8 bo’yicha (3.17) ifodadan grafning 1- bosqichini hosil qilamiz. x 1
1 (1)=x(1)+x(5), x 1 (2)=x(2)+x(6), x 1 (3)=x(3)+x(7), x 1
1 (5)=x(1)-x(5), x 1 (2)=x(2)-x(6), x 1 (3)=x(3)-x(7), Yuqorida biz grafning 1-bosqichini ko’rib chiqdik. (3.14) va (3.15) formulalarni qo’llab qo’yidagilarni hosil qilamiz.
) 3 ( ) 2 ( ) 1 ( ) 0 ( * ) 1 ( ) 1 ( ) 1 ( ) 1 ( * 8 1 ) 3 ( ) 2 ( ) 1 ( ) 0 ( 2 1 1 1 x x x x H H H H C C C С h h h h x x x x (3.18)
) 7 ( ) 6 ( ) 5 ( ) 4 ( * ) 1 ( ) 1 ( ) 1 ( ) 1 ( * 8 1 ) 7 ( ) 6 ( ) 5 ( ) 4 ( 2 1 1 1 x x x x H H H H C C C С h h h h x x x x (3.19) (3.18) va (3.19) larni har qaysini ajratib qo’yidagi ifodani keltirib chiqaramiz. ; ) 1 ( ) 6 ( ) 1 ( * 8 1 ) 3 ( ) 1 ( ) 2 ( ) 0 ( * ) 1 ( * 8 1 ) 1 ( ) 0 ( 2 2 1 1 1 1 x x H x x x x H C С h h x x (3.18a) ; )
( ) 2 ( ) 1 ( * 8 1 ) 3 ( ) 1 ( ) 2 ( ) 0 ( * ) 1 ( * 8 1 ) 3 ( ) 2 ( 2 2 1 1 1 1 x x H x x x x H C С h h x x (3.18b) ; )
( ) 4 ( ) 1 ( * 8 1 ) 7 ( ) 5 ( ) 6 ( ) 4 ( * ) 1 ( * 8 1 ) 5 ( ) 4 ( 2 2 1 1 1 1 x x H x x x x H C С h h x x (3.18v) 33
; ) 7 ( ) 6 ( ) 1 ( * 8 1 ) 7 ( ) 5 ( ) 6 ( ) 4 ( * ) 1 ( * 8 1 ) 7 ( ) 6 ( 2 2 1 1 1 1
x H x x x x H C С h h x x (3.18g) Yuqorida keltirilgan (3.18), (3.19), (3.18a), (3.18b), (3.18v), (3.18g) ifodalar orqali grafning 2- bosqichini hisobladik. Grafning oxirgi qadamini qo’yidagi ifoda orqali hisoblaymiz. 1 1 1 1 h H .;
8*C x (0)=x 2 (0) + x
2 (1) = x
3 (0); 8*C x (1)=x
2 (0) - x
2 (1) = x
3 (1);
8*C x (2)=x 2 (2) + x
2 (3) = x
3 (2); 8*C x (3)=x
2 (2) - x
2 (3) = x
3 (3); (3.20) 8*C x
2 (4)+x
2 (5) = x
3 (4); 8*C x (5)=x
2 (4) - x
2 (5) = x
3 (5);
8*C x (6)=x 2 (6) + x
2 (7) = x
3 (6); 8*C x (7)=x
2 (6) - x
2 (7) = x
3 (7);
(3.20) ifoda grafning oxirgi bosqichini hisoblaydi. Tezkor Uolsh-Adamar keltirishning hisoblash algoritmining N=16 uchun grafini qo’yidagi rasmda keltirilgan (8-rasm) [9,10,12,15].
Download 1.31 Mb. Do'stlaringiz bilan baham: 
|