Ishdan maqsad

Misol 2: Kuyidagi kurinishda axborot berilgan: BBCBBBCDDEDAAADDFFGGHHEE.

Ushbu algoritm buyicha xisoblash natijalari jadval 3.2 keltirilgan.

Xaffmen algoritmi buyicha 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

belgilar	B	D	A	E	C	F	G	H
kodi	01	00	100	101	1101	1100	1111	1110

Kodli kombinatsiyaning urtacha uzunligini xisoblaymiz:

n _urt = ∑ n _i * R(x) = 2,92 bitga 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

№ 4 Laborotoriya ishi

MA’LUMOTLARNI SIQISH ALGORITMLARI (LEMPEL – ZIV, LZSS ALGORITMLARI) NI TADQIQ QILISH

Ishdan maqsad:

1. 
   Axborotni siqib beruvchi Lempel - Ziva algoritmlari bilan tanishib chikish;
   
2. 
   Axborotni yukotishsiz siqib beruvchi LZSS algoritmi yordamida axborotni xajmini kamaytirish buyicha amaliy kunikmalarga ega bo‘lish.
   

Nazariy ma’lumot
Lempel – Ziva algoritmlarini iboralar buyicha 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 bulgan 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 bulgan 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 sikish koeffitsientining kiymati bir necha marta katta. Ushbu algoritmi vositasi axborotni kodlashtirshga misol kurib chiqamiz.

Misol 1. Axborot sifatida quyidagi belgilar ketma ketligini olamiz: АВААDDDDDBAACCCCEAFFFFDAAAA
f – bayroqcha;

i – takrorlangan iboraning uzunligi;

j - takrorlangan iboraning nechi qadam oldin qaytarilganligi;

s – ochiq xolatda uzatilgan belgi.

N_chiq = 14*(1+8)+7*(1+3+5) = 189 (bit)

N_kir = 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 (SRC) KODLASH VA DEKODLASH JARAYONINI MODELLASHTIRISH VA NATIJALARINI TAHLIL QILISH.

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

2. 
   QISQACHA NAZARIY MA’LUMOT
   

Shovqinbardosh kodlar taqsimlangan va taqsimlanmagan kodlarga bo‘linadi. Agar kodli kombinatsiyalarda kombinatsiyadagi razryadlar soni bir xil bo‘lsa, bunday kodlar teng taqsimlangan kodlar deyiladi.

Agarda kodli kombinatsiyalardagi razryadlar soni xar xil bo‘lsa, bunday kodlar teng taqsimlanmagan kodlar deyiladi.

Teng taqsimlangan kodlar ikki turga bo‘linadi: blokli; uzluksiz.

Blokli kodlar uzatilayotgan axborotli ketma-ketlik alohida kodli kombinatsiyalarga bo‘linadi va ular bir-biriga bog‘liq bo‘lmagan holda kodlanadi va dekoderlanadi.

Bu holat uzatilayotgan xabarga n ta elementlardan tashkil topgan blok yoki har xil elementlardan iborat bo‘lgan blok mos keladi. Uzluksiz kodlar esa axborotli razryadlarning uzluksiz ketma-ketligidan iborat va ularni bo‘laklarga bo‘lib bo‘lmaydi. Bunday kodlarda informatsion razryadlar orasiga ortiqcha razryadlar ma’lum tartibda joylashtiriladi.

Siklik kodlar sistematik kodlarning bir ko‘rinishi hisoblanadi va uning barcha xususiyatlariga ega. Ular kodlash va dekodlash sxemalarini osonlashtirish maqsadida yaratilgan. Keyinchalik uning amalda keng tarqalishini ta’minlovchi yuqori korrektlash xususiyatlari aniqlandi.

Siklik kodlar qurilishida kodli kombinatsiyalarni polinom ko‘rinishida tasavvur qilish qabul qilingan. Tasodifiy miqdor tizimida har qanday son polinom kod kombinatsiyasi sifatida yozilgan bo‘lishi mumkin:

G(x)=a_n-1x^n-1+ a_n-2x^n-2 +…+ a₁x^{1 +} a₀x⁰ , (6.1)
bu yerda, a_i=(0.1); x – sanoq sistemasi asosi

3. 
   TOPSHIRIQ
   

