Лекція 08. Додатково про стискання із втратами та аналіз дискретного канала із шумом
Курс “Теорія інформації та кодування”

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

Вейвлетне стискання зображень
Фрактальное стискання зображень
Аналіз дискретного каналу із шумом
Підходи до передачі коду каналом з помилками

8.1 Вейвлетне стискання зображень

Ідея методу
Так званий вейвлетний метод стискання зображень втілено в стандарті JPEG-2000, який розроблявся з метою подолання недоліків JPEG. Зокрема, він повинен був забезпечити істотне підвищення ступеня стискання без мозаїчності зображень, а також — в якості опції - можливість стискання без втрат якості.

Ідея методу - стискання за рахунок усереднення характеристик сусідніх пікселів з поступовим зменшенням коду всього зображення (рис.8.1). При цьому:

Рисунок 8.1 До принципа дії методу JPEG-2000

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

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

- описана процедура виконується кілька разів итеративно (на кожному кроці результати попереднього використовуються в якості вихідних даних). При цьому ми як би рухаємося від більш високочастотних складових спектра (відмінності в сусідніх пікселях) до низькочастотних (плавні зміни фону). Саме таке перетворення називають "вейвлетним" (wavelet - «волночка») або якщо повністю - дискретним вейвлетним перетворенням ДВП;

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

- на кожному кроці перетворення відмінності пікселів від середнього (високочастотні складові) можуть огрубляет за рахунок квантування, що дозволяє істотно стискати їх код, але призводить до втрати якості. Візуально таке стискання проявляється як розмивання зображення. При великих ступенях стискання воно сприймається оком більш лояльно в порівнянні з мозаїчністю JPEG, що дозволяє істотно збільшити ступінь стискання (аж до 1:50).

Загальна структура алгоритму JPEG-2000
В цілому в алгоритмі виділяються ті ж основні етапи, що і в JPEG - попередня обробка, спектральне перетворення (тут саме у вейвлетній формі) і кодування (квантування з подальшим стисненням) - ріс.8.2. При цьому:

Рисунок 8.2 Етапність обробки зображення в JPEG-2000

