Избыточность (теория информации)

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июнь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В теории информационного , избыточность измеряет дробная разность между энтропией H (X) из ансамбля X , и ее максимально возможной величины . ^{[1] [2]} Неформально это количество потраченного впустую «пространства», используемого для передачи определенных данных. Сжатие данных - это способ уменьшить или устранить нежелательную избыточность, в то время как контрольные суммы - это способ добавления желаемой избыточности в целях обнаружения ошибок при обмене данными по шумному каналу ограниченной емкости .${\ displaystyle \ log (| {\ mathcal {A}} _ {X} |)}$

Количественное определение [ править ]

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

${\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),}$

в пределе, когда n стремится к бесконечности, совместной энтропии первых n символов, деленной на n . В теории информации принято говорить о «скорости» или « энтропии » языка. Это уместно, например, когда источником информации является английская проза. Скорость источника без памяти проста , поскольку по определению нет взаимозависимости последовательных сообщений источника без памяти. ^{[ необходима цитата ]}${\displaystyle H(M)}$

Абсолютная скорость языка или источника просто

${\displaystyle R=\log |\mathbb {M} |,\,}$

логарифм от мощности пространства сообщения или алфавита. (Эту формулу иногда называют функцией Хартли .) Это максимально возможная скорость передачи информации, которая может быть передана с помощью этого алфавита. (Логарифм должен быть приведен к основанию, соответствующему используемой единице измерения.) Абсолютная скорость равна фактической скорости, если источник не имеет памяти и имеет равномерное распределение .

Тогда абсолютную избыточность можно определить как

${\displaystyle D=R-r,\,}$

разница между абсолютной ставкой и ставкой.

Величина называется относительной избыточностью и дает максимально возможную степень сжатия данных , когда выражается в процентах, на которые можно уменьшить размер файла. (Выраженное как отношение исходного размера файла к размеру сжатого файла, величина дает максимальную степень сжатия, которую можно достичь.) К концепции относительной избыточности дополняет эффективность , определяемая как таковая . Источник без памяти с равномерным распределением имеет нулевую избыточность (и, следовательно, 100% эффективность) и не может быть сжат.${\displaystyle {\frac {D}{R}}}$${\displaystyle R:r}$${\displaystyle {\frac {r}{R}},}$${\displaystyle {\frac {r}{R}}+{\frac {D}{R}}=1}$

Другие понятия [ править ]

Мера избыточности между двумя переменными - это взаимная информация или нормализованный вариант. Мера избыточности среди многих переменных определяется общей корреляцией .

Избыточность сжатых данных относится к разнице между ожидаемой длиной сжатых данных сообщений (или ожидаемой скоростью передачи данных ) и энтропией (или скоростью энтропии ). (Здесь мы предполагаем, что данные являются эргодическими и стационарными , например, источник без памяти.) Хотя разница в скорости может быть сколь угодно малой при увеличении, фактическая разница не может, хотя теоретически она может быть ограничена сверху единицей в случае конечного -энтропийные источники без памяти.${\displaystyle n}$${\displaystyle L(M^{n})\,\!}$${\displaystyle L(M^{n})/n\,\!}$${\displaystyle nr\,\!}$${\displaystyle r\,\!}$${\displaystyle L(M^{n})/n-r\,\!}$${\displaystyle n\,\!}$${\displaystyle L(M^{n})-nr\,\!}$

См. Также [ править ]

• Кодирование с минимальной избыточностью
  • Кодирование Хаффмана
• Сжатие данных
• Функция Хартли
• Негэнтропия
• Теорема исходного кода
• Неполнота

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

• Реза, Фазлолла М. (1994) [1961]. Введение в теорию информации . Нью-Йорк: Довер [Макгроу-Хилл]. ISBN 0-486-68210-2.
• Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код в C . Нью-Йорк: ISBN John Wiley & Sons, Inc. 0-471-12845-7.
• Ауффарт, B; Lopez-Sanchez, M .; Серкидес, Дж. (2010). «Сравнение мер избыточности и релевантности для выбора признаков в классификации тканей компьютерной томографии». Достижения в интеллектуальном анализе данных. Приложения и теоретические аспекты . Springer. С. 248–262. CiteSeerX  10.1.1.170.1528 .