B I t I r u V m a L a k a V i y I sh I

Adamar almashtirish

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 ko‘rinishida belgilanadi.
Uni matritslar orqali yozish mumkin:

² H  ^1
1 va
_{ 2 H } ^11 _.

1





1




 _{ 1} _1 

Adamarning har qanday olish mumkin, ya’ni
2N tartibli matritsasini
² H dan rekursiv shaklda

^{ N} H ^NH ^

2 N _{H   }
(2.30)

_ ^{N H NH} _
Bu rekursivlik xossasidan Uolsh funksiyasini Adamar tomonidan aniqlangan tartibda joylashtirish natijasida olingan Uolsh-Adamar tez almashtirishini UDA ga nisbatan ancha katta.

3. 
   rasm. Adamarning 8  8 tartibli almashtirish matritsasi
   

Tezlik bilan hisoblash mumkin. tartibda jaylashgan Uolsh (yoki tabiiy tartibda joylashgan) funksiyasi 5-rasmda ko‘rsatilgan.

3. 
   rasm. Adamar
   

4  4
tartibli almashtirish matritssi uchun

diskretizatsiyalash vaqtini ko‘rsatuvchi
n  7
gacha Adamar tartibida

joylashgan Uolsh funksiyasi

III-BOB. SIGNALLARGA SPEKTRIAL ISHLOV BERISHNING TEZKOR ALGORITMLARINI DASTURIY VOSITASINI YARATISH

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
xn
ketma – ketlik uchun
N  10³
bo‘lgan holat uchun Fure

diskret almashtirishini



N 1
Gk   _ xne
n0

• 
  jnk ^2
  

N
, bunda
k  0,1,2,...,N 1
(3.1)

formula orqali aniqlashda va
xn
kompleks kattalik bo‘lganda, N 1²  10⁶ ta

kompleks ko‘paytirish va kerak bo‘ladi.
NN 1  10⁶
ta kompleks qo‘shish amallarini bajarish

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
xn
ketma –

ketlik uchun FTA ni aniqlaymiz. Buning uchun
_N 2n
deb hisoblaymiz. N nuqtali

xn
ketma – ketlik ikki N / 2 nuqtali juf
x₁n va toq
x₂n ketma – ketliklariga

ajratiladi.

x n  x2n, n  0,1,...,^N
1,
(3.2)

1 ₂

x n  x2n, n  0,1,...,^N
1,
(3.3)

1 ₂

N nuqtali
xn ketma – ketlikning FTA quyidagicha aniqlanadi:

Gk  


N 1

 
_ x n e
n0
n juft
_{ j} 2
N


N 1

• 
  
   
  _ x n e
  

n0


ntoq
_{ j} 2
N _
(3.4)

N / 21

N / 21

 
2nk _{
 1W} 2n1k _,

bunda,
_ x 2n W_N
n0
_ x 2n _N
n0

_W N _{ e} j2 / N _² _{ e} j2 / N  _{ W}

(3.5)

2 N / 2
(2.18) ifodani (2.19) ni e’tiborga olgan holda quyidagi shaklga keltiramiz:

N
yoki
Gk  
N / 21

_ x nW₁
nk
N / 2
n0


 W ^k
N / 21

_ x nW₂
nk
N / 2
n0

(3.6)

N

2
Gk   G₁k   W^kG
k ,
(3.7)

bunda
G₁k  va
G₂ k 
mos ravishda
x₁n va
x₂ n
ketma – ketliklarning N / 2

nuqtali FDA ga teng. (3.7) ifoda Gk  N

nuqtali FDA ni G₁k  va G₂ k  N / 2 nuqtali FDA

lari yig‘indisi shakliga aniqlash mumkin.

Agar N / 2
nutali FDA ni oddiy usulda hisoblanganda, N nuqtali FDA ni

aniqlash uchun N ² / 2  N 
ta kompleks ko‘paytirish amalini bajarish kerak

bo‘ladi. N katta bo‘lganda, ya’ni N ² / 2  N  N ² / 2  N  N ² / 2
bo‘lgan holat

uchun
Gk 
ni aniqlashda bajariladigan ko‘paytirish amallari soni taxminan 2

marta kamayadi.

Gk  ni
0  k  N 1 lar uchun aniqlash kerakligini va
G₁k ,
G₂ k 
larni

