15. Код Шеннона–Фано

Эффективное кодирование состоит в том, чтобы, учитывая статистические свойства источника сообщения, а именно, вероятность появления каждого знака первичного алфавита, минимизировать среднее число двоичных знаков, требующихся для кодирования одного знака. То есть наиболее часто повторяющиеся знаки обозначаются минимальным числом двоичных знаков, а те, которые применяются редко, — длинными. Средняя величина знаков на одну букву в результате этого уменьшается на 30%.

Теорема Шеннона для каналов передачи с отсутствием помех: сообщение, передаваемые источником с энтропией Н можно закодировать так, чтобы среднее число двоичных знаков на одну букву первичного алфавита было сколь угодно близким к энтропии, но не меньше этой величины.

Последовательность построения такого кода можно изложить в следующем виде:

1. Буквы первичного алфавита записываются в таблицу в порядке убывания их вероятности появления в сообщении.

2. Все буквы разделяются на две группы, так, чтобы суммы вероятностей в них были примерно одинаковыми.

Например:

z₁. Вероятность появления Р_z1=0,27 P_z2=0,23 P_z3=0,16 P_z4=0,16 P_z5=0,1 P_z6=0,08

Это идеальный пример, но нужно как можно ближе подгонять к половине!! При чем не переставляя буквы местами.

3. Буквы первой группы в качестве первого символа получают 1. А буквам второй группы – 0.

4. Эти две подгруппы снова разбиваются в свою очередь на две подгруппы. С условием, чтобы вероятности в этих подгруппах были приблизительно одинаковыми и равны ¼. Каждой подгруппе присваивается 1 первой половине, 0 – второй половине. Таким образом, разбиваются так подгруппы, пока не дойдет до одной буквы.

Недостаток: неоднозначность вариантов кодов отдельных знаков. Это следует из того, что разбиение знаков алфавита можно сделать большей по вероятности как верхнюю, так и нижнюю. Буквы с равной вероятностью попадают в разные группы, тогда код у нее становится более длинным. Эта неопределенность вносит некоторую избыточность в код.