Тема 5. Характеристики дискретних джерел інформації

План

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

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

 

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

Нехай дискретне джерело X видає послідовність повідомлень {xi}, заданих рядом ймовірностей {pi}.

Якщо джерелом вибирається одне повідомлення xi, то ним виробляється певна кількість інформації. Тоді швидкість утворення джерелом інформації повідомлень - продуктивність джерела щодо конкретного повідомлення можна визначити так:

 

,                                                                    (5.1)

 

де через ti позначено проміжок часу вибору повідомлення xi.

Оскільки джерелом за деякий часовий інтервал вибирається велика кількість повідомлень і в загальному випадку ti¹tj, то продуктивність джерела інформації прийнято характеризувати середнім значенням

 

,                                          (5.2)

 

де tсер – середній час вибору джерелом одного повідомлення.

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

Повідомлення xi передається по каналу зв'язку спостерігачеві Y, роль якого відіграє приймальний пристрій. Вибір повідомлень yjÎY джерелом Y характеризує процес передачі інформації по каналу зв'язку від джерела X на вихід джерела Y. При цьому взаємна кількість інформації I(X, Y) - це середня кількість інформації про стан джерела X, що міститься в одному повідомленні джерела Y.

Оскільки на вибір кожного повідомлення yj джерелом Y витрачається час t, то швидкість передачі інформації по каналу зв'язку знаходиться за формулою

 

.                                                           (5.3)

2. Інформаційні втрати при передачі інформації по дискретному каналу зв'язку

.Математично канал дискретної інформації описується ансамблем повідомлень на вході {xi}, {pi} та йому відповідними йому значеннями на виході {yj}, а також набором умовних ймовірностей p(yj/xi) вибору сигналу yj на виході при передачі сигналу xi.

Задача каналу зв'язку полягає в тому, щоб отримати однозначну відповідність повідомлення yi  повідомленню xi, тобто повинна виконуватися умова p(yi/xi)=1 при i=j і p(yj/xi)=0 при i¹j. У цьому випадку канал зв'язку називається каналом без шуму.

Виконання умов використання каналу без шуму означає повний збіг ансамблів X і Y, тобто повний статистичний взаємозв'язок джерел. Звідси випливає, що

 

H(X/Y)=H(Y/X)=0.                                                    (5.4)

 

Тоді середня кількість інформації на одне повідомлення джерела X, яка дорівнює ентропії H(X), при повній відсутності інформаційних втрат відповідає такій самій кількості прийнятої інформації H(Y), тобто

 

I(X,Y)=H(X)=H(Y)=H(X,Y).                                          (5.5)

Отже, при відсутності завад кількість переданої інформації дорівнює ентропії об'єднання двох джерел або безумовної ентропії одного з них.

При високому рівні завад спостерігається повна статистична незалежність джерел X і Y, тобто

 

H(X/Y)=H(X),                                                      (5.6)

 

H(Y/X)=H(Y),                                                      (5.7)

     

H(X,Y)= H(X)+H(Y).                                              (5.8)

 

У даному випадку через сильний вплив завад порушується взаємозв'язок джерел, і інформація від джерела X джерелу Y не передається, отже,

 

I(X, Y)= 0.                                                        (5.9)

 

У проміжному випадку неабсолютного статистичного взаємозв'язку джерел X, Y завади деякою мірою спотворюють передані повідомлення. При цьому умовна ентропія змінюється в межах від нуля (при повній статистичній залежності джерел) до безумовної ентропії (за відсутності статистичної залежності джерел), тобто

 

