Кодирование Шеннона - Shannon coding

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

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

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

В кодировании Шеннона символы располагаются в порядке от наиболее вероятного к наименее вероятному, а кодовые слова назначаются путем взятия первого ${\displaystyle l_{i}=\left\lceil -\log _{2}p_{i}\right\rceil }$ биты из двоичных разложений кумулятивных вероятностей ${\displaystyle \sum \limits _{k=1}^{i-1}p_{k}.}$ Здесь ${\displaystyle \lceil x\rceil }$ обозначает функция потолка (который раундов ${\displaystyle x}$ до следующего целого значения).

Пример

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

я	пя	ля	${\displaystyle \sum _{n=0}^{i-1}p_{n}}$	Предыдущее значение в двоичном формате	Кодовое слово для ая
1	0.36	2	0.0	0.0000	00
2	0.18	3	0.36	0.0101...	010
3	0.18	3	0.54	0.1000...	100
4	0.12	4	0.72	0.1011...	1011
5	0.09	4	0.84	0.1101...	1101
6	0.07	4	0.93	0.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.