Рассмотреть три распределения вероятностей символов алфавита

Алфавит источника - a, b, c, d
Вероятность появления букв
Вероятность появления букв
Алгоритм – Шеннона-Фано
Для построения кода Шеннона-Фано все символы алфавита сообщений записываются в порядке убывания вероятностей их появления. Полученную ранжированную (упорядоченную) последовательность символов разбивают на две группы так, чтобы суммы вероятностей групп были примерно одинаковыми. Для символов первой группы в качестве первого кодового символа присваивают 0, а для символов второй группы – 1 . Полученные группы символов опять разбивают таким же образом на две подгруппы и опять кодируют. Это продолжается до тех пор пока в последних подгруппах не останется по одному символу.
Равномерное распределение
x p шаг коды
1 2
a 1/4 0 0 00
b 1/4
1 01
c 1/4 1 0 10
d 1/4
1 11
Средняя длина кода будет равна бит
Избыточностью кода называется разность между средней длиной кодового слова и предельной энтропией источника сообщений
Найдем значение энтропии
бит
Следовательно, избыточность кода в данном случае составляет 0
Неравенство Крафта где ni – длины кодов
Проверим выполнение неравенства
Неравенство выполняется.
Распределение P1
x p шаг коды
1 2 3
a 0,01 0 0 0 000
c 0,09
1 001
b 0,1
1 - 01
d 0,8 1 - - 1
Средняя длина кода будет равна
бит
Найдем значение энтропии
бит
Следовательно, избыточность кода в данном случае составляет 0,33117
Неравенство Крафта где ni – длины кодов
Проверим выполнение неравенства
Неравенство выполняется.
Распределение P2
x p шаг коды
1 2 3
b 1/8 0
0 0 000
d 1/8
1 001
a 1/4
1 - 01
c 1/2 1 - - 1
Средняя длина кода будет равна
бит
Найдем значение энтропии
бит
Следовательно, избыточность кода в данном случае составляет 0
Неравенство Крафта где ni – длины кодов
Проверим выполнение неравенства
Неравенство выполняется.