Характеристики і різновиди перешкодостійких код

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

Перешкодостійкий код характеризується трійкою чисел (n, до, d0), де n – спільне число розрядів в передаваному повідомленні, включаючи перевірочні (r), k=n-r – число інформаційних розрядів, d0 – мінімальна кодова відстань між дозволеними кодовими комбінаціями, визначувана як мінімальне число біт, що розрізняються, в цих комбінаціях. Число помилок (розрядів), що виявляються (tо) і (або) виправляються (tи), пов'язане з параметром d0 співвідношеннями:

d0 tо +1,

d0 2tи +1,

d0 tо + tи+ 1

Інколи використовуються додаткові показники надмірності, похідні від приведених вище характеристик n,k: R = r / n – відносна надмірність, v = до / n – відносна швидкість передачі.

Мал. 10.3. Класифікація перешкодостійких код

Існуючі перешкодостійкі коди можна розділити на лаву груп, тільки частка з яких застосовуються для виявлення помилок в передаваних по мережі пакетах (на рис. 10.3 використовувані для цієї мети групи виділені потовщеними стрілками). У групі систематичних (лінійних) код спільною властивістю є те, що будь-яка дозволена комбінація може бути отримана в результаті лінійних операцій над незалежними векторами. Це сприяє спрощенню апаратної і програмної реалізації даних код, підвищує швидкість виконання необхідних операцій. Простими систематичними кодами є біти парності/непарності. Вони не дозволяють виявити помилки парної кратності (тобто помилки одночасно в двох, чотири і так далі бітах) і тому використовуються при невисоких вимогах до вірності даних, що приймаються (або при малій вірогідності помилок в лінії передачі). Прикладом може служити біт Parity (відповідність) в установках режимів роботи послідовного порту за допомогою команди MODE (MS DOS). Не дивлячись на обмежені можливості виявлення помилок, біти парності / непарності мають велике значення в теорії перешкодостійкого кодування. Одні з перших математично обгрунтованих і практично використаних раніше для захисту інформації в пристроях перешкодостійких код, що запам'ятовують, – коди Хеммінга є простою сукупністю перехресних перевірок на парність/непарність. Циклічні коди можуть розглядуватися як узагальнені перевірки на парність/ непарність (див. далі).

Циклічні коди (CRC|)

Циклічні коди – це сімейство перешкодостійких код, що включає як один з різновидів коди Хеммінга. В цілому воно забезпечує велику гнучкість з погляду можливості реалізації код з необхідною здатністю виявлення і виправлення помилок, визначуваною параметром d0, в порівнянні з кодами Хеммінга (для яких d0=3 або d0=4). Широке використання циклічних код на практиці обумовлене також простотою реалізації відповідних кодерів і декодерів.

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

(a0a1.a_n-2a_n-1);

(an-1a0a1.a_n-2);

..........

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

G(x)=g_r xr + gr-1 xr-1 + . + g0

де gi={0,1}, x=2. Крім того, вводяться поліном початкового повідомлення

u(x)= uk-1 xk-1 + uk-2 xk-2 + . +u₀

і кодованого повідомлення|сполучення|

A(x)= an-1 xn-1 + an-2 xn-2 + . + a0

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

Послідовність кодування на прикладі циклічної коди (7,4,3), мають g(x)= x3 + x + 1, наступна:

1) інформаційна частка|частина| повідомлення|сполучення| записується|занотовує| у вигляді полінома:

u(x)= uk-1 xk-1 + uk-2 xk-2 + . +u₀

У даному прикладі k=4 і для повідомлення 0111 виходить

u(x)= x2 + x + 1

2) u(x) умножається xr, що відповідає циклічному зрушенню початкового повідомлення на r розрядів вліво:

u(x) x3 = (x2 + x + 1) x3 = x5 + x4 + x3

3) отриманий многочлен ділиться на q(x):

u(x) •xr/q(x)= з(x) R(x) /q(x)

де з(x) – полином-частное з максимальним ступенем (k—1);

R(x) – поліном-залишок з максимальним ступенем (r-1);