£ H(X/Y£ H(X),                                     (5.10)

 

0 £ H(Y/X) £ H(Y).                                                  (5.11)

 

Кількість інформації, що передається джерелом X спостерігачу Y, можна визначити так. Якщо джерелом X вибрано повідомлення xiÎX, то ним, в середньому, передається кількість інформації H(X). Джерело Y, вибравши повідомлення yjÎY, за умови порушення повної статистичного залежності джерел X і Y виробляє певну кількість інформації H(X/Y).

Після вибору повідомлення yjÎY джерелом Y приймається рішення щодо того, яке з повідомлень xiÎX передане. Прийнявши це рішення, джерело Y виробляє кількість інформації про стан джерела X, яка дорівнює HX. Проте до цього джерело Y вже має H(X/Y) бітів інформації про X, тому кількість переданої по каналу зв'язку інформації як кількість нового відсутнього знання визначається різницею HX і H(X/Y):

 

I(X, Y)=H(X)-H(X/Y).                                    (5.12)

 

Вираз (5.12) за відсутності завад збігається з виразом (5.5), а при високому рівні завад, тобто при виконанні умови статистичної незалежності джерел (5.6 – 5.8) - з виразом (5.9).

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

З властивості симетричності взаємної ентропії випливає рівність

 

H(X)+H(Y/X)=H(Y)+H(X/Y).                                      (5.13)

 

Віднявши від обох частин цієї рівності суму H(X/Y)+H(Y/X), дістанемо

 

H(X)-H(X/Y)=H(Y)-H(Y/X).                                          (5.14)

 

Звідси випливає властивість симетричності взаємної інформації

 

I(X, Y)=I(Y, X).                                                      (5.15)

 

            Скориставшись виразами (5.12), (5.13), (5.15), маємо

 

I(X,Y)=HX-H(X/Y)=HX-(H(X,Y)-HY)=HX+HY-H(X,Y),                (5.16)

 

I(Y,X)=HY-H(Y/X)=HY-(H(Y,X)-HX)=HY+HX-H(Y,X),                 (5.17)

 

чим доводяться властивість 4 кількості інформації і повна симетричність виразів (5.16), (5.17).

 

2.    Пропускна здатність дискретного каналу. Основна теорема про кодування дискретного джерела.

Максимально можлива швидкість передачі інформації по каналу називається пропускною здатністю, або ємністю  каналу зв'язку С.

Виходячи з виразів (5.3) і (5.12), дістанемо формулу

 

.                             (5.18)

 

Очевидно, що вираз (5.18) досягає максимуму при абсолютній статистичній залежності джерел X, Y, тобто за відсутності або при малому рівні завад. У цьому випадку H(X/Y)=0, і оскільки ентропія максимальна у разі рівноімовірних повідомлень, то формула (5.18) набуває вигляду:

 

        .                                              (5.19)

Вираз (5.19) визначає пропускну здатність за відсутності завад.

У разі, коли в каналі наявні завади, умовна ентропія на його вході і виході H(X/Y) знаходиться в діапазоні £ H(X/Y£ H(X). Тоді пропускна здатність каналу визначається за формулою

 

 .                                               (5.20)

 

При зменшенні рівня завад пропускна здатність каналу C прямує до максимального значення (5.19), а при збільшенні рівня завад – до нуля.

Основна теорема кодування дискретного джерела, сформульована і доведена К. Шенноном, полягає в такому.

Припустимо, що при передачі інформації використовується канал без шуму. Розглянемо безнадмірні (рівноймовірні) вхідні повідомлення, що характеризуються максимальною ентропією H(X)max. У цьому випадку може бути досягнута максимальна швидкість передачі в каналі

 

,                                             (5.21)

 

де V=1/T; T - тривалість передачі одного елементарного повідомлення (символу) xi; logk - максимальна ентропія джерела з алфавітом об'ємом k.

            Якщо статистична надлишковість джерела інформації більше нуля, то швидкість передачі інформації по каналу

 

.                                                            (5.22)

 

Як доведено К. Шенноном, при будь-якій статистичній надмірності джерела інформації існує такий спосіб кодування повідомлень, при якому може бути досягнута швидкість передачі інформації по каналу без шуму, скільки завгодно близька до його пропускної здатності. Таким чином, умовою узгодженості джерела інформації і каналу передачі є відповідність продуктивності першого пропускній здатності другого.

Теорема Шеннона про кодування дискретного джерела за відсутності завадОшибка! Закладка не определена. стверджує про таке.

Якщо пропускна здатність каналу без шуму перевищує швидкість створення джерелом повідомлень - його продуктивність, тобто

,

то існує спосіб кодування/ декодування повідомлень джерела з ентропією H(X), що забезпечує скільки завгодно високу надійність зіставлення прийнятих кодових комбінацій переданим, інакше - такого способу немає.

За наявності завад в каналі основна теорема кодування узагальнюється такою теоремою:

Якщо для будь-якого повідомлення дискретного джерела X задана ймовірність його спотворення в каналі e, то для будь-якого e > 0 існує спосіб передачі інформації зі швидкістю

,

скільки завгодно близькою до

,

при якому ймовірність помилки в каналі буде менше e. Цей спосіб утворює завадостійкий код.

Фано доведена зворотна теорема кодування джерела за наявності завад:

Якщо швидкість передачі інформації по каналу зв'язку з шумом , то можна знайти таке e > 0, що ймовірність помилки при передачі повідомлення при будь-якому методі кодування/ декодування буде не менше e (очевидно e зростає із зростанням ).

 

Приклад 1.  Матриця сумісних ймовірностей каналу зв'язку має вигляд

.

            Знайти інформаційні втрати, пропускну здатність і швидкість передачі інформації по дискретному каналу зв'язку, якщо час передачі одного повідомлення t=10-3 с. 

Розв'язання

            Інформаційні втрати в каналі зв'язку визначаються умовною ентропією H(X/Y) одного джерела щодо іншого.

            Для того щоб обчислити повну умовну ентропію H(X/Y), потрібно знайти розподіли безумовних ймовірностей p(xi), p(yj) і побудувати матрицю умовних ймовірностей p(xi/yj).

            Безумовний закон розподілу p(xi) знаходимо, виконавши в матриці сумісних ймовірностей p(xi, yj) згортку за j:

p(x1)= 0,15+0,15+0=0,3,  i=1;

p(x2)= 0+0,25+0,1=0,35,  i=2;

p(x3)= 0+0,2+0,15=0,35,  i=3.

            Перевіряємо умову нормування

p(x1)+ p(x2)+ p(x3)=0,3+0,35+0,35=1.

            Виходячи з розподілу безумовних ймовірностей д. в. в. X, обчислимо її ентропію:

(біт/сим).

      Безумовний закон розподілу p(yj) знаходимо, виконавши в матриці сумісних ймовірностей p(xiyj) згортку за i:

p(y1)= 0,15+0+0=0,15,  j=1;

p(y2)= 0,15+0,25+0,2=0,6,  j=2;

p(y3)= 0+0,1+0,15=0,25,  j=3.

            Перевіряємо умову нормування:

p(y1)+ p(y2)+ p(y3)=0,15+0,6+0,25=1.

            Матрицю умовних ймовірностей знаходимо, скориставшись формулою множення ймовірностей  p(xi, yj)=p(yj)×p(xi/yj).

            Звідси випливає, що .

            Отже, матриця умовних ймовірностей p(xi/yj) знаходиться так:

.

            Для матриці умовних ймовірностей p(xi/yj) повинна виконуватися умова нормування

.

            Перевіряємо цю умову:

,

,

.

            Скориставшись матрицею умовний ймовірностей p(xi/yj), обчислимо часткові умовні ентропії X стосовно Y:

(біт/сим);

(біт/сим);

           (біт/сим).

            Виходячи з безумовного закону розподілу д. в. в. Y та знайдених часткових умовних ентропій H(X/yj), відшукуємо їх математичне сподівання – загальну умовну ентропію

(біт/сим). 

      Отже, інформаційні втрати в каналі зв'язку  H(X/Y)»1,18 (біт/сим).

            Пропускна здатність каналу із шумом обчислюється за формулою

,

де через k позначено об'єм алфавіту джерела; t - час вибору повідомлення джерелом.

      Отже, отримаємо (бод).

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

I(XY)=HX-H(X/Y)=1,581-1,176»0,406 (біт/сим).

            Швидкість передачі інформації  знаходиться так:

(бод).

            Відповідь:  H(X/Y)»1,18 (бітим);  C»409 (бод); v=406 (бод).