Цілісність і доступність інформації

10

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

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

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

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

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

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

Модель системи зв'язку

В наслідок впливу завад та шумів результуючий сигнал S_рез(t) на виході каналу зв'язку є сумою (для адитивних завад, які, як правило, домінують в каналах зв'язку) власне сигнала S (t) та завади n (t) так, що

S_рез(t) = S (t) + n (t).

Наслідком цього впливу є те чи інше викривлення сигналу. Як сигнал, так і завада мають певну енергетику. Чим більшим є співвідношення сигнал/ шум (сигнал/завада)

,

тим кращими є умови для передачи невикривленого сизналу.

Наслідком впливів в каналах ТКС є зменшення співвідношення енергетик сигнал/ шум (сигнал/завада). Оскільки це відношення визначає вірність інформації, визначувану, наприклад, через ймовірність помилок двійкових символів (біт) Р_пом = f(), а також інтенсивність цих помилок. Слід підкреслити, що інтенсивність природних дій в каналах ТКС, яка визначається, в основному, цим співвідношенням, є настільки значною, що лише за їх рахунок, без урахування можливостей зловмисників по створенню загроз, наприклад різного роду завад, середня вірогідність помилки двійкового символу (біта) Р_пом для телефонних кабельних каналів ТКС складає від 1,2910^-4 до 210^-3; для радіорелейних телефонних від 2,6610^-4 до 7,310^-4 відповідно. Відомо також, що з часом такі помилки групуються в пакети двох видів: “короткі” тривалістю 2...10 мс і “довгі“ тривалістю 100…200 мс. “Короткі” пакети з'являються частіше, але більшість зафіксованих помилок зосереджено в “довгих” групах (75 90%).

Як вже поминалося, використання викривленої інформації чревате наслідками (часто надзвичайно важкими) для власників або користувачів цієї інформації. Тому задача забезпечення цілісності і доступності інформаційних ресурсів є однією з найактуальніших при розробці і експлуатації АС і їх елементів. Ця необхідність підтверджується і вимогами щодо допустимої вірогідності Р_п помилок в повідомленнях, яку слід трактувати як вірогідність порушення цілісності інформаційних об'єктів, які обробляються (якщо передача і обробка інформації здійснюється у вигляді повідомлень). Наприклад, вона може задаватися від 10^-4 (у задачах оперативно ? виробничого планування) до 10^-6 (у задачах бухгалтерського обліку).

Використовуючи зв'язок між допустимою вірністю інформації Р_п і середньою вірогідністю помилки символу Р_пом (Р_пом = Р_п/n, де n розрядність повідомлення), одержимо, що середня допустима вірогідність викривлення символу, у разі відсутності засобів захисту від помилок, складе значення від 10^-8 до 10^-6 при обробці повідомлень з довжиною 100 двійкових символів (битий), і від 10^-9 до 10^-7 при обробці повідомлень з довжиною 1000 символів. Слід підкреслити, що ці вимоги не є найвищими. Наприклад, в системах з криптографічним захистом, наслідки викривлень рівноцінні втраті повідомлення, не говорячи вже про втрати, які пов'язані з навмисним викривленням фінансової інформації, навмисним викривленням команд, розпоряджень і т.п. Останнє іноді приводить до постановки задачі передачі інформації з абсолютною цілісністю. Аналіз цих даних дозволяє зробити висновок про необхідність використовування засобів, пристроїв або алгоритмів, які дозволяють забезпечити значне підвищення цілісності інформації, яка приймається.

Серед основних способів (механізмів) забезпечення цілісності (і в раніше визначеному значенні ? доступності) інформації для каналів ТКМ (взагалі для мереж передачі даних) слід виділяти:

1. Збільшення вже згаданого співвідношення сигнал/завада за рахунок:

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

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

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

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

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

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

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

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

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

• У системах із зворотним зв'язком застосовуються процедури виявлення помилок і перезапиту так звані процедури з вирішальним зворотним зв'язком або виявлення помилок з автоматичним запитом повторення (ВЗЗ, АЗП, ARQ ? Automatic Repeat Request). В цьому випадку код застосовується тільки в режимі виявлення помилок, що дозволяє досягти дуже низької вірогідності незнайденої помилки при незначному рівні надмірності, що вводиться.

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

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

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

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

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

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

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

Виділяють дві основні причини виникнення природних помилок при передачі інформації в мережах:

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

* завади, викликані зовнішніми джерелами і атмосферними явищами.

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

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

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

Групові методи захисту від помилок

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

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

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

