Giyalari univ rsit ti urganch filiali

2.3. Uzatilayotgan axborotlarni kodlash va dekodlashning samarali
algoritmlari
Uzatilayotgan axborotdagi ortiqcha razryadlarni bartaraf qilish axborotni
siqib beruvchi kodlarni asosiy maqsad va vazifasi hisoblanadi. Axborotni siqib
beruvchi kodlardan foydalanilganda kanalning o'tkazish oralig’idan samarali
foydalanish mumkin. Hozirgi kunda axborotni siqib beruvchi kodlarning
yo’qotishsiz va yo’qotishli turlari mavjud. Multimedia ko'rinishdagi axborotlarni
siqib jo'natish uchun yuqotishli algoritmlar ishlatiladi. Matn ko'rinishdagi
axborotlarni siqib jo'natish uchun yuqotishsiz siqish algoritmlari ishlatiladi.
Bunday algoritmlarga Xaffman va Shennona – Fano algoritmlari misol bo'la
oladi.
Shennona Fano kodi paydo bo'lguncha aloka kanali bo'ylab
uzatilayotgan axborotlardagi belgilar uzunligi bir xil bo'lgan bitlar yordamida
kodlashtirilar edi. Shennona Fano kodi paydo bo'lgandan so'ng uzatilayotgan
axborotdagi har bir belgini paydo bo'lish ehtimolligiga qarab turib uzunligi har
xil bo'lgan bitlar yordamida kodlash imkoniyati paydo bo'ldi. Boshqa qilib

---

Bajardi:
Bekmetov Sh.N.
Bet 72
Tekshirdi:                  Raximov T.O.
aytganda axborotda biror bir belgining paydo bo'lish ehtimolligi kattaroq bo'lsa
uni ikkilik sanoq sistemasidagi kodi ya'ni ekvivalentining uzunligi kichikrok bit
bo'ladi, agar axborotda biror bir belgining paydo bo'lish ehtimolligi kichikroq
bo'lsa uni ikkilik sanoq sistemasidagi kodi ya'ni ekvivalentining uzunligi
kichikroq bit bo'ladi.
Qurish texnikasi bo'yicha Shennon va Fano kodlari bir-biriga yaqin
bo'lganligi uchun Shennona - Fano kodi deyiladi. Ushbu kod 1948 yilda paydo
bo'lganva keyinchalik algoritm dasturiy ta’minoti ishlab chiqilgan.
Ushbu algoritm yordamida axborotni siqish quyidagicha amalga
oshiriladi:
1. Axborotdagi barcha belgilarning umumiy soni hisoblanadi.
2. Jami qandaydir N ta belgidan iborat bo'lgan axborotdan har bir
belgining paydo bo'lish chastotasi hisoblanadi.
3. Har bir belgining paydo bo'lish chastotasini kamayib borish
tartibida joylashtiriladi.
4. Umumiy bo'lgan jadvaldagi yig'indini teng ikkiga bo'linadi va
tepa qismiga «1» ni pastki qismiga «0» ni qo'yamiz.
5. Teng ikkiga bo'lish to har biriga bittadan belgi qolguncha davom
ettiramiz teng ikkiga bo'lishni.
6. Yuqoridagi algoritm asosida axborotni kodlashtirishga quyidagi ko'rib
chiqiladi.
Quyidagi ko'rinishda axborot berilgan:
BBCBBBCDDEDAAADDFFGGHHEE. Ushbu axborotda umumiy
belgilar soni 24 ta. Dastlab ushbu axborot uchun entropiya ko'rsatkichini
qiymatini hisoblaymiz. N(x) =   R(x) * Log 2 R(x) = 2,89bit ga teng bo'ladi.
Ushbu algoritm bo'yicha hisoblash natijalari jadval 2.1 keltirilgan.
2.4.-Jadval Shennona -Fano algoritmi bo'yicha hisoblash natijalari.

---

