Термин сообщение и его трактовка в теории информации

Обновлено: 18.05.2024

Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.

За перевод спасибо Андрею Пахомову.

Остановимся на этом подробнее. Шеннон полагал, что количественная мера информации должна быть непрерывной функцией от вероятности события p, а для независимых событий она должна быть аддитивной – количество информации, полученное в результате осуществления двух независимых событий, должно равняться количеству информации, полученному в результате осуществления совместного события. Например, результат броска игральных костей и монеты обычно рассматриваются как независимые события. Переведем вышесказанное на язык математики. Если I (p) – это количество информации, которое содержится в событии с вероятностью p, то, для совместного события, состоящего из двух независимых событий x с вероятностью p₁ и y с вероятностью p₂ получаем

(x и y независимые события)

Это функциональное уравнение Коши, истинное для всех p₁ и p2. Для решения этого функционального уравнения предположим, что

Если p₁ = p 2 и p₂ = p, тогда

и т.д. Расширяя этот процесс, используя стандартный метод для экспонент, для всех рациональных чисел m / n, верно следующее

Из предполагаемой непрерывности информационной меры, следует, что логарифмическая функция является единственным непрерывным решением функционального уравнения Коши.

В теории информации принято принимать основание логарифма равное 2, поэтому бинарный выбор содержит ровно 1 бит информации. Следовательно, информация измеряется по формуле

Давайте приостановимся и разберемся, что же произошло выше. Прежде всего, мы так и не дали определение понятию “информация”, мы просто определили формулу ее количественной меры.

Во-вторых, эта мера зависит от неопределенности, и, хотя она в достаточной степени подходит для машин — например, телефонных системы, радио, телевидения, компьютеров и т. д. — она не отражает нормального человеческого отношения к информации.

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

Рассмотрим систему, алфавит которой состоит из символов q с вероятностями pi. В этом случае среднее количество информации в системе (её ожидаемое значение) равно:

Энтропия распределения вероятности играет главную роль в теории кодирования. Неравенство Гиббса для двух разных распределений вероятности pi и qi является одним из важных следствий этой теории. Итак, мы должны доказать, что

Доказательство опирается на очевидный график, рис. 13.I, который показывает, что

а равенство достигается только при x = 1. Применим неравенство к каждому слагаемому суммы из левой части:

Если алфавит системы связи состоит из q символов, то принимая вероятность передачи каждого символа qi = 1/q и подставляя q, получаем из неравенства Гиббса

Рисунок 13.I

Это говорит о том, что если вероятность передачи всех q символов одинакова и равна — 1 / q, то максимальная энтропия равна ln q, в противном случае выполняется неравенство.

В случае однозначно декодируемого кода, мы имеем неравенство Крафта

Теперь если мы определим псевдовероятности

где конечно = 1, что следует из неравенства Гиббса,

и применим немного алгебры (помните, что K ≤ 1, поэтому мы можем опустить логарифмический член, и возможно, усилить неравенство позже), то получим

где L — это средняя длина кода.

Таким образом, энтропия является минимальной границей для любого посимвольного кода со средней длиной кодового слова L. Это теорема Шеннона для канала без помех.

(отправитель)
График 13.II

Далее рассмотрим идею о пропускной способности канала. Не вдаваясь в подробности, пропускная способность канала определяется как максимальный объем информации, который может быть надежно передан по каналу связи, с учётом использования максимально эффективного кодирования. Нет доводов в пользу того, что через канал связи может быть передано больше информации, чем его емкость. Это можно доказать для бинарного симметричного канала (который мы используем в нашем случае). Емкость канала, при побитовой отправки, задается как

где, как и раньше, P — вероятность отсутствия ошибки в любом отправленном бите. При отправке n независимых битов емкость канала определяется как

Как может возникнуть ошибка? Ошибка может произойти в случаях, описанных в таблице ниже:

Рисунок 13.III

Мы можем выбросить первый множитель во втором слагаемом, приняв его за 1. Таким образом получим неравенство

повторно применяем к последнему члену справа

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

кодовых словарей, имеющие одинаковую вероятность ½nM. Конечно, случайный процесс создания кодового словаря означает, что есть вероятность появления дубликатов, а также кодовых точек, которые будут близки друг к другу и, следовательно, будут источником вероятных ошибок. Нужно доказать, что если это не происходит с вероятностью выше, чем любой небольшой выбранный уровень ошибки, то заданное n достаточно велико.
Решающим момент заключается в том, что Шеннон усреднил все возможные кодовые книги, чтобы найти среднюю ошибку! Мы будем использовать символ Av [.], чтобы обозначить среднее значение по множеству всех возможных случайных кодовых словарей. Усреднение по константе d, конечно, дает константу, так как для усреднения каждый член совпадает с любым другим членом в сумме,

который может быть увеличен (M–1 переходит в M )

Читайте также: