Понятие эффективного кодирования
Понятие эффективного кодирования
Задача эффективного кодирования – уменьшение среднего числа символов на знак сообщения до теоретически возможного предела, равного энтропии источника. Приведенный ниже пример эффективного кодирования методом Шеннона – Фано подтверждает один из основных результатов теории информации:
для сокращения количества символов надо кодировать не отдельные знаки, а длинные последовательности знаков.
Пусть имеется источник 
с энтропией Н= - (0,9 log20,9 + 0,1 log20,1) = 0,47.
Если знаки х1 и х2 кодировать символами 0 и 1 соответственно, то для передачи одного знака потребуется 1 бит.
Будем кодировать не отдельные знаки, а двухзнаковые кодовые комбинации. Согласно рассматриваемому методу, все кодовые комбинации разделяют на 2 группы так, чтобы суммы вероятностей кодовых комбинаций каждой группы были по возможности одинаковы. Всем комбинациям одной группы приписывают 0 в качестве первого символа, всем комбинациям другой группы - 1. Затем каждую из полученных групп, в свою очередь, делят на две группы, приписывая комбинациям группы аналогичным образом вторые символы и т.д. В таблице 1 указаны вероятности двухзнаковых комбинаций и соответствующие им двоичные коды, полученные согласно данной методике. Для передачи двухзнаковой комбинации в среднем требуется
1*0,81 + 2*0,09 + 3(0,09 + 0,01) = 1,29 бит,
а для передачи одного знака требуется 0,65 бит.
Рекомендуемые материалы
Таблица 1
| знаки | p | группы | код |
| Х 1 Х1 Х 1 Х2 Х 2 Х1 Х 2 Х2 | 0,81 0,09 0,09 0,01 |
0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 | 1 0 1 0 0 1 0 0 0 |
1Таблица 2 иллюстрирует применение методики Шеннона-Фано к трехзнаковым кодовым комбинациям. Для передачи трехзнаковой комбинации в среднем требуется
1*0,729 + 3*(3*0,81) + 5*(3*0,009 + 0,001) = 1,598 бит,
а для передачи одного знака требуется 0,53 бит. Этот результат близок к теоретическому пределу - значению энтропии данного источника (0,47).
Таблица 2
| знаки | р | группы | код |
| Х1 Х1 Х1 Х2 Х1 Х1 Х1 Х 2 Х1 Х1 Х1 Х2 Х2 Х2 Х1 Х2 Х1 Х2 Х1 Х2 Х2 Х2 Х2 Х2 |
0,081 0,081 0,081 0,009 0,009 0,001 |
0 0 0
0 0000 00001
| 1 011 010 001 Информация в лекции "7. Смазочные и специальные масла" поможет Вам. 00011 00010 00001 00000 |
0,729
1
01 011 
010
001
0 0001 00011
0 00 000 00010Доказано, что эффективность кодирования, теоретически возможная при отсутствии помех, достижима и при помехах (благодаря помехоустойчивому кодированию) за счет удлинения кодируемых последовательностей знаков.
Максимальная скорость передачи информации достигается при кодировании сообщения равновероятными не коррелирующими друг с другом символами.
