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

Теория информации
Собственная информация Информационная энтропия Дифференциальная энтропия Условная энтропия Энтропия объединения Взаимная информация Условная взаимная информация Относительная энтропия Энтропийная скорость
Избыточность информации Скорость передачи информации Пропускная способность канала
Теорема Шеннона для канала без шума Теоремы Шеннона для канала с шумом Теорема Шеннона — Хартли

Избыточность информации — термин из теории информации, характеризующий степень неодинаковости распределения вероятностей различных элементов алфавита, а также степень взаимной зависимости элементов алфавита, проявляющиеся в уменьшении его энтропии по сравнению с максимальным значением^[1].

Если алфавит имеет вероятностное распределение, отличное от равномерного, то его энтропия ${\displaystyle H(A)}$, рассчитанная с учетом вероятностных связей между его элементами, отлична от максимально возможного значения, равного ${\displaystyle H_{max}(A)=\log _{2}(M)}$, называемого абсолютной энтропией, где ${\displaystyle M}$ — основание алфавита (число различных элементов алфавита)^[1].

Избыточность алфавита (избыточность языка, избыточность сообщения) определяется по формуле^[2][3]:

${\displaystyle r=1-{\frac {H(A)}{H_{max}(A)}}.}$

В случае марковского источника ${\displaystyle n}$-го порядка, когда условная вероятность появления текущего символа сообщения ${\displaystyle a_{i}}$ зависит только от ${\displaystyle n}$ предыдущих символов сообщения, то есть при наличия вероятностных связей между символами сообщения (что имеет место в текстовом сообщении), энтропия источника определяется по формуле^[1][4]:

${\displaystyle H=-\sum _{q=1}^{Q}\sum _{i=1}^{M}P(q)p_{q}(a_{i})\log _{2}p_{q}(a_{i})=-\sum _{q=1}^{Q}\sum _{i=1}^{M}p(b_{q},a_{i})\log _{2}p_{q}(a_{i}),}$

где ${\displaystyle P(q)}$ — вероятность ${\displaystyle q}$-го состояния источника, которое определяется ${\displaystyle n}$ символами сообщения, предшествующих текущему символу ${\displaystyle a_{i}}$, ${\displaystyle Q}$ — число состояний, ${\displaystyle p_{q}(a_{i})}$ — условная вероятность выбора источником символа ${\displaystyle a_{i}}$ в ${\displaystyle q}$-ом состоянии, ${\displaystyle b_{q}}$ — ${\displaystyle q}$-ая последовательность из ${\displaystyle n}$ символов, предшествующая символу ${\displaystyle a_{i}}$, ${\displaystyle p(b_{q},a_{i})=P(q)p_{q}(a_{i})}$ — совместная вероятность появления последовательности ${\displaystyle b_{q}}$ и ${\displaystyle a_{i}}$.

Для английского текста, состоящего из 26 букв, ${\displaystyle H_{max}=\log _{2}26=4.7}$. Клодом Шенноном было уcтановлено, что энтропия английского текста при ${\displaystyle n=100}$ равна 0.6—1.3 бит/символ^[5], то есть избыточность английского текста составляет 0.72—0.87.

Избыточность можно уменьшить с помощью сжатия источника. В случае, когда источник не имеет избыточности (${\displaystyle H(A)=H_{max}(A)}$), то есть вероятности всех символов одинаковы, оптимальным кодированием является равномерное кодирование, при котором каждый символ источника кодируется одинаковым числом битов, равным ${\displaystyle \log _{2}(M)}$. В случае, когда ${\displaystyle H(A)<H_{max}(A)}$ источник имеет избыточность, и равномерное кодирование не является оптимальным, так как требует ${\displaystyle \log _{2}(M)}$ битов для кодирования каждого символа источника. Однако избыточность может быть уменьшена полностью или частично, если при кодировании представлять наиболее вероятные символы короткими последовательностями битов, а менее вероятные — более длинными. В этом случае среднее количество битов, приходящихся на один символ, окажется меньшей, чем в случае равномерного кодирования^[6].

