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

Реферат: Спосіб виявлення спотворень в коді умовних лишків із застосуванням Z-алгоритму, полягає у використанні механізму формування контрольних ознак. Сформовані на етапі кодування контрольні символи надають змогу при декодуванні прийняти рішення про відсутність чи наявність спотворень в інформаційному повідомленні. UA 78181 U (54) СПОСІБ ВИЯВЛЕННЯ СПОТВОРЕНЬ В КОДІ УМОВНИХ ЛИШКІВ ІЗ ЗАСТОСУВАННЯМ ZАЛГОРИТМУ UA 78181 U UA 78181 U 5 10 15 20 25 30 35 40 Корисна модель може бути використана в сучасних інформаційно-комунікаційних системах та мережах з метою контролю достовірності інформаційного потоку даних. Відомий спосіб забезпечення цілісності інформації на базі завадостійкого коду Хеммінга [1]. В цьому коді для формування контрольних ознак використовується процедура, яка є залежною лише від обраної довжини базового кодового слова і не залежить від інших умов. Недоліком такого способу є можливість корегування тільки однократних помилок. Внаслідок використання коду Хеммінга багатократні помилки в інформаційному повідомлені не виявляються, що приводить до порушення функціонування інформаційної системи та помилок при прийнятні рішення. Відомий також спосіб контролю цілісності інформації на базі системи числення в лишкових класах [2]. В цій системі числення інформаційні об'єкти представляються як набір лишків від розподілу вихідного інформаційного об'єкту на сукупність із m так званих робочих та k контрольних основ. Ці основи вибираються із досить численної сукупності взаємно простих чисел і мають, як правило, різну розрядність. Отже, і символи представлення - узагальнені символи - лишки від розподілу вихідного інформаційного об'єкту на сукупність робочих та контрольних основ мають різну розрядність. Спосіб забезпечує виявлення багатократних помилок в групах, розташованих поспіль символів, - в узагальнених символах. Недоліками такого способу є необхідність застосування системи числення лише в лишкових класах та неоднакова розрядність узагальнених символів. Метою даного способу є використання алгоритму виявлення спотворень в коді умовних лишків із застосуванням Z-алгоритму, який є стійким щодо несанкціонованої модифікації інформаційного потоку даних за рахунок виявлення багатократних помилок. Використання даного способу дозволяє підвищити достовірність інформаційного потоку даних на основі виявлення багатократних спотворень в інформаційному повідомленні. Для досягнення поставленої мети була поставлена задача розробки способу виявлення спотворень в коді умовних лишків із застосуванням Z-алгоритму. Технічний результат, який може бути отриманий при створенні даної корисної моделі полягає в тому, що підвищується надійність та ефективність інформаційної системи та забезпечується достовірність інформаційного потоку даних на основі зменшення ймовірність появи спотворень за рахунок виявлення багатократних помилок в інформаційному повідомленні. Поставлена задача вирішується тим, що згідно з корисною моделлю, сформовані на етапі кодування контрольні символи надають змогу при декодуванні прийняти рішення про відсутність чи наявність спотворень в інформаційному повідомленні. Код умовних лишків належить до класу узагальнених (групових) кодів [3-5]. Під узагальненими розуміють коди, призначені для виявлення (виявлення і виправлення) пакетних спотворень кратності b, в яких використовують алгоритми кодування і декодування по відношенню до узагальнених b-розрядних символів. В цих кодах початкова двійкова кодова послідовність - базове кодове слово (БКС) - I1 І2…Іk розбивають на n=k/b груп двійкових розрядів з розрядністю b, в яких передбачається виявлення та виправлення спотворень: I1.........Ib , Ib1.........I2b .........Ik b1.........Ik .            1а гру па 45 50 2а гру па nа гру па Двійкові символи, що входять в одну b-розрядну групу, розглядаються як b-значний b узагальнений символ, який може приймати будь-яке із s значень від 0 до (s-1), де s=2 . Ці n узагальнених символів розглядаються як лишки 1 (i=1, 2,…, n) від розподілу умовного числа А на основи pi (і=1, 2,…, n) деякої також умовної системи числення в лишкових класах. Внаслідок цього увесь початковий інформаційний об'єкт - сукупність з n узагальнених символів розглядається як n-символьне число в умовній системі числення в лишкових класах. Властивості цієї умовної системи лишкових класів (СЛК) використані для реалізації способів кодування/декодування. Це і визначило назву коду як код умовних лишків. Умовна система числення в лишкових класах вводиться як сукупність із "робочих" основ n системи числення рi (і=1, 2,…, n), які утворюють робочий діапазон системи [0, Р), P   pi , та i1 додаткової pn+1 (контрольної) основи рn+1=рk. Величина цієї контрольної основи при вирішенні задач виявлення спотворень повинна відповідати умові: рk≥рn, де рn - найбільша основа з їх сукупності. За допомогою контрольної 55 основи утворюється "повний" [0, R), P  n1  pi i1 1 та "контрольний" [Р, R) діапазони. Для UA 78181 U 5 10 забезпечення відповідності умовного числа вимогам системи числення в лишкових класах величини основ pi цієї умовної СЛК повинні задовольняти умові pi>s. Окрім робочих та контрольних основ визначають константи СЛК: Вi - ортогональні базиси, такі що Вi=mi·R/рi; mi - "вага" і-го ортогонального базису така, що {Вi·mi}mod pi=1. Для вирішення задач виявлення спотворень в ЛУ-коді за цим способом використовують властивості СЛК, коли при визначенні надмірних символів (контрольних ознак) в ЛУ-коді розраховують контрольну ознаку по додатковій (контрольній) основі рk. В таких умовах ЛУ-код дозволяє знаходити 6-розрядні пакети спотворень, згруповані в межах будь-якого з n узагальнених символів. Потрібна при цьому надмірність складає близько r≈b+1 двійкових розрядів (r=[log2рk]+1), де позначка [х] означає обчислення цілої частини від х. В основі цього способу лежить той факт, що будь-яке спотворення в одній із груп розрядів i k 15 переводить початкове число А з робочого діапазону [0, P   pi ) до діапазону [Р, R=рk·Р), тобто 20 призводить до збільшення початкового числа АР=R/рk тобто навіть при li=1 величина R/pi>R/pk за тієї причини, що pk>pі. ~ Відтак, сума A  A'A  P , тобто спотворене число, вийшло за межі робочого діапазону Р і попало до діапазону [Р, R). Отже, цей факт використовується в алгоритмах декодування запропонованого способу. Отже для застосування запропонованого способу здійснюють кодування коду початкового nсимвольного інформаційного об'єкта шляхом обчислення контрольної ознаки (лишку) в ЛУ-коді по додатковій (контрольній) основі рk і, в подальшому, зберігають чи передають цей інформаційний об'єкт разом із визначеною контрольною ознакою. Контрольну ознаку для початкового інформаційного об'єкта, що розглядається як nсимвольне число в умовній системі числення в лишкових класах, розраховують як лишок від початкового інформаційного об'єкта по додатковій (контрольній) основі рk. Із цією метою здійснюють перетворення початкового інформаційного об'єкта із умовної системи числення в лишкових класах в позиційну систему числення з використанням відомого співвідношення: n1 n1   A /    iBi  1/ R    iBi   R ,   i1 i1   де i (i=1, 2,…, n) - лишки від розподілу умовного числа A на основи pi (i=1, 2,…, n) введеної умовної системи числення в литкових класах, та обчислюють контрольну ознаку як лишок від цієї величини по контрольній основі рk: n1 n1    k  { A / } mod pk  {   iBi  1/ R    iBi   R} mod pk .   i1 i1   Оскільки другий доданок останнього виразу є кратним контрольній основі рk, то цей вираз набуває вигляду: n1  k  { A / } mod pk  {  iBi } mod pk . i1 50 На етапі кодування контрольну ознаку можна розрахувати також з виразу: k  (pk  P  [Z  pk ]) (mod pk ) . 2 UA 78181 U 5 10 15 20 25 30 35 Порядок обчислення величини Z визначено нижче. На етапі декодування для виявлення спотворень у Z-алгоритмі використовують відмічений вище факт, що спотворене число виходить за межі робочого діапазону, тобто: ~ A  P . (1) Далі використовують співвідношенням для переводу чисел з СЛК у позиційну систему числення: n1   ~ n1 A    iBi  1/ R    iBi   R , (2)   i1 i1   де Bi - константа системи числення, її ортогональний базис, причому Bi  R  mi / pi , (i  1 2,..., n  1) ; (3) , (n+1) - число умовних основ, включаючи контрольну; mi - "вага" ортогонального базису Вi. Підставляють вираз (2) у (1) та з урахуванням (3), отримують: n1 n1     iRm i / pi  1/ R    iRm i / pi   R  R / pk . (4)   i1 i1   Скорочують обидві частини (4) на R, отримують, що в разі наявності спотворень, Z>1/pк, (5) де n1 n1  Z    imi / pi     imi / pi  . (6)  i1  i1   Вирази (5), (6) визначають Z-алгоритм декодування для ЛУ-коду, який визначає наявність спотворень. Цей алгоритм включає (n+1) незалежних операцій множення коду i-ї групи (i=1,…, n+1) на відповідні константи і потім додавання (n+1) отриманих добутків. Джерела інформації: 1. Жураковський Ю.П. Теорія інформації та кодування/ Ю.П. Жураковський, В.П. Полторак / Навчальний посібник - К.: Вища школа, 2001. - 255 с. 2. Акушский И.Я. Машинная арифметика в остаточных классах / И.Я. Акушский, Д.И. Юдицкий // М.: Сов. радио, 1966. - 421 с. 3. Василенко B.C. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об'єктів. Код умовних лишків / B.C. Василенко, О.А. Матов // Реєстрація, зберігання і обробка даних - 2006. - Т. 8, № 3. - С. 48-66. 4. Василенко B.C. Узагальнений завадостійкий код умовних лишків в задачах забезпечення цілісності впливів / B.C. Василенко, O.K. Юдін // Радіотехніка. Всеукраїнська міжвідомча науково-технічна збірка. Темат. вип… "Проблеми телекомунікацій". - Харків: ХНУРЕ, 2007. - Вип. 148 - С. 228-233. 5. Пат. 67988 Україна, МПК Н03М 13/00 Спосіб забезпечення цілісності інформації на базі завадостійкого коду умовних лишків/ Василенко B.C., Василенко М.Ю., Чунарьов А.В.; заявник та патентовласник Нац. авіац. ун-т. - u201110207; заявл. 19.08.2011; опубл. 12.03.2012, Бюл. №. 5-4 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 40 Спосіб виявлення спотворень в коді умовних лишків із застосуванням Z-алгоритму, що полягає у використанні механізму формування контрольних ознак, який відрізняється тим, що сформовані на етапі кодування контрольні символи надають змогу при декодуванні прийняти рішення про відсутність чи наявність спотворень в інформаційному повідомленні. Комп’ютерна верстка В. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3