27. Шеннон-фано кодын құру қағидаларына шолу жасаңыз. Шеннон-фано кодына мысал келтіріңіз.

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

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

Шеннон-Фано коды ағаш түрінде тұрғызылады. Ағаштың тұрғызылуы түбірінен басталады.

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

a, b, c и d төрт символдан тұратын әліпби берілсін.

Әр символды кодтау үшін 2 бит жеткілікті. Мысал: a – 00, b – 01, c – 10, d – 11.

Сонымен ababcaacdb хабарламасы 20 битпен кодталады.

ababcaacdb хабарламасы бойынша әр символдың үлесін анықтайық және оларды үлестің кемуі бойынша кестеге орналастыру керек.

Символ	a	b	c	d
Мәтіндегі үлесі	4/10	3/10	2/10	1/10

Үлестердің қосындысы әр бөлікте аз ерекшеленетіндей етіп, кестені екіге бөлеміз. Бірінші бөліктегі символдар коды 0-ден, ал екіншісі 1-ден басталсын:

Символ

a

b

c

d

Мәтіндегі үлесі

4/10

3/10

2/10

1/10

Үлестер қосындысы

4/10

6/10

Кодтың бірінші цифры

0

1

Кестенің бір символдан артық бөліктеріне осы процедураны қайталаймыз:

Символ

a

b

c

d

Мәтіндегі үлесі

4/10

3/10

2/10

1/10

Үлестер қосындысы

4/10

6/10

Кодтың бірінші цифры

0

1

3/10

3/10

Кодтың екінші цифры

0

1

Символ

a

b

c

d

Мәтіндегі үлесі

4/10

3/10

2/10

1/10

Үлестер қосындысы

4/10

6/10

Кодтың бірінші цифры

0

1

3/10

3/10

Кодтың екінші цифры

0

1

2/10

1/10

Кодтың үшінші цифры

0

1

Сонымен әліпби символдары үшін жаңа код алынды:

a – 0, b – 10, c – 110 и d – 111.

аbabcaacdb хабарламасы 19 битті құрайды.

1- мысал. a, b, c, d симводары берілген олардың жиіліктері: fa = 0,5;  fb = 0,25;  fc = 0,125;  fd = 0,125. Шеннон-Фано әдісімен тиімді кодты тұрғызыңыз.

Шешуі:

Алғашқы деректерді кестеге жазайық

	Алғашқы символдар		Символдар жиілігі
	a		0,5
	b		0,25
	c		0,125
	d		0,125
Алғашқы символдар		Символдар жиілігі			Қалыптасқан код
a		0,5			1
b		0,25			0
c		0,125			0
d		0,125			0
Алғашқы символдар			Символдар жиілігі			Қалыптасқан код
a			0,5			1
b			0,25			01
c			0,125			00
d			0,125			00
Алғашқы символдар				Символдар жиілігі			Қалыптасқан код
a				0,5			1
b				0,25			01
c				0,125			001
d				0,125			000

Тұрғызылған кодтың тиімділігін формула бойынша есептейміз

lср = 0,5*1 + 0,25*2 + 0,125*3 + 0,125*3 = 1,75.

Пара	Вероятность пары	Код пары	Длина кода
АА	0.7∙0.7=0.49	1	1
АВ	0.7∙0.3=0.21	01	2
ВА	0.3∙0.7=0.21	001	3
ВВ	0.3∙0.3=0.09	000	3

Средняя длина кода К₂=1∙0.49+2∙0.21+3∙0.21+3∙0.09=1.81; в расчете на один символ К₁=К₂/2=0.905. Коэффициент эффективности кода К_ОЭ = 0.88/0.905 = 0.972.

2) Составим алфавит из трёхбуквенных комбинаций.

Пара	Вероятность пары	Код пары	Длина кода
ААА	0.343	11	2
ААВ	0.147	10	2
АВА	0.147	011	3
ВАА	0.147	010	3
АВВ	0.063	0011	4
ВАВ	0.063	0010	4
ВВА	0.063	0001	4
ВВВ	0.027	0000	4

Средняя длина кода К₃=2.686; в расчете на один символ К₁=К₃/3=0.895.

Коэффициент эффективности кода К_ОЭ = 0.88/0.895 = 0.983.