КОНТРОЛЬ ПЕРЕДАЧІ ІНФОРМАЦІЇ

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

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

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

Коди поділяються на рівномірні і нерівномірні. У рівномірних кодахвсі слова містять однакове число розрядів. У нерівномірних кодах числорозрядів в словах може бути різним. В обчислювальних машинахзастосовуються переважно рівномірні коди.

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

Здатність коду виявляти або виправляти "помилки" визначається такзваним мінімальною кодовою відстанню. Кодовою відстанню між двомасловами називається кількість розрядів, в яких символи слів не збігаються.
Якщо довжина слова п, то кодова відстань може приймати значення від 1 доп. Мінімальним кодовою відстанню даного коду називається мінімальнавідстань між двома будь-якими словами в цьому коді. Якщо є хоча бодна пара слів, що відрізняються один від одного тільки в одному розряді, томінімальна відстань даного коду дорівнює 1.

Простий (не надмірна) код має мінімальну відстань dmin - 1. Длянадлишкових кодів dmin> 1. Якщо dmin> 2, то будь-які два слова в цьому кодівідрізняються не менш ніж у двох розрядах, отже, будь-яка поодинокапомилка призведе до появи забороненого слова і може бути виявлена.
Якщо dmin = 3, то будь-яка поодинока помилка створює заборонене слово,що відрізняється від правильного в одному розряді, а від будь-якого іншогодозволеного слова - у двох розрядах. Замінюючи заборонене слово найближчим донього (в сенсі кодового відстані) дозволеним словом, можна виправитиодиночну помилку.

У загальному випадку, щоб надлишковий код дозволяв виявляти помилкикратністю r, має виконуватися умова dmin> r 1. (2)

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

Для виправлення r-кратної помилки необхідно, щоб нове слово,отримане в результаті такої помилки, не тільки не збігалося з яким-небудьдозволеним словом, а й залишалося ближче до правильного слова, ніж до будь-якогоіншому дозволеному слову. Від правильного слова нове відстоїть навідстані r. Отже, від будь-якого іншого дозволеного слова вономає відстояти не менш ніж на r + 1, а мінімальна кодова відстаньповинно бути не менше ніж сума цих величин: dmin> 2r 1. (3)

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

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

Мінімальна відстань коду dmin = 1, тому код з перевіркою парностівиявляє всі поодинокі помилки, а крім того, всі випадки непарного числапомилок (3, 5 і т. д.). При одночасному виникненні двох або будь-якогоіншого парного числа помилок код з перевіркою парності не виявляєпомилок.

При контролі за непарності контролюється повне зникненняінформації, оскільки кодове слово, що складається з О, відноситься дозабороненим.

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

При побудові схем визначення парності суми 1 слова використовуютьлогічні елементи з парафазним виходом, подібні до зображеного на рис. 1,a) і б). Показання схеми виконують операцію складання по модулю 2 (умовнепозначення М2) для двійкових змінних х та у. На рис. 1, в показана схемавизначення ознаки парності байти.

Рис. 1. Схеми визначення парності

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

Рис 2. Схема контролю за збігом

Легко встановити зв'язок кодування при контролі по парності звиконанням складання по модулю 2. Якщо кількість 1 в слові має бутипарних, то в контрольний розряд записується прямий код суми за модулем 2всіх інформаційних розрядів слова. При контролі на непарність вконтрольний розряд заноситься зворотний код зазначеної суми.

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

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

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

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

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

Коригувальні код Хеммінга. В оперативній пам'яті застосовують код
Хеммінга, що дозволяє виправляти помилки.

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

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

Розглянемо процес кодування для коду Хеммінга з корекцієюодиночної помилки (мінімальна кодова відстань dmin = 3). Якщо кодовеслово не містить помилок, то коригуючий число повинне бути дорівнює 0. Принаявності помилки коригуючий чисто повинно містити номер помилковогорозряду. Якщо в молодшому розряді коригуючого числа з'явиться 1, то цеозначає помилку в одному з тих розрядів слова, порядкові номери якихмають 1 у молодшому розряді (тобто розрядів з непарними номерами). Введемоперший контрольний розряд, якому привласнимо непарний порядковий номер іякий встановимо при кодуванні таким чином, щоб сума 1 всіхрозрядів з непарними порядковими номерами була дорівнює 0. Ця операція можебути записана у вигляді

