4 ПЕРЕДАВАННЯ ТА КОДУВАННЯ ІНФОРМАЦІЇ

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

4.1 Кількість інформації та ентропія

4.1.1 Моделі Хартлі (Шеннона)

Джерело інформації, яке може в кожний момент часу знаходитися в одному з можливих станів, називається дискретним джерелом інформації. Називатимемо кінцеву множину всіх можливих станів {u₁, u₂ ., u_N} абеткою джерела (N – розмір абетки або число можливих станів). У загальному випадку різні стани u_i вибираються джерелом з різною вірогідністю p_i, і його можна охарактеризувати сукупністю абетки і безлічі вірогідності станів – ансамблем  U_N = {u₁, p₁, u₂, p₂ ., u_N, p_N}. Зрозуміло, сума вірогідності всіх станів повинна дорівнювати 1.

Введемо міру невизначеності стану джерела H(U), що задовольняє таким умовам:

• монотонність: міра повинна монотонно зростати із зростанням кількості можливих станів;
• адитивність: міра, обчислена для складного джерела, що складається з двох незалежних джерел (з розмірами абеток N і M, тоді розмір абетки складного джерела – NM), повинна дорівнювати сумі мір цих двох джерел. Згідно з умовою адитивності міра повинна задовольняти співвідношенню:

.                           (4.1)

Крім того, існує гранична умова: міра невизначеності для джерела з розміром алфавіту 1 повинна дорівнювати 0. Можна показати, що цим умовам задовольняє логарифмічна функція (з довільною основою).

Для джерела з абеткою розміру N і рівноімовірними станами (p_i = 1/N для будь-якого i) логарифмічна міра була запропонована Р. Хартлі у 1928 р. і має вигляд:

 .                                 (4.2) 

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

Моделі Хартлі бракує врахування вірогідності станів. Якщо, наприклад, джерело має два можливі стани з вірогідністю 0.999 і 0.001, зрозуміло, що міра невизначеності такого джерела повинна бути менша 1 біта: є велика упевненість у виборі першого стану. Якщо вірогідність станів відрізняється трохи (наприклад, 0.51 і 0.49), то й міра невизначеності повинна змінитися трохи порівняно з рівноімовірним випадком. Таким чином, міра невизначеності повинна залежати від вірогідності станів джерела, від всього ансамблю. Така модель джерела інформації називається моделлю Шеннона (1948 р.). Міра невизначеності вибору дискретним джерелом стану з ансамблю U_N називається ентропією дискретного джерела інформації або ентропією кінцевого ансамблю.

,                            (4.3)

де C – довільне позитивне число.

За умови рівної вірогідності станів джерела міра Шеннона зводиться до міри Хартлі.

Доведено, що приведена функція – єдина і така, що задовольняє всім переліченим умовам. Термін “ентропія”  запозичений з термодинаміки і використаний для міри невизначеності через те, що обидві ентропії –  термодинамічна й інформаційна – характеризують ступінь різноманітності станів даної системи і описуються аналогічними функціями.

4.1.2 Властивості ентропії:

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

Одиниці  кількості інформації. Біт – дрібна одиниця вимірювання кількості інформації. Крупніша одиниця – байт, що складається з восьми бітів. В мережах застосовуються і більш крупніші одиниці від кілобайтів (Кбайт) – 1024 байт =  2¹⁰ байт до петабайтів (Пбайт) – 1024 Тбайт =  2⁵⁰ байт.

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

4.2 Вимоги до мереж з позиції якості обслуговування

Головна вимога – виконання мережею того набору послуг, для надання яких вона призначена. Решта вимог – продуктивність, надійність, сумісність, керованість, захищеність, розширюваність і масштабованість. Часто «якість обслуговування» (Quality of Service, QоS) включає тільки дві найважливіші характеристики мережі – продуктивність і надійність.

Продуктивність характеризується параметрами:

Час реакції мережі – інтегральна характеристика мережі– інтервал часу між виникненням запиту користувача до мережної служби і отриманням відповіді на цей запит.

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

Максимальна швидкість передачі для каналу без шуму, згідно з теоремою Найквіста, становить

,                                              (4.4) 

де F – пропускна спроможність, М – кількість помітних рівнів сигналу.

Для реальних каналів (з шумом) максимальна швидкість передачі визначається згідно з теоремою Шеннона:

,                                   (4.5) 

де S/N – відношення потужності корисного сигналу до потужності шуму .

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

Надійність оцінюється характеристиками: коефіцієнтом готовності (availability) – часткою часу, протягом якого система може бути використана; рівнем помилок – визначається як вірогідність безпомилкової передачі певного об'єму даних. Наприклад, вірогідність 0,99999 відповідає 1 помилковому біту на 100 000 переданих бітів. Для локальних мереж характерний рівень помилок 1 на 10⁸-10¹² біт, для глобальних мереж – 1 на 10⁴-10⁷; середнім часом відновлення працездатності мережі.

Додаткові аспекти надійності: збереження даних і захист їх від спотворень; узгодженість (синхронізація) даних; відмовостійкість (fault tolerance) – здатність системи приховувати від користувача відмову окремих її елементів . Іншим аспектом загальної надійності є безпека даних (security), тобто здатність системи захистити дані від несанкціонованого доступу.

Керованість мережі – можливість централізовано контролювати стан основних елементів мережі, виявляти і вирішувати проблеми, що виникають при роботі мережі, виконувати аналіз продуктивності і планувати розвиток мережі.

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

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

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

4.3 Кодування інформації

Кодування на двох нижніх рівнях моделі OSI визначає спосіб презентування даних сигналами, що розповсюджуються по середовищу передачі. Природно, що на приймаючій стороні здійснюється симетричне декодування.

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

Найбільш поширені такі коди (рисунок 4.1):

NRZ (Non-Return to Zero – без повернення до нуля) – потенційний код, стан якого прямо або інверсно відображає значення біта даних;

Диференційний NRZ – стан змінюється на початку бітового інтервалу для “1” і не змінюється при “0”;

NRZI (Non-Return to Zero Inverted – без повернення до нуля з інверсією) – стан змінюється на початку бітового інтервалу при передачі “0” і не змінюється при передачі “1”. Використовується в FDDI, 100BaseFX;

RZ (Return to Zero – з поверненням до нуля) – біполярний імпульсний код, тобто є таким, що сам синхронізується, представляє “1” та “0” імпульсами протилежної полярності, що тривають половину такту (інша половина такту стану встановлюється в нуль); всього використовується три стани; застосований у виділених каналах Т1 (1,544 Мбіт/с);

AMI (Bipolar Alternate Mark Inversion – біполярне кодування з альтернативною інверсією) – використовуються три стани: 0, + і –, для кодування логічного нуля використовується стан 0, а логічна одиниця кодується по черзі станами + і –. Використовується в ISDN, DSx ;

Манчестерське кодування (manchester encoding) – двофазне полярне кодування, що самосинхронізується, логічна одиниця кодується перепадом потенціалу в середині такту від низького рівня до високого, логічний нуль – зворотним перепадом (якщо необхідно представити два однакові значення один за одним, на початку такту відбувається додатковий службовий перепад потенціалу). Використовується в Ethernet;

Рисунок 4.1 – Способи цифрового кодування даних

Диференційне манчестерське кодування (differential manchester encoding) – двофазне полярне кодування, що синхронізується саме, логічний нуль кодується наявністю перепаду потенціалу на початку такту, а логічна одиниця – відсутністю перепаду; в середині такту перепад є завжди (для синхронізації). В Token Ring застосовується модифікація цього методу, окрім “0” та “1”, що використовує службові біти “J” та “K”, що не мають перепаду в середині такту (“J” не має перепаду на початку такту, “К” – має);

MLT-3 – трирівневе кодування зі скремблюванням без самосинхронізації, логічний нуль кодується збереженням стану, а логічна одиниця кодується по черзі наступними станами: +V, 0, -V, 0, +V і так далі. Використовується в FDDI і 100BaseTX;

PAM5 (Pulse Amplitude Modulation) – п'ятирівневе біполярне кодування, при якому кожна пара біт даних представляється одним з п'яти рівнів потенціалу. Чотирьом можливим комбінаціям (00,01, 10, 11) відповідає певний рівень сигналу. П'яте значення зумовлює надмірність, яку використовують для виявлення помилок. Код застосовують  в 1000 Base-ТХ паралельно по чотирьох парах. Швидкість передачі по одній з них – 250 Мбіт/с при тактовій частоті 125 Мгц;