Ushbu laboratoriya mashg’ulot ishida 6.1 va 6.2-rasmda keltirilgan sxemalarni mos variantlar bilan shovqinbardosh kodli va shovqinbardosh kodsiz keltirilgan sxemalarni yig’ish zarur. Bu yerda koder va dekoder elementlari o’rniga mos ravishda siklik kodini koder va dekoderlari qo’yiladi.

6.1-rasm. Siklik kodisiz tuzilgan ma’lumot uzatish tizimi modeli

6.2-rasm. Siklik kodi bilan tuzilgan ma’lumot uzatish tizimi modeli
Modelni tuzishda 6.1 va 6.2-rasmlarda keltirilgan sxemadagi ikkilik simmetrik kanalda xatolarni paydo bo’lish ehtimolligi qiymatlarini (Error Probability) 0.01 dan 0.20 gacha 0.01 qadam bilan o’zgartirish talab etiladi.

Kanalda Chiziqli blokli kodini qo’llagan va qo’llanmagan sxema bo’yicha modellashtirish natijalarini grafigida xatolik koeffitsientini xatolarni paydo bo’lish ehtimolligi qiymatlariga bog’lagan holda bitta grafikda ifodalang.

Hisobotni tarkibida mavjud bo’lishi zarur bo’lgan elementlar:

• 
  laboratoriya ishini raqami va nomi;
  
• 
  mos variant bilan bajarilgan topshiriq;
  
• 
  MatLAB dasturida yaratilgan modelni ko’rinish;
  
• 
  Siklik kodini qo’llagan va qo’llanmagan sxema bo’yicha modellashtirish natijalari;
  
• 
  Olingan natijalar bo’yicha xulosalar.
  

4. 
   TOPSHIRIQNI BAJARISHGA KO’RSATMALAR
   

Ushbu ishni bajarishda quyida ko’rsatilgan bloklardan foydalanish zarur:

• 
  tasodifiy sonlar generatori - Communication Blockset bloklar kutubxonasidagi Comm Sources → Random Data Sources bloklar guruhidan «Random Integer Generator» bloki;
  
• 
  sonlarni bitlarga o’zgartiruvchi - Communication Blockset bloklar kutubxonasidagi Utility Blocks bloklar guruhidan «Integer To Bit Converter» bloki;
  
• 
  bitlarni sonlarga o’zgartiruvchi - Communication Blockset bloklar kutubxonasidagi Utility Blocks bloklar guruhidan «Bit To Integer Converter» bloki;
  
• 
  Siklik koder - Communication Blockset bloklar kutubxonasidagi Error Detection and Correction → Block guruhidan «Binary Cyclic Encoder» bloki;
  
• 
  Siklik dekoderi - Communication Blockset bloklar kutubxonasidagi Error Detection and Correction → Block guruhidan «Binary Cyclic Decoder» bloki;
  
• 
  ikkilik simmetrik kanal - Communication Blockset bloklar kutubxonasidagi Channels guruhidan «Binary Symmetric Channel» bloki;
  
• 
  xatolarni hisoblovchi - Communication Blockset bloklar kutubxonasidagi Comm Sinks guruhidan «Error Rate Calculation» bloki;
  
• 
  displey – Simulink bloklar kutubxonasidagi Sinks guruhidan «Display» bloki.
  

Tasodifiy sonlar generatori [0; 15] intervalidagi butun sonlarni hosil qilishi lozim, buning uchun «Random Integer Generator» blokini «M-ary number» parametrini 16 ga sozlash talab etiladi.

Kodlash uchun [0; 15] intervaldagi sonlarni 4 bitdan qilib ifodalash lozim, buning uchun «Integer To Bit Converter» va «Bit To Integer Converter» bloklaridagi «Number of bits per integer» parametrini 4 ga sozlash talab etiladi.

Xatolar sonini bilish uchun «Error Rate Calculation» blokidagi «Output data» parametriga Port ga sozlash talab etiladi.

« Binary Cyclic Encoder» va « Binary Cyclic Decoder» bloklaridagi Codeword length» va «Message length» parametrlari mos holda belgilanadi.

Modellashtirish vaqtini 100000 ga sozlash talab etiladi.

5. 
   NAZORAT SAVOLLARI
   

1. 
   Ishonchlilikni oshirish usullari?
   
2. 
   Ishonchlilikni oshirish usullariga qo‘yiladigan talablar?
   
3. 
   Shennonning asosiy teoremasi?
   
