4-ma’ruza. Yo‘qotishli va yo‘qotishsiz siqish usullari

Modemlarda axborotlarni siqish protokollari


Siqishning lug‘atli usullari

Siqishning lug‘atli usullari kiritish belgilar ketma-ketligini tasodifiy raqamni o‘z ichiga olgan qatorlar ketma-ketligi kabi ko‘rishga asoslangan. Bu belgilar qatorini qaysidir lug‘atdagi qator indeksiga mos keluvchi kodlar bilan almashtirish mumkin. Lug‘at tashkil etuvchi qatorlarni iboralar deb ataymiz. Qayta tiklash indeks lug‘atdagi mos ibora bilan almashinuvi orqali amalga oshiriladi.

Bu holda, lug‘at shunday qayta ishlanadigan xabarda uchrashi mumkin bo‘lgan ibora majmualaridan iborat bo‘ladi. Lug‘atning ibora indekslari shunday tuzilishi kerakki, undagi belgilar o‘rtacha soni lug‘atning iboralaridagi belgilar sonidan kamroq bo‘lishi lozim. Aynan shu original xabarni siqishni amalga oshiradi.


Lempel-Ziv siqish algoritmlari

Klassik Lempel-Ziv algoritmlari lug‘atli siqishning universal algoritmidir, qaysiki original xabar qayta ishlanib bo‘lgan kirish oqimidagi belgilar qismi asosida tashkil topgan lug‘at bo‘lsa, ya’ni ushbu algoritmlar adaptivdir. Ushbu algoritmlarning farqi faqatgina lug‘at iboralarining shakllanish usullaridagina mavjud.

Algoritm LZ77

Algoritm LZ77 sirg‘aluvchi lug‘atga (sirg‘aluvchi oyna) ega birinchi algoritm hisoblanadi. Ushbu algoritmda lug‘at sifatida kodlab bo‘lingan ketma-ketlik blokidan foydalaniladi. Qayta ishlashni amalga oshirish meyorida ushbu blokning joylashishiga nisbatan ketma-ketlik boshlanishi o‘zgaradi.

Sirg‘aluvchi oyna N uzunlikdagi belgilardan va 2 qismdan iborat :
- lug‘at hisoblanovchi W = N-n uzunlikdagi kodlangan belgilar ketma-ketlik;
- n uzunlikdagi tasdiqlaydigan bufer.


Nazorat savollari

1. 
   Matnli axborotlarni kodlashga tushuncha bering?
   
2. 
   Tasvirli axborotlarni kodlashga tushuncha bering?
   
3. 
   Yo‘qotishli siqish usuliga tushuncha bering?
   
4. 
   Yo‘qotishsiz siqish usuliga tushuncha bering?
   

5. Ma’lumotni siqish algoritmlarining xarakteristikalari va ularning qo‘llanilishiga tushuncha bering?
6. Zamonaviy modemlardagi siqish protokollariga tushuncha bering?
7. Siqishning lug‘atli, Lempel-Ziv va LZ77 usullariga tavsif bering?