2. Ентропія джерел дискретних повідомлень

Нехай ДДП описується деякою дискретною ймовірнісною моделлю .

Означення. Ентропією ДДП (або ентропією випадкового символу ) називається величина, яка визначається функціоналом

(1)

де – символ математичного сподівання.

Якщо в (l) логарифм береться за основою , то ентропія вимірюється вбітах (bit = binary digit), а якщо використовується натуральний логарифм за основою , то ентропія вимірюється унатах (nat = naturаl digit).

Ми будемо користуватися логарифмом за основою , отже, вимірювати ентропію в бітах.

Зауваження. Невизначеність , що зустрічається в (1) розв’язується таким чином:.

Зауваження. Вперше поняття ентропії було введено Хартлі в 1928 р. у вигляді

(2)

для випадкового символу зрівноймовірними значениями, тому (2) іноді і тепер називають ентропією Хартлі. Ентропія в загальному вигляді (1) називається ентропією Шеннона.

Сформулюємо основні властивості функціонала ентропії.

1. Функціонал ентропії набуває невід’ємних значень: , він обертається в 0 тільки для виродженого розподілу:

, ,,.

(Вироджений розподіл відповідає випадку, коли символ не є випадковим:).

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

,

яке досягається, якщо дискретний розподіл – рівномірний, тобто всізначень символів рівноймовірні:.

Наслідок. Чим більше потужність алфавіту, тим більше ентропія Хартлі (максимально можлива ентропія).

3. (властивість адитивності) Якщо випадкові символи ,повідомлення незалежні, то сумісна ентропія дорівнює сумі ентропій:

.

Наслідок. Якщо незалежні в сукупності випадкових символів,, …,, то їх спільна ентропія адитивна:

4. Додавання до алфавіту символів одного символу з нульовою ймовірністю, а отже, і будь-якої кількості таких символів не змінює ентропії ДДП.

3. Умовна ентропія

Щоб вивчити нові важливі властивості ентропії, які використовуються в криптосистемах, введемо поняття умовної ентропії.

Нехай визначений випадковий -вектор символів з деяким-вимірним дискретним розподілом ймовірностей

,

де . Нехай задано натуральне число,і визначений-вимірний дискретний розподіл ймовірностей підвектораза умови, що зафіксований підвектор:

.

(Тут використана формула множення ймовірностей).

Означення. Умовною ентропією підвектору за умови, що зафіксований підвекторназивається функціонал

(3)

Означення. Умовною ентропією підвектору символів відносно випадкового підвектору символівназивається функціонал, отриманий усереднюванням (3):

(4)

Продовжимо дослідження властивостей ентропії і умовної ентропії з урахуванням введених понять.

Теорема 1. Якщо підвектори випадкових символів , незалежні, то умовна ентропія збігається з безумовною:

Теорема 2. Для будь-якої послідовності випадкових символів повідомлення ентропія маєвластивість ієрархічної адитивності:

.

Наслідок. Якщо випадкові символи повідомлення незалежні в сукупності, то ентропія має властивість адитивності 3:

Теорема 3. Умовна ентропія не може перебільшувати безумовну:

.

Наслідок 1. При додаванні умов умовна ентропія не збільшується:

.

Наслідок 2. Ентропія послідовності випадкових символів повідомлення не перебільшує суми ентропій кожного символу:

Теорема 4. При дискретному функціональному перетворенні повідомлення ентропія не збільшується:

,

причому рівність досягається тоді і тільки тоді, коли – бієкція.

Введений в (1) функціонал ентропії Шеннона має всі властивості, які необхідно вимагати від кількісної міри невизначеності. Тому ентропію Шеннона і використовують в криптології як кількісну міру невизначеності повідомлення. Причому функціонал ентропії Шеннона є єдиним функціоналом, що має вивчені властивості. Має місце теорема

Теорема 5 (єдиності функціоналу ентропії). Нехай для будь-якого натурального числа функціязмінних

, ,

неперервна по сукупності аргументів і має наступні три властивості:

а) максимальне значення функції досягається при рівномірному розподілі:

б) ієрархічна аддитивність:

в) додавання до алфавіту, що складається з символів, одного символу

з нульовою ймовірністю () не змінює значення ентропії:

.

Тоді ця функція необхідно має шенноновський вигляд:

де – довільна додатна константа.