Лекція 10. Загальні відомості про криптографічні протоколи

Задача 3.2.3

Задача 3.2.2

Задача 3.2.1

Приклади розв’язання задач

Знайти пропускну здатність трійкового стаціонарного каналу без пам’яті, який має таку матрицю перехідних ймовірностей

.

Швидкість передачі символів по каналу v ₀=100 Бод.

Знайти середню кількість інформації, що переноситься одним символом, та швидкість передачі інформації по такому каналу від дискретного немарковського джерела інформації з алфавітом X = { x ₁, x ₂, x ₃}, якщо ймовірності виникнення символів

Часові характеристики джерела та каналу узгоджені, тобто тривалість кожного символу на виході джерела

Розв’язання. Аналізуючи матрицю перехідних ймовірностей каналу, можна зробити висновок, що канал є симетричним в посиленому значенні, тому для розрахунку пропускної здатності каналу скористуємося виразом (3.14):

Швидкість передачі інформації розрахуємо, користуючись виразом (3.8). Щоб отримати H ( Y ), знайдемо за виразом

(3.19)

Маємо p ( y ₁) = 0,556 ; p ( y ₂) = 0,315 ; p ( y ₃) = 0,129 ;

H ( Y ) = 1,377 біт.

Нарешті = 100 × ( 1,377 – 0,557 ) = 82 біт / с.

Для каналу, який має матрицю перехідних ймовірностей

знайти середню кількість інформації, що переноситься одним символом, та швидкість передачі інформації по каналу, якщо до входу каналу підключене марковське стаціонарне дискретне джерело інформації з алфавітом та глибиною пам’яті описується такою матрицею умовних ймовірностей виникнення символу x_i при умові, що йому передував символ x_k :

Розв’язання. Оскільки до входу каналу підключене марковське джерело, вихід каналу теж в загальному випадку буде являти собою марковське джерело, при цьому глибина пам’яті може бути більше одиниці. Це ускладнює застосування виразів (3.6) та (3.8), оскільки для розрахунків недостатньо знати тільки безумовні ймовірності p (y_k) виникнення символів на виході каналу; треба знати також умовні ймовірності p (y_k/s), де s – стан джерела з алфавітом (виходу каналу), який визначається попередніми символами на виході каналу.

Для розрахунку середньої кількості інформації, що переноситься одним символом, доцільніше в цьому випадку користуватись виразом (3.5). Щоб знайти умовну ентропію, треба знайти умовні ймовірності, для чого скористуємося виразом

Ймовірності p (x_i) можна отримати, скористувавшись рівняннями:

Підставивши сюди значення умовних ймовірностей з відповідної матриці та дещо спростивши, будемо мати систему лінійних рівнянь:

Розв'язання системи дає:

Ймовірності p (y_k/x_i) є відомими. Для розрахунку ймовірностей p (y_k) скористуємося виразом (3.19). Маємо

p (x ₁) = 0,70037; p (x ₂) = 0,16802; p (x ₃) = 0,13161.

Тепер знаходимо набір ймовірностей:

.

Умовна ентропія. Тепер потрібно знайти ентропію марковського джерела з глибиною пам’яті. Для використаємо відповідне співвідношення (лек. 5):

,

тоді

Кількість інформації, що переноситься одним символом, з урахуванням значення ентропії:

.

Швидкість передачі інформації по каналу

= v ₀ × I (Y, X) = 100 × 0,601 = 60,1 біт / c.

Отримати вирази для пропускної здатності симетричного в посиленому значенні каналу без пам’яті для довільної потужності алфавіту та для біноміального каналу. Проаналізувати залежність пропускної здатності біноміального каналу від ймовірності помилки в каналі.

Розв’язання. Матриця перехідних ймовірностей для симетричного в посиленому значенні каналу з алфавітом потужності М містить М рядків, М стовпців та має вигляд

.

(3.20)

Тут

Дата добавления: 2013-12-12