Главная Обратная связь

Дисциплины:






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



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

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

(1)

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

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

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

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

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

(2)

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

 

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

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

, , , .

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

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

,

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

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

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

.

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

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

 

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

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

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

,

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

.

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

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

(3)

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

(4)

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



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

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

.

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

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

.

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

.

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

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

,

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

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

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

, ,

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

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

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

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

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

.

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

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

 





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...