Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів
Для використання в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів запропоновано узагальнені завадостійкі коді. Для использования в задачах обеспечения целостности информационных объектов в условиях естественных влияний предложены обобщенные помехоустойчивые коды. G...
Saved in:
| Published in: | Реєстрація, зберігання і обробка даних |
|---|---|
| Date: | 2006 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50864 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 64-74. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859596082565087232 |
|---|---|
| author | Матов, О.Я. Василенко, В.С. |
| author_facet | Матов, О.Я. Василенко, В.С. |
| citation_txt | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 64-74. — Бібліогр.: 4 назв. — укр. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Для використання в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів запропоновано узагальнені завадостійкі коді.
Для использования в задачах обеспечения целостности информационных объектов в условиях естественных влияний предложены обобщенные помехоустойчивые коды.
Generalized noise combating codes for the use in the tasks of providing integrity of information holding objects in the conditions of natural factors influence are proposed.
|
| first_indexed | 2025-11-27T21:02:23Z |
| format | Article |
| fulltext |
64
УДК 004.056.2
О. Я. Матов1, В. С. Василенко2
1Інститут проблем реєстрації інформації НАН України
вул. М. Шпака, 2, 03113 Київ, Україна
2Національний авіаційний університет
пр. Космонавта Комарова, 1, 03058 Київ, Україна
Узагальнені завадостійкі коди в задачах
забезпечення цілісності інформаційних об’єктів
в умовах природних впливів
Для використання в задачах забезпечення цілісності інформаційних
об’єктів в умовах природних впливів запропоновано узагальнені завадо-
стійкі коді.
Ключові слова: виявлення викривлень, виправлення викривлень, конт-
роль цілісності, завадостійкі корегувальні коди.
Вступ
Для забезпечення контролю та поновлення цілісності інформаційних об’єктів
в умовах тих чи інших руйнуючих впливів до складу інформації, яка захищається,
включають надмірну інформацію — ознаку цілісності або контрольну ознаку (за-
лежно від прийнятої в задачах контролю цілісності або завадостійкого кодування
термінології) — своєрідний образ, відображення цієї інформації, процедура фор-
мування якого відома, і який із дуже високою вірогідністю відповідає інформації,
що захищається [1].
При цьому між інформацією, що захищається, і ознаками цілісності, або кон-
трольними ознаками встановлюється регулярний (функціональний) односторон-
ній зв’язок (процедури розрахунку контрольної ознаки за початковою інформаці-
єю, що захищається, відомі, а процедури розрахунку початкової інформації за ко-
нтрольними ознаками найчастіше не існує). Контроль цілісності (на відсутність
викривлень) зводиться при цьому до тих або інших процедур перевірки наявності
вказаного регулярного (функціонального) одностороннього зв’язку між ознаками
цілісності та прийнятою з каналу зв’язку (або зчитаною з запам’ятовуючого при-
строю (ЗП)) інформацією.
Характерною особливістю випадкових (природних) викривлень є те, що вони,
через їхню хаотичність, відсутність навмисності, порушують регулярний (функці-
ональний) односторонній зв’язок між прийнятою (або зчитаною з ЗП) інформаці-
єю й ознаками цілісності, сформованими перед передачею (перед записом у ЗП).
© О. Я. Матов, В. С. Василенко
Узагальнені завадостійкі коди в задачах
забезпечення цілісності інформаційних об’єктів в умовах природних впливів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 65
Тому при виявленні порушення вказаного зв’язку встановлюється факт наявності
таких викривлень, а за певних умов, і їхнього місця та величини (характеру). За
відсутності порушення цього зв’язку встановлюється факт відсутності викрив-
лень.
Одним зі способів (механізмів) забезпечення цілісності інформації в умовах
природних дій (проблема завадостійкості) для каналів телекомунікаційних мереж
(взагалі для мереж передачі даних) є застосування різного роду завадостійких ко-
регувальних кодів (ЗКК), які дозволяють реалізувати програмні, апаратурні або
програмно-апаратурні засоби виявлення та усунення викривлень.
Цей спосіб (механізм) забезпечення цілісності інформаційних об’єктів наразі
знайшов широке застосування в стандартах радіозв’язку, наприклад, стільниково-
го. Він не потребує зворотного каналу й забезпечує, як правило, прийнятне зна-
чення часу затримки передавання інформаційних об’єктів. Тому, чи не єдиною
проблемою в цих мережах із використанням радіоканалів є проблема забезпечен-
ня цілісності інформаційних об’єктів в умовах впливу навіть природних (не гово-
рячи вже про штучні, навмисні завади) пакетних викривлень як «коротких» (три-
валістю 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-а група
При кодуванні та декодуванні операції над узагальненими символами пропо-
нується виконувати за деяким модулем, тобто розшукувати лишок від розподілу
результату операції на деякий модуль. Це дало авторам можливість, у разі засто-
О. Я. Матов, В. С. Василенко
66
сування алгоритмів, які можуть бути аналогічними відповідним алгоритмам коду-
вання–декодування двійкових кодів, але по відношенню до узагальнених симво-
лів, для відмінності відповідних узагальнених кодів від двійкових увести в їхню
назву слово «лишок», тобто говорити про лишково-Хеммінгові (ЛХ), лишково-
матричні (ЛМ), лишково-згорточні (ЛЗ) чи лишково-ланцюгові (ЛЛ) та інші коди.
Принципи побудови та застосування таких кодів розглянемо на прикладі ли-
ше деяких із таких кодів. У разі потреби читач може самостійно застосувати ви-
кладені підходи й по відношенню до інших кодів цього класу.
У лишково-Хеммінгових кодах двійкові базові кодові слова, розбиті на 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:
Узагальнені завадостійкі коди в задачах
забезпечення цілісності інформаційних об’єктів в умовах природних впливів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 67
α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.
О. Я. Матов, В. С. Василенко
68
Знаючи величину (ά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, корекція якого
нескладна.
У лишково-матричних кодах БКС розбивається на узагальнені символи, які
зводяться в прямокутну матрицю розмірності m´n (m стовпців і n рядків) (рис. 1).
mnnmnm
mmm
m
aaa
aaa
aaa
...
......
...
...
2)1(1)1(
221
21
+-+-
++ .
Рис. 1. Представлення БКС у вигляді матриці
Узагальнені завадостійкі коди в задачах
забезпечення цілісності інформаційних об’єктів в умовах природних впливів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 69
Ця матриця при кодуванні розширюється на один рядок і один стовпець за
рахунок перевірочних символів, кожний з яких є доповненням до s суми за моду-
лем s елементів відповідного рядка або відповідного стовпця, при цьому одержу-
ють нову розширену матрицю (рис. 2), яка записується в ЗП (передається до кана-
лу зв’язку).
ååå
å
å
å
==
+-
=
+-
=
+-+-+-
=
+++
=
---
-
-
-
n
k
nm
n
k
km
n
k
km
m
i
inmnmnmnm
m
i
immmm
m
i
im
ssssss
ss
ss
ss
11
2)1(
1
1)1(
1
)1(2)1(1)1(
1
221
1
21
) (mod...) (mod) (mod
) (mod...
.......
) (mod...
) (mod...
aaa
aaaa
aaaa
aaaa
Рис. 2. Представлення БКС у вигляді розширеної матриці
При декодуванні викривлених БКС ті перевірочні елементи з додаткових ря-
дка й стовпця, які відповідають рядку або стовпцю, що містить викривлені симво-
ли, відрізнятимуться від нуля, що дає можливість визначати місце викривлення.
Якщо викривленим є тільки один елемент у рядку й стовпці, то ненульове значен-
ня відповідних перевірочних символів визначить величину цієї помилки. У цьому
значенні можливості ЛМ-коду по відношенню до узагальнених символів повністю
співпадатимуть із можливостями по виявленню й виправленню викривлень двій-
кового матричного коду по відношенню до двійкових символів.
Приклад. Нехай необхідно закодувати ЛМ-кодом восьмирозрядне БКС
10.00.11.10. Для b = 2 і s = 4 одержимо матрицю:
43
21
aa
aa
=
0111
0010
.
Після кодування розширена матриця матиме вигляд:
))(mod())(mod(
))(mod(
))(mod(
4231
4343
2121
ssss
ss
ss
aaaa
aaaa
aaaa
+-+-
+-
+-
=
1111
000111
100010
.
Нехай зчитана (прийнята з каналу зв’язку) послідовність, що відповідає на-
ступній матриці (викривлений елемент першого рядка другого стовпчика):
О. Я. Матов, В. С. Василенко
70
1111
000111
100110
.
У результаті декодування шляхом додавання за модулем s усіх елементів
(включно з додатковими) відповідних рядків та стовпців, одержуємо матрицю
0100
000111
010110
,
з якої виходить, що викривленим є елемент першого рядка й другого стовпця, а
величина викривлення дорівнює 01. Після чого корекція b-розрядного викривлен-
ня стає тривіальною.
Узагальнений завадостійкий код умовних лишків.
Алгоритми кодування–декодування
Ще одним із прикладів узагальнених кодів є [1] код умовних лишків (лишків
умовних код, ЛУ-код), який дозволяє знаходити й виправляти b-розрядні пакети
викривлень, згруповані в межах будь-якого з n узагальнених символів і потребує
при цьому надмірність біля
r ≈ 2b + 1
двійкових розрядів (оскільки рk ≈ 2рn рn+1, r = [log2рk] + 1).
Оскільки в основі ЛУ-коду лежать властивості системи лишкових класів
(СЛК), то в цьому коді принципово можуть бути використані відомі алгоритми
кодування–декодування. До таких алгоритмів відносяться алгоритм нулізації і,
так званий Z-алгоритм [4].
В основі цих алгоритмів лежить той факт, що будь-яке викривлення в одній із
груп розрядів αі переводить початкове число з робочого діапазону [0, P = Õ
=
k
i
ip
1
)
до діапазону [P, R = pk·Р), тобто призводить (див. рис. 3) до збільшення початко-
вого числа А′ < Р на деяку величину li·Ri. Тут li і Ri = R/ pi — цілі числа. Дійсно,
якщо вихідне число
А = α1, α2, …, αi,…,αn, αk
є викривленим по основі pi і має вигляд:
A~ = α1, α2, …, ia~ ,…, αn, αk,
Узагальнені завадостійкі коди в задачах
забезпечення цілісності інформаційних об’єктів в умовах природних впливів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 71
де
ia~ = {αi + Δαi } (mod pi),
то це є еквівалентним наступному перетворенню (при виконанні операцій у лиш-
кових класах):
A~ = (α1, α2, …, αi,…, αn, αk) + (0, 0, …, Δαi, …,0, 0) =
= (α1, α2, …, {αi + Δαi } (mod pi),…, αn1, αk).
0 PA 2·P k· P A/= li·Ri + A
R
. . . . . .
(pk - 1)·P
Рис. 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.
Відтак, сума A~ = А′ + ΔА > Р, тобто викривлене число, вийшло за межі робо-
чого діапазону Р і попало до діапазону [P, R). Отже, цей факт можна використати
в алгоритмах кодування–декодування. Один із таких алгоритмів — алгоритм ну-
лізації — розглянуто в [1]. У цій статті розглянемо ще один — Z-алгоритм.
Для виявлення викривлень у Z-алгоритмі використовується відмічений вище
факт, що викривлене число виходить за межі робочого діапазону, тобто:
A~ ≥ Р. (3)
Скористаємось відомим співвідношенням для переводу чисел з СЛК у пози-
ційну систему числення:
A~ = RBRB
ni
i
iii
ni
i
i ´ú
û
ù
ê
ë
é
- åå
+=
=
+=
=
1
1
1
1
)/1( aa , (4)
О. Я. Матов, В. С. Василенко
72
де Ві — константа системи числення, її ортогональний базис, причому
Ві = R·mi/pi, (i = 1, 2, …, n + 1); (5)
(n + 1) — число умовних основ, включаючи контрольну; mi — ціле позитивне чи-
сло («вага» ортогонального базису Ві), таке, при якому miВі (mod pi) = 1.
Підставивши вираз (4) у (3) з урахуванням (5), отримаємо:
k
ni
i
iiiii
ni
i
i pRRpRmRpRm //)/1(/
1
1
1
1
>´ú
û
ù
ê
ë
é
- åå
+=
=
+=
=
aa . (6)
Скоротивши обидві частини (6) на R, отримаємо, що в разі наявності викрив-
лень,
Z > 1/рк, (7)
де
ú
û
ù
ê
ë
é
-= åå
+
=
+
=
1
1
1
1
//
n
i
iiii
n
i
ii pmpmZ aa . (8)
Вирази (7), (8) визначають Z-алгоритм декодування для ЛУ-коду, який лише
визначає наявність викривлень. Цей алгоритм включає (n + 1) незалежних (за не-
обхідності одночасних) операцій множення коду i-ї групи (i = 1,…, n + 1) на від-
повідну константу і потім додавання (n + 1) отриманих добутків.
Для побудови алгоритму, здатного не лише визначати наявність, але й випра-
вляти викривлення, скористаємось наступними міркуваннями.
Оскільки викривлення по i-й основі, як показано вище, має величину
ΔА = li·Ri = li·R/pi, то очевидним є нерівність:
A~ - li·Ri < Р, (9)
причому величина li·визначається з виразу:
[ A~ /Ri] = [(A + li·Ri) / Ri] = li. (10)
Тоді з урахуванням (4)–(6), (9) вираз (10) набуде вигляду:
Z·pi – [Z·pi] < pi/рк, (11)
Ясно, що вираз (6) і еквівалентний йому вираз (11) справедливі лише для тієї
основи pi, у лишку якої мається викривлення. Відтак, вираз (11) дозволяє визначи-
ти місце (номер групи), де виникло викривлення. Неважко впевнитися, що вели-
чина цього викривлення:
Узагальнені завадостійкі коди в задачах
забезпечення цілісності інформаційних об’єктів в умовах природних впливів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 73
.}]{[}]/~{[
ipiiipiii RZpRRA ×=×=Da
Власне виправлення зводиться до операції:
.}{
ipiii aaa D-= (
(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.
О. Я. Матов, В. С. Василенко
74
Оскільки, згідно з виразом (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 — нерівність є справедливою.
Звідки витікає висновок про викривлення в третій групі розрядів величиною
3
}]{[ 333 pRZp ×=Da = {[1,03561,22]·1420}7 = {1420}7 = 6,
тому
3333 }{ paaa D-= = {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.
Надійшла до редакції 08.12.2006
11.10.10.00.00.11.01 = α1, α2, α3, α4, α5, α6, α7,
11.10.10.00.00.11.01 = α1, α2, α3, α4, α5, α6, α7,
11.10.10.00.00.11.01 = α1, α2, α3, α4, α5, α6, α7,
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.
Після обчислення нових контрольних символів, одержимо:
звідки
Δαj = {άi − αi}s. (2)
Для вищерозглянутого прикладу:
або
що і є насправді.
з якої виходить, що викривленим є елемент першого рядка й другого стовпця, а величина викривлення дорівнює 01. Після чого корекція b-розрядного викривлення стає тривіальною.
двійкових розрядів (оскільки рk ≈ 2рn рn+1, r = [log2рk] + 1).
є викривленим по основі pi і має вигляд:
де
то це є еквівалентним наступному перетворенню (при виконанні операцій у лишкових класах):
= (α1, α2, …, αi,…, αn, αk) + (0, 0, …, Δαi, …,0, 0) =
оскільки тільки число вигляду
має всі лишки, окрім лишка по основі pi, такими, що дорівнюють нулю. Але ΔА = li·Ri > P = R/pk, тобто навіть при li = 1 величина R/pi > R/pk за тієї причини, що pk > pi.
де Ві — константа системи числення, її ортогональний базис, причому
де
причому величина li·визначається з виразу:
Тоді з урахуванням (4)–(6), (9) вираз (10) набуде вигляду:
Власне виправлення зводиться до операції:
і тоді вирази (8), (13) визначають Z-алгоритм кодування.
де позначка ]х[ означає обрахування дробової частини від величини х.
Тоді
то робимо висновок про наявність викривлення в наданій кодовій комбінації.
тому
|
| id | nasplib_isofts_kiev_ua-123456789-50864 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Ukrainian |
| last_indexed | 2025-11-27T21:02:23Z |
| publishDate | 2006 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Матов, О.Я. Василенко, В.С. 2013-11-05T20:00:37Z 2013-11-05T20:00:37Z 2006 Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 64-74. — Бібліогр.: 4 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50864 004.056.2 Для використання в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів запропоновано узагальнені завадостійкі коді. Для использования в задачах обеспечения целостности информационных объектов в условиях естественных влияний предложены обобщенные помехоустойчивые коды. Generalized noise combating codes for the use in the tasks of providing integrity of information holding objects in the conditions of natural factors influence are proposed. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів Обобщенные помехоустойчивые коды в задачах обеспечения целостности информационных объектов в условиях естественных влияний Generalized Noise Combating Codes in the Tasks of Providing Integrity of Information Holding Objects in the Conditions of Natural Factors Influence Article published earlier |
| spellingShingle | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів Матов, О.Я. Василенко, В.С. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів |
| title_alt | Обобщенные помехоустойчивые коды в задачах обеспечения целостности информационных объектов в условиях естественных влияний Generalized Noise Combating Codes in the Tasks of Providing Integrity of Information Holding Objects in the Conditions of Natural Factors Influence |
| title_full | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів |
| title_fullStr | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів |
| title_full_unstemmed | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів |
| title_short | Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів |
| title_sort | узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об’єктів в умовах природних впливів |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50864 |
| work_keys_str_mv | AT matovoâ uzagalʹnenízavadostíikíkodivzadačahzabezpečennâcílísnostíínformacíinihobêktívvumovahprirodnihvplivív AT vasilenkovs uzagalʹnenízavadostíikíkodivzadačahzabezpečennâcílísnostíínformacíinihobêktívvumovahprirodnihvplivív AT matovoâ obobŝennyepomehoustoičivyekodyvzadačahobespečeniâcelostnostiinformacionnyhobʺektovvusloviâhestestvennyhvliânii AT vasilenkovs obobŝennyepomehoustoičivyekodyvzadačahobespečeniâcelostnostiinformacionnyhobʺektovvusloviâhestestvennyhvliânii AT matovoâ generalizednoisecombatingcodesinthetasksofprovidingintegrityofinformationholdingobjectsintheconditionsofnaturalfactorsinfluence AT vasilenkovs generalizednoisecombatingcodesinthetasksofprovidingintegrityofinformationholdingobjectsintheconditionsofnaturalfactorsinfluence |