14.2.2. Энтропия и неопределенность

Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.2.2. Энтропия и неопределенность

Как обсуждалось в главе 9, объем информации в сообщении связан с вероятностью появления сообщения. Сообщения вероятности 0 либо 1 не содержат информации, поскольку можно с известной долей определенности предсказать их появление. Чем больше неопределенности существует в предсказании появления сообщения, тем больше оно содержит информации. Следовательно, если все сообщения множества равновероятны, мы не можем быть уверенными в возможности предсказания появления конкретного сообщения, и неопределенность информационного содержания сообщения является максимальной.

Энтропия Н(К) определяется как средний объем информации на сообщение. Она может рассматриваться как мера того, насколько в выбор сообщения X вовлечен случай. Она записывается как следующее суммирование по всем возможным сообщениям.

                                             (14.5)

Если, как выше, логарифм берется по основанию 2, Н(Х) представляет собой математическое ожидание числа битов в оптимально закодированном сообщении X. Это все еще не та мера, которую хотел бы иметь криптоаналитик. Им будут перехвачены некоторые шифрованные тексты, и он захочет узнать, насколько достоверно он может предсказать сообщение (или ключ) при условии, что был отправлен именно этот конкретный шифрованный текст. Неопределенность, определенная как условная энтропия X при данном Y, является для криптоаналитика более полезной мерой при попытке взлома шифра. Она задается с помощью следующей формулы.

            (14.6)

Неопределенность может рассматриваться как неуверенность в том, что отправлено было сообщение X, при условии получения Y. Желательным для криптоаналитика является приближение H(X|Y) к нулю при увеличении объема перехваченного шифрованного текста Y.

Пример 14.3. Энтропия и неопределенность

Рассмотрим выборочное множество сообщений, состоящее из восьми равновероятных сообщений {X} = Х1, Х2, ... Х8.

а)    Найдите энтропию, связанную с сообщением из множества {X}.

б)   Дано другое множество равновероятных сообщений {Y}=Y1, Y2. Пусть появление каждого сообщения Y сужает возможный выбор X следующим образом.

При наличии Y1 возможны только Х1, Х2, Х3или Х4

При наличии У2 возможны только Х5, Х6, Х7 или Х8

Найдите неопределенность сообщения X, обусловленную сообщением Y.

Решение

а) Р(Х)=

    Н(Х) =  = 3 бит/сообщение

б) Р(Y)=. Для каждого Y,   P(X|Y)=для четырех сообщений из множества {X} и P(X|Y)=0  для оставшихся четырех. Используя уравнение (14.6), получим следующее.

H(X|Y)== 2 бит/сообщение

Видно, что знание Y сводит неопределенность X с 3 бит/сообщение до      2 бит/сообщение.









© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.
E-mail: formyneeds@yandex.ru