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

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

Передача сообщений и информации

Избыточность - это часть сообщения , не содержащая никакой информации . Избыточная часть сообщения может зависеть от информации, содержащейся в сообщении. В приложениях информационных технологий и телекоммуникаций избыточность используется специально для обнаружения сбоев . Более сильное резервирование позволяет не только обнаруживать ошибки, но и их исправлять. Избыточность позволяет повысить качество (меньше ошибок) за счет количества (более высокая скорость передачи данных). Сила избыточности, которая будет использоваться в каждом случае, зависит от отказоустойчивости соответствующего приложения - в банковском деле и космических путешествиях один перевернутый бит может стоить больших денег, в то время как в интернет-телефонии или DVB даже постоянная потеря всего пакеты не имеет значения.

Отказоустойчивость

Связь может быть проведена устойчива к ошибкам через избыточную информацию через информационный канал , так как потеряна или фальсифицирован частичная информация может быть восстановлена из своего контекста на получателе при определенных обстоятельствах . Расстояние Хэмминга является мерой отказоустойчивости .

Средняя длина кодового слова

Будь алфавитом и${\ displaystyle Z}$${\ displaystyle z \ in Z}$

${\ displaystyle C (z)}$обозначает кодовое слово, которое будет использоваться${\ displaystyle z}$

${\ displaystyle l (z)}$ обозначает длину ${\ displaystyle C (z)}$

Средняя длина кодового слова исходного кода с распределением вероятностей определяется как: ${\ Displaystyle L (C)}$${\ displaystyle C (z)}$${\ displaystyle p (z)}$

${\ Displaystyle L (C) = \ сумма _ {я = 1} ^ {| Z |} {l (z_ {i}) p (z_ {i})}}$

Избыточность кода

Избыточность кода разница между средней длиной кодового слова и энтропией . (Пример: кодирование Хаффмана для оптимального (= минимального) ). ${\ Displaystyle L (C)}$ ${\ Displaystyle H (X)}$${\ Displaystyle L (C)}$

${\ Displaystyle R _ {\ текст {Код}} = L (C) -H (X) \,}$

Избыточность источника представляет собой разность между максимальной энтропией и энтропией источника сообщений. ${\ displaystyle H _ {\ text {max}} (X) = \ log _ {2} | Z |}$${\ Displaystyle H (X)}$

${\ displaystyle R _ {\ text {source}} = \ log _ {2} | Z | -H (X) \,}$

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

Кодирование

В теории кодирования различают два проявления избыточности:

• В распределении резервирования заключается в различной вероятности появления отдельных символов алфавита.
• Избыточность галстука является то , что после определенных символов, появление некоторого другого характера, в частности , скорее всего. Например, в немецком тексте за q почти всегда следует u.

Базы данных и структуры данных

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

Избыточности можно в значительной степени избежать , нормализовав схему базы данных. Есть также дублирование, которое неизбежно (например, дублирование ключей ) и поэтому принимается как неизбежное зло . Также допустимы избыточности, поскольку их устранение потребовало бы слишком больших усилий по отношению к их проблеме, например, многократное вхождение значения атрибута или двойное хранение имени Мюллер для г-на Мюллера и для г-жи Мюллер.

Преднамеренное принятие избыточности для повышения производительности чтения называется денормализацией .

недостаток

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

преимущества

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

литература

• Ф. Топсе: Теория информации. Введение, BG Teubner Verlag, Штутгарт 1974, ISBN 978-3-519-02048-6 .
• Отто Милденбергер: теория информации и кодирование. 2-е издание. Фридрих Веег и Зон Verlagsgesellschaft, Висбаден 1992, ISBN 3-528-13046-6 .
• Вернер Мейер-Эпплер: Основы и приложения теории информации. 2-е издание, Springer Verlag, Берлин / Гейдельберг 1969, ISBN 978-3-642-49130-6 .
• Мартин Боссерт: Введение в коммуникационные технологии. Ольденбург, Мюнхен 2012 г., ISBN 978-3-486-70880-6 .
• Эрнст Шульце: Введение в математические основы теории информации. Springer Verlag, Берлин / Гейдельберг 1969, ISBN 978-3-540-04633-2 .
• Мартин Вернер: техника связи. Введение во все курсы, 7-е издание, Vieweg + Teubner Verlag, Wiesbaden 2010, ISBN 978-3-8348-0905-6 .

веб ссылки

• Основы теории информации (по состоянию на 23 февраля 2018 г.)
• Coding Theory (по состоянию на 23 февраля 2018 г.)