Кодтау: оңтайлы Хаффман коды

1. Дәріс 14-15:

«Кодтау:
оңтайлы Хаффман коды»
ст.преп., PhD
Сеитова Алия Амангалиевна

2. Код түсінігі

Шекті жиын таңбалары алфавит деп аталады.
А алфавитінің шекті тізбек таңбалары А
алфавитінің хабары деп аталады.
А алфавитінің барлық хабар жиынын А* арқылы
белгілейміз.

3.

Код түсінігі
К бейнелеуі: Алф1* —> Алф2*, тіркесімдері
бойынша, яғни К(с1с2...сN) = К(с1) К(с2)... К(сN)
теңдігін қанағаттандыратын Алф1* ішіндегі
с1с2...сN кез-келген хабары үшін код деп аталады.
К(с1с2...сN) мағынасы с1с2...сN хабар коды деп
аталады.
К : Алф1* —> {0,1}* коды екілік код деп аталады.

4. Кодтау және декодтау

Хабар кодын есептеу хабарды кодтау деп
аталады.
Кодтың әсерінен оның түпбейнесін есептеу
хабарды декодтау (дешифрлеу) деп аталады.
Егер К-1 кері функциясы болса, онда К коды
бірмәнді декодтау деп аталады.
Егер К-1 есептеуі көп уақыт мөлшерін қажет етсе,
онда ол кодтау туралы емес, шифрлеу туралы
айтады.

5. 1-Мысал

Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) = 01, К(с) = 10, К(d) = 1
К-1(01101010) = {addbba, bссс} – түпбейне
01101010
Берілген код бірмәнді декодтау болып табылмайды.

6. 2-Мысал

Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111
Берілген код бірмәнді декодтау болып табылады.

7. Кодтау ағашы

Т ағашының Алф2 ішіндегі қабырғалары таңбамен
белгіленген К коды:Алф1 ->Алф2 кодтау ағашы деп
аталады, егер
Т түбіріндегі кез-келген жол, Алф1 ішіндегі қандай
да бір таңбаның бастапқы кодымен сәйкес келсе;
Алф1 ішіндегі кез-келген таңба коды Т түбірінің
қандай да бір жолына тиісті.

8. Кодтау ағашына мысал

Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) = 01,
К(с) = 10, К(d) = 1
0
1
a
d
1
b
Неге 01101010 хабарында екі
түпбейне?
c
0

9. Кодтау ағашына мысал

Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) = 10,
К(с) = 110, К(d) = 111
0
1
a
0
1
b
0
1
c
d
Неге кез-келген хабарда бір түпбейне?

10. Префикстік код

К коды префикстік деп аталады, егер кез-келген U
және V екі хабары үшін К(V) кодының бастапқы
(префиксті) коды К(U) болмаса және керісінше.
Префикстік кодының қасиеті:
Префикстік кодының ағашында барлық таңбалар
коды жапырақтарында аяқталады.
Префикстік коды ажырату белгісін қолданбай
таңбалар кодын белгілей алады.
Кодтаудың сапа критерийі:
— ең аз код ұзындығы;
— бірмәнді декодтау.

11. Шеннон-Фано шарты

Ешқандай кодтық сөз басқа кодтық сөздің
басы бола алмайды.
Шеннон-Фано шартын қанағаттандыратын код
префикстік код деп аталады.
Әрбір кодтық сөздер жиынтығын сол кодты
анықтайтын бағытталған графпен
салыстыруға болады.
Теорема: Кез-келген префикстік коды
бірмәнді декодталады.

12. Шеннон-Фано әдісі

Алғашқы сығылу алгоритмдерінің бірін
префикстік кодтың негізінде американдық
ғалымдар Клод Шеннон мен Роберт Марио
Фано тұжырымдаған.

13.

a
b
c
d
e
f
g
h
i
00
01
10
011
100
101
1001
1010
1111
0
0
1
1
0
c
b
a
1
0
1
f
e
d
1
g
Берілген код префиксті болып
табылмайды.
1
1
0
1
h
i

14.

a
00
b
10
c
010
d
110
e
0110
f
0111
g
1110
h
1111
0
a
0
1
1
0
0
b
1
c
0
e
1
1
0
d
1
f
0
1
g
Берілген код префиксті, өйткені кодталатын
таңбалар жаңа доғалар шықпайтын төбелерде
орналасқан.
h

15.

Сығылу- ақпаратты көлемін кішірейту
мақсатында кодтау.
Сығылу коэффициенті- ақпараттың
бастапқы көлемінің сығылу нәтижесінде
алынған көлеміне қатынасы:
V0
Kc
V1
V0 ақпараттың бастапқы көлемі
V1 сығылған ақпараттың көлемі

16. Оңтайлы код ұғымы

Белгіленуі
Δ – кодтар жиыны Алф1* -> Алф2*
К – Δ ішіндегі қандай да бір код
R – Алф1*-дағы кез-келген хабар
L(К, R) – кодтаудан кейінгі R ұзындығы
p х – cх-тің R-ге енген таңбалар саны
сонымен қатар біз Алф1-дегі таңбаларды нөмірледік,
х – сх таңбасының нөмірі.
R хабар кодының ұзындығы L(К,R) = ∑ pх∙L (К, cх).
Δ кодтар жиынындағы R хабары үшін К* коды оңтайлы деп
аталады, егер
L(К*,R) = min { длина(К,R) | K Δ }

17. Оңтайлы екілік префткстік код

Берілген хабар үшін оңтайлы екілік
префикстік кодын қалай тез құруға
болады?
Оңтайлы екілік префикстік кодын құру
алгоритмі-- 1951, David A. Huffman,
Massachusetts Institute of Technology
Оңтайлы екілік префикстік коды хабарлардағы
таңбалардың ретіне байланысты емес, тек жеке
таңбалардың жиілігіне байланысты.

18. Префикстік код құрудағы Хаффман алгоритмі

1.
2.
3.
4.
Кодталған ақпараттың барлық таңбалары төбежапырақтарын құрайды. Әрбір төбеге берілген
таңбаның хабарға енген санына тең салмағы қоса
жазылады.
Салмақтары жазылған төбелердің арасынан салмақтары
ең аз екеуі таңдалады (егер ондай бірнеше болса, онда
кез-келген біреуі).
Алдыңғы қадамда таңдалған екі доға шыққан
төбелерден графтың келесі төбесі құрылады: бір доғасы
0 таңбасымен белгіленеді, басқасы- 1 таңбасымен.
Құрылған төбелерге таңдалған төбелердің
салмақтарының қосындысына тең салмақ жазылады, ал
осы екі төбенің салмақтары өшіріледі.
Салмақтары жазылған төбелерге, бастапқы
таңбалардың салмақтарының қосындысына тең
салмақпен бір төбе қалмайынша, 2 мен 3 қадамдары
қолданыла береді.

19.

0
1
1
0
0
1
0
1
0
д
0
1
е
1
0
н
а
в
00
010 0110 0111 1000 1001
,
0
1
0
р
о
1
1
т
101 1100 1101
_
111

20. Морзе әліпбиі мысал

1840 Alfred Vail телеграф компаниясының тапсырысы
бойынша Samuel F.B. Morse
Екілік (нүкте, сызықша) префикстік емес код – неге?
Үштік (нүкте, сызықша, үзіліс) префикстік код – неге?
Латын тілі үшін екілік коды ретінде Морзе әліпбиінің
код ағашы