2. Коды Шеннона - Фано.

Код Шеннона-Фано строится также, как и двоичный код, его можно представить таблично, только сообщения вписываются в таблицу в порядке убывания вероятностей. Деление на группы производится таким образом, чтобы суммы вероятностей в каждой из групп были бы по возможности одинаковыми. Основной принцип, положенный в основу кодирования по методу Шеннона-Фано, заключается в том, что при выборе каждой цифры кодового обозначения следует стремиться к тому, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения (0 и 1) по возможности с одинаковой вероятностью.

Путь X = {x₁, x₂, ... , x_n} — множество сообщений источника, а P₁, P₂, ... , P_n — вероятности появления этих сообщений. Правила составления кода заключается в следующем. Сообщения x₁, ... , x_n вписываются в столбец в порядке убывания вероятностей P₁, ... ,P_n. Столбец делится на две группы так, чтобы суммарные вероятности появления каждой из групп были примерно одинаковы. Верхняя группа кодируется единицей, нижняя - нулем, т. е. всем сообщениям верхней группы в качестве первого сигнала приписывается 1, а всем сообщениям нижней группы — 0. Каждая из образованных групп аналогичным образом делится на две группы, определяя второй символ кодовой комбинации (1 или 0). Процесс продолжается, пока в каждой подгруппе не останется по одному сообщению.

Пример.

Символ	Вероятность	Группа				Код символа
		I	II	III	IV
x1	0.3		1			11
x2	0.25		0			10
x3	0.2		1			01
x4	0.15			1		001
x5	0.06				1	0001
x6	0.04				0	0000

2.1.3 Коды Хаффмана.

Правило составления кода по методу Хаффмана состоит в следующем.

Сообщения выписываются в столбец по убыванию вероятностей. Во второй столбец записываются вероятности соответствующих сообщений. Два последних значения (наименьших) из второго столбца суммируются. Из полученной суммы и других значений вероятности формируется третий столбец в порядке убывания вероятностей. Процесс продолжается до тех пор, пока в очередном столбце не останется единственный элемент с вероятностью, равной 1.

Чтобы составить кодовую комбинацию, соответствующую данному сообщению, необходимо проследить путь перехода сообщения по строкам и столбцам таблицы. Для наглядности строится кодовое дерево. Последний столбец соответствует корню кодового дерева, ему присваивается вес, равный единице. Из корня строят две ветви с узлами, веса которых равны значениям элементов предпоследнего столбца (из суммы которых образован последний). Ветви, оканчивающейся узлом с большим весом присваивается символ 1, с меньшим — символ 0. Далее выбирают один из висячих узлов и наращивают дерево еще двумя узлами по указанному выше принципу. Процесс продолжается до тех пор, пока веса всех «висячих» (тупиковых) узлов дерева не окажутся значениями вероятностей исходных сообщений. Для получения кодовой комбинации отдельного сообщения нужно выбрать тупиковый узел кодового дерева, соответствующую данному сообщению, и выписать по порядку веса ребер, составляющих путь от корня дерева к данному висячему узлу.

Пример.

Сообщение	Вероятность	Вспомогательные столбцы
		1	2	3	4	5
x1	0.3	0.3	0.3	0.45	0.55	1
x2	0.25	0.25	0.25	0.30	0.45
x3	0.2	0.20	0.25	0.25
x4	0.15	0.15	0.20
x5	0.06	0.1
x6	0.04

Полученные кодовые комбинации представлены ниже:

Сообщение	x1	x2	x3	x4	x5	x6
Код	11	10	00	011	0101	0100

4. Особенности эффективных кодов Шенона-Фано и Хаффмана

Основной принцип, положенный в основу кодирования по методу Шенона-Фано и Хаффмана, заключается в то, что при выборе кодового слова следует стремиться к тому, чтобы содержащееся в ней кол-во информации было наименьшим, т.е. чтобы независимо от значений всех предыдущих цифр эта цифра приняла оба значения (0 и 1) по возможности с одинаковой вероятностью.

Коды Шенона-Фано и Хаффмана являются оптимальными только в том случае, когда все символы сообщения имеют вероятности появления равные целым отрицательным степеням двойки (можно показать, что тогда n_ср=n_min).

Следует заметить ещё одну важную особенность кодов Шенона-Фано и Хаффмана – так как коды являются неравномерными, то для безошибочного их декодирования надо, чтобы более короткие кодовые комбинации не являлись началом более длинных, иначе более длинные никогда не будут приняты. Например, если бы в результате ошибки построения кода символ х1 (см. пример 2 выше) получил кодовую комбинацию «01»,а всё остальное было бы без изменений, то сообщение «х5 х4 х6» (в закодированном виде «01010110100») было бы декодировано как «х1 х1 х1 х2 х2 #».