4. 
   Siklik kodlar qurish prinsipi qanday?
   
5. 
   Siklik kodning kodli kombinatsiyasini nechta usul yordamida olish mumkin, misol keltiring?
   
6. 
   Shovqinbardosh siklik kodlar yordamida axborotni kodlash va dekodlash tartibi?
   
7. 
   Shovqinbardosh kodlarga qo‘yiladigan asosiy va qo‘shimcha talablar nimalardan iborat?
   

№ 6 laboratoriya ishi

XEMMING KODINI KODLASH VA DEKODLASH JARAYONINI MODELLASHTIRISH VA NATIJALARINI TAHLIL QILISH

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

2. 
   QISQACHA NAZARIY MA’LUMOT
   

Kod deb – istalgan ko‘rinishdagi axborotni masofadan turib uzatish uchun qulay shaklda ifodalashga mo‘ljallangan shartli belgilar (simvollar) yoki signallar tizimiga aytiladi. Bu belgilar yoki signallar to‘plamiga kod alfaviti deyiladi. Koddagi elementlar yoki belgilar soni har doim chegaralangan bo‘ladi. Bu elementlardan kodli kombinatsiyalar tuziladi.

Shovqinli kanalda kodlash haqida Shennonning asosiy teoremasi:

• 
  Har qanday xabar manbaining mahsuldorligi kanalni o‘tkazish qobiliyatidan kichik, shunga ko‘ra hosil qilingan xabar manbai barcha axborotni yetarlicha kichik xatolik ehtimollik bilan uzatishga imkon beruvchi kodlash usuli mavjud bo‘ladi.
  
• 
  Agar xabar manbaining mahsuldorligi kanalni o‘tkazish qobiliyatidan katta bo‘lsa, u holda axborotni yetarlicha kichik xatolik ehtimollik bilan uzatishga imkon beruvchi kodlash usuli mavjud emas.
  

Axborot qismini uzunligi k kod asosi va xabar alfaviti hajmi orqali aniqlanadi. Tekshiruvchi qismini uzunligi r kerak bo‘ladigan to‘g‘rilash qobiliyati bilan aniqlanadi.

Kod uzunligi n=k+r.

Shovqinbardosh kod deb – xato qabul qilingan razryadlarni aniqlaydigan va to‘g‘rilaydigan kodga aytiladi.

Bunday kodlar quyidagi prinsipga asoslanib tuziladi: n razryadli kodli kombinatsiyalar soni N ta bo‘lsin.

Lekin axborot uzatish uchun esa faqatgina ulardan N_r tasi ishtirok etadi va ular ruxsat etilgan kombinatsiyalar deyiladi.

N – N_r tasi esa man qilingan kodli kombinatsiyalar deyiladi.

Agar kodli kombinatsiyalarda kombinatsiyadagi razryadlar soni bir xil bo‘lsa, bunday kodlar teng taqsimlangan kodlar deyiladi.

Agarda kodli kombinatsiyalardagi razryadlar soni har xil bo‘lsa, bunday kodlar teng taqsimlanmagan kodlar deyiladi.

Teng taqsimlangan kodlar ikki turga bo‘linadi: blokli va uzluksiz.

Blokli kodlar uzatilayotgan axborotli ketma-ketlik alohida kodli kombinatsiyalarga bo‘linadi va ular bir-biriga bog‘liq bo‘lmagan holda kodlanadi va dekoderlanadi.

Bu xolat uzatilayotgan xabarga n ta elementlardan tashkil topgan blok yoki har xil elementlardan iborat bo‘lgan blok mos keladi.

Uzluksiz kodlar esa axborotli razryadlarning uzluksiz ketma-ketligidan iborat va ularni bo‘laklarga bo‘lib bo‘lmaydi. Bunday kodlarda informatsion razryadlar orasiga ortiqcha razryadlar ma’lum tartibda joylashtiriladi.

3. 
   TOPSHIRIQ
   

Ushbu laboratoriya mashg’ulot ishida 6.1 va 6.2-rasmda keltirilgan sxemalarni mos variantlar bilan shovqinbardosh kodli va shovqinbardosh kodsiz keltirilgan sxemalarni yig’ish zarur.

4.1-rasm. Xemming kodisiz tuzilgan ma’lumot uzatish tizimi modeli

6.2-rasm. Xemming kodi bilan tuzilgan ma’lumot uzatish tizimi modeli

Modelni tuzishda 6.1 va 6.2-rasmlarda keltirilgan sxemadagi ikkilik simmetrik kanalda xatolarni paydo bo’lish ehtimolligi qiymatlarini (Error Probability) 0.01 dan 0.20 gacha 0.01 qadam bilan o’zgartirish talab etiladi.

Kanalda Xemming kodini qo’llagan va qo’llanmagan sxema bo’yicha modellashtirish natijalarini grafigida xatolik koeffitsientini xatolarni paydo bo’lish ehtimolligi qiymatlariga bog’lagan holda bitta grafikda ifodalang.

Hisobotni tarkibida mavjud bo’lishi zarur bo’lgan elementlar:

• 
  laboratoriya ishini raqami va nomi;
  
• 
  mos variant bilan bajarilgan topshiriq;
  
• 
  MatLAB dasturida yaratilgan modelni ko’rinish;
  
• 
  Xemming kodini qo’llagan va qo’llanmagan sxema bo’yicha modellashtirish natijalari;
  
• 
  Olingan natijalar bo’yicha xulosalar.
  

4. 
   TOPSHIRIQNI BAJARISHGA KO’RSATMALAR
   

Ushbu ishni bajarishda quyida ko’rsatilgan bloklardan foydalanish zarur:

• 
  tasodifiy sonlar generatori - Communication Blockset bloklar kutubxonasidagi Comm Sources → Random Data Sources bloklar guruhidan «Random Integer Generator» bloki;
  
• 
  sonlarni bitlarga o’zgartiruvchi - Communication Blockset bloklar kutubxonasidagi Utility Blocks bloklar guruhidan «Integer To Bit Converter» bloki;
  
• 
  bitlarni sonlarga o’zgartiruvchi - Communication Blockset bloklar kutubxonasidagi Utility Blocks bloklar guruhidan «Bit To Integer Converter» bloki;
  
• 
  Xemming koderi - Communication Blockset bloklar kutubxonasidagi Error Detection and Correction → Block guruhidan «Hamming Encoder» bloki;
  
• 
  Xemming dekoderi - Communication Blockset bloklar kutubxonasidagi Error Detection and Correction → Block guruhidan «Hamming Decoder» bloki;
  
• 
  ikkilik simmetrik kanal - Communication Blockset bloklar kutubxonasidagi Channels guruhidan «Binary Symmetric Channel» bloki;
  
• 
  xatolarni hisoblovchi - Communication Blockset bloklar kutubxonasidagi Comm Sinks guruhidan «Error Rate Calculation» bloki;
  
• 
  displey – Simulink bloklar kutubxonasidagi Sinks guruhidan «Display» bloki.
  

Tasodifiy sonlar generatori [0; 15] intervalidagi butun sonlarni hosil qilishi lozim, buning uchun «Random Integer Generator» blokini «M-ary number» parametrini 16 ga sozlash talab etiladi.

Kodlash uchun [0; 15] intervaldagi sonlarni 4 bitdan qilib ifodalash lozim, buning uchun «Integer To Bit Converter» va «Bit To Integer Converter» bloklaridagi «Number of bits per integer» parametrini 4 ga sozlash talab etiladi.

Xatolar sonini bilish uchun «Error Rate Calculation» blokidagi «Output data» parametriga Port ga sozlash talab etiladi.

«Hamming Encoder» va «Hamming Decoder» bloklaridagi Codeword length» va «Message length» parametrlari mos holda belgilanadi.

Modellashtirish vaqtini 100000 ga sozlash talab etiladi.

5. 
   NAZORAT SAVOLLARI
   

1. 
   Ishonchlilikni oshirish usullari?
   
2. 
   Ishonchlilikni oshirish usullariga qo‘yiladigan talablar?
   
3. 
   Shennonning asosiy teoremasi?
   
4. 
   Shovqinbardosh kod nima va vazifasi?
   
5. 
   Shovqinbardosh kodlardan amaliy foydalanish vazifalari
   
6. 
   Siklik kodlar qurish prinsipi qanday?
   
7. 
   Siklik kodning kodli kombinatsiyasini nechta usul yordamida olish mumkin, misol keltiring?
   
8. 
   Xemming kodiga tushuncha bering?
   
9. 
   Kodli kombinatsiyada xatolikni aniqlash?