Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів

О. Я. Матов, В. С. Василенко

Размещено на http://www.allbest.ru//

74

Размещено на http://www.allbest.ru//

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

О. Я. Матов

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

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

Вступ

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

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

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

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

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

Цей спосіб (механізм) забезпечення цілісності інформаційних об'єктів наразі знайшов широке застосування в стандартах радіозв'язку, наприклад, стільникового. Він не потребує зворотного каналу й забезпечує, як правило, прийнятне значення часу затримки передавання інформаційних об'єктів. Тому, чи не єдиною проблемою в цих мережах із використанням радіоканалів є проблема забезпечення цілісності інформаційних об'єктів в умовах впливу навіть природних (не говорячи вже про штучні, навмисні завади) пакетних викривлень як «коротких» (тривалістю 2...10 мс), так і особливо «довгих» (тривалістю 100…200 мс). Це є особливо актуальним для радіоканалів, наприклад, у системах стільникового зв'язку [2]. У цих каналах тривалість пакета викривлень може бути порівняною чи, навіть, значно перевищувати тривалість інформаційного пакета, що може суттєво вплинути на результативність процедур інформаційного обміну.

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

Узагальнені завадостійкі коди. Лишково-Хеммінгові та лишково-матричні коди

Нагадаємо, що під узагальненими [1] розуміються коди, призначені для виявлення (виявлення та виправлення) пакетних викривлень із кратністю b, у яких використовуються алгоритми кодування та декодування по відношенню до узагальнених b-розрядних символів.

У цих кодах початкова двійкова k-бітна кодова послідовність -- базове кодове слово (БКС) -- І1, 2, …, Іk розбивається на n = k/b груп двійкових розрядів -- узагальнених символів (УС) з розрядністю b, в яких передбачається виявлення та виправлення викривлень:

І1……Іb, Іb+1……І2b Іk-b+1 ……Іk

1-а група 2-а група n-а група

При кодуванні та декодуванні операції над узагальненими символами пропонується виконувати за деяким модулем, тобто розшукувати лишок від розподілу результату операції на деякий модуль. Це дало авторам можливість, у разі застосування алгоритмів, які можуть бути аналогічними відповідним алгоритмам кодування-декодування двійкових кодів, але по відношенню до узагальнених символів, для відмінності відповідних узагальнених кодів від двійкових увести в їхню назву слово «лишок», тобто говорити про лишково-Хеммінгові (ЛХ), лишково-матричні (ЛМ), лишково-згорточні (ЛЗ) чи лишково-ланцюгові (ЛЛ) та інші коди.

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

У лишково-Хеммінгових кодах двійкові базові кодові слова, розбиті на b-розрядні УС, записуються у вигляді б1, б2,…, бn, де бi ? s = 2b - 1, а N = b·n. Так само, як і у двійковому коді Хеммінга (класична форма запису коду) УС бі з номерами і = 2j (j = 0, 1,…) є перевірочними, решта символів -- інформаційні. Причому для отримання перевірочних символів при кодуванні використовується алгоритм для двійкового коду Хеммінга, але по відношенню до узагальнених символів. При цьому всі необхідні для кодування та декодування операції здійснюються за деяким модулем. Тобто, у ЛХ-коді для отримання першого перевірочного символу необхідно скласти за деяким модулем (одержати лишки від суми) усі УС базового кодового слова, що мають у коді свого номера одиницю в першому (молодшому) розряді; для отримання другого перевірочного символу -- скласти за модулем усі символи, що мають у коді свого номера одиницю в другому розряді, й т.д.

Як модуль для отримання контрольних символів досить зручно використовувати величину s = 2b тобто:

б1 = {б3 + б5 + б7 + ………………}s,

б2 = {б3 + б5 + б6 + б7 + …………}s,

………………………………

При такому значенні модуля потрібна розрядність перевірочних символів не відрізняється від розрядності узагальнених символів b.

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

Якщо приписати результатам порівняння значення 0, а результатам непорівняння значення 1, то одержана сукупність нулів і одиниць утворює код, який також, як і у двійковому коді Хеммінга, є номером викривленого символу.