– позначення порозрядної операції підсумовування по модулю 2 (що виключає АБО). Кодоване повідомлення представляється у вигляді

A(x)=u(x)xr R(x)

Таким чином, в цьому випадку

A(x)= (x5 + x4 + x3) x = x5 + x4 + x3 + x

Передаване кодоване повідомлення|сполучення| в звичайній|звичній| двійковій формі має вигляд|вид|

Один з можливих варіантів апаратурної реалізації кодера для даного прикладу змальований на рис. 10.4 разом з послідовністю сигналів, підтверджуючою отримання тих же перевірочних розрядів (010) на восьмому такті (r + до + 1=8). Кодером є сдвиговый регістр із зворотними зв'язками, організовуваними за допомогою елементів М2 (що виключає АБО, суматор по модулю 2). Структура зворотних зв'язків повністю визначається ненульовими коефіцієнтами полінома g(x), що породжує. На перших восьми тактах ключ Кл. знаходиться у верхньому положенні, формуються перевірочні розряди. Потім ключ Кл встановлюється в нижнє положення, що відповідає розриву ланцюгів зворотних зв'язків і передачі безпосередньо в канал зв'язку або на

Мал. 10.4. Приклад формування циклічної коди (сигнал зворотного зв'язку відмінний від нуля на 5-му і 6-му тактах)

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

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

Поліноми, що породжують, є так званими многочленами (діляться лише на одиницю і на самих себе), що не приводяться, табульовані для різних значень n, до і d0. Практично в комп'ютерних мережах використовуються циклічні коди завдовжки в 2 або 4 байти (16 або 32 бита), а параметри n, до і d0 в явному вигляді не указуються. Це пов'язано з можливістю вибору різної довжини поля даних в пакеті на етапі встановлення і вибору параметрів з'єднання при незмінній довжині поля циклічної коди. Теоретична вірогідність помилки при прийомі в разі використання циклічної коди не гірше pош 1/2r, так що для виконання умови стандарту p 10-6 необхідне число перевірочних розрядів r log2106 20. Окрім випадково розподілених, циклічний код дозволяє виявляти підряд наступні помилки (так звані пакети помилок) довжиною l = r або менше. Це особливо поважно у зв'язку з можливістю виникнення тривалих в часі перешкод, що діють на протяжні лінії передачі в комп'ютерних мережах.

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

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

Слід зробити два зауваження щодо термінології, що склалася. Поняття "Циклічні коди" достатньо широке, проте на практиці його зазвичай використовують для позначення тільки одній різновиду, описаного вище і що має в англомовній літературі назву CRC (Cyclic Redundancy Check – циклічна надлишкова перевірка). Більш того, поле пакету або кадру, що фактично містить код CRC, часто називається "Контрольною сумою" (FCS – контрольна сума кадру), що в принципі не вірно, оскільки контрольна сума формується інакше. Проте саме цей термін набув широкого поширення.

Перспективними з погляду апаратурної реалізації представляються коди БЧХ (коди Боуза – Чаудхурі – Хоквінгема), так само, як і коди Хеммінга, що входять в сімейство циклічних код. Коди БЧХ не дуже великої довжини (приблизно до n=1023) оптимальні або близькі до оптимальних кодів, тобто забезпечують максимальне значення d0 при мінімальній надмірності. Ці коди вже знайшли практичне застосування в цифрових системах запису звуку (мови, музики), причому у варіанті, що передбачає виправлення виявлених помилок. Відносно невисокі частоти дискретизації звукових сигналів (48 або 96 кГц) не перешкоджають проведенню додаткових обчислень так жорстко, як в разі високошвидкісних мереж.

11. Лекція: Стандартні сегменти Ethernet|

Як вже наголошувалося, існує декілька стандартних сегментів мережі|сіті| Ethernet/Fast Ethernet|. Кожен з них має свої достоїнства і недоліки|нестачі|, сфери застосування. При установці мережі|сіті| необхідно зробити обгрунтований вибір устаткування|обладнання|, з|із| тим щоб|аби| потім не довелося|припало| витрачати значні суми на його заміну.