2B1Q (2 Binary 1 Quarternary) – пара біт даних представляється одним четвертинним символом, тобто одним з чотирьох рівнів потенціалу. Застосовується в ISDN.

4.4 Логічне кодування

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

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

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

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

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

Розглянемо деякі поширені схеми логічного кодування.

Логічний код 4B/5B замінює кожні 4 біта вхідного потоку (початковий символ) на 5-бітовий вихідний символ. Оскільки кількість різних 5-бітових символів дорівнює 32, а початкові символи можуть містити лише одну з 16 бітових комбінацій, серед можливих вихідних кодів можна відібрати 16 “зручних” комбінацій – що не містять великої кількості нулів (більше трьох підряд), серед кодів, що залишилися, виділити службові символи (для підтримки синхронізації, виділення меж кадрів та їх полів і так далі), а коди, що залишилися, вважати забороненими.

Таблиця 4.1. – Код 4B/5B

Накладні витрати при кодуванні 4B/5B становлять 25% (один зайвий біт на чотири біта даних), відповідно для досягнення тієї ж пропускної спроможності, що і без логічного кодування, передавач повинен працювати на підвищеній на 25% частоті. Код 4B/5B використовується в FDDI і Fast Ethernet: 100BaseFX і 100BaseTX.

Логічний код 8B/10B замінює кожний 8-бітовий початковий символ 10-бітовим вихідним символом. При тому ж рівні накладних витрат (25%), що в коді 4B/5B, має 4-кратну надмірність (1024 вихідних символів і 256 початкових символів).

При кодуванні 8B/10B кожному початковому символу зіставлене два вихідних символи, вибір з яких здійснюється залежно від останнього біту попереднього переданого символу. Як наслідок, код забезпечує стабільне співвідношення “0” і “1”  у вихідному потоці, незалежно від початкових даних. Ця властивість важлива для лазерних передавачів, оскільки від даного співвідношення залежить їх нагрівання і кількість помилок прийому. Код 8B/10B використовується в Gigabit Ethernet: 1000BaseSX,LX,CX.

Логічний код 8B/6T кодує кожні 8 біт початкової інформації шістьма трійковими (T – ternary, трійковий) розрядами, що приймають значення {+, 0, –}. Наприклад, “00000000” = “+–00+–“, “11111110” = “– +0+00”. Надмірність коду 8B/6T вища, ніж у коду 4B/5B і становить 36/28 = 729/256 = 2,85. Застосовується в 100BaseT4.

Скремблювання полягає в побітному обчисленні вихідної послідовності на підставі значень біт початкової послідовності і вже обчислених біт результату. Наприклад, скремблер може обчислювати для кожного біта такий вираз: B_i=A_iÅB_i-5Å B_i-7, де A_i – i-й біт початкової послідовності, B_i – i-й біт результату скремблювання, Å – операція додавання по модулю 2. Різні алгоритми скремблювання відрізняються різною кількістю доданків і різним зрушенням між доданками (у наведеному вище прикладі використовується два доданки зі зрушеннями 5 і 7). Наприклад, в ISDN використовується два варіанти скремблювання: зі зрушеннями 5 і 23, та зі зрушеннями 18 і 23.

Існують спеціальні методи скремблювання, вживані спільно з певними методами фізичного кодування. Наприклад, для поліпшення коду AMI застосовуються методи B8ZS і HDB3. Метод B8ZS (Bipolar win 8-Zeros Substitution, біполярний із заміною 8 нулів) замінює послідовності, що складаються з 8 нулів на “000V10V1”, де V – сигнал одиниці забороненої в даному такті полярності, а 1 – сигнал одиниці коректної полярності. Якщо на 8 тактах приймач спостерігає три початкові нулі і два спотворення полярності, то він замінює ці  8 біт на 8 логічних нулів. Метод HDB3 (High-Density Bipolar 3-Zeros, біполярний трьох-нульової високої щільності) замінює послідовності з чотирьох нулів, що йдуть чередою, на один з чотирьох  біполярних кодів залежно від передісторії – полярності попереднього імпульсу і попередньої заміни.

4.5 Коди, що синхронізуються самі

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

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

Більшість технологій локальних мереж використовують  коди, що синхронізуються самі: у Ethernet застосовується манчестерський код, в Token Ring – варіант диференційного манчестерського коду.