Лекція 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)

Тут