esa
0  k  N / 2 1
uchun aniqlash kerakligini e’tiborga olib, (3.8) ifoda

k  N / 2
uchun aniqlanadi:

N 2
Gk   G₁k   W^kG k , agar 0  k  N / 2 1, (3.8)

Bunda
G₁k  va
G₂ k 
lar har
N / 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
xn
ketma-ketligi ikkita
x₁n-juft va
x₂ n-toq

ketma-ketlikka bo‘laklangan bo‘lib, ular uchun
G₁ k  va
G₂ k 
lar aniqlanadi.

So‘ngra (3.9) ifodaga asoslanib
Gk 
aniqlanadi. O‘z navbatida har bir
x₁n va

x₂ n
ketma-ketliklar ikkiga bo‘linib, to‘rtta ikki nuqtali ketma-ketliklarni hosil

qilish mumkin. (3.6) va (3.7) ifodalarni e’tiborga olib, N 2 nuqtali FDA ikkita


N 4 nuqtali FDA kombinatsiyalari shakliga keltirishi mumkin:
G k   Ak W ^k Bk , (3.10)
1 N 2

yoki
G k   Ak   W ^2k Bk , (3.11)

1 N


Bunda, 0  k  N 2 1, Ak  va Bk  N 4 nuqtali x₁ n ning juft va toq FDAlari.

Misol: Berilgan qo’yidagi ketma ketlik
X[m]  1,
2, 1, 1, 3,
2, 1,
2 signal

qiymatlarini Diskret Fur’e almashtirish koeffisentlarini hisoblashning Tezkor Fur’e almashtirish algoritmidan foydalanish.

3. 
   rasm. Sakkiz nuqtali FTA ni ikkita to‘rt nuqtali graflardan foydalanish usuli
   

29

Sakkiz nuqtali Fur’e tezkor almashtirishning 1-bosqichini qarab chiqamiz. x₁(l)=x(l)+x(l+4) l=0,3 x₁(l)=x(l-4)-x(l) l=4,7
x₁(0)=x(0)+x(4) = 1+3=4 x₁(4)=x(0)-x(4) = 1-3= -2
x₁(1)=x(1)+x(5) = 2+2=4 x₁(5)=x(1)-x(5) = 2-2=0
x₁(2)=x(2)+x(6) = 1+1=2 x₁(6)=x(2)-x(6) = 1-1=0
x₁(3)=x(3)+x(7) = 1+2=3 x₁(7)=x(3)-x(7) = 1-2= -1

2. 
   Bosqich ketma ket yaqinlashish usuli(iteratsiya)ni grafigini qurish. x₂(0)=x₁(0)+x₁(2) = 4+2=6 x₂(4)=x₁(4)+x₁(6) = 4+2=6
   

x₂(1)=x₁(1)+x₁(3) = 4+3=7 x₂(5)=x₁(5)+x₁(7) = 0-1=-1
x₂(2)=x₁(0)-x₁(2) = 4-2=2 x₂(6)=x₁(4)-x₁(6) = -2-0=-2
x₂(3)=x₁(1)-x₁(3) = 4+2=6 x₂(7)=x₁(5)-x₁(7) = 0+1=1

2. 
   Bosqich ketma ket yaqinlashish usuli(iteratsiya)ni grafigini qurish. x₃(0)=x₂(0)+x₂(1) = 6+7=13 x₃(4)=x₂(4)+x₂(5) = -2-1=-3
   

x₃(1)=x₂(0)-x₂(1) = 6-7= -1 x₃(5)=x₂(4)-x₂(5) =-2+1=-1
x₃(2)=x₂(2)+x₂(3) = 2+1=3 x₃(6)=x₂(6)+x₂(7) = -2+1=-1
x₃(3)=x₂(2)-x₂(3) = 2-1=1 x₃(7)=x₂(6)-x₂(7) = -2-1=-3

2. 
   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(4)=-1/8; C_x(5)=-1/8;
C_x(6)=1/8; C_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
Cx	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

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.

С (3)  ¹ * H
x ₈ h
(3)* X (3),
(3.12)

bu erda C_x  spektr ko’ffisentlari.

(3.12) ifodani qo’yidagi ko’rinishga keltiramiz.

