Арифметикалық кодтау

Арифметикалық кодтауда нормалданған бөлінуде дереккөз символдарының (және оларға сәйкес шамаланған жиіліктерінің) ықтималдықтарының сомасы әрдайым бірге тең деген факттан бастаймыз. Егер символдардың шамаланған жиіліктері тасымалдағышқа және қабылдағышқа белгісіз болса:

6.1 Кесте. Әріптер және олардың шамаланған жиіліктері.

- олар мән берілген уақытта тасымалданып жатқан ақпараттың статистикалық өзгерістері арқылы анықтала алады;

- қабылдағыш және тасымалдағыш шамаланған жиіліктерден біргелесіп кодтаудың қатаң қағидаларын орнатады.

Арифметикалық кодтаудың ерекшелігі [0, 1] интервалындағы натурал сандар ағынындағы символдар реттілігін көрсету үшін шамаланған жиіліктер қолданылатыны болып табылады.

Мұндай көрсетудің нәтижесі болып символдарды олардың ықтимал-дықтарына сәйкес қысу болып табылады. Арифметикалық кодтау идеясын келесі мысал арқылы айқындаймыз.

«GELEEESSER» реттілі әріптерінің арифметикалық кодтауын қарастырамыз. Бұл ағындағы әріптердің шамаланған жиіліктері 6.1 кестеде көрсетілген.

Кодтау процедурасы 6.2 суретте көрсетілген.

Бірінші «G» әріпіне, оның шамаланған жиілігіне сәйкес, [0.7, 0.8] интервалы дәл келеді. Алгоритмге сәйкес, G- дан басталатын әрбір әріптер тізбегі осы интервалға меншікті сан түрінде көрсетілетін болады. Осылайша, қарастырылып отырған мысалда үтірден кейінгі бірінші ондық сан анықталды.

Келесі әріптерді кодтау енді алдыңғы қадамда таңдалған интервал бөлінуге кезігетін ерекшелікпен жүзеге асатын болады. 6.2 сурет бойынша, екінші қадамда «Е» әріпіне [0.7, 0.75] интервалы сәйкес келеді.

Кодтау алгоритмі қадам бойынша жүрген 6.3 кестеде «GELEEESSER» реттілігі 740387 саны түрінде көрсетіледі. Ескере өтетін жайттар:

1. Жиі кездесетін әріптерге сәйкестікке үлкен интервалдар қойылады. Оларды көрсетуге сирек кездесетін әріптерге қарағанда азырақ ондық сан жұмалады.

2. Ұзын хабарламалар «ұзын» сандар түрінде көрсетіледі. Бұл сандарды хабарламалар тасымалына қажетті екілік формада көрсету үлкен ұзындықты кодты сөздердің пайда болуына алып келеді.

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

 

 

6.2 Сурет. Арифметикалық кодтау.

Алгоритм 6.2 кестеде көрсетілген. Оның жұмыс істеу механизмі 6.3 кесте арқылы ашылады. Біздің мысалда кодтауды орындау үшін алты ондық санды сақтауға арналған регистр жетерлі.

6.2 кестеге сәйкес, бірінші қадамда LO және HI айнымалыларының іске кірісуы болады. Бірінші кодталатын «G» әріпі үшін интервал кеңдігі тең. Төменгі және жоғарғы шектер сәйкес және тең болады. Бірінші ондық сан анықталып қойған және 7-ге тең, ал LO және HI регистрлерінің құрамы солға бір позиция жылжиды. LO регистрінде бос орынды 0 алады, HI регистрінде – 9 болатынына назар салайық.

 

6.2 Кесте. Арифметикалық кодтаудың алгоритмі.

Екінші «Е» әріпі үшін интервал кеңдігі тең, сондықтан және аламыз. Келесі әріптерді кодтау ұқсас әдіспен орындалады. Алгоритм жұмысын тәмәмдау уақтысында соңғы интервалдан қандай-да бір сан беріледі. Сол үшін біз кіші разрядтарды мүмкін болғанша лақтырып интервалының жоғарғы шегін дөңгелетеміз. Нәтижесінде соңғы интервалға меншікті минималды цифр көлемді сан аламыз.

Лемпель - Зив кодтауы.

Лемпель – Зивтің LZ77 кодтау алгоритмі динамикалық сөздіктер ұстанымдарында негізделген. Біз бұл концепцияны қысқаша айтып өтеміз және кәдімгі мысалдарда айқындаймыз.

