6.29) ставленням
Лекції з Теорії передачі сигналів
6. Елементи теорії інформації
6.5. Оптимальне статистичне кодування повідомлення
Для дискретних каналів без перешкод Шенноном була доведена наступна теорема:якщо продуктивність джерела ,деε-завжди мала величина, то завжди існує спосіб кодування, що дозволяє передавати по каналу всі повідомлення джерела. Передачу всіх повідомлень при здійснити неможливо.
Сенс теореми зводиться до того, що як би не була велика надмірність джерела, всі його повідомлення можуть бути передані каналом, якщо. Зворотне твердження теореми легко доводиться протилежного. Припустимо,,але передачі всіх повідомлень джерела каналом необхідно, щоб швидкість передачіRбула менше. Тоді маємо,що неможливо, оскільки за визначенням пропускна спроможність .
Для раціонального використання пропускної спроможності каналу необхідно застосовувати відповідні способи кодування повідомлень.Статистичнимабооптимальнимназивається кодування, при якому найкраще використовується пропускна здатність каналу без перешкод. При оптимальному кодуванні фактична швидкість передачі по каналуRнаближається до пропускної здатностіС,що досягається шляхом узгодження джерела з каналом. Повідомлення джерела кодуються таким чином, щоб вони найбільшою мірою відповідали обмеженням, які накладаються на сигнали, що передаються каналом зв'язку. Тому структура оптимального коду залежить від статистичних характеристик джерела, і від особливостей каналу.
Розглянемо основні засади оптимального кодування з прикладу джерела незалежнихповідомлень, які необхідно узгодити з двійковим каналом без перешкод. За цих умов процес кодування полягає у перетворенні повідомлень джерела у двійкові кодові комбінації. Оскільки має місце однозначна відповідність між повідомленнями джерела та комбінаціями коду, то ентропія кодових комбінацій дорівнює ентропії джерела:
(6.34)
а швидкість передачі в каналі визначається виходячи з (6.29) ставленням
(6.35)
Тут середня тривалість кодової комбінації, яка в загальному випадку нерівномірного коду записується за аналогією з виразом (6.26) як
(6.36)
де - Тривалість одного елемента коду і, - Число елементів в комбінації, що присвоюється повідомленню .
Підстановка у ф-лу (6.35) виразів (6.6) і (6.36) призводить до співвідношення
(6.37)
в якому чисельник визначається виключно статистичними властивостями джерела, а величина характеристиками каналу. При цьому виникає питання, чи можна закодувати повідомлення, щоб швидкість передачіR(6.37) досягла свого максимального значення, рівного пропускної здатності двійкового каналуС=1/. Легко помітити, що ця умова виконується, якщо
(6.38)
що відповідає мінімуму і максимумуR.Очевидно, вибірC,що суперечить вище доведеному твердженню теореми Шеннона.
Одним із кодів, що задовольняють умові (6.38), є код Шеннона-Фано. Для ознайомлення з принципами його побудови розглянемо як приклад джерело повідомлень, що виробляє чотири повідомлення та з ймовірностями: ; ;
Усі повідомлення виписуються в кодову таблицю (табл. 6.1) у порядку зменшення їх ймовірностей. Потім вони поділяються на дві групи так, щоб суми їх ймовірностейможливості були однаковими. У даному прикладі в першу групу входить повідомлення з ймовірністю і в другу - повідомлення з сумарною ймовірністю, також дорівнює 0,5.
Комбінаціям, які відповідають повідомленням першої групи, приховується як перший символ коду 0, а комбінаціям другої групи -1. Кожна з двох груп знову ділиться на дві групи із застосуванням того ж таки правила присвоєння символів 0 і 1.
В ідеальному випадку після першого поділу ймовірності кожної групи повинні дорівнювати 0,5, після другого поділу - 0,25 і т. д. Процес поділу триває доти, поки в групах не залишиться по одному повідомленню.
При заданому розподілі ймовірностей повідомлень код виходить нерівномірним, його комбінації мають різну кількість елементівпi,причому, як неважко помітити, такий спосіб кодування забезпечує виконання умови (6.38) повністю для всіх повідомлень.
У нерівномірних кодах при декодуванні виникає труднощі щодо меж між комбінаціями. Для усунення можливих помилок зазвичай використовуються спеціальні розділові знаки. Так, у коді Морзе між літерами передається розділовий знак у вигляді паузи тривалістю в один тир. Передача розділових знаків займає додатковий час, що знижує швидкість передачі.
Важливою властивістю коду Шеннона-Фано є те, що, незважаючи на його нерівномірність, тут не потрібні знаки розподілу. Це пов'язано з тим, що короткі комбінації є початком довших комбінацій. Вказану властивість легко перевірити на прикладі будь-якої послідовності:
Таким чином, всі елементи закодованого повідомлення мають корисну інформацію, що при виконанні умови (6.38) дозволяє отримати максимальну швидкість передачі.Вона може бути знайдена також шляхом безпосереднього обчислення ф-ле (6.37)'
(6.39)
Для порівняння розглянемо кодування тих же чотирьох повідомлень ,, із застосуванням звичайного рівномірного двійкового коду. Кількість коміацій при цьому визначається виразом деn— кількість елементів у комбінації. Оскількиm=4, то,а тривалість кожної комбінації 2. Виконуючи обчислення за аналогією з (6.39), отримаємо
Пропускна здатність у разі використовується лише частково. З виразу (6.38) випливає основний принцип оптимального кодування. Він зводиться до того, що найбільш вірогідним повідомленням повинні надаватися короткі комбінації, а повідомленням з малою ймовірністю —довші комбінації.
Можливість оптимального кодування за методом Шеннона-Фано доводить, що сформульована вище теорема справедлива принаймні для джерел незалежних повідомлень. Теорема Шеннона може бути підтверджена і для загального випадку залежних повідомлень.
Одним із способів оптимального кодування залежних повідомлень є застосування так званих "ковзаючих" кодів, основна ідея яких полягає в тому, що присвоєння кодових комбінацій за правилом Шеннона-Фано проводиться з урахуванням умовних, а не апріорних ймовірностей повідомлень. Число елементів у кодовій комбінації вибирається як,тобто поточному повідомленню присвоюється та чи інша комбінація в залежності від того, які повідомлення йому передували.
Необхідно підкреслити, що при оптимальному способі кодування сигналів, що передають повідомлення джерела, зовсім відсутня будь-яка надмірність. Усунення надмірності призводить до того, що процес декодування стає дуже чутливим до впливу перешкод. Це особливо сильнопроявляється при оптимальному кодуванні залежних повідомлень. Наприклад, у «ковзаючих» кодах одна єдина помилка може спричинити неправильне декодування всіх наступних сигналів.Тому оптимальні коди застосовні тільки для каналів, в яких вплив перешкод незначний.