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

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

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

Методы кодирования Шеннона-Фано положили начало области теории информации, и без ее вклада в мире не было бы ни одного из многих преемников; например, кодирование Хаффмана или арифметическое кодирование . Большая часть нашей повседневной жизни находится под значительным влиянием цифровых данных , и это было бы невозможно без кодирования Шеннона-Фано и постоянного развития его методов. ^[2]^{[ нужна страница ]}

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

Пример [ править ]

В таблице ниже приведен пример создания схемы кодирования для от ₁ до 6 _{символов} . Значение l _i дает количество битов, используемых для представления символа a _i . Последний столбец представляет собой битовый код каждого символа.

я	Пи	l_я	$\sum _{n=0}^{i-1}p_{n}$	Предыдущее значение в двоичном формате	для i _{Кодовое слово}
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

Ссылки [ править ]

^ Шеннон, Клод Э. (июль 1948 г.). «Математическая теория связи [перепечатка с исправлениями]» (PDF) . Технический журнал Bell System . 27 (3): 379–423. дои : 10.1002/j.1538-7305.1948.tb01338.x . hdl : 11858/00-001M-0000-002C-4314-2 .
^ Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .

Шеннон, Клод Элвуд. «Математическая теория связи». Обзор мобильных вычислений и связи ACM SIGMOBILE 5.1 (2001): 3-55.

[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 .

[LiDrew2014-2] Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .

[1]

[2]