С_x (0)
C_x (1)
C_x (2)
C_x (3)
_{ 1 *} H_h (2)
X (0)
X (1)
X (2)
^H_h ⁽²⁾ _* X (3)
(3.13)

C_x (4)
C_x (5)
C_x (6)
C_x (7)
8 H_h (2)
 H_h (2)
X (4)
X (5)
X (6)
X (7)

(3.13) ifodani ko’rinishni qo’yidagi 2 ta shaklga keltiramiz.

С_x (0)
C_x (1)


 ¹ * H
X ₁ (0)

h
_{(2) *} X ₁ (1)

(3.14)

C_x (2) 8 X ₁ (2)

C_x (3)
С_x (4)
C_x (5)
 ¹ * H
X ₁ (3)
X ₁ (4)

h
_(2)* X ₁ (5)

(3.15)

C_x (6) 8 X ₁ (6)
C_x (7) X ₁ (7)

Bu erdan qo’yidagi ifodani keltirib chiqamiz. x₁(l)=x(l)+x(4+l), l=0,1,2,3; (3.16)

x₁(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).

8-rasm. Tezkor Uolsh-Adamar almashtirish grafi N=8 bo’yicha (3.17) ifodadan grafning 1- bosqichini hosil qilamiz.

x₁(0)=x(0)+x(4), x₁(1)=x(1)+x(5), x₁(2)=x(2)+x(6), x₁(3)=x(3)+x(7),
x₁(4)=x(0)-x(4), x₁(5)=x(1)-x(5), x₁(2)=x(2)-x(6), x₁(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.

С_x (0)
C_x (1)


_{1 }H_h (1)


^{Hh (1)} 
^{x1 (0)} 
^x (1) ^

 * _{
 *} 
^ (3.18)

x
C_x (2)
8 _H_h (1)
 H_h (1)_
^x₁ (2)^

C_x (3)
^ (3)^



 2
С_x (4)
C_x (5)


_{1 }H_h (1)


^{Hh (1)} 
^{x1 (4)} 
^x (5) ^

 * _{
 *} 
^ (3.19)

x
C_x (6)
8 _H_h (1)
 H_h (1)_
^x₁ (6) ^

C_x (7)
^ (7)^



 2

;
(3.18) va (3.19) larni har qaysini ajratib qo’yidagi ifodani keltirib chiqaramiz.

_С_x (0)<sub>  1 * H


(1) * </sub>x₁ (0)  x₁ (2)<sub>  1 * H


(1)</sub>^{x2 (6)}

(3.18a)

^{C (1) } 8 ^{h
x (1)  x (3) } 8
^{h }x (1) ^

;
 x 
 1 1 
 2 

_С_x (2)<sub>  1 * H


(1) * </sub>x₁ (0)  x₁ (2)<sub>  1 * H


(1)</sub>^{x2 (2)}

(3.18b)

^{C (3)} 8 ^{h
x (1)  x (3) } 8
^{h }x (3)^

;
 x 
 1 1 
 2 

_С_x (4)<sub>  1 * H


(1) * </sub>x₁ (4)  x₁ (6)<sub>  1 * H


(1)</sub>^{x2 (4)}

(3.18v)

^{C (5)} 8 ^{h
x (5)  x (7)} 8
^{h }x (5)^

 x 
 1 1 
 2 

_С_x (6)<sub>  1 * H


(1) * </sub>x₁ (4)  x₁ (6)<sub>  1 * H


(1)</sub>^{x2 (6)}
(3.18g)

^{C (7)} 8 ^{h
x (5)  x (7)} 8
^{h }x (7)^

 x 
 1 1 
 2 

;
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.

₁

h
H  ^1

^1 .;

 ^1


8*C_x(0)=x₂(0) + x₂(1) = x₃(0); 8*C_x(1)=x₂(0) - x₂(1) = x₃(1);
8*C_x(2)=x₂(2) + x₂(3) = x₃(2); 8*C_x(3)=x₂(2) - x₂(3) = x₃(3); (3.20)
8*C_x(4)=x₂(4)+x₂(5) = x₃(4); 8*C_x(5)=x₂(4) - x₂(5) = x₃(5);
8*C_x(6)=x₂(6) + x₂(7) = x₃(6); 8*C_x(7)=x₂(6) - x₂(7) = x₃(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].


8-rasm. N=16 uchun tezkor Uolsh-Adamar algoritmining grafi