Приклад. Нехай необхідно закодувати ЛХ-кодом восьмирозрядну (N = 8) послідовність 10001101. Якщо код орієнтований на виправлення двократних викривлень, то b = 2, кількість узагальнених символів n = N/b = 4. Як модуль для отримання контрольних символів використаємо величину s = 4. Відомо, що в коді Хеммінга при n = 4 потрібно три перевірочні символи б1, б2, б4, а інформаційними символами є б3 = 10, б5 = 00, б6 = 11, б7 = 01 Для отримання першого перевірочного символу складемо за модулем чотири б3, б5, б7:

б1 = {б3 + б5 + б7}4 = 11.

Аналогічно цьому:

б2 = {б3 + б6 + б7}4 = 10,

б4 = {б5 + б6 + б7}4 = 00.

Після кодування одержано код

11.10.10.00.00.11.01 = б1, б2, б3, б4, б5, б6, б7,

який може бути записаним у запам'ятовуючий пристрій, переданим до каналу зв'язку й т.д.

Нехай зчитаний або прийнятий із каналу зв'язку код має викривлення в п'ятій групі:

б1, б2, б3, б4, Ь5, б6, б7 = 11.10.10.00.01.11.01.

Після обчислення нових контрольних символів, одержимо:

б1 = {б3 + Ь5 + б7}4 = 00,

б2 = {б3 + б6 + б7}4 = 10,

б4 = {Ь5 + б6 + б7}4 = 01.

Результати порівняння дадуть код 101, оскільки перший та третій перевірочні символи не співпадають. Це свідчить про виявлення помилки в п'ятому символі, що й було насправді.

Неважко визначити й величину викривлення. Дійсно, будь-який із перевірочних символів, наприклад, бi, при викривленні деякого інформаційного, наприклад, бj, що приймає участь у формуванні символу бi, має величину:

Ьі = {бc + бd + … + {бj + Дбj} + …}s = {бі + Дбj}s, (1)

звідки

Дбj = {Ьi ? бi}s. (2)

Для вищерозглянутого прикладу:

Дб5 = {Ь1 - б1}4 = {00 ? 11}4 = 01,

або

Дб5 = {Ь4 - б4}4 = {01 ? 00}4 = 01.

Знаючи величину (Ьi) та місце викривлення (i), легко здійснити корекцію, оскільки з (2) витікає:

Бi = {Ьi ? Дбj}s.

У нашому прикладі

б5 = {Ь5 - Дб5}4 = {01 - 01}4 = 00,

що і є насправді.

Алгоритм декодування ЛХ-коду може бути спрощеним, якщо при кодуванні замість перевірочних символів бi в записану або передану послідовність записувати величину

Дбі = {s ? Дбj}s.

Тоді для вже розглянутого прикладу (б1 =11, б2 =10, б4 = 00) Дб1 = 01, Дб2 =

= 10, Дб4 = 00 записувати (передавати) необхідно код:

Дб1, Дб2, б3, Дб4, б5, б6, б7 = 01.10.10.00.00.11.01.

Якщо зчитано або прийнято слово з тим же викривленням, що й раніше, тобто

б1, б2, б3, б4, Ь5, б6, б7, = 01.10.10.00.01.11.01,

то після декодування отримаємо:

Дб1 = {б1 + б3 + Ь5 + б7}4 = 01,

Дб2 = {б2 + б3 + б6 + б7}4 = 00,

Дб4 = {б4 + Ь5 + б6 + б7}4 = 01.

При цьому, якщо відмінним від нуля перевірочним символам приписати значення 1, а іншим код 0, то одержимо код і = 101, що визначає місце викривлення, величина якого дорівнює значенню будь-якого ненульового перевірочного символу. Для розглянутого прикладу величина викривлення Дбі = 01, корекція якого нескладна.

У лишково-матричних кодах БКС розбивається на узагальнені символи, які зводяться в прямокутну матрицю розмірності mn (m стовпців і n рядків) (рис. 1).

.

Рис. 1. Представлення БКС у вигляді матриці

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

Рис. 2. Представлення БКС у вигляді розширеної матриці

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

