|
Belgilar
|
Paydo bo’lish chastotasi
|
Yordamchi jadval
|
Kodi
|
B
|
5
|
1
|
1
|
|
11
|
D
|
5
|
0
|
1
|
101
|
A
|
3
|
0
|
100
|
E
|
3
|
0
|
1
|
1
|
011
|
C
|
2
|
0
|
010
|
F
|
2
|
0
|
1
|
|
001
|
G
|
2
|
0
|
1
|
0001
|
H
|
2
|
0
|
0000
|
Kodli kombinatsiyaning o`rtacha uzunligini hisoblaymiz:
bitga teng.
Xozirgi kunda eng keng tarqalgan, amaliyotda ko’p ishlatiladigan entropiyali kodlash usuliga asoslangan yo`qotishsiz siqish algoritmlaridan biri bu –Xaffman algoritmi Xisoblanadi. Xaffman algoritmi asosida matnli axborotlar sikiladi.
Axborotdagi barcha belgilar soni, ya’ni N ni xisoblanadi
Jami N ta belgidan iborat bo`lgan axborotdagi Xar bir belgining paydo bo’lish chastotasi xisoblanadi.
Xar bir belgining paydo bo’lish chastotasini kamayib borish tartibida jadvalga joylashtiriladi
Jadvaldagi oxirgi ikkita chastota yigindisi xisoblanib, bitta umumiy bo`lgan yigindi chastotaga birlashtiriladi
Xisoblangan yangi yigindi chastotadan va xisoblashda katnashmagan boshka chastotalardan jadvalning yangi ustuni xosil kilinadi (bunda xam chastotalar kamayib borish tartibida joylashtiriladi)
Shu tarzda to bitta umumiy N ga teng bo`lgan yigindi xosil bulguncha jarayon davom etaveradi
Jadval tuldirilgandan sung, jadvaldagi xisoblashlarga muvoffik daraxt kuriladi.
Daraxtning tepa kismida N joylashgan bo’ladi va uni teng ikkiga bo’lish kerak, Xosil bыlgan natijalarni yana teng ikkiga bo’lish kerak. Shu tarzda axborotdagi xar bir belgini paydo bo’lish chastotasi topilguncha bo’lishni davom ettirish kerak.
Misol 2: Quyidagi ko’rinishda axborot berilgan: BBCBBBCDDEDAAADDFFGGHHEE.
Ushbu algoritm bo’yicha xisoblash natijalari jadval 3.2 keltirilgan.
Xaffmen algoritmi bo’yicha xisoblash natijalari.
Jadval 3.2.
Belgilar
|
Paydo bo’lish chastotasi
|
Yerdamchi 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
|
|
|
|
|
|
|
|
3.3-jadval
belgilar
|
B
|
D
|
A
|
E
|
C
|
F
|
G
|
H
|
kodi
|
01
|
00
|
100
|
101
|
1101
|
1100
|
1111
|
1110
|
Kodli kombinatsiyaning o`rtacha uzunligini xisoblaymiz:
n o`rt = ∑ n i * R(x) = 2,92 bitga teng.
3.4 – 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 ўрт Shennon-Fano
|
2.95
|
2.56
|
2.77
|
2.48
|
2.43
|
2.52
|
2.26
|
n ўрт Xaffman
|
2.92
|
2.52
|
2.62
|
2.44
|
2.36
|
2.41
|
2.20
|
Mustaqil ishlash uchun topshiriqlar
Variant
|
xabarlar
|
1
|
BBCCCCDEEEEFFFFGGGGFFFFFFDD
|
2
|
DFABBBEECEDDEFFFAEBBCBBBBBBC
|
3
|
CCCCCCCCCCCBBBBBAAAADDDDEEEF
|
4
|
BCDEEFAACCADEEDDDEDBAAEEEDDD
|
5
|
AAAAAAAABBAAAABBBCCCCCDDDDDEEE
|
6
|
CEDDBCEFABBBFDDFAEBAADDDEEAAA
|
7
|
BBCBBDBBDEEFDABBDABBBBACACCEG
|
8
|
DDFEBBCAADAEFFBEGHAABFFBD
|
9
|
BBCBBBCDDEDAAADDFFGGHHEE
|
10
|
DDECBFFEEEAAADBBBEEEAAAAABBB
|
11
|
CAADDDAEDADDEAAEBEFBEDEFEEA
|
12
|
FFFBBCDEEAAFDFFGBBGFADAABFFFF
|
13
|
CEEFFDDDEBBAAAEDEDAECBAADDD
|
14
|
EEEEBBBEEEEBBCCCCDDDDFFFFAEEEE
|
15
|
GBDBBBADDABADAAAFFFEEEEBBBEE
|
16
|
BBBAAAEDDAAABBFEFFDDEEGAAAAA
|
17
|
FFFBBCDEEAAFDFFGBBGFADAAA
|
18
|
GFFFFBBBBAAAACCFFFFFCCDDE
|
19
|
ABBCEHABCAEGAAAAAADADDDD
|
20
|
AAAAAAABBCCDDEEFFGGHHHAAAA
|
21
|
ABBBCEDDEFFFAEBBCCCCADAAABB
|
22
|
DDDDDDDDAAABBBCCCDDDEEEFFF
|
№ 4 Laborotoriya ishi
MA’LUMOTLARNI SIQISH ALGORITMLARI (LEMPEL – ZIV, LZSS ALGORITMLARI) NI TADQIQ QILISH
Ishdan maqsad:
Axborotni siqib beruvchi Lempel - Ziva algoritmlari bilan tanishib chikish;
Axborotni yuqotishsiz siqib beruvchi LZSS algoritmi yordamida axborotni xajmini kamaytirish bo’yicha amaliy kunikmalarga ega bo‘lish.
Nazariy ma’lumot
Lempel – Ziva algoritmlarini iboralar bo’yicha arxivlovchi algoritmlar deyiladi, chunka ushbu algoritmlarda axborotdagi iboralar yoki xarflar birlashmasi uzidan olidinrok kaytarilgan xuddui shunday ibora yeki xarflar birlashmasi bilan almashtirishga asoslangan. Iboralar bo’yicha yo’qotishsiz arxivlovchi algoritmlarni ayrim adabiyotlarda jadval asosida arxivlovchi algoritmlar ham deyiladi. Ushbu algoritmlarni asoschilari Yakoba Ziva (Jakob Ziv) va Abraxam Lempel (Abraham Lempel) xisoblanadi. Iboralar buycha arxivlovchi algoritmlar dastlabkisi 1977 yilda paydo buldi va ushbu algoritmnig nomi LZ77 deb nomlangan. Keyinchalik bir yildan so‘ng ushbu algoritmning modifikatsiyalangan varianti yaratildi va algoritm nomi LZ78 deb atala boshlandi.
Masalan ushbu axborotni kodlashtirish talab qilsin "aaabbabaabaaabab". Ushbu axborotni jadval 4.1 ko’rsatilganidek yettita mayda iboralarga (xarflar birlashmasi) bulamiz. Axborotdagi xarbir xarf yoki iboralar (xarflar birlashmasi) uzidan oldin kaytarilgan iboralar (xarflar birlashmasi) va kushuv mavjud bo`lgan belgi bilan kodlanadi. Masalan, oxirgi uchta belgi 4 ("b") iborasi sifatida kodlshtiriladi. Jadval 4.1 LZ78 algoritmi yordamida "aaabbabaabaaabab" axborotni kodlashtirish natijalari keltirilgan.
Jadval 4.1.
Axborotni iboralarga bo’lish
|
a
|
aa
|
b
|
ba
|
baa
|
baaa
|
bab
|
Raqamlarga ajratish
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Natija
|
(0,a)
|
(1,a)
|
(0,b)
|
(3,a)
|
(4,a)
|
(5,a)
|
(4,b)
|
Xozirgi kunga kelib LZ oilasiga mansub bo`lgan algoritmlar ichida eng samaraliroklaridan biri bu LZSS algoritmi xisoblanadi. Ushbu algoritm 1982 yilda Storer va Jimanskilar tomonidan LZ77 algoritmini modifikatsiyalash natijasida paydo buldi. Ushbu algoritm vositasida axboroni kodlashtirilsa siqish koeffitsientining kiymati bir necha marta katta. Ushbu algoritmi vositasi axborotni kodlashtirshga misol kurib chiqamiz. Misol 1. Axborot sifatida quyidagi belgilar ketma ketligini olamiz: АВААDDDDDBAABAACCCCEAFFFFDAAAA
f – bayroqcha;
i – takrorlangan iboraning uzunligi;
j - takrorlangan iboraning nechi qadam oldin qaytarilganligi;
s – ochiq xolatda uzatilgan belgi.
Nchiq = 14*(1+8)+7*(1+3+5) = 189 (bit)
Nkir = 30*8=240 bita. Axborot xajmini kamaytirish natijasida olingan yutuk 240-189= 51 bit ga teng.
Mustakil ishlash uchun topshiriqlar
Variant
|
xabarlar
|
1
|
BBCCCCDEEEEFFFFGGGGFFFFFFDD
|
2
|
DFABBBEECEDDEFFFAEBBCBBBBBBC
|
3
|
CCCCCCCCCCCBBBBBAAAADDDDEEEF
|
4
|
BCDEEFAACCADEEDDDEDBAAEEEDDD
|
5
|
AAAAAAAABBAAAABBBCCCCCDDDDDEEE
|
6
|
CEDDBCEFABBBFDDFAEBAADDDEEAAA
|
7
|
BBCBBDBBDEEFDABBDABBBBACACCEG
|
8
|
DDFEBBCAADAEFFBEGHAABFFBD
|
9
|
BBCBBBCDDEDAAADDFFGGHHEE
|
10
|
DDECBFFEEEAAADBBBEEEAAAAABBB
|
11
|
CAADDDAEDADDEAAEBEFBEDEFEEA
|
12
|
FFFBBCDEEAAFDFFGBBGFADAABFFFF
|
13
|
CEEFFDDDEBBAAAEDEDAECBAADDD
|
14
|
EEEEBBBEEEEBBCCCCDDDDFFFFAEEEE
|
15
|
GBDBBBADDABADAAAFFFEEEEBBBEE
|
16
|
BBBAAAEDDAAABBFEFFDDEEGAAAAA
|
17
|
FFFBBCDEEAAFDFFGBBGFADAAA
|
18
|
GFFFFBBBBAAAACCFFFFFCCDDE
|
19
|
ABBCEHABCAEGAAAAAADADDDD
|
20
|
AAAAAAABBCCDDEEFFGGHHHAAAA
|
21
|
ABBBCEDDEFFFAEBBCCCCADAAABB
|
22
|
DDDDDDDDAAABBBCCCDDDEEEFFF
|
№ 5 laboratoriya ishi
SIKLIK KODLARNI (СRC) KODLASH VA DEKODLASH JARAYONINI MODELLASHTIRISH VA NATIJALARINI TAHLIL QILISH.
ISHDAN MAQSAD
Ushbu laboratoriya ishi quyidagilarni o’rganishga mo’ljallangan:
Ma’lumot uzatish tizim va tarmoqlarida mavjud kodlash usullari bilan tanishish;
Mavjud kodlash usullarini shovqinbardoshliligini taqqoslash va tahlil qilish.
Do'stlaringiz bilan baham: |