В результате устранения избыточности источник (файл) будет занимать меньший размер, и его символы могут быть переданы по каналу связи более быстро. Однако устранение избыточности имеет следующий недостаток. Последовательности неравномерного кода, лишенные или практически лишенные избыточности, оказываются весьма «хрупкими» при наличии шумов. Эта хрупкость заключается в том, что достаточно исказить один из символов кодовой последовательности, чтобы сделать невозможным правильное декодирование не только символа источника, а который входит кодовый символ, но и ряда последующих символов источника^[7].

Основная теорема кодирования канала без шума гласит, что символы источника с основанием алфавита ${\displaystyle M}$, имеющее энтропию ${\displaystyle H(A)}$, можно так закодировать посредством кодовых символов с основанием алфавита ${\displaystyle D}$, что среднее число кодовых символов на один символ источника ${\displaystyle {\bar {n}}}$ удовлетворяет неравенству^[8]:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+\epsilon ,}$

где ${\displaystyle \epsilon }$ — сколь угодно мало.

Это неравенство выполняется в случае, когда символы источника объединяются в группы по ${\displaystyle N}$ символов, и производится кодирование этих групп кодовыми символами, причём величина ${\displaystyle N}$ стремится к бесконечности^[9][10].

Таким образом, среднее число кодовых символов на один символ источника не может быть сделано меньше, чем ${\displaystyle H(A)/\log _{2}(D)}$. В противном случае, символы источника нельзя достоверно восстановить. Теоретически возможен код, у которого ${\displaystyle {\bar {n}}}$ стремиться к ${\displaystyle H(A)/\log _{2}(D)}$.

Если кодирование производится двоичными кодовыми символами ${\displaystyle D=2}$, то это означает, что при кодировании без потерь среднее число битов, приходящихся на символ источника, может быть сделано очень близким к энтропии источника, которая и является средним количеством информации (битов), приходящееся на символ источника.

При использовании кодирования избыточность источника после кодирования вычисляется по формуле^[11]:

${\displaystyle r=1-{\frac {H(X)}{H_{max}(X)}},}$

где ${\displaystyle H(X)}$ — энтропия кодовых символов ${\displaystyle X}$, ${\displaystyle H_{max}(X)}$ — максимальное значение энтропии кодовых символов, ${\displaystyle H_{max}(X)=\log _{2}(D)}$, где ${\displaystyle D}$ — основание кодового алфавита (число различных символов кода).

Энтропия источника ${\displaystyle H(A)}$ при однозначном декодировании связана с энтропией кодовых символов ${\displaystyle H(X)}$ по формуле:

${\displaystyle H(A)={\bar {n}}H(X)}$.

Таким образом, формула для избыточности источника после кодирования примет вид^[11]:

${\displaystyle r=1-{\frac {H(A)}{{\bar {n}}\log _{2}(D)}}.}$

Следовательно, использование кода, у которого ${\displaystyle {\bar {n}}\rightarrow H(A)/\log _{2}(D)}$, почти полностью устраняет избыточность без потери информации. В этом случае ${\displaystyle H(X)\rightarrow H_{max}(X)}$, то есть кодовые символы должны быть практически равновероятными и независимыми друг от друга^[11].

Сжатие без потерь может быть реализовано с помощью кодирования Хаффмана, кодирования Лемпеля — Зива — Велча или арифметического кодирования.

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

• Избыточность источника далеко не всегда соответствует свойствам канала и не может быть полностью использована для повышения точности декодирования, так как всегда можно выбрать наиболее согласованный с каналом помехоустойчивый код.
• Часть используемых помехоустойчивых кодов позволяет производить обнаружение и исправление ошибочно принятых последовательностей с помощью относительно простых правил в процессе декодирования, в то время как избыточность источника часто обусловлена весьма сложными зависимостями между его символами (например, в текстовом файле) и позволяет обнаружить ошибки после декодирования символов за счет догадок.
• Когда непосредственным получателем сообщений является не человек, а машина, избыточность источника весьма трудно использовать для повышения точности приёма. При этом сознательно внесённая кодером канала избыточность, согласованная со свойствами канала, позволяет повысить точность передачи информации^[12].

• Обнаружение и исправление ошибок
• Алгоритмическая теория информации
• Колмогоровская сложность