Декілька нижче ми вивчимо решту методів захисту від помилок: завадостійке кодування і методи захисту від помилок в системах передачі із зворотним зв'язком.

Двійкові завадостійкі коди

Характеристики корегуючих кодів

Завадостійке (надмірне) кодування, що припускає розробку і використовування корегуючих (завадостійких) кодів, широко застосовується не тільки в ТКС, але і в ЕОМ для захисту від помилок при передачі інформації між пристроями машини. Воно дозволяє одержати вищі якісні показники роботи систем зв'язку. Його основне призначення ? забезпечення малої вірогідності викривлень переданої інформації, не дивлячись на присутність завад або збоїв в роботі мережі.

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

До числа найважливіших характеристик корегуючих кодів відносяться:

* значність коду, або довжина базового кодового слова, яка включає інформаційні символи (m) і перевірочні, або контрольні, символи (k). Звичайно значність коду п є сума n = т + k;

* відносна швидкість коду ? R, є відношенням числа інформаційних символів в кодовій комбінації m до значності коду n: R = m/n;

* надмірність коду К_надм, є відношенням числа контрольних символів в кодовій комбінації k до значності коду n:

К_надм = к/n = (n ? m)/n = 1 ? m/n = 1 ? R;

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

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

Принципи побудови завадостійких кодів

Найчастіше як передумову при введенні кодів розглядають деякий початковий набір з m двійкових символів “0”и “1” (двійковий вектор), званий часто базовим кодовим словом (БКС). Зрозуміло, що число можливих БКС при цьому рівно числу можливих кодових комбінацій N₀ = 2^m. Кожне таке БКС можна розглядати як представлене в двійковій системі числення число А, діапазон представлення яких (робочий діапазон коду) знаходиться в межах від 0 до 2^m, тобто А [0, 2^m]. Для такого коду будь-яке випадкове викривлення можна розглядати у вигляді суми (як правило, порозрядної, по модулю 2) початкового коду і двійкового m символьного випадкового вектора Е. У звичного (не завадостійкого, не надлишкового) коду така сума є новим двійковим вектором з того ж набору можливих кодових комбінацій. Знайти при цьому викривлення неможливо.

Завадостійкий код відрізняється від звичного коду тим, що в БКС, окрім початкового набору з m двійкових символів “0”и “1” вводиться k додаткових, надлишкових символів, які передаються в канал (записуються в ЗП) разом початковим набором. Кількість, правила формування і місця розташування цих надлишкових (надлишкових) символів визначаються виглядом і властивостями завадостійкого коду. Надлишкові символи звичайно прийнято називати контрольними або перевірочними, а їх сукупність -- контрольною ознакою (ознакою цілісності). Введення k надлишкових символів є рівносильним збільшенню діапазону представлення чисел а 2^k разів, так що діапазон можливих представлень чисел в розширеному діапазоні

А [0, 2ⁿ],

де n = m + k. Для такого коду, як і раніше, будь-яке випадкове викривлення можна розглядати також у вигляді у вигляді порозрядної суми по модулю 2 (або іншому модулю) початкового n символьного коду і двійкового n символьного випадкового вектору Е.

Процес завадостійкого кодування при цьому зводиться до наступного. Кожен перевірочний розряд (або контрольна ознака в цілому) визначається (розраховується) як деяка функція (у деяких кодах, наприклад в кодах Хеммінга (див. нижче) сукупність функцій) від початкового БКС або від сукупності його певних інформаційних розрядів. Які, конкретно, інформаційні розряди беруть участь у формувань даного перевірочного розряду (або контрольної ознаки в цілому) і по якому закону він формується, визначається алгоритмом побудови даного коду. Дуже часто значення кожного перевірочного розряду (“0” або “1”) вибирається так, щоб сума по модулю 2 певних інформаційних і даного перевірочного розрядів дорівнювала 0. Перевірочні розряди, у принципі, можуть розташовуватися в кодовій комбінації на будь-якому місці. Для визначеності вважатимемо, що вони розміщуються в кінці початкового коду (повідомлення). При цьому вимагають, щоб правильні, (не викривлені) числа в новому, розширеному діапазоні як і раніше відповідали вимозі А [0, 2^m]. Цей розширений діапазон має вигляд, представлений на рис. 19. При такій постановці правомочно вважати контрольну ознаку лишком r (А) по деякому модулю М (залишком від розподілу на М ? відображенням) деякої функції (у загальному випадку ? функціонала) від початкового числа F (A) (у простому випадку ? від самого початкового числа А), так що

