5 УПРАВЛІННЯ ПЕРЕДАВАННЯМ ІНФОРМАЦІЇ ТА СТИСКАННЯ ДАНИХ

5.1 Режими передачі

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

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

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

5.2 Асинхронна, синхронна, ізохронна

 і плезіохронна передача

Для послідовної передачі даних достатньо однієї лінії, по якій можуть послідовно передаватися біти даних.  Приймач повинен вміти розпізнавати, де починається і де закінчується сигнал, відповідний кожному біту даних. Іншими словами, передавач і приймач повинні вміти синхронізуватися. Якщо якість синхронізації низька (за час передачі одного біта відхилення досягає декількох відсотків), використовується асинхронний (asynchronous) режим: виконується узгодження синхрогенераторів на початку передачі кожного байта. Передача байта починається зі спеціального старт-біта, потім йдуть біти даних, а за ними, можливо, біт парності. Після всіх бітів даних передається стоп-біт. Старт-біт і стоп-біт завжди мають певне значення: старт-біт кодується логічним нулем, а стоп-біт – логічною одиницею. Між передачею стоп-біта одного байта і старт-біта наступного байта може проходити довільний час. Швидкість передачі в асинхронному режимі обмежена сотнями кілобіт в секунду (стандартні швидкості: 50, 75, 110, 150, 300, 600, 1200, 2400, 4800, 9600, 19200, 38400, 57600, 115200 біт/с).

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

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

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

5.3 Контроль достовірності передачі

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

Контроль достовірності передачі вимагає введення деякої надмірності в передавану інформацію. Надмірність може вводитися як на рівні окремих передаваних символів або їх груп, так і на рівні передаваних кадрів. У надмірні поля передавач розміщує код, що обчислюється по певних правилах з корисної інформації. Приймач порівнює цей код з тим значенням, яке він обчислив сам. Невідповідність значень свідчить про спотворення інформації, збіг – про високу вірогідність правильної передачі. Вірогідність виявлення помилки залежить від схеми контролю і співвідношення розмірів інформаційного і контрольного полів. Найненадійніша схема – контроль паритету (проста схема). Найекономічніша – дублювання інформації. Найнадійніше виявлення дає CRC- контроль, реалізація якого дещо складніша, але накладні витрати менші (типові - 2 байти на 4 Кбайт даних). Між ними знаходиться схема з обчисленням контрольної суми.

Дублювання інформації зводиться до повторення одного й того ж елементу двічі. Приймач перевіряє збіг копій. Копія іноді представляється в інверсному вигляді. Дублювання застосовують лише для окремих коротких елементів кадру, для яких контроль іншими способами  незручний. Дублювання приводить до 100-відсоткових накладних витрат. Застосовується, наприклад, в байті стану кадру Token Ring.

Контроль паритету (parity check) використовує контрольний біт, доповнюючий число одиничних біт контрольованого елементу до парного (even parity, контроль парності) або непарного (odd parity, контроль непарності) значення, залежно від прийнятої угоди. Контроль паритету дозволяє виявляти тільки помилки непарної кратності, а  спотворення двох, чотирьох і так далі біт контрольованої області залишаться непоміченими. Контроль може бути «горизонтальним» або «вертикальним». При горизонтальному контролі біт паритету «р» вводиться в кожний передаваний символ, цей вид контролю широко використовується в послідовних інтерфейсах RS-232С і інших, накладні витрати – 1 біт на кожен байт.

Контрольні суми і CRC-коди застосовуються для контролю цілого кадру (або його декількох полів). Для них в кадрі визначається спеціальне поле для контрольного коду, зазвичай 1, 2 або 4 байти. Контрольна сума застосовується для кадрів довжиною кратних байту (слову).

Контрольна сума (checksum) зазвичай обчислюється як доповнення суми всіх байтів кадру до нуля (або FF – всіх двійкових одиниць). Підсумовування виконується по модулю, відповідному розрядності поля контрольного коду. При цьому приймач, підсумувавши по тому ж модулю всі байти або слова кадру, включаючи контрольні коди, повинен отримати те ж число (0 або FF). Контрольна сума - найпростіший спосіб контролю кадру, вірогідність виявлення помилок - до 99,6 %.

