Блокові згорткові коди в задачах контролю цілісності
Для задач контролю цілісності інформаційних об’єктів в умовах природних впливів запропоновано блоковий згортковий код з використанням алгоритмів кодування–декодування, що є притаманними класичному завадостійкому корегувальному згортковому коду, який був би спроможний забезпечити виявлення та виправл...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2007 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50879 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Блокові згорткові коди в задачах контролю цілісності / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 1. — С. 100-107. — Бібліогр.: 4 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859848015756394496 |
|---|---|
| author | Матов, О.Я. Василенко, В.С. |
| author_facet | Матов, О.Я. Василенко, В.С. |
| citation_txt | Блокові згорткові коди в задачах контролю цілісності / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 1. — С. 100-107. — Бібліогр.: 4 назв. — укр. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Для задач контролю цілісності інформаційних об’єктів в умовах природних впливів запропоновано блоковий згортковий код з використанням алгоритмів кодування–декодування, що є притаманними класичному завадостійкому корегувальному згортковому коду, який був би спроможний забезпечити виявлення та виправлення подвійних викривлень.
Для задач контроля целостности информационных объектов в условиях естественных воздействий предложен блочный сверточный код с использованием алгоритмов кодирования– декодирования, присущих классическому помехоустойчивому корректирующему сверточному коду, который способен обеспечить выявление и исправление двойных искажений.
The task of construction of block convolutional code with the use of encoding–decoding algorithms, which are inherent to the classic noise-combating, correcting convolutional code which would be able to provide the detection and correction of double distortions, is considered.
|
| first_indexed | 2025-12-07T15:40:05Z |
| format | Article |
| fulltext |
100
УДК 004.056.2
О. Я. Матов1, В. С. Василенко2
1Інститут проблем реєстрації інформації НАН України
вул. М. Шпака, 2, 03113 Київ, Україна
2Національний авіаційний університет
вул. Космонавта Комарова, 1, 03058 Київ, Україна
Блокові згорткові коди в задачах контролю цілісності
Для задач контролю цілісності інформаційних об’єктів в умовах при-
родних впливів запропоновано блоковий згортковий код з використан-
ням алгоритмів кодування–декодування, що є притаманними класич-
ному завадостійкому корегувальному згортковому коду, який був би
спроможний забезпечити виявлення та виправлення подвійних викрив-
лень.
Ключові слова: базове кодове слово, викривлення, згортковий код, ін-
формаційний обмін.
Вступ
Відомо [1–3], що канали, якими передається інформація, практично ніколи не
бувають ідеальними (каналами без завад). У них завжди присутні завади, і мова
може йти лише про рівні завад (співвідношення сигнал/завада) та їхній спектра-
льний склад. Завади в каналах утворюються з різних причин, але результат їхньої
дії на передану інформацію завжди один — порушується цілісність інформацій-
них об’єктів, інформація спотворюється (втрачається).
Для запобігання втратам інформації в каналі застосовуються різноманітні за-
вадостійкі надмірні коди (коди з надмірністю). Перевага завадостійкого коду по-
лягає у тому, що при прийомі його із викривленнями (кількість викривлених сим-
волів залежить від ступеня надмірності й структури коду) інформація може бути
відновлена. Для різних завад у каналі існують різні за своєю структурою та надмі-
рністю коди. Звичайно надмірність кодів знаходиться в межах 10 … 60 % або тро-
хи більше, залежно від умов та мети їхнього застосування. Наприклад, надмір-
ність 25 % застосовується при записі інформації на лазерні диски і в системах ци-
фрового супутникового телебачення [3].
Відоме велике число завадостійких кодів, які класифікуються за різними
ознаками. Виходячи зі змісту статті, відмітимо лише, що відомі завадостійкі згор-
токові коди відносяться до роздільних, безперервних, які характеризуються тим,
© О. Я. Матов, В. С. Василенко
Блокові згорткові коди в задачах контролю цілісності
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 101
що операції кодування й декодування здійснюються над безперервною послідов-
ністю символів без розбиття її на блоки.
Серед безперервних найбільш застосовні згорткові коди. У цих кодах кожні n
символів складаються, як і в інших кодах, із m інформаційних і k перевірочних. Ці
коди можуть мати різну надлишковість, але найбільш просто вони реалізуються
при m = k, тобто коли n = 2m = 2k, а надмірність Rk = m/n = 0,5. Тоді відносну
швидкість передачі R можна записати у вигляді:
R = 1 – Rk = m/n = m/2m = 0,5.
У цьому коді алгоритмами формування перевірочних та контрольних симво-
лів створюються послідовно пов’язані ланцюги, що й відображено в одній із назв
коду «ланцюговий».
Безперечною перевагою згорткових кодів є можливість виявляти й виправля-
ти групові викривлення, а певним недоліком — звуження області застосування
лише потоковими кодами, що при передачі, наприклад, коротких повідомлень в
умовах зашумленого каналу, створює певні труднощі. Ці труднощі полягають у
неможливості формування відомими методами контрольних та перевірочних сим-
волів для символів, які розташовані на початку та в кінці інформаційних блоків.
У статті показана можливість побудови блокового згорткового коду з вико-
ристанням алгоритмів кодування–декодування, які є притаманними для класично-
го згорткового коду, і не має зазначених вад.
Побудова блокового згорткового коду
При блоковому кодуванні послідовність елементарних повідомлень джерела
розбивається на відрізки, і кожному відрізку ставиться у відповідність певна пос-
лідовність (блок) кодових символів, звана звично кодовою комбінацією чи базо-
вим кодовим словом. Саме безліч усіх кодових комбінацій, можливих при даному
способі блокового кодування, і є блоковим кодом.
Для побудови згаданого блокового згорткового коду як блок чи як базове ко-
дове слово будемо розглядати фрагмент одного з незалежних ланцюгів непере-
рвного коду, в якому кількість інформаційних символів обмежимо величиною m.
У цьому коді, як і в рекурентному, ланцюговому коді, формується k = m пере-
вірочних символів. Як у відомого ланцюгового коду кожен із них формується
шляхом додавання за модулем 2 двох суміжних інформаційних так, що будь-який
інформаційний символ використовуються для формування двох перевірочних.
Перевірочні символи розташовуються між інформаційними після другого з інфо-
рмаційних, який використовувався для його формування.
Для формування першого та останнього перевірочних символів пропонується
додавати за модулем 2 останній (m-й) та перший інформаційні символи даного
базового кодового слова. Цей перевірочний символ пропонується розташувати
після першого інформаційного. Таким чином, на погляд авторів, усувається зазна-
чена у вступі вада.
Основні операції алгоритму кодування–декодування утвореного блокового
коду пропонується здійснювати як і у відомого ланцюгового. Зокрема, на боці
О. Я. Матов, В. С. Василенко
102
приймача з інформаційних символів ( /a ) за тими ж правилами, що й перевірочні,
на боці передавача, формуються контрольні. Контрольні символи порівнюються із
перевірочними і, в разі їхнього неспівпадання, формується висновок про наявність
викривлення.
Передавання
Приймання
2,121 Пaa =Å , 3,232 Пaa =Å 2,1
/
2
/
1 Kaa =Å , 3,2
/
3
/
2 Kaa =Å
… …
mmmm Пaa ,11 -- =Å , 1,1 mm Пaa =Å mmmm Kaa ,1
//
1 -- =Å , 1,
/
1
/
mm Kaa =Å
Кожен контрольний символ порівнюється із відповідним перевірочним:
=+1,iiS /
1,1, ++ Å iiii ПK , =++ 2,1 iiS /
2,12,1 ++++ Å iiii ПK і т.д.
Ознакою відсутності викривлень є те, що всі суми дорівнюють нулю:
=+1,iiS =++ 2,1 iiS …= 0.
Зрозуміло, що викривленим може бути як інформаційний, так і перевірочний
символ. На викривлення перевірочного символу покаже те, що лише одна із сум
дорівнює одиниці. Наприклад, при викривленні /
1, +iiП отримаємо 11, =+iiS , оскіль-
ки 1, +iiK не співпадає з /
1, +iiП . Якщо подальша передача цієї послідовності не здій-
снюється (ретрансляція відсутня), то ніяких виправлень здійснювати не слід.
Наявність же двох сум, які дорівнюють одиниці свідчить про викривлення
двох перевірочних символів, або одного інформаційного, в разі, коли номери по-
зиції у цій парі сум є спільними.
Для ілюстрації розглянемо приклад застосування блокового згорткового коду
за умови, що перевірочні символи прийнято без викривлень. Нехай з викривлен-
ням прийнято один інформаційний символ. Формування перевірочних і контроль-
них символів показано на рис. 1.
Порівняємо контрольні елементи із перевірочними, які є прийнятими:
,101/
4,34,34,3 =Å=Å= ПKS
.101/
5,45,45,4 =Å=Å= ПKS
Видно, що створилися дві пари сум, які дорівнюють одиниці: 4,3S і 5,4S .
Звідси робимо висновок, що викривлено той інформаційний символ, номер
позиції якого є спільним у кожній парі сум, тобто 4a . Значення цього символу не-
обхідно виправити на протилежне: прийнято 0 — повинна бути 1, і навпаки. Та-
ким чином, викривлення виправлено.
Блокові згорткові коди в задачах контролю цілісності
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 103
a1 a2 a3 a4
Передавання
a5 a6 a7
1 1 1 1 1 1 1
П1,2
П4,5П2,3 П3,4
П5,6 П6,7
0 0 0 00000
Приймання
a8
1
П7,8 П1,8
a/
1 a/
2 a/
3 a/
4 a/
5 a/
6 a/
7 a/
8
Викривлення
1 1 1 1 1 10
K1,2 K2,3 K3,4 K4,5 K5,6 K6,7 K7,8
0 0 1 1
1
0 00 0
K1,8
Рис. 1. Формування перевірочних і контрольних символів за наявності
викривлення в символі з номером 4
Приклад 2. Значення інформаційних і перевірочних символів при передаван-
ні — такі ж як і в попередньому прикладі (див. рис. 1). Перевірочні символи при-
йнято без викривлень, із викривленнями прийнято інформаційні символи /
1a , /
4a ,
/
7a (рис. 2). Звернемо увагу на те, що такі викривлення перевищують можливість
коду з їхнього виявлення та виправлення.
a/
1 a/
2 a/
3 a/
4 a/
5 a/
6 a/
7 a/
8
Викривлення
0 1 1 1 0 10
K1,2 K2,3 K3,4 K4,5 K5,6 K6,7 K7,8
1 0 1 1
1
0 11 1
K1,8
Рис. 2. Формування перевірочних і контрольних символів за наявності
викривлення в символах з номерами 1, 4, 7
Результатами порівнянь перевірочних і контрольних символів є:
,101/
2,12,12,1 =Å=Å= ПKS ,101/
8,18,18,1 =Å=Å= ПKS
О. Я. Матов, В. С. Василенко
104
,101/
4,34,34,3 =Å=Å= ПKS ,101/
5,45,45,4 =Å=Å= ПKS
,101/
7,67,67,6 =Å=Å= ПKS .011/
8,78,78,7 =Å=Å= ПKS
Ці результати порівняння свідчать про наявність викривлень в інформаційних
символах з номерами 1 і 4 ( 18,12,1 == SS , 15,44,3 == SS ), що є вірним, і відсутність
викривлень у решті символів, що є невірним, оскільки викривлення в символі з
номером 7 є невиявленим. Звернемо увагу на те, що в даному випадку невірно ви-
значена відсутність викривлень у символі, в якого до або після розташовано лише
один не викривлений символ (символ з номером 8).
Приклад 3. Значення інформаційних і перевірочних символів при передаван-
ні такі ж як і в попередньому прикладі (див. рис. 1). Перевірочні символи прийня-
то без викривлень, із викривленнями прийнято інформаційні символи /
1a , /
4a , /
6a
(рис. 3). Ці викривлення також перевищують можливість коду з їхнього виявлен-
ня та виправлення.
a/
1 a/
2 a/
3 a/
4 a/
5 a/
6 a/
7 a/
8
Викривлення
0 1 1 0 1 10
K1,2 K2,3 K3,4 K4,5 K5,6 K6,7 K7,8
1 0 1 1
1
1 11 0
K1,8
Рис. 3. Формування перевірочних і контрольних символів за наявності
викривлення в символах з номерами 1, 4, 6
Результатами порівнянь перевірочних і контрольних символів є:
,101/
2,12,12,1 =Å=Å= ПKS ,101/
8,18,18,1 =Å=Å= ПKS
,101/
4,34,34,3 =Å=Å= ПKS ,101/
5,45,45,4 =Å=Å= ПKS
,101/
6,56,56,5 =Å=Å= ПKS ,101/
7,67,67,6 =Å=Å= ПKS
.000/
8,78,78,7 =Å=Å= ПKS
Ці результати порівняння свідчать про наявність викривлень в інформаційних
символах з номерами 1, 4, 6 ( 18,12,1 == SS ; 15,44,3 == SS ; 17,66,5 == SS ), що є вір-
ним, і наявність викривлень у символі з номером 5 ( 16,55,4 == SS ), що є невірним.
Блокові згорткові коди в задачах контролю цілісності
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 105
Звернемо увагу на те, що в даному випадку невірно визначено наявність викрив-
лень у символі із номером 5, з обох боків якого розташовані викривлені символи.
Розглянувши три приклади з різною кількістю викривлених інформаційних
символів, можна зробити висновок, що блоковий згортковий код виправляє гру-
пове викривлення в одному з інформаційних символів (див. перший та третій
приклади), якщо праворуч та ліворуч від викривлення є два не викривлених сим-
воли.
Із викладеного раніше зрозуміло також, що інформаційні та перевірочні сим-
воли повинні чергуватися. Для визначеності будемо вважати, що інформаційні
символи мають непарні номери, а перевірочні — парні.
Місце розташування перевірочних символів визначається двома обставинами:
по-перше, групове (в даному випадку, подвійне) викривлення не повинно одноча-
сно охоплювати інформаційний і відповідний перевірочний символи; по-друге, не
повинно бути неправильного виправлення інформаційних символів, тобто не по-
винні бути одночасно викривлені ті перевірочні символи, номери позиції яких є
спільними щодо відповідного інформаційного.
Із цих міркувань витікає, що перевірочні символи повинні розташовуватися
мінімум через три інформаційних символи від найближчих із своїх інформацій-
них. Тоді, перевірочний символ 1, +iiП , створений з інформаційних ia та 1+ia , по-
винен займати позицію після (i + 4) інформаційного. Наприклад, перевірочний
символ 2,1П , створений з інформаційних 1a та 2a , повинен займати позицію після
5-го інформаційного. Відповідно, перевірочний символ 1,nП , створений з інфор-
маційних 1a та na , повинен займати позицію після 4-го інформаційного, і т.д.
Неважко упевнитися в тому, що з урахуванням останніх вимог блок такого
коду мінімально можливої довжини має вигляд, як показаного на рис. 4, і має
складатися з n = 16 символів, коли m = k = 8.
Останнє може бути проілюстрованим наступним прикладом.
Приклад 4. Значення інформаційних і перевірочних символів при передаван-
ні — такі ж як і в попередніх прикладах (див. рис. 1). Із викривленнями прийнято
(рис. 4) інформаційний символ /
2a та перевірочний /
6п (на рис. 4 показані значення
переданих та контрольних символів, а значення прийнятих, у тому числі викрив-
лених символів, не показані), що відповідає можливостям коду.
Результатами порівнянь перевірочних і контрольних символів є:
,101/
2,12,12,1 =Å=Å= ПKS
,101/
3,23,23,2 =Å=Å= ПKS
.110/
7,67,67,6 =Å=Å= ПKS
О. Я. Матов, В. С. Василенко
106
a1 a2 a3
011 010
K1,2K8,1 K3,4K6,7
0 0
1
1
1
п5 п6 п7 a4 п8
0
п6,7 п1,2
п8,1п5,6
Викривлення
0
a5 п1 a8a6 п2 п4a7
п2,3
п3
п3,4 п4,5
п7,8
1 1 11 0
K5,6 K7,8 K2,3 K4,5
0 0 0 0 0 0
Рис. 4. Мінімально допустима структура блокового згорткового коду
Ці результати порівняння свідчать про наявність викривлень в інформацій-
ному символі з номером 2, ( 13,22,1 == SS ), що є вірним, і наявність викривлень у
перевірочному символі з номером 6 ( 17,6 =S ), що також є вірним.
Отже, при такій структурі блокового згорткового коду в послідовності з
шістнадцяти символів забезпечується безумовне виявлення й виправлення викри-
влень одного з інформаційних й одного з перевірочних символів, що розташовані
послідовно. Іншими словами, код з такими параметрами забезпечує виявлення і
виправлення групових (парних, розташованих послідовно) викривлень кратності 2
при досить високому значенні ймовірності викривлення символу Рв ≈ 2/16 = 0,125.
Не важко помітити також, що кожне збільшення довжини коду на один інфо-
рмаційний і один перевірочний символи дозволяє потенційно збільшити на оди-
ницю кількість пар викривлених символів. Але з урахуванням наведених вище
обмежень їхнє розташування не є довільним. Не важко зрозуміти, що мінімально
допустима відстань m між груповими викривленнями розглянутого коду (рис. 5)
дорівнює 5. Оскільки ймовірність появи в базовому кодовому слові декількох
групових викривлень з такою відстанню між ними розрахувати складно, але вихо-
дячи із природи таких викривлень (можна припустити її досить низьке значення),
то більш надійним є припущення, що блоковий згортковий код дозволяє в кожно-
му базовому кодовому слові виправляти один викривлений інформаційний сим-
вол, що є притаманним і для решти двійкових блокових кодів. Але, точніше, бло-
ковий згортковий код дозволяє виправляти пару послідовно розташованих симво-
лів, з яких один інформаційний, а другий — перевірочний, що перевищує можли-
вості інших двійкових блокових кодів і є притаманним узагальненим [4] блоковим
кодам.
Блокові згорткові коди в задачах контролю цілісності
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 107
b = 2 b = lm = 5
Рис. 5. Мінімально допустима відстань між груповими викривленнями
У разі ж необхідності забезпечити виявлення та виправлення чи то більшого
пакета викривлень, чи то більшої кількості двократних викривлень, слід застосо-
вувати загальновідомий механізм перемежування.
Таким чином, у статті запропоновано варіант побудови та використання згор-
ткового завадостійкого корегувального коду та відповідні алгоритми кодування–
декодування для застосування в задачах контролю, чи контролю та поновлення
цілісності інформаційних об’єктів в умовах пакетних викривлень. Здійснено їхній
аналіз, показані переваги та вади.
1. Матов А.Я. Основы теории передачи дискретной информации: Учеб. пособ. — К.:
КВИРТУ ПВО, 1977. — 242 с., ил.
2. Кунегин С.В. Системы передачи информации. Курс лекций. — М.: в/ч 33965, 1997. —
317 с., ил.
3. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети. — М.: МГТУ
им. Н.Э.Баумана, 1999. — 432 с., ил.
4. Василенко В.С., Матов О.Я. Узагальнені завадостійкі коди в задачах забезпечення цілісно-
сті інформаційних об’єктів. Код умовних лишків // Реєстрація, зберігання і оброб. даних. — 2006.
— Т. 6, № 4. — С. 82–93.
Надійшла до редакції 19.02.2007
|
| id | nasplib_isofts_kiev_ua-123456789-50879 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:40:05Z |
| publishDate | 2007 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Матов, О.Я. Василенко, В.С. 2013-11-05T23:47:47Z 2013-11-05T23:47:47Z 2007 Блокові згорткові коди в задачах контролю цілісності / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 1. — С. 100-107. — Бібліогр.: 4 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50879 004.056.2 Для задач контролю цілісності інформаційних об’єктів в умовах природних впливів запропоновано блоковий згортковий код з використанням алгоритмів кодування–декодування, що є притаманними класичному завадостійкому корегувальному згортковому коду, який був би спроможний забезпечити виявлення та виправлення подвійних викривлень. Для задач контроля целостности информационных объектов в условиях естественных воздействий предложен блочный сверточный код с использованием алгоритмов кодирования– декодирования, присущих классическому помехоустойчивому корректирующему сверточному коду, который способен обеспечить выявление и исправление двойных искажений. The task of construction of block convolutional code with the use of encoding–decoding algorithms, which are inherent to the classic noise-combating, correcting convolutional code which would be able to provide the detection and correction of double distortions, is considered. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Блокові згорткові коди в задачах контролю цілісності Блочные сверточные коды в задачах контроля целостности Block Convolutional Codes in Integrity Check Tasks Article published earlier |
| spellingShingle | Блокові згорткові коди в задачах контролю цілісності Матов, О.Я. Василенко, В.С. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Блокові згорткові коди в задачах контролю цілісності |
| title_alt | Блочные сверточные коды в задачах контроля целостности Block Convolutional Codes in Integrity Check Tasks |
| title_full | Блокові згорткові коди в задачах контролю цілісності |
| title_fullStr | Блокові згорткові коди в задачах контролю цілісності |
| title_full_unstemmed | Блокові згорткові коди в задачах контролю цілісності |
| title_short | Блокові згорткові коди в задачах контролю цілісності |
| title_sort | блокові згорткові коди в задачах контролю цілісності |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50879 |
| work_keys_str_mv | AT matovoâ blokovízgortkovíkodivzadačahkontrolûcílísností AT vasilenkovs blokovízgortkovíkodivzadačahkontrolûcílísností AT matovoâ bločnyesvertočnyekodyvzadačahkontrolâcelostnosti AT vasilenkovs bločnyesvertočnyekodyvzadačahkontrolâcelostnosti AT matovoâ blockconvolutionalcodesinintegritychecktasks AT vasilenkovs blockconvolutionalcodesinintegritychecktasks |