Bajardi:
Bekmetov Sh.N.
Bet 73
Tekshirdi:                  Raximov T.O.
Kodli kombinasiyaning o'rtacha uzunligini hisoblaymiz:
bitga teng.
Hozirgi kunda eng keng tarqalgan, amaliyotda ko'p ishlatiladigan
entropiyali kodlash usuliga asoslangan yo'qotishsiz siqish algoritmlaridan biri bu
–Xaffman algoritmi hisoblanadi. Xaffman algoritmi asosida matnli axborotlar
siqiladi.
Axborotdagi barcha belgilar soni, ya'ni N ni hisoblanadi
Jami N ta belgidan iborat bo'lgan axborotdagi har bir belgining paydo
bo'lish chastotasi hisoblanadi.
Har bir belgining paydo bo'lish chastotasini kamayib borish tartibida
jadvalga joylashtiriladi.
Jadvaldagi oxirgi ikkita chastota yigindisi hisoblanib, bitta umumiy
bo'lgan yig'indi chastotaga birlashtiriladi.
Belgilar
Paydo bo’lish
extimolligi
Yordamchi jadval
Kodi
B
5
5 (1)
5 (1)
3 (1)
5 (1)
11
D
5
5 (0)
3 (0)
5 (1)
101
A
3
3 (0)
100
E
3
3 (0)
2 (0)
2 (0)
2 (0)
2 (0)
3 (1)
3 (1)
011
C
2
2 (1)
2 (0)
010
F
2
2 (0)
2 (0)
2 (0)
2 (1)
001
G
2
2 (0)
2 (0)
2 (1)
0001
H
2
2 (0)
0000

---

Bajardi:
Bekmetov Sh.N.
Bet 74
Tekshirdi:                  Raximov T.O.
Hisoblangan yangi yig'indi chastotadan va hisoblashda qatnashmagan
boshqa chastotalardan jadvalning yangi ustuni hosil qilinadi (bunda ham
chastotalar kamayib borish tartibida joylashtiriladi).
 Shu tarzda to bitta umumiy N ga teng bulgan yigindi hosil bo'lguncha
jarayon davom etaveradi.
Jadval to'ldirilgandan so'ng, jadvaldagi hisoblashlarga muvofiq daraxt
quriladi.
Daraxtning tepa qismida N joylashgan bo'ladi va uni teng ikkiga bo'lish
kerak, hosil bo'lgan natijalarni yana teng ikkiga bo'lish kerak. Shu tarzda
axborotdagi har bir belgini paydo bo'lish chastotasi topilguncha bo'lishni davom
ettirish kerak.
Quyidagi ko'rinishda axborot berilgan:
BBCBBBCDDEDAAADDFFGGHHEE.
Ushbu algoritm bo'yicha hisoblash natijalari jadval 2.5- keltirilgan.
Kodli kombinasiyaning o'rtacha uzunligini hisoblaymiz:
bitga teng.
Belgilar
Paydo bo’lish
ehtimolligi
Yordamchi jadval
B
5
5
5
6
8
10
14
24
D
5
5
5
5
6
8
10
A
3
4
4
5
5
6
E
3
3
4
4
5
C
2
3
3
4
F
2
2
3
G
2
2
H
2
belgilar
B
D
A
E
C
F
G
H
Kodi
01
00
100
101
1101
1100
1111
1110

---

Bajardi:
Bekmetov Sh.N.
Bet 75
Tekshirdi:                  Raximov T.O.
Yuqoridagi ko'rib chiqilgan 1 va 2- kodlashtirilayotgan axborot
qo'yidagicha, ya'ni BBCBBBCDDEDAAADDFFGGHHEE. Biroq, hisoblash
natijalariga ko'ra, kodlashtirilgan axborotdagi xar bir belgiga mos kelgan kodli
kombinasiyaning o'rtacha uzunligi Shennona - Fano usuli uchun
bitga, Xaffen usuli uchun esa
bitga teng
chiqdi. Bundan xulosa qilinadiki, yuqoridagi axborotni Xaffen usuli bilan
kodlashtirilsa maqsadga muvofiq bo'ladi, chunki ushbu algoritm bilan axborotni
kodlashtirilganda axborodagi xar bir belgiga mos keluvchi kodli
kombinasiyaning o'rtacha uzunligi kichkina, ya'ni axborotni uzatish uchun kam
bit sarflanadi. Bu esa o'z navbatida axborotni uzatish tezligini oshirishga olib
keladi.
Ushbu Shennona-Fano va Xaffmen algoritmlarining imkoniyatlarini
komp yuterda solishtirish maqsadida dasturiy ta'minot ishlab chiqildi. Ishlab
chiqilgan dasturdan “Ma'lumotlarni uzatish asoslari” fanining amaliyot
mashg'ulotida foydalanish mumkin.
Ishlab chiqilgan dasturning tarkibiy qismi uchta qismdan iborat bo'lib, ularga
quyidagilar kiradi:
-
ishni bajarish tartibi;
-
nazariy qism;
-
amaliy qism.
Ishni bajarish tartibi qismida quyidagi ma'lumotlar berilgan:
ishning maksadi;
-
topshiriq;
-
ishni bajarish tartibi;
-
dastur maketining tuzilishi.
Nazariy qismda esa quyidagi ma'lumotlar berilgan:
-
axborotni Shennon-Fano algoritmi yordamida kodlash ketma-ketligi;