r (А) = F (A) mod (M).

0 2^m 2^2m (M - 1) 2^m 2ⁿ

Рис. 1. Діапазони представлення чисел

Підкреслимо знов, що алгоритми розрахунку і модуля М і функціонала F (A) визначається алгоритмом побудови даного коду.

При такій постановці правомочно вважати контрольну ознаку лишком r (А).

Сукупність початкового числа А і його контрольної ознаки r (А) прийнято називати кодовим числом а, за певних умов, завадостійким кодом або:

А = (А, r (А)), (1)

Таке базове кодове слово можна вважати також представленням початкового числа А в системі числення в залишкових класах по двох основах р₁ = 2^m і р₂ = М: де значення А в круглих дужках А = А mod (2^m) = А, оскільки за умовою А < 2^m.

Відомо, що при такому представленні і

М = 2^k > 2^m, (2)

будь-яке викривлення в першому з символів (тобто в початковому числі А) переводить початкове число А з робочого діапазону [0, 2^m] в контрольний [2^m + 1, 2ⁿ], що може бути легко знайденим, а за певних умов така викривлення може бути і виправленою. Дійсно, викривлення в першому символі (тобто в початковому числі А) має в уявленні (1) вигляд Е/ = (Е, 0), тобто є числом кратним М, отже, числом вигляду Е = s М, де s = 1, 2, …, (2^m - 1). Тоді при будь-якому значенні М викривлене число В = A + s•М > 2^m, тобто знаходиться в контрольному діапазоні.

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

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

Виходом з цієї ситуації є постановка задачі виявлення або виявлення і виправлення не будь-яких викривлень в початковому коді, а тільки всіх можливих в заданих умовах. Іншими словами відповідний завадостійкий код слід орієнтувати на реальну статистику викривлень в каналі передачі (у ЗП даного типа), коли число викривлених символів t_{в =} n·Р_пом, де Р_пом ? згадана вище ймовірність викривлення біта в каналі передачі (ЗП).

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

Таким чином, загальна кількість викривлень кратності t_в і менш дорівнює звідки мінімальне необхідне число перевірочних розрядів для виправлення викривлень кратності t_в і менш визначається з наступної нерівності:

2^k ?

звідкіля

k ? log₂ . (3)

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

Приклад 2. Кодова комбінація містить m = 10 інформаційних одиничних елементів. Визначити необхідне число перевірочних одиничних елементів для виправлення будь-якої двократної помилки.

Рішення. Вираз (3) для заданих умов матиме вигляд

k ? log₂ (С⁰_п + С¹_п + С²_n) або 2^k ? 1 + n + [n (n ? 1)]/2. (4)

Згідно з цим виразом складемо таблицею:

З таблиці видно, що умова (4) виконується лише при k ? 8 розрядах.

Відповідь. k = 8 розрядів.

Примітка. З формул (3) і (4) можна визначити нижню межу числа надлишкових розрядів. Практично ж кількість надлишкових розрядів перевищує вказане число.

Важливими показниками коду є ймовірність виявлення Р_в і невиявлення Р_нв викривлень, під якими розуміють відношення числа викривлень, що знаходяться (що не знаходяться), до числа всіх можливих викривлень. Помилки не виявляються, коли передана кодова комбінація перетвориться в іншу дозволену. Число всіх дозволених комбінацій при m інформаційних розрядів рівне 2^m.

Отже, при передачі якої-небудь кодової комбінації можливе число випадків невиявлення викривлень буде рівним

N_нв = 2^m. (5)

Оскільки число всіх можливих варіантів викривлень дорівнює 2ⁿ, де n кількість розрядів в кодовій комбінації, той вираз для визначення величини Р_нв матиме вигляд:

Р_нв = (2^m 1)/2ⁿ = 1/(2^n?m) 1/2^{n =} 1/2^{k 1}/2ⁿ, (6)

де k = (n m) кількість надлишкових розрядів. З урахуванням того, що, як правило, n >> k, то величиною 1/2ⁿ можна знехтувати і вважати Р_нв ? 1/2^k.

Оскільки число всіх заборонених кодових комбінацій рівне 2ⁿ 2^m, то ймовірність Р_в може бути визначеною з виразу:

Р_в = (2^nm) / 2ⁿ = 1 1/2^k = 1 Р_нв. (7)

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

Р_пп = Р_в Р_бр(t),

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

k_пор ? 0,4 (m + k_пор).

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

Двійкові коди з перевіркою на парність або на непарність (контроль по модулю 2)