Приклад. Нехай необхідно закодувати ЛМ-кодом восьмирозрядне БКС 10.00.11.10. Для b = 2 і s = 4 одержимо матрицю:

= .

Після кодування розширена матриця матиме вигляд:

= .

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

.

У результаті декодування шляхом додавання за модулем s усіх елементів (включно з додатковими) відповідних рядків та стовпців, одержуємо матрицю

,

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

Узагальнений завадостійкий код умовних лишків. Алгоритми кодування-декодування

Ще одним із прикладів узагальнених кодів є [1] код умовних лишків (лишків умовних код, ЛУ-код), який дозволяє знаходити й виправляти b-розрядні пакети викривлень, згруповані в межах будь-якого з n узагальнених символів і потребує при цьому надмірність біля

завадостійкий код інформаційний матриця

r ? 2b + 1

двійкових розрядів (оскільки рk ? 2рn рn+1, r = [log2рk] + 1).

Оскільки в основі ЛУ-коду лежать властивості системи лишкових класів (СЛК), то в цьому коді принципово можуть бути використані відомі алгоритми кодування-декодування. До таких алгоритмів відносяться алгоритм нулізації і, так званий z-алгоритм [4].

В основі цих алгоритмів лежить той факт, що будь-яке викривлення в одній із груп розрядів бі переводить початкове число з робочого діапазону [0, P = ) до діапазону [P, R = pk·Р), тобто призводить (див. рис. 3) до збільшення початкового числа А? < Р на деяку величину li·Ri. Тут li і Ri = R/ pi -- цілі числа. Дійсно, якщо вихідне число

А = б1, б2, …, бi,…,бn, бk

є викривленим по основі pi і має вигляд:

= б1, б2, …, ,…, бn, бk,

де

= {бi + Дбi } (mod pi),

то це є еквівалентним наступному перетворенню (при виконанні операцій у лишкових класах):

= (б1, б2, …, бi,…, бn, бk) + (0, 0, …, Дбi, …,0, 0) =

= (б1, б2, …, {бi + Дбi } (mod pi),…, бn1, бk).

Рис. 3. Вихід викривленого числа за межі робочого діапазону

При цьому величина викривлення перевищує величину робочого діапазону Р:

ДА = (0, 0, …, Дбi, …,0, 0) > Р,

оскільки тільки число вигляду

ДА = li·Ri = li·R/pi

має всі лишки, окрім лишка по основі pi, такими, що дорівнюють нулю. Але ДА = li·Ri > P = R/pk, тобто навіть при li = 1 величина R/pi > R/pk за тієї причини, що pk > pi.

Відтак, сума= А? + ДА > Р, тобто викривлене число, вийшло за межі робочого діапазону Р і попало до діапазону [P, R). Отже, цей факт можна використати в алгоритмах кодування-декодування. Один із таких алгоритмів -- алгоритм нулізації -- розглянуто в [1]. У цій статті розглянемо ще один -- z-алгоритм.

Для виявлення викривлень у z-алгоритмі використовується відмічений вище факт, що викривлене число виходить за межі робочого діапазону, тобто:

? Р. (3)

Скористаємось відомим співвідношенням для переводу чисел з СЛК у позиційну систему числення:

=, (4)

де Ві -- константа системи числення, її ортогональний базис, причому

Ві = R·mi/pi, (i = 1, 2, …, n + 1); (5)

(n + 1) -- число умовних основ, включаючи контрольну; mi -- ціле позитивне число («вага» ортогонального базису Ві), таке, при якому miВі (mod pi) = 1.

Підставивши вираз (4) у (3) з урахуванням (5), отримаємо:

. (6)

Скоротивши обидві частини (6) на R, отримаємо, що в разі наявності викривлень,

z > 1/рк, (7)

де

. (8)

Вирази (7), (8) визначають z-алгоритм декодування для ЛУ-коду, який лише визначає наявність викривлень. Цей алгоритм включає (n + 1) незалежних (за необхідності одночасних) операцій множення коду i-ї групи (i = 1,…, n + 1) на відповідну константу і потім додавання (n + 1) отриманих добутків.

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

Оскільки викривлення по i-й основі, як показано вище, має величину

ДА = li·Ri = li·R/pi, то очевидним є нерівність:

li·Ri < Р, (9)

причому величина li·визначається з виразу:

[/Ri] = [(A + li·Ri) / Ri] = li. (10)

Тоді з урахуванням (4)-(6), (9) вираз (10) набуде вигляду:

z·pi - [z·pi] < pi/рк, (11)

Ясно, що вираз (6) і еквівалентний йому вираз (11) справедливі лише для тієї основи pi, у лишку якої мається викривлення. Відтак, вираз (11) дозволяє визначити місце (номер групи), де виникло викривлення. Неважко впевнитися, що величина цього викривлення:

Власне виправлення зводиться до операції:

(12)

Таким чином, вирази (8), (11), (12) визначають z-алгоритм декодування для корегувального ЛУ-коду.

Причому, оскільки лишки по будь-яким основам є рівноправними, то все сказане вище відноситься й до контрольної основи. Прийнявши на етапі кодування бk = 0, отримаємо:

бk = (рk P[Zрk]) (mod рk), (13)

і тоді вирази (8), (13) визначають z-алгоритм кодування.

Розглянемо приклади використання z-алгоритму стосовно р1 = 4, р2 = 5, р3 =

= 7, рk = 71, розрахувавши попередньо константи, які є необхідними для визначення змінних z. Для обраних умов отримаємо: Р = 4·5·7 = 140; R = Р·рk = 9940.

При цьому R1 = 2485; R2 = 1988; R3 = 1420; R4 = Р = 140, m1 = 1; m2 = 2; m3 = 6; m4 = 3. Позначивши значення mi /pi як gi, отримаємо:

g1 = 0,25; g2 = 0,4; g3 = 0,85714; g4 = 0,493257.

Приклад. Закодувати повідомлення 11.01.10 із використанням z-алгоритму ЛУ-коду. Приймемо на етапі кодування б4 = 0. З виразу (8) отримаємо:

Z = ]б1·g1 + б2·g2 + б3·g3 + б4·g4[ =

= ]3·0,25 + 1·0,4 + 2·0,857142 + 0·0,493257[ = ]2,86428[ = 0,86428,

де позначка ]х[ означає обрахування дробової частини від величини х.

Тоді, згідно з (13):

б4 = (р4 P?[z?р4]) (mod р4) = (71 140?[0,86428?71]) (mod 71) = 51(10) = 110011(2).

Приклад. Знайти й виправити викривлення в повідомленні, що використане вище, де

Г = 11.01.01.110011.

Тоді

Z = ]3·0,25 + 1·0,4 + 1·0,857142 + 51·0,493257[ = ]27,147949[ = 0,147949.

Оскільки, згідно з виразом (7):

z = 0,147949 > 1/рk,

то робимо висновок про наявність викривлення в наданій кодовій комбінації.

Для виявлення місця викривлення оцінюємо справедливість нерівностей (11):

z·p1 - [z·p1] = 0,91796 < p1/рk = 0,09859 -- нерівність не є справедливою,

z·p2 - [z·p2] = 0,739745 < p2 /рk = 0,070422 -- нерівність не є справедливою,

z·p3 - [z·p3] = 0,035643 < p3/рk = 0,09859 -- нерівність є справедливою.

Звідки витікає висновок про викривлення в третій групі розрядів величиною

= {[1,03561,22]·1420}7 = {1420}7 = 6,

тому

= {1 - 6}7 = 2 = 10(2).

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

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

Література

1. Матов О.А., Василенко В.С. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об'єктів. Код умовних лишків. // Реєстрація, зберігання і оброб. даних. -- 2006. -- Т. 8, № 3. -- С. 48-66.

2. Дубровский В.В. CDMA -- взгляд глазами профессионала // mailto:v_dubrovskii@mail.ru.

3. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. -- М.: Сов. радио, 1966. -- 421 с.

4. Василенко В.С., Будько М.М., Короленко М.П. Контроль и відновлення цілісності інформації в автоматизованих системах // Правове, нормативне та метрологічне забезпечення Системи захисту інформації в Україні. -- К.: НТУУ «КПІ», 2002. -- Вип. 4. -- С. 119-128.

Размещено на Allbest.ru

...