Цей мінімум визначається ентропією джерела, яка характеризує його стстистичні властивості. Таке кодування називається ефективним статистичним кодуванням.
При відсутності шумів потрібно забезпечити без надмірне кодування, передаючи найбільш вірогідні відліки та ділянки інформації найкоротшими кодовими символами.
2. Для каналу із спотвореннями існує спосіб кодування з виправленням помилок за рахунок надмірності, при якій буде передаватися інформація із будь-якою високою достовірнітю. Тобто з малою ймовірністю помилок, незважаючи на шуми в каналі. При цьому швидкість передачі Н на повинна перевищувати пропускну здатність каналу зв’язку.
Існує велика кількіть завадостійких кодів. Серед них розглянемо манчестерський код.
В цьому коді кожний розряд двійкового початкового коду записується в вигляді 2-х елементів
0→01 1→10
Таким чином в комбінації 0110→ 0110101.
Приймальний пристрій в кожному такті, який складається із двох сусідніх елементів кореляційного коду повинен зафіксувати перехід із 0 в 1 або із 1 в 0. Коли прийнято два нулі чи дві одиниці, то зразу фіксується помилка.
Кореляційний код надає можливість виявляти помилки будь-якої кратності. Однак він не може виявити двокртатні зеркальні помилки.
4.1 Надмірність зображень
Термін «надмірність» носить статистичний характер. Він визначає середню кількість інформації (ентропію), що містить повідомлення. Якби всі можливі повідомлення, що підлягають передачі, були незалежні один від одного і рівноможливі, то вони мали би максимальну кількість інформації. Уявимо собі двохградаційне зображення, що складається з випадково розташованих незалежних один від одного чорних і білих елементів. Приймемо імовірності появи чорного Р1 і білого Р2 елементів рівними: Р1=Р2=0,5. Тоді середня кількість інформації, що міститься в одному елементі
Якби всі рівні яскравості квантованого на N рівнів напівтонового зображення були рівноможливі і незалежні, то кожен рівень яскравості містив би Н=log2N біт. При N=128 H=16 біт. Насправді реальні зображення містять набагато меншу кількість інформації, що пояснюється наявністю сильних зв'язків елементів у зображенні. Однак повний підрахунок цих зв'язків являє собою важко розв'язну задачу. Тому, обмежуються розглядом зв'язків найближчих декількох елементів. Це дає занижене значення ентропії. Так, для двоградаційного зображення «середнього» газетного і машинописного тексту була отримана оцінка 0,06<H<0,23 біт/елемент. Використовуємо величину Нтах/Н, називану коефіцієнтом стискання, що показує, у скільки разів можна зменшити число двійкових цифр для представлення повідомлень джерела з ентропією Н у порівнянні з тим, коли всі повідомлення рівноможливі. У розглянутому випадку Нмах/Н= 16,6÷4.
Оскільки пропускна здатність каналу (біт/с) без обліку перешкод З = H/τ0, де τ0 — тривалість двійкового сигналу, то
Тому пропускна здатність каналу для передачі факсимільного зображення у виді тексту може бути збільшена мінімум у 4 рази.
Надмірність зображення
Для розглянутого факсимільного зображення надмірність R= 0,94÷0,77.
Для збільшення пропускної здатності каналу необхідно усувати надмірність сигналу зображення. Як видно з попереднього, можна або в 4(16) разів збільшити пропускну здатність (розширивши смугу каналу), або, залишивши ту ж пропускну здатність, у стільки ж раз зменшити смугу частот.
4.2 Ефективне кодування зображень
Перш ніж розглянути деякі методи кодування для усунення надмірності, необхідно зазначити, що при вирішенні цієї задачі варто враховувати перешкоди в каналі зв'язку. У реальних зображеннях між елементами є сильні зв'язки, саме тому зображення об'єктів можна виділити на тлі перешкод, оскільки перешкоди такими зв'язками не володіють.
Побудова ефективної системи зв'язку повинна задовольняти двом суперечливим вимогам — збільшенню пропускної здатності і збереженню при цьому заданої якості відтворення зображення.
Оптимізація системи передачі відразу по двох критеріях являє собою важку і дотепер невирішену задачу. На практиці поступають таким чином: спочатку усувають надмірність джерела повідомлень, а потім для підвищення вірності вносять надмірність штучним шляхом, наприклад застосовуючи завадостійке кодування. Нижче обговорюються деякі способи скорочення надмірності. Для простоти ці способи викладені для двохградаційних зображень, хоча усі вони застосовні і до напівтонових зображень.
Теорія інформації вказує на принципові можливості застосування статистичного кодування. Використання статистичних властивостей дозволяє зменшити загальну «довжину» повідомлень і, отже, необхідний час для їхньої передачі. У загальному виді задачу стиску дискретного сигналу методами статистичного кодування вирішують, скорочуючи середнє число елементів у кодових комбінаціях, що представляють вихідний сигнал. Чим більше імовірність появи даних елементів у вихідному повідомленні, тим менше повинна бути довжина відповідної кодової комбінації.
Алфавітом повідомлень називається безліч повідомлень, що підлягають передачі. Наприклад, при передачі телеграм алфавіт повідомлень складається з 32 букв, цифр і деяких службових знаків і є кінцевим алфавітом. У випадку передачі сигналів двохградаційного зображення елементами алфавіту служать різні реалізації сигналу, точніше «довжини» відрізків, що представляють білі і чорні полючи в зображенні. Безліч цих довжин — серій білого і чорного — складають алфавіт повідомлень.
Задачею ефективного кодування, яке дозволяє щонайкраще використовувати канал зв'язку, є представлення елементів алфавіту кодовими комбінаціями (словами), що складаються з мінімального числа розрядів (коду).
У випадку рівномірного кодування, коли всі кодові комбінації однакової довжини, і мінімальна довжина кодової комбінації п, з кінцевим алфавітом повідомлень визначається зі співвідношення
тп=N,
де т — основа коду; N — число «букв» алфавіту; п — довжина кодової комбінації. Ефективним є такий код, при якому букви, які часто зустрічаються передаються більш короткими комбінаціями. Звідси випливає, що статистичне кодування повинне використовувати нерівномірні коди.
У випадку статистичного кодування сигналу двохградаційного зображення задача ускладнюється тим, що алфавіт даного джерела повідомлень дуже великий: «довжини» обмежені форматом переданого зображення і мінімальним розміром одиничного штриха. Оскільки всередині цього інтервалу довжина серій може змінюватися випадково, то має сенс говорити тільки про середні характеристики цієї довжини.
Теоретично показано, що у випадку ефективного кодування мінімальна середня довжина кодової комбінації
де Н — ентропія повідомлення; т — основа коду.
Для двійкового коду
Відношення до реально досягнутої в даному коді середньої довжини кодового слова називається ефективністю коду:
Загальне правило знаходження ефективного коду невідоме, однак запропоновані алгоритми кодування, у яких величина близька до Ці алгоритми задовольняють наступним умовам:
· довжина даної кодової комбінації повинна бути зворотньо пропорційна ймовірності відповідного елемента алфавіту;
· у довгій кодовій комбінації елементи коду повинні бути незалежні і рівноможливі.
Цим умовам відповідають, наприклад, відомі коди Хаффмена і Фано-Шеннона.
Труднощі практичної реалізації ефективного кодування зв'язані з нерівномірністю надходження в канал кодових комбінацій, тому що останні мають різну довжину. Для того щоб швидкість передачі була постійною, необхідно між кодером і передавачем установлювати узгоджуючий пристрій, що представляє собою блок пам'яті великої ємності.
На практиці використовують найбільш прості способи статистичного кодування. Серед них велике поширення для стискання факсимільних сигналів одержав спосіб кодування довжин серій (КДС).
Сигнал представляється серіями білого і чорного: білому полю відповідає серія нулів, а чорному — серія одиниць. Суть способу полягає в кодуванні довжин серій. У канал передається номер довжини даної серії.
Оскільки довжини серій різні, довжини кодових комбінацій будуть неоднаковими. Цей спосіб буде найбільш ефективним, якщо використовувати вищезгадані принципи кодування, але при цьому пристрій, що кодує, буде складним. Обмежити кількість довжин серій (кількість кодових комбінацій) можна, використовуючи статистичні властивості серій. Наприклад, для зображення метеокарт доцільно білі серії кодувати шестиелементними кодовими комбінаціями, а чорні серії — трьохелементними. За допомогою цих кодових комбінацій можна закодувати всі білі серії довжиною від 1 до 63 елементів (26=64), а всі чорні серії довжиною від 1 до 7 елементів (23=8). Якби за кожною білою серією випливала чорна, то послідовність кодових комбінацій представляла б собою регулярно змінюючі один одного шести- і трьохелементні кодові групи (рис. 3.1).
Якщо ж у зображенні зустрічаються довжини, більші чим 63 чи 7 елементів (для чорних серій), то регулярність чергування кодових комбінацій порушується і для правильного прийому необхідно використовувати службові кодові комбінації, що розділяли б відповідні кодові слова (рис. 3.2). При передачі метеокарт подібний спосіб кодування практично дозволив одержати коефіцієнт стискання до 80%, тобто приблизно на 80% зменшується загальна кількість переданих двійкових чисел.
У розглянутому способі КДС використані статистичні властивості сигналу, що відповідає рядку розгортки зображення. Врахування міжрядкових зв'язків у зображенні може ще більше підвищити ефективність кодування. Дійсно, з огляду на високу роздільну здатність передавальної апаратури і властивості зображення (сусідні рядки «дуже схожі» один на одного), сигнали можна кодувати одночасно. Спочатку один рядок зображення віднімається з іншого (сусіднього), і далі кодується різницевий сигнал
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