---

Bajardi:
Bekmetov Sh.N.
Bet 76
Tekshirdi:                  Raximov T.O.
-
axborotni Xaffmen algoritmi vositasida kodlash ketma-ketligi;
Amaliy qismda esa bevosita Shennona – Fano va Xaffmen algoritmlari
yordamida istalgan axborotni kodlash mumkin.
  Ushbu ishlab chiqilgan dastur yordamida bir nechta axborotni kodlash
jarayonini ko'rib chiqamiz. 2.23- rasmda dasturning Shennona - Fano algoritmi
asosida axborotni kodlashtirish uchun mo'ljallangan oynasing ko'rinishi
keltirilgan.
2.23- rasm Dasturni Shennona - Fano algoritmi asosida axborotni kodlashtirish
uchun mo'ljallangan oynasi.

---

Bajardi:
Bekmetov Sh.N.
Bet 77
Tekshirdi:                  Raximov T.O.
2.24-rasm. Dasturni Xaffmen algoritmi asosida axborotni kodlashtirish uchun
mo'ljallangan oynasi.
Ushbu ishlab chiqilgan dastur yordamida bir nechta axborotni kodlash
jarayonini ko'rib chiqamiz. Dastlab Xaffmen va Shennona – Fano algoritmlari
vositasida axborotni kodlash uchun tarkibiy tuzilishi turlicha bo'lgan
axborotlarni tanlab olamiz:
Axborot 1: BBCBBBCDDEDAAADDFFGGHHEE
Axborot 2: GFFFFBBBBAAAACCFFFFFCCDDE
Axborot 3: AAAAAAABBCCDDEEFFGGHHHAAAA
Axborot 4: BBCCCCDEEEEFFFFGGGGFFFFFFDD
Axborot 5: CCCCCCCCCCCBBBBBAAAADDDDEEEF
Axborot 6: BBCBBDBBDEEFDABBDABBBBACACCEG
Axborot 7: AAAAAAAABBAAAABBBCCCCCDDDDDEEE
Ushbu keltirilgan axborotlarni har birini avval Shennona – Fano, so'ng Xaffmen
algoritmlari yordamida kodlashtiriladi.

---

Bajardi:
Bekmetov Sh.N.
Bet 78
Tekshirdi:                  Raximov T.O.
Axborot 1: BBCBBBCDDEDAAADDFFGGHHEE. Umumiy belgilar
soni 24 ta.
Dastlab ushbu axborot uchun entropiya ko'rsatkichining qiymatini
hisoblaniladi. N(x) =   R(x) * Log 2 R(x) = 2,89 bit ga teng bo'ladi.
Barcha keltirilgan axborotlar uchun dastur yordamida hisoblash natijalari
2.6-jadvalda keltirilgan. Ushbu jadvalda ko'rinib turganidek, ettita berilgan
axborotdagi axborot hajmi turlicha.
2.6
-
Jadval. Hisoblash natijalari
Axborot
hajmi
24
belgi
25
belgi
26
belgi
27
belgi
28
belgi
29
belgi
30
belgi
Entropiya
2.89
2.46
2.59
2.39
2.29
2.38
2.15
n
o’rt
Shenno-
Fano
2.95
2.56
2.77
2.48
2.43
2.52
2.26
n
o’rt
Xaffen
2.92
2.52
2.62
2.44
2.36
2.41
2.20
Jadvaldagi ma'lumotlarga qarab, kodli kombinasiyaning o'rtacha
uzunligini axborot hajmiga bog'liklik grafigini chiziladi (1.5 Rasm).

