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

Ma’lumotni siqish algoritmlarining xarakteristikalari va ularning qo‘llanilishi

• Ma’lumotni siqish algoritmlarining xarakteristikalari va ularning qo‘llanilishi
•  Siqish algoritmining asosiy xarakteristikasi – siqish koeffisienti hisoblanadi va u birlamchi siqilmagan ma’lumot hajmini ma’lum bir algoritm bo‘yicha siqilgan ma’lumot hajmiga nisbati bilan aniqlanadi, ya’ni
•  
• bunda k — siqish koeffisienti, 
• So — birlamchi ma’lumot hajmi,
• Sc — siqilgan ma’lumot hajmi.
• Siqish koeffisienti qancha katta bo‘lsa, shuncha siqish algoritmi samarali bo‘ladi. Agar k = 1 bo‘lsa algoritm birlamchi ma’lumot ustidan hech qanday siqish jarayonini amalga oshirmagan bo‘ladi. Amaliyotda k < 1 holat ham bo‘lishi mumkin, bunda algoritm ma’lumotni siqish o‘rniga uning hajmini kengaytirib yuboradi.
• Siqish koeffisienti o‘zgarmas va o‘zgaruvchan bo‘lishi mumkin. Ikkinchi holatda har bir holat uchun u alohida hisoblanadi yoki ma’lum bir mezon orqali aniqlanadi:
• Ma’lumotni siqish darajasi o‘rtacha (ma’lum bir test ma’lumotlari orqali aniqlanadi);
• Ma’lumotni siqish darajasi maksimal (eng yaxshi natija);
• Ma’lumotni siqish darajasi minimal (eng yomon holat)
• Yo‘qotishli siqish algoritmlarida K ning qiymati yo‘l qo‘yilishi mumkin bo‘lgan xato darajasiga bog‘liq bo‘ladi, shu orqali uning sifati belgilanadi.
• Modemlarda axborotlarni siqish protokollari

Siqishning lug‘atli usullari

• 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

• Matnli axborotlarni kodlashga tushuncha bering?
• Tasvirli axborotlarni kodlashga tushuncha bering?
• Yo‘qotishli siqish usuliga tushuncha bering?
• Yo‘qotishsiz siqish usuliga tushuncha bering?
• Ma’lumotni siqish algoritmlarining xarakteristikalari va ularning qo‘llanilishiga tushuncha bering?
• Zamonaviy modemlardagi siqish protokollariga tushuncha bering?
• Siqishning lug‘atli, Lempel-Ziv va LZ77 usullariga tavsif bering?