Захист інформації від спотворення за допомогою теорії кодування - Захист інформації від спотворення
Раніше зазначалося, що при передачі повідомлень каналами зв'язку можуть виникати перешкоди, здатні призвести до спотворення знаків, що приймаються. Так, наприклад, якщо ви спробуєте передати мовленнє повідомлення у вітряну погоду людині, яка знаходиться від вас на значній відстані, воно може бути сильно спотворене такою перешкодою як вітер.
Працюючи з кодованої інформацією, спотвореної перешкодами, можна назвати такі основні проблеми: встановлення самого факту те, що сталося спотворення інформації; з'ясування того, в якому місці переданого тексту це сталося; виправлення помилки - хоча б із певним ступенем достовірності.
Нині темпи розвитку телекомунікаційних систем стали передумовою появи принципово нових методів кодування повідомлень. Причому одним із завдань кодування стало не лише достовірна передача, а й швидка обробка даних. Незважаючи на зростання потужності обчислювальної техніки, актуальним залишається питання побудови простих алгоритмів корекції помилок. Одним із маловивчених напрямів у цій галузі можна вважати використання кодів з ірраціональною основою. Перешкодостійке кодування інформації, що передається, дозволяє в приймальній частині системи виявляти і виправляти помилки. Коди, що застосовуються при завадостійкому кодуванні, називаються коригуючими кодами. Як правило, код коригування може виправляти менше помилок, ніж виявляти. Число помилок, які коригуючий код може виправити в певному інтервалі послідовності двійкових символів, наприклад, в одній кодовій комбінації, називається здатністю коду виправлення.[4]
Теорія кодування виникла наприкінці 40-х з появою робіт Голея, Хеммінга і Шеннона.
Поява робіт Шеннона викликала справжнюЕйфорію серед вчених та інженерів, здавалося, що практичне вирішення цих завдань буде так само просто і зрозуміло, як Шеннон зробив це математично. Однак ейфорія швидко пройшла, тому що практичного рішення у прямій постановці Шеннона знайти так не вдалося. У той же час, зроблені Шенноном постановки задачі та доказ фундаментальних теорем теорії інформації дали поштовх для пошуку розв'язання задач з використанням детермінованих (невипадкових) сигналів та методів алгебри перешкодостійкого кодування захисту від перешкод і шифрування для забезпечення секретності інформації.
У 50-ті-70-ті роки було розроблено велику кількість кодів алгебри з виправленням помилок, серед яких найбільш затребуваними стали коди Боуза-Чоудхурі-Хоквінгема (БЧХ), Ріда-Соломона (РС), Ріда-Малера, Адамара, Юстенсена, Гоппи , циклічні коди, коди згортки з різними алгоритмами декодування (послідовне декодування, алгоритм Вітербі), арифметичні коди.
Однак на практиці застосовується відносно невелика група алгебраїчних завадостійких кодів: БЧХ, Ріда-Соломона та надточні коди. Найбільш широко застосовуються циклічні коди з виявленням помилок стандартних протоколах HDLC, Х.25/2 (LAP-B, LAP-M). Коди Ріда-Соломона з виправленням помилок знаходять застосування у каналах радіозв'язку. У каналах супутникового зв'язку, що характеризуються незалежним характером помилок, широко застосовуються надточні коди.
Слід зазначити той факт, що хоча існуючі на даний момент системи передачі даних відповідають усім основним стандартам і вимогам, вони все ж таки не є досконалими. Причин тому вплив перешкод у каналі зв'язку. Одним із засобів вирішення подібних невідповідностей у системах передачі цифрової інформації є застосування перешкодостійких.кодів, що у основі пристроїв кодування/декодирования.[5]
У різних середовищах характер перешкод різний. Помилки можуть бути одиночними, а можуть виникати групами, відразу по кілька. Через війну перешкод можуть зникати біти чи навпаки - з'являтися зайві.
Основною характеристикою інтенсивності перешкод у каналі є параметр шуму - p. Це число від 0 до 1, що дорівнює ймовірності інвертування біта, за умови, що він був переданий каналом і отриманий на іншому кінці.
Наступний параметр - p2. Це ймовірність тієї самої події, але за умови, що попередній біт також було інвертовано.
Цими двома параметрами можна обмежитися при побудові теорії. Але, в принципі, можна було б враховувати аналогічні ймовірності для зникнення біта, а також використовувати повну інформацію про просторову кореляцію помилок, тобто кореляції сусідніх помилок, розділених одним, двома або більше бітами. У групових помилок є свої плюси та мінуси. Плюси полягають у наступному. Нехай дані передаються блоками 1000 біт, а рівень помилки 0,001 на біт. Якщо помилки ізольовані та незалежні, то 63% блоків будуть містити помилки. Якщо вони виникають групами по 100 відразу, то помилки міститимуть 1% блоків.
Для надійної передачі кодів було запропоновано два основні методи.
Перший - додати в переданий блок даних кількох "зайвих" біт так, щоб, аналізуючи отриманий блок, можна було б сказати, є в переданому блоці помилки чи ні. Це так звані коди з виявленням помилок.
Другий - внести надмірність настільки, щоб, аналізуючи отримані дані, можна як помічати помилки, а й вказати, де саме виникли спотворення. Це коди, що виправляють помилки.[6]
У процесі кодування під час передачіінформації з інформаційних розрядів відповідно до визначених кожному за коду правилами формуються додаткові символи - перевірочні розряди. При декодуванні з прийнятих кодових слів за тими самими правилами знову формують перевірочні розряди та порівнюють їх із прийнятими; якщо вони не збігаються, отже, при передачі відбулася помилка. Існують коди, що виявляють факт спотворення повідомлення, та коди, що виправляють помилки, тобто такі, за допомогою яких можна відновити первинну інформацію.
Помилки в переданих словах можуть виникати внаслідок або незалежних спотворень розрядів (у цьому випадку застосовують, наприклад, коди типу коду Хеммінга), або спотворень групи поряд розрядів (для таких випадків розроблені коди, що виправляють одиночні пачки помилок, і коди, що виправляють більше однієї пачки помилок); виявлення помилок у процесі обчислень на ЕОМ розроблено звані арифметичні коди.