дәріс. Тривиалды (қарапайым) жүйелік кодтау. Топтық кодтар үшін кодтау мен кодты ашудың (декодирование) техникалық құралдары. Ашық кілтті шифрлар. Цифрлық қол қою
15 дәріс. Тривиалды (қарапайым) жүйелік кодтау. Топтық кодтар үшін кодтау мен кодты ашудың (декодирование) техникалық құралдары. Ашық кілтті шифрлар. Цифрлық қол қою. Тривиалды (қарапайым) жүйелік кодтау әдістердің негізгілері:
Хаффман алгоритмі;
RLE алгоритмі;
Хаффман алгоритмі Сығу дәрежесін жақсарту үшін жиі қайталанатын символдарды қысқа кодпен, ал сирек кездесетіндерді ұзын кодпен алмастыру керек. Бүл әдіс идеясын ұсынған - Д. Хаффман (1952 жыл).
Хаффман алгоритмінің көмегімен деректерді сығу кезінде кездесетін символдар жиілігі есептелінеді, содан кейін Хаффман кодтау ағашы тұрғызылады. Кодтау ағашы бойынша символдар коды жасалынады.
Хаффман ағашын тұрғызу алгоритмі:
Алғашқы символдар бос түйіндер тізімін құрайды. Әр түйіннің алғашқы хабарламадағы символдар санына тең салмағы бар.
Тізімнен ең кіші салмағы бар екі бос түйін таңдалады.
Олардың салмақтарының қосындысына тең салмағы бар «ата-ана» түйіні құрылады, ол «ұрпақтарымен» доға арқылы байланысады.
«Ата-анадан» шығатын бір доғаға 1, екіншісіне 0 қойылады.
«Ата-ана» бос түйінді тізімге қосылады, ал оның «ұрпақтары» тізімнен жойылады.
Тізімдегі қадам тек бір бос түйін қалғанша қайталана береді. Ол ағаштың басы (тамыры) болып есептелінеді.
Мысалы. «КОЛ_ОКОЛО_КОЛОКОЛА» мәтіні үшін Хаффман ағашын тұрғызу және префикстік кодты алу:
О
00
К
01
Л
10
Бос орын
110
А
111
Төбелерін қоссақ, шығатыны:
3+7+11+18=39
Мәтін коды 39/бит немесе 5 байт.
Сығу коэффициенті
18/5 = 3,6.
Сығылған деректерді қалпына келтіру үшін Хаффман ағашын қолданамыз.
Хаффман коды префиксті болып табылады, себебі әр символ коды басқа символдың кодының басы болып саналмайды.