де x1, х3 і т. д. - програмні символи, розміщені в розрядах зпорядковими номерами 1, 3 і т. д.

Поява 1 в другому розряді (праворуч) коригуючого числа означаєпомилку в тих розрядах слова, порядкові номери яких (2, 3, 6, 7, 10, 11,
14, 15 і т. д.) мають 1 у другий праворуч розряді. Тому друга операціякодування, що дозволяє знайти другий контрольний розряд, який маєбути присвоєний будь-якої порядковий номер з групи 2, 3, 6, 7, 10, 11 і т.д., має вигляд

Розмірковуючи аналогічним чином, можна визначити всі інші контрольнірозряди шляхом виконання операцій

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

вважається коригувальним.

При відсутності помилок EkEk-1 ... E2E1 = 0 при наявності помилки не рівниминулю будуть ті суми Еi, в утворенні яких брав участь помилковий розряд;коригуючий число при цьому буде дорівнює порядковому номеру помилковогорозряду.

Вибір місця для контрольних розрядів проводиться таким чином, щобконтрольні розряди брали участь тільки в однієї операції підрахунку парності.
Це спрощує процес кодування. Розгляд виразів для E1, Е2, Е3 і т.д. показує, що такими позиціями є розряди з номерами,які є цілими ступенями двійки: 1, 2, 4, 8, 16 і т. д.

(4)

(12.5)

Необхідна кількість контрольних розрядів (або, що те ж саме,розрядність коригуючого числа) визначається з наступних міркувань.
Нехай кодове слово завдовжки п розрядів має m інформаційних і k = п - тконтрольних розрядів. Коригувальна число довжиною k розрядів описує 2kстанів, що відповідають відсутності помилки і появи помилки в i-мрозряді. Таким чином, повинно дотримуватися співвідношення

або

З цієї нерівності випливає, наприклад, що п'ять контрольних розрядівдозволяють передавати в коді Хеммінга до 26 інформаційних розрядів і т. д.

Якщо у ВП одночасно записуються або зчитуються вісімінформаційних байт (64 розряду), то при використанні коду Хеммінгабуде потрібно сім додаткових контрольних розрядів.

Контроль за кодом Хеммінга реалізується за допомогою набору схем підрахункупарності (див. рис.1), які при кодуванні визначають контрольнірозряди, а при декодуванні формують коригуючий число.

Модифікований код Хеммінга. До контрольним розрядами Хеммінгадодається ще один (в останньому прикладі восьмий) розряд КР контролюпарності всіх одночасно прочитуються (записуваних) інформаційних іконтрольних розрядів. При зчитуванні формуються коригуючий число EkEk-
1 ... E1, і розряд загальної парності КР 'для всіх лічених розрядів, включаючи
КР. Модифікований код Хеммінга дозволяє усувати поодинокі івиявляти подвійні помилки, як це випливає з табл. 1.

Корекція подвійних помилок в ОП. При використанні в ОПмодифікованого коду Хеммінга може здійснюватися корекція подвійнихпомилок.

Таблиця 1

Нехай X - слово, записане в ОП. а X '- лічену з ОП слово, вякому виявлено дві помилки. Тоді по сигналу схеми контролю ініціюєтьсянаступна процедура.

У несправну комірку ОП записується зворотний код вважати слова X 'і потім проводиться його зчитування. Над одержуваних при цьому кодом (Х) ікодом X 'проводиться операція

Код Z містить 1 в розрядах, в яких є помилки.

Схеми управління ВП за кодом Z коректують одну помилку. Після цьогосхема корекції однієї помилки виправляє другі помилку.
Використана література:

1. А.Я. Савельєв «Основи інформатики»; Моск. ; Изд. МГТУ імені

Н. Е. Баумана.

2.
-----------------------< br>(5)