Властивості ентропії

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 4. Властивості ентропії

Висновки

Контрольні питання

1. Поясніть блочне шифрування в режимі простої заміни.

2. Поясніть блочне шифрування в режимі зчеплення блоків

3. Поясніть блочне шифрування в режимі зворотного зв'язку з шифртекстом.

4. Як може застосуватися блокове шифрування у протоколі аутентифікації?

5. Поясніть алгоритм блокового шифрування DES.

6. Поясніть алгоритм блокового шифрування потрійний DES.

7. Поясніть алгоритм блокового шифрування IDEA.

Задачі

Задача 4.1. Опишите процесс дешифрования в режиме обратной связи по шифртексту.

Задача 4.2. Рассмотрим блочный шифр, используемый в режиме сцепления блоков. Предположим, что в процессе передачи -й блок шифртекста оказался испорчен. На какое число блоков открытого текста это повлияет? Ответьте на тот же вопрос для режима обратной связи с шифртекстом.

Задача 4.3. Можно ли в системе IDEA, сохранив общую схему и элементарные операции, увеличить длину рабочих блоков? (Длина таких блоков в IDEA составляет 16 битов.) Какая проблема при этом возникает?

1.... Властивості ентропії 1

2.... Ентропія при безперервному повідомленні 4

1. Дмитриев В.И. Прикладная теория информации. Учебник для студентов ВУЗов по специальности «Автоматизированные системы обработки информации и управления». – М.: Высшая школа, 1989 – 320 с.

Більш детально розглянемо ентропію шляхом визначення її властивостей та формулювання ентропії безперервного повідомлення.

При равновероятности знаков алфавита из формулы Шеннона получают:

.

Из этого следует, что при равновероятности знаков алфавита энтропия определяется исключительно числом знаков m алфавита и по существу является характеристикой только алфавита источника сообщений.

Если же знаки алфавита неравновероятны, то алфавит можно рассматривать как дискретную случайную величину, заданную статистическим распределением частотпоявления знаков (или вероятностей ) табл. 2.1:

Таблица 2.1.

Такие распределения получают обычно на основе статистического анализа конкретных типов сообщений (например, русских или английских текстов и т.п.).

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

На основании выражения

,

величину можно рассматривать как частную энтропию, характеризующую информативность знака , а энтропию H - как среднее значение частных энтропий.

Функция отражает вклад знака в энтропию H. При вероятности появления знака эта функция равна нулю, затем возрастает до своего максимума, а при дальнейшем уменьшении стремится к нулю (функция имеет экстремум, рис. 2.1).

Рис. 2.1. Графики функций и

Для определения координат максимума этой функции нужно найти производную и приравнять ее к нулю.

Учтем следующее: , , откуда , . Таким образом, функция при имеет максимум: , т.е. координаты максимума .

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

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

Энтропия максимальна,если все знаки алфавита равновероятны, т.е.
.

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

Если источник информации имеет, например, два возможных состояния с вероятностями 0,99 и 0,01, то неопределенность выбора у него значительно меньше, чем у источника, имеющего два равновероятных состояния.

Действительно, в первом случае результат практически предрешен (реализация состояния, вероятность которого равна 0,99), а во втором случае неопределенность максимальна, поскольку никакого обоснованного предположения о результате выбора сделать нельзя. Ясно также, что весьма малое изменение вероятностей состояний вызывает соответственно незначительное изменение неопределенности выбора.