WikiDer > Кодирование Шеннона

Shannon coding

В области Сжатие данных, Кодирование Шеннона, названный в честь его создателя, Клод Шеннон, это сжатие данных без потерь техника построения код префикса на основе набора символов и их вероятностей (оценочных или измеренных). Это неоптимально в том смысле, что не достигает минимально возможной ожидаемой длины кодового слова, например Кодирование Хаффмана делает, и никогда не лучше, но иногда равняется Кодирование Шеннона – Фано.

Метод был первым в своем роде, методика использовалась для подтверждения Теорема Шеннона о бесшумном кодировании в своей статье 1948 года «Математическая теория коммуникации»,[1] и поэтому является центральным элементом информационного века.

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

В кодировании Шеннона символы располагаются в порядке от наиболее вероятного к наименее вероятному, а кодовые слова назначаются путем взятия первого биты из двоичных разложений кумулятивных вероятностей Здесь обозначает функция потолка (который раундов до следующего целого значения).

Пример

В таблице ниже приведен пример создания схемы кода для символов. а1 к а6. Значение ля дает количество битов, используемых для представления символа ая. Последний столбец - это битовый код каждого символа.

япяляПредыдущее значение в двоичном форматеКодовое слово для ая
10.3620.00.000000
20.1830.360.0101...010
30.1830.540.1000...100
40.1240.720.1011...1011
50.0940.840.1101...1101
60.0740.930.1110...1110

Рекомендации

  1. ^ Шеннон, Клод Э. (Июль 1948 г.). «Математическая теория коммуникации» (PDF). Технический журнал Bell System. 27 (3): 379–423. Дои:10.1002 / j.1538-7305.1948.tb01338.x. HDL:11858 / 00-001M-0000-002C-4314-2.