---

Bajardi:
Bekmetov Sh.N.
Bet 79
Tekshirdi:                  Raximov T.O.
2.25.-rasm. Shennona-Fano va Xa
ffmen algoritmlarining axborot
hajmiga
bog'liqlik chizmasi.
Fayra kodi asos qilib olingan kodli kombinasiyalarni muayyan tarzda
tanlab olish orqali xosil qilinadi. Bu kodli kombinasiyalar esa matrisa
ko'rinishida yozilib, shu matrisa orqali Fayra kodining tegishli kodli
kombinasiyalari xosil qilinadi. n ta ustun va k ta qatordan iborat bo'lgan bunday
matrisa xosil qiluvchi matrisa deyiladi.
Fayra kodida kodlashtirish algoritmi 2.1 rasmda keltirilgan. U quyidagi
bosqichlardan (bloklardan) iborat:
1. Fayra kodi parametrlari n, k, r lar kiritiladi.
2. g(x) keltirilmaydigan ko'pxad va k ning darajasi t kiritiladi;
3. kiritilgan g(x) va uning darajasi t chop etiladi;
4. qo'shimcha ko'pxad (x s +1) va uning darajasi s ni kiritish;
5. M ning qiymati M=2 t –1 formula bo'yicha hisoblanadi;
6. S sonini xisoblab chiqarilgan M soniga karraliligi tekshiriladi.
Agar karralik bo'lsa, 4-blokka o'tiladi. Unda (xs +1) ko'pxad va uning
darajasi s qaytadan kiritiladi. Agar shart bajarilmasa, keyingi 7-blokka o'tiladi;
1. Kiritilgan (x s +1) va uning darajasi s chop etiladi;
2. R(x) yasovchi polinom kiritiladi;
3. kiritilgan R(x) polinom chop etiladi;
4. kodning informasion qismi k1 (x) kiritiladi;
5. k1 (x) kombinasiyaga muvofiq n1 parametr n1 = k1 + r formulaga
asosan aniqlanadi;
6. k1 (x) ni r razryad chapga siljitish ishi bajariladi.
7. xosil bo'lgan kombinasiya R(x) yasovchi polinomga bo'linadi va R(x)
qoldiq xosil qilinadi;
8. xosil bo'lgan R(x) qoldiq k1 (x) informasion qismga biriktiriladi;
9. kodlangan axborot chop etiladi.

---

Bajardi:
Bekmetov Sh.N.
Bet 80
Tekshirdi:                  Raximov T.O.
2.26-rasm Fayra kodida kodlashtirish algoritmi

---

Bajardi:
Bekmetov Sh.N.
Bet 81
Tekshirdi:                  Raximov T.O.
2.27-rasm Fayra kodida kodlashtirish algoritmi davomi
Fayra kodida kodlashtirilgan axborotlarni dekoderlash usullari Fayra
kodi, n – elementli kodli kombinasiyada xosil bo'luvchi, uzunligi v va undan

---

Bajardi:
Bekmetov Sh.N.
Bet 82
Tekshirdi:                  Raximov T.O.
kichik bo'lgan bir karralik xatolar guruxini to'g'irlaydi va bir vaqtning o'zida
uzunligi
 v bo'lgan bir karralik xatolar guruxini aniqlaydi.