- на етапі попередньої обробки, як і в JPEG, виконується перехід до різностноколірної моделі YUV і проріджування колірних складових. Важлива відмінність полягає в тому, що в JPEG-2000 не відбувається розбиття на мікроблоки 8х8. Зображення може оброблятися або повністю, або (з урахуванням обмежень по використовуваної пам'яті) розбивається на великі квадратні зони тайли (tile - «плитка»), для кожного з яких обробка ведеться незалежно;

- подальша обробка виконується крок за кроком (зазвичай від 4 до 8 итерацій), число яких алгоритм визначає з урахуванням необхідного ступеня стиснення. Оскільки на кожному кроці замість чотирьох чисел зберігається тільки три (за виключенням «діагональних» коефіцієнтів), то навіть без врахування втрат, залишок коду за 4 ітерації може скласти (3/4)4 = 0,32, а за 8 ітерацій (3/4)4 = 0,10 — досить суттєве стискання;

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

Особливості обробки для однієї ітерації перетворення
Етапи обробки всередині кожної ітерації показані на рис.8.3:

Рисунок 8.3 Детальна характеристика ітерації стискання

- кожний крок вейвлетного перетворення включає обчислення середнього значення для четвірки cоседніх пікселів (Lli), а також обчислення напіврізниць по рядку (Hli), стовпцю (Lhi) і діагоналі (Hhi). В результаті такої операції замість чотирьох чисел приблизно одного порядку деоржуємо одне близьке до них число (Lli) і два значно менших (Hli та Lhi). Четверте число (Hhi), як ми вже знаємо, можна не зберігати;
- покажемо аналогічну операцію для двох чисел, наприклад, 125 та 121. Тут середнє (напівсума) складає (125+121)/2 =123, а напіврізниця (125-122)/2=2. Значення 123 та 2 несуть ту ж інформацію, що й 125 та 121 (зокрема 123+2=125, а 123-2=121), однак число 2 значно менше і потребує меншого обсягу коду. У випадку четвірок пікселів додатковий ефект досягається за рахунок зберігання 3-х чисел замість 4-х;
- наступна ітерація вейвлетного перетворення виконується виключно для середніх значень Lli, значення Hli та Lhi або зберігаються незмінними (в режимі стсикання без втрат), або додатково квантуються для наступного статистичного стискання;
- при кодуванні зазвичай спочатку виділяються блоки розміром 32х32 пікселя. Це зручно для стандартизації їх обробки, але також сприяє завадостійкості алгоритму, оскільки можливі спотворення при передачі або зберіганні впливають тільки на невелику частину зображення. Для "підготовчого" кодування використовується досить витончений алгоритм, що забезпечує збільшення кількості нулів (тут ми не станемо розглядати його детально). На кінцевому етапі застосовується арифметичне кодування.

В цілому JPEG-2000 здатний забезпечити майже дворазове збільшення стискання з втратами в порівнянні з JPEG. У частині стискання без втрат він не настільки ефективний і програє спеціалізованим рішенням (зокрема JPEG-LS), проте сама така можливість вигідно відрізняє його від попереднього стандарту. Важливою перевагою JPEG-2000 є можливість вибирати режими стискання для різних зон зображення, а також стійкість до викривлень. Крім того він набагато краще стискає зображення, створені в комп'ютерних редакторах, і зображення документів. Зниження якості зображення проявляється в його згладжуванні («замилюванні»), а при сильному стисненні - також в появі мерехтіння в околицях різких кордонів. Головним недоліком методу є низька швидкість стиснення.

Контрольні питання
1. Розкажіть про ідею методу стиснення в JPEG-2000, спираючись на рис.7.6.
2. Розкажіть про структуру алгоритму JPEG-2000, використовуючи ріс.7.7.
3. Охарактеризуйте особливості етапу підготовки зображення в JPEG-2000.
4. Як реалізується в алгоритмі вейвлетного перетворення. Які переваги дає його застосування.
5. Які особливості етапів огрубіння і кодування в JPEG-2000.
6. У чому полягають переваги та недоліки JPEG-2000 щодо JPEG.


8.2 Фрактальное стиснення зображень

Ідея і область застосування методу
Багато зображень містять схожі один на одного елементи, які різняться лише розташуванням, масштабом, кутами повороту, розтягуванням і т.п. Яскравим прикладом тут може служити гілка папороті, де листя схожі не тільки один на одного, але і на всю гілку в цілому. Про такі елементи кажуть, що вони мають властивість "самоподібності". Принципово важливо, що для них може бути отримано компактний математичний опис на основі варіації параметрів одного єдиного об'єкта-прототипу, який називають фракталом (рис.8.4).

Рисунок 8.4 До принципу фрактального стискання

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

- математичний апарат для формування складних зображень з фракталів досить простий. Класичним прикладом тут часто служить та ж гілка папороті, побудована таким методом (цей приклад пов'язаний з ім'ям відкривача методу і його часто називають «папороттю Барнслі»);

- в силу простоти математичних перетворень швидкість побудови зображення по його фрактальному опису висока (c позицій стиснення даних така операція відповідає декодуванню). Разом з тим, зворотню задачу, - яка включає знаходження схожих ("самоподібних") елементів і визначення відповідних параметрів фракталів для вихідного зображення, - вирішити набагато складніше. На практиці таке рішення, що відповідає кодування зображення, вимагає чималого часу;

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

Поняття про математику фракталів: аффінні перетворення
В основі математичного апарату фрактального стиснення лежить використання математичних "афінних" перетворень (ріс.8.5):

Рисунок 8.5 Поняття про аффінні перетворення

- аффінні перетворення (АП) включають переміщення об'єкта на площині і його повороти (рух), а також його розтягування і стискання щодо точки (масштабування) і щодо прямих (рівномірне розтягнення-стискання на площині);
- важливою особливістю афінних перетворень є збереження деяких властивостей фігур. Зокрема, при АП прямі переходять в прямі, зберігається наявність кривизни і паралельність ліній, відношення довжин відрізків на прямій і співвідношення площин;

- для фрактальних перетворень широко використовуються так звані стискаючі АП, які зближують точки зображення. Зокрема, їх застосовують в ітеративному режимі (коли результати попереднього кроку перетворення використовуються в якості вихідних даних наступного). Простим прикладом стискаючого перетворення може бути процедура yк + 1 = 0,5yк. До використання стискаючих АП ми повернемося в подальшому.

Поняття про математику фракталів: системи ітерованих функцій (СІФ)
Для побудови зображень на основі аффінних перетворень використовуються так звані «системи ітерованих функцій» (СІФ) - рис.8.6:

Рисунок 8.6 Використання СІФ для побудування сталого зображення

- зокрема, на рис.8.6а показана послідовне побудова так званого «трикутника Серпінського». Тут середини сторін рівностороннього трикутника з'єднуються між собою, а з чотирьох утворених таким чином менших трикутників «внутрішній» видаляється. Ця процедура повторюється ітеративно для кожного утвореного трикутника. У міру продовження ітерацій фігура змінюється все менше, тобто вона прагне до деякого сталого зображення;

- на ріс.8.6б відображена дображена СІФ, яка призводить до описаних результатів. Кожна з трьох функцій f1, f2 і f3 зменшують масштаб вихідного трикутника і сдвигают результат в відповідну позицію - лівий кут для f1, правий - для f2 і верхній - для f3 (кольори тут використані для наочності). Як можна бачити, перетворення виконується за допомогою простих функцій, а його налаштування визначаються лише 18-ю числовими коефіцієнтами;

- нарешті, на рис.8.6в показано використання тієї ж СІФ в тому разі, коли вихідною фігурою буде не трикутник, а квадрат. Цікаво і важливо, що в результаті послідовності ітерацій незалежно від вихідного «матеріалу» виходить та ж сама фігура (у міру зменшення розміру елементів візуальні відмінності поступово нівелюються). Це означає, що отримане зображення повністю визначається параметрами СІФ.

Наведений приклад розкриває механізм побудови зображень за допомогою заданих СІФ. При цьому складні зображення можуть включати безліч фракталів, для кожного з яких повинні бути задані власні параметри СІФ. Власне, набір цих параметрів і становить код стиснутої картинки. Але, як ми пам'ятаємо, головна складність полягає саме у визначенні цих параметрів для вихідного стискається зображення.

Поняття про алгоритм фрактального стискання
Отже, фрактальное стискання має забезпечити виявлення в зображенні самоподібних елементів - фракталів і визначення параметрів відповідних СІФ, які б розміщували фрактали в потрібних позиціях і ракурсах. Принципи побудови популярної версії такого алгоритму ілюструє рис.8.7:

Рисунок 8.7 До алгоритму фрактального стискання

- спочатку все зображення ділиться на безліч квадратних елементів — квантів (термін range також буквально перекладають як "рангова область"). З них в подальшому формується мінімальний набір необхідних фракталів. Отриману сітку називають ще Панеллю вибору;

- формується пул (набір) всіляких блоків зображення (доменів - domain), що складаються з четвірок сусідніх квантів;

- для кожного кванта по черзі "приміряються" різні доменні блоки і при їх збігу з достатньою точністю визначаються параметри перетворення, які дозволяють замістити їм дану ділянку зображення.

Етапами «примірки» фракталу до вмісту конкретного домену можуть бути (рис.8.7):
- ідентифікація домену (чи підходить він як кандидат на заміщення даними фракталом;
- корекція фону і огрублення - своєрідне калібрування характеристик домену під фрактал. Тут визначаються параметри необхідних перетворень;
- оцінка «похибки» апроксимації, з урахуванням якої приймається рішення, чи буде фрактал при сформованих параметрах використовуватися в даному домені.

На практиці використовуються безліч удосконалень алгоритму, що дозволяють скоротити трудомісткість фрактального стискання. Однак, така процедура як і раніше вимагає значних ресурсів комп'ютерів і займає відносно багато часу. У цьому полягає недолік даного підходу. Ще одне обмеження, що перешкоджає широкому поширенню фрактального стискання - це проблеми з патентуванням.

Контрольні питання
1. Охарактеризуйте ідею і область застосування фрактального стиснення зображень.
2. Користуючись ріс.8.5, поясніть особливості афінних перетворень зображень. Як такі перетворення використовуються у фрактальному стисненні.
3. На прикладі, показаному на рис.8.6, поясніть використання систем ітерованих функцій (СІФ) для посторенная складних зображень з фракталів.
4. Дайте загальну характеристику алгоритму фрактального стискання зображень.
5. Спираючись на рис.8.7, поясніть етапи «примірки» фрактала, що міститься в оброблюваному кванті зображення, до вмісту чергового домену.


8.3 Аналіз дискретного каналу із шумом

Модель передачі по дискретному каналу із помилками
Математичний апарат, який використовується ТІК для оцінки інформативності повідомлень, дозволяє також аналізувати показники ефективності передачі інформації каналом. ТІК розглядає дві основні моделі передачі - для так званого дискретного та безперервного каналів. В першому випадку розглядається передача послідовності знаків (зокрема, розрядів двійкового коду). Саме такий варіант ми розглянемо тут для аналізу передачі повідомлень на рівні коду. В другому випадку- передача безперервних повідомлень (зокрема, це відповідає фізичному рівню передачі сигналів). Цю модель будемо розглядати надалі, аналізуючи показники передачі фізичних сигналів. В обох моделях використовується поняття інформаційного шуму, який обмежує вірність передачі.
Модель дискретного канала передачі відображена на рис.8.8:

Рисунок 8.8 Інформаційна модель дискретного каналу передачі

- Джерело виробляє потік повідомлень, що складаються з знаків алфавіту Z з безумовною ентропією Hz;

- Кодер перетворює передані знаки zi в послідовність розрядів коду xj, які характеризуються безумовної ентропією Hx. У зв'язку з можливими помилками передачі на вхід Декодера надходять значення розрядів уj;

- Канал забезпечує передачу з середньою швидкістю Vx (розряд/с) при ймовірності виникнення помилок po. Наявність випадкових помилок відображує вплив інформаційного шуму в моделі дискретного каналу. Помилки обумовлюють невизначеність, що вноситься каналом (ентропію Hy/x або Hx/y). Розглядається випадок, коли ймовірність помилок не залежить від значень розрядів (канал "симетричний"). Внаслідок цього справедливо Hx = Hy і Hx/y = Hy/x;

- інформативність розрядів, що передаються через такий канал (біт/розряд), може бути визначена як різниця ентропії кодера і ентропії каналу (Ixy = Hх-Hx/y). В силу симетричності каналу справедливо також Ixy = Hy- Hy/x;

- виходячи із згаданих параметрів моделі може бути розрахована пропускна здатність каналу (максимальна кількість інформації, яку канал здатний пропускати в середньому за одиницю часу) С = Vx max {Ixy} = Vx max {Hy- Hy/x} (біт / c).

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

Рисунок 8.9 Одержання робочої формули для пропускної спроможності каналу

- в якості вихідної приймається обґрунтована вище формула С = Vx max {Hy- Hy/x};
- для дискретного каналу можемо використовувати відповідну формулу умовної ентропії Hy/x;
- з огляду на те, що канал двійковий, отримаємо максимальне значення безумовної ентропії (1 біт/розряд), а також розгорнуту формулу для умовної ентропії;
- для випадку симетричного каналу (помилки для 0 і 1 відбуваються з однаковою ймовірністю) виразимо умовну ентропію через ймовірність помилок.

Таким чином, розрахункова формула для визначення пропускної здатності двійкового симетричного каналу з помилками матиме вигляд
С = Vx [1 + po log2po + (1-po) log2(1-po)].
Пропускна здатність каналу без помилок визначається з початкової формули за припущенні Hy/x = Hx/y = 0. В цьому випадку С = Vx max{Нx}. Оскільки для двійкового каналу max{Нx} = 1 біт / розряд, пропускна здатність чисельно дорівнює швидкості передачі С = Vx (біт/с).

Аналіз пропускної спроможності та її використання
Спираючись на отриману формулу, можна проаналізувати залежність пропускної здатності дискретного каналу від його параметрів — рис.8.10:

Рисунок 8.10 До аналізу пропускної спроможності дискретного каналу

- максимум пропускної спроможності вочевидь відповідає відсутності помилок (po = 0). При цьому, як ми вже знаємо, величина пропускної спроможності (біт/с) чисельно дорівнює швидкості передачі розрядів Vх, оскільки кожен двійковий розряд коду без втрат доносить один біт інформації. Цікаво, що згідно з формулою максимум пропускної спроможності спостерігається також при ймовірності помилок po = 1. Цей парадокс легко пояснити: якщо заздалегідь відомо, що при передачі значення розряду зміниться на протилежне, то його завжди можна відновити інвертуванням;

- мінімум пропускної спроможності (її повна відсутність С = 0) відповідає ймовірності помилок po = 0,5. Це також легко пояснити: якщо ймовірності отримання вірного або помилкового значення розряду однакові, то у нас немає жодних підстав вважати за краще один з цих варіантів. А отже, передача інформації тут неможлива;

- проміжні значення пропускної здатності характеризуються вираженою нелінійністю. При цьому найбільш значні її втрати припадають якраз на діапазон відносно невеликих ймовірностей помилок. Зокрема: при ймовірності po = 0,01 величина C знижується на 8%; при ймовірності po = 0,05 - на 29%; при ймовірності po = 0,10 - на 47%;

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

Контрольні питання
1) Спираючись на рис.8.8, охарактеризуйте інформаційну модель дискретного каналу передачі.
2) Запишіть формули для питомої інформативності розряду коду і пропускної здатності каналу. Що відображає в цих формулах умовна ентропія Нy/x = Нx/y
3) Використовуючи ріс.8.9, розкажіть про етапність виведення формули для пропускної здатності дискретного каналу.
4) Запишіть формули для розрахунку пропускної спроможності дискретного каналу з помилками і без помилок.
5) Спираючись на рис.8.10, поясніть залежність пропускної здатності дискретного каналу від ймовірності помилок передачі. Чому ця залежність симетрична щодо значення ймовірності помилок 0,5
6) Поясніть особливості пропускної здатності дискретного каналу. Якими є максимальне і мінімальне значення пропускної спроможності і за яких умов вони проявляються. Назвіть орієнтовну величину зниження пропускної спроможності при ймовірності помилок 1% і 10%.


8.4 Підходи до передачі коду каналом з помилками

Кодування для захисту від помилок передачі
Принципові особливості передачі повідомлень по дискретному каналу з помилками пояснює рис.8.11:

Рисунок 8.11 До принципу передачі дискретним каналом із шумом

- образно кажучи, кодування для передачі по каналу з помилками створює "захисну оболонку" для переданого інформаційного коду. "Міцність" такої оболонки визначається надмірністю створюваного коду. У мінімальному варіанті вона дозволяє фіксувати "пошкодження", а в максимальному — також усувати їх;

- прийнято виділяти два рівня кодування: стискання повідомлень називають кодуванням джерела, а захист від помилок - кодуванням каналу. На першому з рівнів усувається вихідна надмірність. На другому, навпаки, надмірність коду додається - але вже корисна, необхідна для усунення помилок передачі;

- для кодування каналу Клод Шеннон сформулював і довів теорему, подібну до тієї, з якою ми знайомилися для стиснення повідомлень. Суть теореми Шеннона в тому, що завжди можна закодувати повідомлення таким чином, що пропускна здатність каналу буде використана максимально повно (при цьому подолати обмеження пропускної здатності за рахунок кодування неможливо);

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

Приклади використання контрольних розрядів коду
Методи надлишкового кодування із захистом від помилок передачі будуть детально розглянуті в наступних двох лекціях, а поки ми лише проілюструємо на простих прикладах приницип його дії - рис.8.12:

Рисунок 8.12 Приклади кодування із захистом від помилок

- найпростіший спосіб такого кодування полягає в використанні одного контрольного розряду, значення якого доповнює до парної кількість «1» в блоці коду (приклад А). Якщо при передачі відбувається помилка в одному з розрядів, то правило парності порушується і тим виявляється помилка. Зрозуміло, такий спосіб не дозволяє визначити позицію помилкового розряду і це означає, що код не здатний виправити виявлену помилку. Більш того, якщо при передачі "постраждають" одночасно два розряду коду, умова парності не порушується і така помилка залишиться не виявленою;

- посилити можливості коду (його коригувальну здатність) можна, якщо використовувати більшу кількість контрольних розрядів. У прикладі Б показано використання трьох таких розрядів при передачі одного полубайта. Застосування одночасно трьох перевірок дозволяє локалізувати позицію помилкового розряду, а значить - виправити помилку шляхом його інвертування (в даному випадку 3 перевірки дають 8 варіанов коду, які можуть охопити 7 варіантів помилки і 1 варіант безпомилкової передачі). Подібні коди (вони називаються кодами Хеммінга) застосовуються для усунення результатів збоїв оперативної пам'яті серверів;

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

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

Виправлення помилок з використанням зворотнього зв'язку
Більш гнучким і раціональним способом виправлення помилок є використання зворотного зв'язку для повторної передачі помилкових блоків коду (ріс.8.13):

