Лекция 9 Модуляция және демодуляция процедураларының мазмұны мен ролі

Шеннон-Фэно әдісі, Хаффман және арифметикалық кодтауларды жалпы түрде статистикалық әдістер деп атайды.Сөздікті алгоритмдердің математикалық жағынан маңызы аз болғанымен, олар практикада кеңінен қолданылады.

LZ77 алгоритмы 1977 жылы жарияланды. Бұл әдісті израилдық математиктер Якиб Зив(Ziv) пен Авраам Лемпел(Lempel) енгізді. Ақпаратты сығудың көптеген программалары LZ77 модификациясын қолданылады. Бұл алгоритмның ерекшелігі - оның қарапайымдылығы және тиімділігі болып табылады.

LZ77 негізігі идеясы – жіберілген хаттың соңғы жолындағы символдар алдындағы жолдың сілтемелерімен алмастырылады.

LZ77 әдісі хаббардың қарастырылған бөлімін сөздік ретінде қарастырады. Ақпаратты сығу үшін ағымдағы хабардың бөлігін сөздік мазмұнының сілтемесіне алмастыруға тырысады.

LZ77 хабардың екі тең емес бөлікке бөлінген жылжымалы терезелерінде қолданылады. Көлемі бойынша үлкен бірінші терезе хабардың қарастырылған бөлігін қамтиды. Ал екінші терезе кодталмаған символдардан тұратын буфер болып табылады.

Әдетте терезе бірнеше килобайттан тұрса, ал буфердің көлемі жүз байттан аспайды. Алгоритм сөздіктен(бірінші терезеден) буфердің мазмұнымен сәйкес келетін бөлікті іздейді.

LZ77 алгоритмы үш элементтен тұратын кодты қарастырады:

• 
  буфердің алғашқы жолының сөздіктегі бастапқы жолға қатысты қысқаруы;
  
• 
  осы жодың ұзындығы;
  
• 
  осы жолдан кейінгі буфердің алғашқы символы;
  

LZ77 кодын декодтау оларды алудан әлдеқайда жеңіл болып табылады, себебі, сөздікте іздеу жүргізілмейді.

LZ77 кемшіліктері:

1. 
   сөздік көлемі неғұрлым үлкен болған сайын алгоритм-кодер жұмысының жылдамдығы соғұрлым пропорционалды түрде төмендейді .
   
2. 
   жалғыз символдарды кодтау тиімсіз болып табылады.
   

Соңғы жолдағы «А» әріпі соңғы символ болғандықтан ол сөздіктен алынбайды.

Кодтың ұзындығы келесі әдіспен есептеледі: жолдың ұзындығы буфер көлемінен аса алмайды, ал ығысу сөздік-1 көлемінен үлкен болмайды. Сондықтан ығысудың екілік кодының ұзындығы log₂ бойынша (сөздік көлеміне байланысты) дөңгелектеледі,ал жол ұзындығы үшін екілік кодтың ұзындығы log₂ бойынша (буфер көлемі+1) дөңгелектеледі. Ал символ 8 битпен (мысалға, ASCII+ ) кодталады.

Соңғы мысалда ізделінді кодтың ұзындығы 9*(3+3+8)=126 бит.

1982 жылы Сторер(Storer) мен Шимански(Szimanski) LZ77 негізінде LZSS алгоритмын құрастырды. Бұл алгоритм LZ77-ден кодтары арқылы ерекшеленді.

LZSS бірбиттік префикстен басталады, ол кодталмаған символдан ерекшелеу үшін қажет болып табылады. Код мынадай жұптан тұрады: ығысу және ұзындық.. LZSS-де терезе табылған жолдың ұзындығына немесе 1-ге жылжиды. LZSS-де жолдың ұзындығы 0-ден үлкен болады, сондықтан екілік кодтың ұзындығы жолдың ұзындығы үшін – жол ұзындығынан табылған дөңгелектелген екілік логарифм.

Мысал. LZSS алгоритмы бойынша «КРАСНАЯ КРАСКА» жолын кодтаңыз.

Сөздік(8)	Буфер(5)	Код	Кодтың ұзындығы
«. . . . . . . .»	«КРАСН»	0 «К»	9
«. . . . . . . К»	«РАСНА»	0 «Р»	9
«. . . . . . КР»	«АСНАЯ»	0 «А»	9
«. . . . . КРА»	«СНАЯ »	0 «С»	9
«. . . . КРАС»	«НАЯ К»	0 «Н»	9
«. . . КРАСН»	«АЯ КР»	1 <5,1>	7
«. . КРАСНА»	«Я КРА»	0 «Я»	9
«. КРАСНАЯ»	« КРАС»	0 « »	9
«КРАСНАЯ »	«КРАСК»	1 <0,4>	7
«НАЯ КРАС»	«КА . . .»	1 <4,1>	7
«АЯ КРАСК»	«А . . . .»	1 <0,1>	7

Мұндағы алынатын кодтың ұзындығы 7*9+4*7=91.

LZ77 пен LZSS төмендегідей кемшіліктері бар:

1. 
   егер екі жолдың ара-қашықтығы сөздіктің ұзындығынан үлкен болса, оларды кодтау мүмкін емес.
   
2. 
   кодталатын жолдың ұзындығы буфердің көлемімен шектеледі.
   

1978 жылы LZ77 авторлары LZ78 алгоритмын құрды, бұл алгоритмның жоғарыда аталған кемшіліктері болмады.

LZ78 «жылжымалы» терезелерді қолданбайды, оның сөздігі қарастырылып өткен жолдардан құралады. Алгоритм жұмыс жасағанда ол тек бір бос жолдан тұрады .А Алгоритм хабардың символдарын сөздікпен сәйкес келетін жол табылғанша жинайды да оларды қосады. Табылған жол сөздіктегі жолдан кем дегенде бір символға ерекшеленсе, алгоритм сөздіктегі жолдың индексінен тұратын кодты өңдейді. Егер сөздік толған болса, ондағы барлық салыстырмалы жолдар жойылады.

Сөздіктегі жолдардың көлемі негізгі код болып табылады, себебі LZ78 әдісі бойынша кодтағанда әрбір код сөздіктегі жолдың номерін қамтиды. Қорыта айтқанда, бұл кодтардың тұрақты ұзындығы екілік логарифмделген дөңгелектелген сөздік+8 көлеміне тең болады (ASCII кеңейтілуімен қолданылатын байт-кодтағы биттердің көлемі).

Мысал. 16 жолдан тұратын сөздікті қолдана отырып, LZ78 алгоритмы бойынша «КРАСНАЯ КРАСКА» жолын кодтаңыз.

Кодталатын жол	Код	Кодтың ұзындығы
« »		0
«К»	<0 ,«К»>	1
«Р»	<0 ,«Р»>	2
«А»	<0 ,«А»>	3
«С»	<0 ,«С»>	4
«Н»	<0 ,«Н»>	5
«АЯ»	<З ,«Я»>	6
« »	<0 ,« »>	7
«КР»	<1 ,«Р»>	8
«АС»	<З ,«С»>	9
«КА»	<1 ,«А»>	10

Мұндай сөздіктегі кез-келген жолдың сілтемесі – 0 ден 15 дейінгі сандар, оны кодтау үшін 4 бит жеткілікті.

Соңғы мысалдағы алынған кодтың ұзындығы 10*(4+8)=120 бит.

LZSS, LZ78 және LZ77 алгоритмдері математикдердің көмегімен құрылды және кең көлемде қолданылады.

1984 жылы Уэлч (Welch) LZ78 модификация жолымен LZW алгоритмын құрды.

Осы алгоритмның қадамдық сипаттамасы төмендегідей.

1-қадам. Барлық мүмкін болатын бірсимволдық жолдармен сөздікті инициализациялау (әдетте ASCII кеңейтілуімен қолданылатын 256 символ).

2-қадам. Кодталатын хабардан келесі К символды санау.

3-қадам. Егер ХАБАРДЫҢ_СОҢЫ болса

w үшін кодты анықтаңыз

Соңы

Егер сөздікте wК жолы бар болса

2-қадамға көшу

Әйтпесе

w кодын анықтау

wК сөздікке қосу

Кодталатын жолға К мәнін меншіктеу

2-қадамға көшу

LZ78 әдісіндегідей LZW алгоритмында алынатын кодтың көлемі үшін негізгі код жолдардағы сөздіктің көлемі болып табылады: LZW-коды сөздік көлемінің екілік логарифміне тең болатын тұрақты ұзындығына тең.

Мысал. LZW алгоритмы бойынша «КРАСНАЯ КРАСКА» жолын кодтаңыз.Сөздік көлемі – 500 жол.

Кодталатын жол, wК(сөздікте)	w үшін код	Сөздіктің орны
ASCII+		0-255
«КР»	0 «К»	256
«РА»	0 «Р»	257
«АС»	0 «А»	258
«СН»	0 «С»	259
«НА»	0 «Н»	260
«АЯ»	0 «А»	261
«Я »	0 «Я»	262
« К»	0 « »	263
«КРА»	<256>	264
«АСК»	<258>	265
«КА»	0 «К»	266
«А»	0 «А»

Бұл мысалда алынған кодтың ұзындығы 12*9=108 битке тең.

Сөздік толған жағдайда, яғни толған сөздікке жаңа жол енгізу үшін, одан не ең сирек қолданылатын, не бірлік символдан басқа барлық жолдар жойылады.

LZW интеллектуалды меншіктелген алгоритм болып табылады. Оның аппараттық деңгейдегі лицензиондалмаған қолданысы көптеген қиындықтарға әкеліп соқтырады.

LZW алгоритміне бір мезгілде екі фирма сұраныс берген – алдымен IBM, кейіннен Unisys, дегенмен алдымен Unisys сұранысы қарастырылды. Бірақ , LZW қолданысына дейін Unix әлемінде compress ақпаратты сығу программасы кеңінен қолданылды.