Fayra kodida kodlashtirilgan axborotlarni dekoderlashning ikki xil usuli
mavjud. Ularning har birini alohida qarab chiqamiz:
f(x) uzatilgan kodli kombinasiyaga xi V(x) ko'rinishdagi xatolar paketi
ta'sir qilsin.
V (x) – xatolar paketini ifodalovchi ko'pxad;
xi - xatolar paketi boshlangan razryad.
Ushbu algoritmni blok-sxema ko'rinishdagi taxlili 2.28-rasmda berilgan.
Rasmdagi bloklarning vazifasini izoxlab o'tamiz:
1. xatolar paketi boshlangan razryad nomeri «I1» kiritiladi;
2. xatolar paketining qiymati V(x) kiritiladi;
3. kodlangan f(x) kombinasiyaga «I1» razryaddan boshlab V(x) xato kiritiladi va
F(x) xato kombinasiya xosil qilinadi;
4. F(x) xato kombinasiya chop etiladi;
5. F(x) ni R(x) yasovchi polinomga bo'lish bajariladi va R(x) qoldiq olinadi;
6. R(x) qoldiq tekshiriladi. Agar R(x) = 0 bo'lsa, u xolda 30-blokka o'tiladi.
Unda F(x) kombinasiyada xato yo'q degan xabar chop etiladi va dastur ishi
yakunlanadi. Agar shart bajarilmasa navbatdagi 7-blokka o'tiladi;
7. F(x) kombinasiyada xato mavjud degan xabar chop etiladi;
8. F(x) ni g(x) ga bo'lish bajariladi va V1(x) qoldiq xosil qilinadi;
9. F(x) ni (x s +1) ga bo'lish bajariladi va V2(x) qoldiq xosil qilinadi;
10. qoldiq V1(x) ga ko'paytirish kerak bo'lgan xi ning boshlang'ich darajasi
beriladi;
11. qoldiq V2(x) ga ko'paytirish kerak bo'lgan xj ning boshlang'ich darajasi
beriladi;
12. V2(x) ni J razryad chapga surish ishi bajariladi ya'ni x j ga ko'paytiriladi;
13. Xosil bo'lgan kombinasiya (xs+1)ga bo'linadi va qoldiq j xosil qilinadi.

---

Bajardi:
Bekmetov Sh.N.
Bet 83
Tekshirdi:                  Raximov T.O.
14. V 1 (x) ni I razryad chapga surish ishi bajariladi
(xi ga ko'paytiriladi).
15. Xosil bo'lgan natija g (x) ga bo'linadi va QOLI olinadi.
16. Qol I va QOL j larning tengligi solishtiriladi. Agar qoldiqlar teng bo'lmasa
17 blokka o'tiladi.
17. Xj ning navbatdagi daraja ko'rsatkichi olinadi, ya'ni J daraja bir birlikka
orttiriladi.
18. J ning kod uzunligi n1 dan kattaligi tekshiriladi. Agar shart bajarilmasa 12-
blokka o'tiladi, ya'ni sikl takrorlanadi. Agar shart bajarilsa 19-blokka o'tiladi;
19. x i ning navbatdagi daraja ko'rsatkichiga o'tiladi, ya'ni I daraja bir birlikka
oshiriladi;
20. I ning n , dan kattaligi tekshiriladi. Agar shart bajarilmasa 11-blokka o'tiladi.
Agar shart bajarilsa 21-blokka o'tiladi;
21. «xatolarni to'g'rilash imkoni yo'q» degan xabar chop etiladi va dastur ishi
yakunlanadi;
16-blokdagi shart bajarilganda 22-blokka o'tiladi;
22. bir xil bo'lgan qoldiq V(x) (KOL I q KOL J ) chop etiladi;
23. qoldiqlari teng bo'lgan daraja ko'rsatkich I va J lar chop etiladi;
24. D1 ning qiymati topiladi;
25. D2 ning qiymati aniqlanadi;
26. D1 va D2 lar asosida xatolar paketi boshlangan I razryad aniqlanadi;
27. F (x) xato kombinasiya to'g'irlanadi;
28. to'g'rilangan kombinasiya chop etiladi;
Dastur ishi yakunlanadi.

---

Bajardi:
Bekmetov Sh.N.
Bet 84
Tekshirdi:                  Raximov T.O.
2.28-rasm Fayra kodini dekoderlash algoritmi

---

Bajardi:
Bekmetov Sh.N.
Bet 85
Tekshirdi:                  Raximov T.O.
2.29-rasm Fayra kodini dekoderlash algoritmi

---

Bajardi:
Bekmetov Sh.N.
Bet 86
Tekshirdi:                  Raximov T.O.
2.30-rasm Fayra kodini dekoderlash algoritmi

---

Bajardi:
Bekmetov Sh.N.
Bet 87
Tekshirdi:                  Raximov T.O.