Надмірний циклічний контроль CRC (Cyclic Redundancy Check) використовує складніший алгоритм. Вибирається породжуючий поліном, розрядністю більшою, ніж поле контрольного коду. Для 16-бітового CRC рекомендується  х¹⁶+х¹²+х⁵+1  (10001000000100001b). Кадр (як довге двійкове число) з обнуленим полем CRC ділиться на поліном, і залишок цього ділення (по модулю розрядності поля CRC) поміщується в поле CRC передаваних даних. Приймач ділить прийнятий кадр (разом з полем CRC) на той же поліном і порівнює залишок від ділення з деяким еталоном (нулем або іншим числом). Якщо вони співпали, ухвалюється рішення про коректність кадру. 16-бітовий CRC дозволяє виявляти  помилки (спотворення групи сусідніх біт) з вірогідністю до 99,9984 %. 16-розрядний CRC застосовується в багатьох мережевих протоколах.

ЕСС-контроль (Error Correction Code), дозволяє не тільки виявити, але і виправляти деякі помилки. У мережах ЕСС практично не застосовується, оскільки вимагає більшої надмірності (він застосовується в пристроях зберігання, де у разі помилки «перепитати» не буде в кого).

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

Для контролю отримання інформації приймачем застосовують квітування (handshaking – рукостискання) – відсилання повідомлення про отримання кадру (пакету). На кожний прийнятий кадр приймач відповідає коротким кадром-підтвердженням. У разі ухвалення коректного кадру посилається позитивне підтвердження АСК (ACKnowledge), у разі помилкового – негативне NACK (Negative ACKnowledge). При отриманні NACK передавач відразу повторно посилає кадр. За відсутності підтвердження протягом певного часу тайм-ауту (timeout) передавач також віконує повторну передачу, але на очікування втрачається час. Таке підтвердження можна використовувати і для управління потоком – відсилання підтвердження є і сигналом готовності. Недолік – темп відсилання кадрів обмежується часом оберту по мережі. 

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

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

Коди, що самовідновлюються

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

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

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

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

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

Систематичні коди 

Інший підхід до побудови кодів – розділення розрядів коду на інформаційні і контрольні. Такі коди називаються систематичними. 

Хай всього в коді n розрядів, з них k – інформаційних і r – контрольних розрядів (n=k+r). Такий код може передавати N = 2k різних повідомлень. З r контрольних розрядів можна організувати 2r різних комбінацій. Для виявлення і виправлення одиничної помилки потрібно, по-перше, вказати наявність/відсутність помилки і, по-друге, вказати номер розряду, в якому відбулася помилка.

Щоб в контрольних розрядах можна було передавати інформацію для виправлення одиничних помилок, їх кількість повинна задовольняти нерівності 2^r≥n+1 або 2ⁿ/(n+1) ≥N. Якщо досягається рівність: 2ⁿ/(n+1) = N, тоді кількість контрольних розрядів, що доводяться на один інформаційний, буде найменшою. Наприклад, для N=4 різних повідомлень (k=2) найменше значення n рівне п'яти (24/(4+1)= 3,2 < 4, а 25/6 х 5,3 > 4). Отже, кількість контрольних розрядів, необхідна для виявлення і виправлення одиничних помилок r = n-k = 5-2 = 3.

5.4 Алгоритми стиснення даних

Стиснення даних - таке їх перетворення, що його результат займає менший об'єм пам'яті. При цьому (в порівнянні з початковим виглядом) економиться пам'ять для їх зберігання і скорочується час передачі стислих даних по каналах зв'язку. Синоніми терміну “стиснення” – пакування, компресія, архівація. Зворотний процес (отримання початкових даних по стислим) називається розпаковуванням, декомпресією, відновленням. Якість стиснення характеризується коефіцієнтом стиснення, рівним відношенню об'єму стислих даних до об'єму початкових даних.

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

Для багатьох різновидів даних – текстів, виконуваних файлів і так далі – допустиме застосування тільки алгоритмів стиснення без втрат.

Стиснення без втрат, в основному, базується на двох групах методів: словникових і статистичних.

Словникові методи використовують наявність повторюваних груп даних і, наприклад, записують перше  входження повторюваної ділянки безпосередньо, а всі подальші входження замінюють на посилання на перше входження. Інші словарні методи окремо зберігають словник в явній формі і замінюють всі входження словарних термінів на їх номер в словнику.

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

5.4.1 Алгоритм RLE

Найпростіший із словарних методів – RLE (Run Length Encoding, кодування змінної довжини) уміє стискати дані, в яких є послідовності байтів, що повторюються. Упаковані RLE дані складаються з байтів що управляють та байтів даних.

Якщо старший біт байта, що управляє, рівний 0, то наступні байти (у кількості, записаній в семи молодших бітах байта, що управляє) при пакуванні не змінюються.

Якщо старший біт рівний 1, то наступний байт потрібно повторити стільки разів, яке число записане в решті розрядів байта, що управляє.

Наприклад, початкова послідовність 00000000 00000000 00000000 00000000 11001100 10111111 10111011  буде закодована в наступному вигляді (виділені байти, що управляють): 10000100 00000000 00000011 11001100 10111111 10111011.

А  дані що складаються з сорока нульових байтів, будуть закодовані всього двома байтами: 1010 1000 00000000.

5.4.2 Алгоритм Лемпела –Зіва

Найширше використовуються словарні алгоритми з сімейства LZ, чия ідея була описана Лемпелом і Зівом в 1977 році. Існує безліч модифікацій цього алгоритму, що відрізняються способами зберігання словника, додавання слова в словник і пошуку слова в словнику.

Словом в цьому алгоритмі називається послідовність символів (не обов'язково співпадаюча зі словом природної мови). Слова зберігаються в словнику, а їх входження в початкові дані замінюються адресами (номерами) слів в словнику. Деякі різновиди алгоритму зберігають окремо словник і окремо упаковані дані у вигляді послідовності номерів слів. Інші вважають словником весь вже накопичений результат стиснення. Наприклад, стислий файл може складатися із записів вигляду  [а,l,t], де а – адреса (номер позиції), з якої починається такий же рядок довжини l, що і поточний рядок. Якщо a>0, то запис прочитався посиланням на словник і поле t (текст) в ній – порожнє. Якщо а = 0, то в полі t записані l символів, які до цих пір в такій послідовності не зустрічалися.

Алгоритм стиснення полягає в постійному пошуку у вже упакованій частині даних максимальної послідовності символів, співпадаючої з послідовністю, що починається з поточної позиції. Якщо така послідовність (довжини > 3) знайдена, в результат записується її адреса і довжина. В іншому разі в результат записується 0, довжина послідовності і сама (нестиснута) послідовність.

5.4.3 Кодування Шеннона-Фано

Методи ефективного кодування повідомлень для передачі  дискретним каналом без перешкод, запропоновані Шенноном і Фано, заклали основу статистичних методів стиснення даних.

Код Шеннона-Фано: символи алфавіту виписують в таблицю в порядку зменшення імовірності. Потім їх розділяють на дві групи так, щоб суми імовірностей в кожній з груп були максимально близькі (по можливості, рівні). У кодах  символів верхньої групи перший біт встановлюється рівним 0, в нижній групі – 1. Потім кожну з груп розбивають на дві підгрупи з однаковими сумами імовірностей, і процес призначення бітів коду продовжується по аналогії з першим кроком. Кодування завершується, коли в кожній групі залишиться по одному символу.

Якість кодування по Шеннону-Фано залежить від вибору розбиття на підгрупи: чим більша різниця сум імовірностей підгруп, тим більш надмірним виявляється код. Для подальшого зменшення надмірності, використовують кодування великими блоками – як “символи” використовуються комбінації початкових символів повідомлення, але і цей підхід має ті ж обмеження. Від вказаного недоліку вільна методика кодування Хафмана.

5.4.4 Алгоритм Хаффмана

Алгоритм Хаффмана гарантує однозначну побудову коду з найменшим для даного розподілу імовірності середнім числом символів коду на символ повідомлення. На першому кроці підраховуються частоти всіх символів в початкових даних. На другому кроці будуються нові коди (бітові послідовності) для кожного символу, так, щоб ніякі дві різні послідовності не мали загального початку, наприклад, три послідовності 0, 10, 110. задовольняють цій вимозі. Хаффман запропонував будувати двійкове дерево символів, в корені якого знаходиться найбільш частий символ, на відстані 1 від кореня – наступні по частоті символи, і так далі. На основі такого дерева коди для символів виходять шляхом виконання простої процедури обходу дерева. Кодом є шлях від кореня до символу, в якому 1 означає перехід по лівій гілці, а 0 – по правій. Такий спосіб побудови гарантує потрібну властивість коду. Нарешті, на останньому кроці у вихідні дані записується побудоване дерево, а за ним надходять закодовані дані.

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