Агоритм негізінде 4 негізгі идея жатыр:

1. Әрбір келесі кодталған символдар реттілігі алдын кодталған символдарға онымен бірге барлық тасымалданған және қабылданған ақпараттарды өзара келіспейтін сөздерге бөлетін амалмен қосылады.

2. Мұндай бөліну жадта сақталады және алдағыда сөздік ретінде қолданылады.

3. Кодтау қалыптасқан фразалар сөздігінен фразаларға көрсеткіштер арқылы орындалады.

 

6.3 Кесте. «GELEEESSER» фразасын арифметикалық кодтау.

4. Кодтау блоктарға ориентирленген динамикалық процедура болып табылады. Кодтау процессінің өзі фразалар сөздігін және Look-ahead буферін қамтамасыз ететін жылжымалы терезелермен толықталуы мүмкін.

6.3 Сурет. FACH фразасына сәйкес келетін LZ77 алгоритмінің

жылжымалы терезесі.

Кодтау процессінде өндіріліп жатқан мәтін көрсеткіштер немесе байрақтар реттілігінде көрсетіледі. Кодталған мәтіннің құрамы 6.4 суретте көрсетілген. 6.3 суретте көрсетілген мысалдағы FACH әріптер тізбегі [21,4, B ] реттілігімен алмасады.

6.4 Сурет. Көрсеткіштер құрамы.

 

6.5 Сурет. LZ77 алгоритмі бойынша нөлдік фразалармен және

символдарды қайталаумен кодтау мысалы.

6.5 суретте қандай-да бір бөлек жағдай және оның алгоритмдық шешімі көрсетілген. Кодтаудың алтыншы қадамында кездесетін фразалар сөздігінде жоқ «Е» символы болып табылады. Бұл жағдайда ол «нөлдік фраза» арқылы кодталады. «Нөлдік фраза» [0, 0, символ] түрінде болады және декодтау уақтысында жанындағы екі нөл арқылы танылады.

Тағы бір қызық жағдай Character Rans деп аталатын символдардың қайталануы болып табылады. Бұл жағдайда символды алмастыру үшін екі байрақ қолданылады. Бірінші «0» мәтіннің ерекшелігінің нышаны болып табылады. Келесі «1» және символ символдың қайталанатынын білдіреді.

Екінші байрақта қайталанулар саны және келесі символ көрсетіледі.

Кодтауға жұмсалатын шығын фразалар сөздігінен, буферінің Look ahead ұзындығынан және көрсеткіштің екілік көрсетуіне жұмсалатын шығыннан тұратын терезенің ұзындығы арқылы анықталады

Лемпель – Зив кодтауы кодтауға жұмсалатын шығындар, яғни екілік есептегі көрсеткіш ұзындығы орташа мәнде тікелей көшіруге қарағанда, мысалы бір символға 8 бит сәйкес келетін ASCII кодымен көшрігенде кіші болып табылған жағдайда, мағлұматтарды қысуға алып келеді.

Кәдімгі жағдайда және және көрсеткіштің екілік көрсетілуіне жұмсалған шығындар 24 биттң құрайды. Фразалар сөздігінде бар төрт әріптен тұратын фраза үшін, экономия, ASCI (32 бит) кодымен тікелей кодтағанға қарағанда, 25 % құрайды.

Лемпель – Зив кодтауы үшін:

● Жиі пайда болатын символдар тізбегі өте нәтижелі кодталады;

● Сирек пайда болатын символдар және символдар реттіліктері уақыт өте фразалар сөздігінен жойылып кетеді;

● Қайталанатын символдар нәтижелі кодталады;

● Нөлдік фразаларды кодтау үшін шамамен көп көлемдегі бит шығындалады;

● Ақпараттар теориясының әдістері Лемпель – Зив әдісімен кодтау асимптотикалық түрде оптималды болып табылатынын дәлелдеуге мүмкіндік береді. Бұл дегеніміз өте ұзын мәтін үшін шығын жойылады, яғни бір символды кодтауға қажетті биттердің орташа саны мәтіннің энтропиясына ұмтылады;

● Ұзын мәтіндер үшін практикалық түрде жетімді қысу дәрежесі 50 – 60 % құрайды.

 

БӨЛІМ

ЖАДСЫЗ ДИСКРЕТТІ