 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Описание алгоритма построения кода Шеннона-Фэно
|
|
Принцип построения кода Шеннона - Фэно позволяет говорить об оптимальности кода, так как соответствует поставленным выше требованиям. Способ построения кода проиллюстрирован в табл. 2.
Он удовлетворяет тому условию, для которого символы в закодированном тексте встречаются в среднем одинаково часто. Идея построения кода Шеннона - Фэно состоит в том, что кодируемые символы (у нас буквы) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации символов становится 0, для второй группы - 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы: для символов первой подгруппы на втором месте ставится 0; для второй подгруппы - 1 и т.д.
В нашей задаче возьмем первые шесть букв (от - до Т), сумма их вероятностей = 0.498; на все остальные буквы (от Н до Ф) придется вероятность 0.502. Первые шесть букв будут иметь на первом месте 0, остальные - 1.
Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: (от - до о) и (от е до т) и т. д. Для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы - единицу. Процесс будем продолжать пор, пока в каждом подразделении не окажется ровно одна буква, которая и будет закодирована определенным двоичным числом. Механизм построения кода показан на табл. 2, а сам код приведен в табл. 3
Таблица 2
| буквы | 1-й | 2-й | 3-й | 4-й | 5-й | 6-й | 7-й | 8-й | 9-й |
| - | |||||||||
| о | |||||||||
| е | |||||||||
| а | |||||||||
| и | |||||||||
| т | |||||||||
| н | |||||||||
| с | |||||||||
| р | |||||||||
| в | |||||||||
| л | |||||||||
| к | |||||||||
| м | |||||||||
| д | |||||||||
| п | |||||||||
| у | |||||||||
| я | |||||||||
| ы | |||||||||
| з | |||||||||
| ъ,ь | |||||||||
| б | |||||||||
| г | |||||||||
| ч | |||||||||
| й | |||||||||
| х | |||||||||
| ж | |||||||||
| ю | |||||||||
| ш | |||||||||
| ц | |||||||||
| щ | |||||||||
| э | |||||||||
| ф |
Таблица 3
| буква | дв. код | буква | дв.код | буква | дв.код |
| - | к | ч | |||
| о | м | й | |||
| е | д | х | |||
| а | п | ж | |||
| и | у | ю | |||
| т | я | ш | |||
| н | ы | у | |||
| с | з | щ | |||
| р | ь, ъ | э | |||
| в | б | ф | |||
| л | г |
ПРИМЕР КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ СООБЩЕНИЙ МЕТОДОМ ШЕННОНА - ФЭНО
С помощью табл. 2 можно закодировать и декодировать любое сообщение. В виде примера запишем двоичным кодом фразу: "Теория информации"
0 111 010000 11 01 000 11 011 11 0000
01101000111111 111 00110 100
11 0000 10111111 10101100110
Отметим, что здесь нет необходимости отделять буквы друг от друга специальным знаком, т.к. и без этого декодирование выполняется однозначно. Убедимся в этом, декодируя с помощью табл. 2 следующую фразу:
Результат декодирования - фраза "способ кодирования". При таком кодировании любая ошибка (случайное перепутывание знаков 0 и 1) губительна, т.к. декодирование всего следующего за ошибкой текста становится невозможным. Поэтому данный принцип кодирования используется тогда, когда ошибки при кодировании и передаче сообщения исключены.
Анализ оптимальности кода Шеннона - Фэно
Для того, чтобы выяснить, является ли построенный код оптимальным, необходимо найти среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравнить ее с максимально возможной информацией, которая равна одной двоичной единице. Для этого определяется сначала средняя информация, содержащаяся в одной букве передаваемого текста, т. е. энтропия на одну букву:
,
где pi - вероятность того, что буква примет определенное состояние (-, о, е, а,..., ф).
Из табл. 1 определяем
Н(б) = - (0.145 log 0.145 + 0.095 log 0.095 +... + 0.002 log 0.002),
Н(б)» 4.42 (двоичных единиц на одну букву текста).
По табл. 2 определяется среднее число элементарных символов на букву
nср = 3×0.145 + 3×0.095 +... + 9×0.002 = 4.45.
Деля энтропию Н(б) на nср, вычисляется информация на один элементарный символ
Iср = 4.42 / 4.45» 0.994 (дв. ед.).
Таким образом, информация на один символ очень близка к своему верхнему пределу - 1. Следовательно построенный код в целом отвечает принципу оптимальности. Оставаясь в пределах задачи кодирования по буквам, ничего лучшего получить нельзя
Необходимо отметить, в случае кодирования простым двоичным кодом каждая буква изображается пятью двоичными знаками, и информация на один символ была бы
Iср = 4.42 / 5.00= 0.884 (дв. ед.),
т. е. заметно меньше, чем при кодировании методом Шеннона - Фэно.
Однако следует обратить внимание, что кодирование “по буквам” вообще не является экономичным. Дело в том, что между соседними буквами любого осмысленного текста всегда имеется зависимость. Например, после гласной буквы в русском языке не может стоять “ъ” или ”ь”; после шипящих не могут стоять “я” или ”ю”; после нескольких согласных подряд увеличивается вероятность гласной и т.д.
Известно, что при объединении зависимых систем суммарная энтропия меньше суммы энтропий отдельных систем. Следовательно, информация, передаваемая отрезком связного текста, всегда меньше, чем информация на один символ, умноженная на число символов. С учетом этого обстоятельства более экономичный код можно построить, если кодировать не каждую букву в отдельности, а целые “блоки” из букв. Например, в русском тексте имеет смысл кодировать целиком некоторые часто встречающиеся комбинации букв, как “тся”, “ает”, “ние” и т. п. Кодируемые блоки располагаются в порядке убывания частот, как буквы в табл. 1, а двоичное кодирование осуществляется по тому же принципу.
В ряде случаев оказывается разумным кодировать даже не блоки из букв, а целые осмысленные куски текста. Например, для разгрузки телеграфа в предпраздничные дни целесообразно кодировать условными номерами целые стандартные тексты, вроде:
“поздравляю новым годом желаю здоровья успехов работе”.
Дата публикования: 2015-10-09; Прочитано: 177 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
