Спосіб забезпечення цілісності інформації на базі лишково-хеммінгового коду

Реферат: UA 75938 U UA 75938 U 5 10 15 20 25 30 Запропонована корисна модель може бути використана в сучасних інформаційнокомунікаційних системах та мережах з метою забезпечення цілісності та достовірності інформаційного потоку даних. Відомий спосіб забезпечення цілісності інформації на базі завадостійкого коду Хеммінга [1]. В цьому коді для формування контрольних ознак використовується процедура, яка є залежною лише від вибраної довжини базового кодового слова і не залежить від інших умов. Недоліком такого способу є простота модифікації інформації, яка циркулює в інформаційно-комунікаційних системах та мережах, з наступним формуванням відповідної контрольної ознаки та виявлення тільки однократних помилок. Внаслідок використання коду Хеммінга багатократні помилки в інформаційному повідомлені не виявляються, що призводить до порушення функціонування інформаційної системи та помилок при прийнятті рішення. Задачею даного способу є використання нового механізму формування контрольних ознак, які є стійкими щодо несанкціонованої модифікації інформаційних об'єктів за рахунок виявлення багатократних помилок. Використання даного способу формування контрольних ознак дозволяє підвищити достовірність та цілісність інформаційного потоку даних на основі виявлення багатократних помилок та зменшення спотворень в інформаційному повідомленні. Для вирішення поставленої задачі розробки способу формування контрольних ознак на базі лишково-Хеммінгового коду, в якому технічний результат, що може бути отриманий при створенні даної корисної моделі полягає в тому, що підвищується надійність та ефективність інформаційної системи та забезпечується цілісність і достовірність інформаційного потоку даних на основі зменшення імовірності появи помилок та усунення спотворення за рахунок виправлення та виявлення багатократних помилок в інформаційному повідомленні. Задача вирішується тим, що згідно з корисною моделлю, для отримання першого перевірочного символу складають по модулю (одержують лишки від суми) всі узагальнені символи базового кодового слова, що мають в коді свого номера одиницю в першому (молодшому) розряді; для отримання другого перевірочного символу складають по модулю усі символи, що мають в коді свого номера одиницю в другому розряді і т.д. Під узагальненими розуміють коди, призначені для виявлення (виявлення і виправлення) пакетних викривлень з кратністю b, в яких використовують алгоритми кодування і декодування відносно до узагальнених b-розрядних символів. В цих кодах початкова двійкова кодова послідовність - базове кодове слово (БКС) - ІI І2…Ik розбивають на n=k/b груп двійкових розрядів з розрядністю b, в яких передбачається виявлення та виправлення викривлень: II ......... b , Ib1......... 2b ,......... к b1......... k . I I I I         1а група 35 40 45 50 55 2а група nа група Двійкові символи, що входять в одну b-розрядну групу, розглядаються як b-значний b узагальнений символ, який може приймати будь-яке із s значень від 0 до (s-1), де s=2 . При кодуванні та декодуванні операції над узагальненими символами виконують по деякому модулю, тобто розшукують лишок від розподілу результату операції на деякий модуль. Це дає можливість, в разі застосування алгоритмів, які можуть бути аналогічними відповідним алгоритмам двійкових кодів, але відносно до узагальнених символів, для відмінності відповідних узагальнених кодів від двійкових ввести в їх назву слово "лишок", тобто говорити про лишковохеммінгові (ЛХ) коди. У лишково-хеммінгових (ЛХ) кодах двійкові базові кодові слова, розбивають на b-розрядні b узагальнені символи, тобто записують у вигляді 1, 2,… n, де i  2 -1, a N - кількість бітів у . вихідній послідовності, N=b n. Так само, як і в двійковому коді Хеммінга (класична форма запису j коду) узагальнені символи j з номерами і = 2 (j=0, 1,…) є перевірочними, решта символів інформаційні. Для отримання перевірочних символів при кодуванні використовують алгоритм, аналогічний алгоритму для двійкового коду Хеммінга, але відносно до узагальнених символів. Усі необхідні для кодування і декодування операції здійснюють за деяким модулем. Тобто, в ЛХ - коді для отримання першого перевірочного символу складають по деякому модулю (одержують лишки від суми) всі узагальнені символи базового кодового слова, що мають в коді свого номера одиницю в першому (молодшому) розряді; для отримання другого перевірочного символу складають по модулю усі символи, що мають в коді свого номера одиницю в другому розряді і т.д. Якщо код орієнтований на виправлення t-кратних викривлень, то b=t. b Як модуль для отримання контрольних символів використовують величину s=2 , тобто 1   3   5   7  ...s ,  2   3   5   6   7  ...s ,... 1 UA 75938 U 5 10 При такому значенні модуля потрібна розрядність перевірочних символів не відрізняється від розрядності узагальнених символів b. При декодуванні алгоритм розрахунку перевірочних i символів аналогічний алгоритму при кодуванні, але при додаванні за модулем використовують і контрольні символи. Знов одержані перевірочні символи порівнюють з відповідними перевірочними символами, обчисленими при кодуванні. При їх відповідності роблять висновок про відсутність викривлення, в решті випадків про наявність викривлення. Якщо приписати результатам порівняння значення 0, а результатам непорівняння - значення 1, то одержана сукупність нулів і одиниць утворює код, який також, як і в двійковому коді Хеммінга, є номером викривленого символу. Величину викривлення визначають наступним чином: будь-який з перевірочних символів, наприклад i, при викривленні деякого інформаційного символів, наприклад j, що приймає участь у формуванні символу i має величину    c  d  ...   j   j  ...s   j   j s .    i Звідки 15 20 25 30  j      i s . i Знаючи місце і величину викривлення здійснюють корекцію. Джерела інформації: 1. Жураковський Ю. П. Теорія інформації та кодування/ Ю. П. Жураковський, В. П. Полторак / Навчальний посібник - К.: Вища школа, 2001-255 с. 2. Сорока Л.С. Основи теорії інформації / Л.С. Сорока / Навчальний посібник - X.: ХНУ ім. В.Н. Каразіна, 2007.-264 с. 3. Василенко B.C. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об'єктів. Код умовних лишків / B.C. Василенко, О.А.Матов // Реєстрація, зберігання і обробка даних - 2006. - Т. 8, № 3. - С. 48-66. 4. Василенко B.C. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об'єктів в умовах природних впливів / B.C. Василенко // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні.-2006. - Вип. 2 (13) – С. 144159. 5. Василенко B.C. Узагальнений завадостійкий код умовних лишків в задачах забезпечення цілісності впливів / B.C. Василенко, O.K. Юдін // Радіотехніка. Всеукраїнська міжвідомча науково-технічна збірка. Темат. вип… "Проблеми телекомунікацій". - Харків: ХHYPE.,-2007. Вип. 148 – С. 228-233. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 40 Спосіб забезпечення цілісності інформації на базі лишково-хеммінгового коду, що полягає у використанні механізму формування контрольних ознак, який відрізняється тим, що для отримання першого перевірочного символу складають по модулю (одержують лишки від суми) всі узагальнені символи базового кодового слова, що мають в коді свого номера одиницю в першому (молодшому) розряді; для отримання другого перевірочного символу складають по модулю усі символи, що мають в коді свого номера одиницю в другому розряді і т. д. Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 2