Рисунок 8.13 Використання схеми передачі із зворотнім зв'язком

- тут вузли А і Б (наприклад, вузли комп'ютерної мережі) обмінюються повідомленнями поперемінно в ролі Передавача і Приймача. Передавач кодує блок повідомлення, доповнюючи його контрольними розрядами, і відправляє по Прямому каналу. Приймач декодує отриманий блок і в залежності від результату формує та відправляє по Зворотному каналу підтвердження правильності або перезапрос на повторну передачу. При отриманні перезапроса Передавач повторює відповідний блок. Оскільки помилки в Каналі є випадковими, імовірність їх повторення значно зменшується (в загальному випадку спроби передачі повторюються до досягнення позитивного результату);

- надмірність коду, необхідна для виявлення помилок, значно менше тієї, що необхідна для їх виправлення. При цьому погіршення умов передачі компенсується зростанням кількості перезапросів, а значить - повного часу доставки повідомлень. Таким чином спосіб зворотного зв'язку економічніший і до того ж він автоматично реагує на зміни пропускної здатності каналу. При цьому наявність зворотнього каналу при двосторонньої передачі означає, що додаткові витрати на обладнання не потрібні;

- показана на ріс.8.13 схема відповідає способу, який називають "вирішальним" зворотним зв'язком (ВЗЗ). Тут рішення про необхідність повторної передачі приймає Приймач і додаткове навантаження на зворотний канал мінімальне. Такий спосіб набув найбільшого поширення і застосовується, зокрема, в комп'ютерних мережах. В альтернативній схемі (з «інформаційної» зворотним зв'язком - ІЗЗ) інформаційний блок, що передається, повертається по зворотному каналу і вже Передавач приймає рішення про його правильність. В цьому випадку навантаження на зворотний канал значно вище. Спосіб ІЗЗ застосовується, коли зворотний канал потужніше за прямий (наприклад, в системах зв'язку з літаючими об'єктами).

Контрольні питання
1) Поясніть поняття "кодування джерела" і "кодування каналу". У чому сенс введення надмірності в код на другому з цих етапів, тоді як на першому надмірність навпаки усувалася.
2) Сформулюйте теорему Шеннона про кодування для каналу з помилками. У чому полягають її особливості в порівнянні з теоремою про кодування джерела.
3) Поясніть принцип дії найпростішого завадозахисні коду з контролем парності. Які його можливості і обмеження.
4) Спираючись на рис.8.12, поясніть, яким чином за рахунок збільшення надмірності кодування можна виправляти виявлені помилки або виявляти ланцюжка помилок.
5) Використовуючи рис.8.13, поясніть принцип виправлення помилок передачі з використанням зворотного зв'язку.
6) У чому полягає перевага виправлення помилок з використанням зворотнього зв'язку відносно безпосереднбого виправлення за допомогою коду.
7) Поясніть відмінності способів виправлення помилок за допомогою вирішального і інформаційного зворотного зв'язку. Де застосовуються способи ВЗЗ і ІЗЗ.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2019 • Теория информации и кодирования
UP