Вибір величини контрольної основи для коду умовних лишків
Розглянуто вимоги щодо величини контрольної основи в задачах захисту цілісності інформаційних об’єктів телекомунікаційних мереж в умовах застосування узагальненого коду умовних лишків. Рассмотрены требования к величине контрольного основания в задачах защиты целостности информационных объектов телек...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2010 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50438 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Вибір величини контрольної основи для коду умовних лишків / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і обробка даних. — 2010. — Т. 12, № 1. — С. 73-78. — Бібліогр.: 3 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859611475625115648 |
|---|---|
| author | Матов, О.Я. Василенко, В.С. |
| author_facet | Матов, О.Я. Василенко, В.С. |
| citation_txt | Вибір величини контрольної основи для коду умовних лишків / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і обробка даних. — 2010. — Т. 12, № 1. — С. 73-78. — Бібліогр.: 3 назв. — укр. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Розглянуто вимоги щодо величини контрольної основи в задачах захисту цілісності інформаційних об’єктів телекомунікаційних мереж в умовах застосування узагальненого коду умовних лишків.
Рассмотрены требования к величине контрольного основания в задачах защиты целостности информационных объектов телекоммуникационных сетей в условиях применения обобщенного кода условных вычетов.
Requirements to the size of control base in the tasks of protection of integrity for information objects of telecommunication networks in the conditions of application of the generalized conditional remainder code are considered.
|
| first_indexed | 2025-11-28T12:41:41Z |
| format | Article |
| fulltext |
Методи захисту інформації
в комп’ютерних системах і мережах
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 1 73
УДК 004.056.2
О. Я. Матов1, В. С. Василенко2
1Інститут проблем реєстрації інформації НАН України
вул. М. Шпака, 2, 03113 Київ, Україна
2Національний авіаційний університет
вул. Космонавта Комарова, 1, 03058 Київ, Україна
Вибір величини контрольної основи
для коду умовних лишків
Розглянуто вимоги щодо величини контрольної основи в задачах захи-
сту цілісності інформаційних об’єктів телекомунікаційних мереж в
умовах застосування узагальненого коду умовних лишків.
Ключові слова: викривлення, завадостійке кодування, код умовних ли-
шків, основи системи числення.
Вступ
При використанні в завадостійкому кодуванні системи лишкових класів
(СЛК) в класичному вигляді чи у вигляді коду умовних лишків (ЛУ-коді) [1] по-
стає традиційна для задач цього класу проблема розрізняння не викривлених
(правильних) кодових комбінацій (чисел, базових кодових слів) від викривлених
(неправильних). Нагадаємо, що в цих системах кодова комбінація (базове кодове
слово) розглядається як деяке (реальне в СЛК чи умовне в ЛУ-коді) число. В за-
значених умовах не викривленими вважаються такі числа, величина яких не пере-
вищує визначеного наперед діапазону представлення не викривлених чисел (ро-
бочого діапазону)
1
n
i
i
P p
, де ip (і = 1, 2,…, n) — основи системи числення, об-
рані для даної системи представлення. В цих кодах для завадостійкого кодування,
як і в інших кодах, вводиться надлишковість у вигляді реального чи умовного
лишку від розподілу вихідного числа А на контрольну основу kp (чи q). Її введен-
ня призводить до розширення діапазону представлення до величини
kR P p P q . При цьому природно вважається, що викривлені (неправильні)
числа A
~
, на відміну від не викривлених, зосереджені за межами робочого діапа-
зону, тобто A
~
> Р. При виборі чи визначенні елементів системи числення в систе-
мі лишкових класів важливою задачею є вибір таких основ цієї системи, які б за-
безпечили просте та надійне виявлення факту викривлення, а в корегуючих кодах
© О. Я. Матов, В. С. Василенко
О. Я. Матов, В. С. Василенко
74
також — як місця, так і величин можливих викривлень в базових кодових словах.
Що стосується вибору основ, які створюють робочий діапазон, то вимога до них
одна — ці основи повинні бути взаємно простими числами.
Вибір величин контрольної основи в задачах контролю цілісності
Оскільки за визначенням викривлені числа задовольняють умові A
~
> Р, то
звідсіля для задач контролю наявності викривлень неважко визначити вимогу до
величини контрольної основи цієї системи, а отже, здійснити в подальшому її ви-
бір. Тобто, для виявлення наявності викривлень досить визначити, в якому з діа-
пазонів (робочому чи контрольному) знаходиться число, правильність якого пере-
віряється. Для цього слід вимагати, щоби викривлення лишку (символу початко-
вого числа А) по будь-якій основі, наприклад, по основі ip збільшувало би почат-
кове не викривлене число А < P
А = 1 2 3, , ,..., ,..., ,i n k
на величину, яка забезпечує вихід викривленого числа в контрольний діапазон,
тобто на величину
0,0,0,..., ,...,0,0i i iA l R P .
Тоді за рахунок цього викривлене число
kniii RlAAA ,,...,~,...,,,
~
321
/
перейде з початкового діапазону [0, Р) до контрольного діапазону (див. рисунок),
наприклад, до діапазону [ ii Rl , ii Rl )1( ) величиною /i iR P q p . Таким чином,
буде забезпечена умова
/ /i i i il R l P q p P P q q .
P
A A /= li R i + A
R
. . .
l R i
. . .
A //= ljR j + A
ljRj
. . .
(li +1)Ri (lj +1)Rj
До виходу викривленого числа за межі робочого діапазону
Звідси витікає:
/ 1/i il p q ,
а отже, при найменшому значенні il = 1
0 Р liRi (li + 1) Ri ljRj (lj + 1)Rj R
Вибір величини контрольної основи для коду умовних лишків
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 1 75
iq p ,
тобто умовою однозначного визначення наявності викривлень є перевищення ве-
личиною контрольної основи величини будь-якої з інших основ. В останніх вира-
зах: A — величина викривлення; i — значення не викривленого символу (ли-
шку по основі з номером і); il — номер інтервалу, в який потрапляє число, викри-
влене по основі із номером і; /i iR P q p — величина даного інтервалу;
( ) modi i i ip — значення викривленого символу; i — величина ви-
кривлення і-го символу.
Вибір величин контрольної основи в задачах контролю
та поновлення цілісності
У задачах контролю та поновлення цілісності недостатньо лише встановити
факт наявності порушення цілісності інформаційного об’єкта, а потрібно визна-
чити місце викривлення та його величину. Зрозуміло, що для вирішення задач ви-
явлення місця та, особливо, величин викривлень, необхідно забезпечити іденти-
фікацію викривленого числа (чи величини викривлення) з номером основи (для
нашого прикладу — і чи j), по якій таке викривлення має місце, та визначення (в
подальшому) величини цього викривлення (відповідно i чи j ). Для цього
можна використати той факт, що аналогічне викривлення по основі jp перево-
дить викривлене число (див. рисунок)
/ /
1 2 3, , ,..., ,..., ,j j j n kA A A l R ,
до діапазону [ j jl R , ( 1)j jl R ) величиною jR .
Із наведеного витікає, що механізми визначення наявності, місця виникнення
та величини викривлення повинні ґрунтуватися на виявленні тим чи іншим шля-
хом хоча б однієї з таких взаємно пов’язаних величин як і, ip , та, відповідно, i ,
il , iR , A . Також із наведеного робимо висновок, що для ідентифікації викривле-
ного числа (чи величини викривлення) з номером основи і слід забезпечити попа-
дання викривлених по різним основам чисел до різних діапазонів, що, в свою чер-
гу, є можливим за умови, що відстань між двома довільними діапазонами, в які
можуть потрапити викривлені числа, перевищувала б максимальне значення не
викривленого числа (Р). Наприклад, при i il R > j jl R (при зворотному співвід-
ношенні результат не зміниться):
i il R > j jl R + P, чи i il R – j jl R > P. (1)
У загальному випадку цей вираз із урахуванням того, що в СЛК операції в ді-
апазоні [0, R) здійснюються за модулем R, набуде вигляду:
.mod)( PRRlRl jjii
О. Я. Матов, В. С. Василенко
76
Звідси неважко перейти до визначення загальних вимог щодо величини конт-
рольної основи q :
/i il P q p – /j jl P q p > P (2)
за умови /i il P q p > /j jl P q p ,
чи
R + /i il P q p – /j jl P q p – [(R + /i il P q p – /j jl P q p )/R]∙R > P (3)
за умови /i il P q p < /j jl P q p . В останньому виразі квадратні дужки означають
обчислення цілої частини від відповідного дробового числа.
При визначенні вимог щодо величини контрольної основи q , виходячи з ви-
разу (2), після скорочення на Р одержимо:
/i il q p – /j jl q p > 1,
( / / ) 1i i j jq l p l p ,
а, отже, в результаті вимога до контрольної основи приймає вигляд нерівності
1/ ( / / ) / ( )i i j j i j i j j iq l p l p p p l p l p . (4)
Звернемо увагу на те, що права частина нерівності (4) в загальному випадку
може бути дробовим, а не цілим числом, яким повинна бути контрольна основа.
До того ж шукане значення контрольної основи повинно бути цілим. Для роз-
в’язання цієї нерівності спочатку слід визначити максимальне значення чисельни-
ка та мінімальне значення знаменника. Зрозуміло, що максимальне значення чи-
сельника в цьому виразі дорівнює добутку двох найбільших із основ системи чис-
лення 1n np p , а мінімальне значення знаменника (це цілочисленна величина!)
1i j j il p l p ,
оскільки дорівнювати нулю знаменник може лише тоді, коли
i j j il p l p .
Останнє, в свою чергу, є досяжним лише при i il p , а j jl p , що є неможли-
вим (нагадаємо, що основи системи числення, наразі це величини ip та jp , є вза-
ємно простими числами).
Оскільки мінімальне значення знаменника дорівнює одиниці, то граничне
значення виразу (4) є цілою величиною. Причому, в разі визначення як величини,
Вибір величини контрольної основи для коду умовних лишків
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 1 77
так і місця викривлення за фактом попадання викривленого числа до інтервалу il
чи jl , вимога до величини контрольної основи може бути записаною у вигляді
1 nn ppq . (5)
При визначенні вимог щодо величини контрольної основи q , виходячи із ви-
разу (3), після скорочень на Р та q одержимо:
q + ii pql / – jj pql / – [1 + ii pl / – jj pl / ]∙q > 1,
,1])//1[//1( jjiijjii plplplplq
а, отже, в результаті вимога до контрольної основи приймає вигляд нерівності
]).//1[//1/(1 jjiijjii plplplplq (6)
Звернемо увагу на те, що вираз у знаменнику є дробовим число, звідси вели-
чина контрольної основи є більшою за чисельник, отже більшою за одиницю. Для
уточнення цієї величини приведемо вирази у знаменнику до спільного знаменни-
ка, яким є величина ji pp , та перенесемо останню у чисельник. Тоді нерівність
(6) перетвориться на вимогу
)])./()[(/( jiijjijijiijjijiji ppplplppppplplppppq
Оскільки знаменник, як і у виразі (6), є меншим одиниці, а величина контро-
льної основи q повинна бути цілим, взаємно простим числом з усіма іншими ос-
новами з усієї їхньої множини, то слід зробити висновок, що вимога щодо вели-
чини q перетворюються на вимогу вигляду
,ji ppcq (7)
де величина с з урахуванням уже визначеної вимоги (5) може прийняти таке зна-
чення с > 1, яке є цілим та взаємно простим числом з усіма основами використо-
вуваної системи числення. З іншого боку, слід враховувати, що від величини q
залежить можлива надлишковість коду, яку бажано мати найменшою. Виходячи з
цього, слід зробити висновок, що сформульованим обмеженням задовольняє ви-
мога, яку з урахуванням викладеного вище можна розглядати як єдину можливу:
.2 ji ppq (8)
Таким чином, при дотриманні умови (8), можливо забезпечити однозначний
результат виявлення та виправлення всіх можливих викривлень в одному з уза-
гальнених символів представлення інформаційних об’єктів при їхній циркуляції в
О. Я. Матов, В. С. Василенко
78
сучасних телекомунікаційних мережах. Можливості щодо такого застосування
коду умовних лишків уже розглянуті в роботах [1–3].
1. Василенко В.С. Использование ВУ-кодов для повышения верности информации в радіока-
налах / В.С. Василенко // Матеріали 28 НТС Асоціації зв’язку України. — К.: КВІРТУ ППО. —
1991. — С. 23.
2. Акушский И.Я. Машинная арифметика в остаточных класах / И.Я. Акушский, Д.И. Юдиц-
кий. — М.: Сов. радио, 1966. — 421 с.
3. Василенко В.С. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформа-
ційних об’єктів. Код умовних лишків / В.С. Василенко, О.Я. Матов // Реєстрація, зберігання і об-
роб. даних. — 2006. — Т. 6, № 4. — С. 82–93.
Надійшла до редакції 02.03.2010
|
| id | nasplib_isofts_kiev_ua-123456789-50438 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Ukrainian |
| last_indexed | 2025-11-28T12:41:41Z |
| publishDate | 2010 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Матов, О.Я. Василенко, В.С. 2013-10-20T19:20:25Z 2013-10-20T19:20:25Z 2010 Вибір величини контрольної основи для коду умовних лишків / О.Я. Матов, В.С. Василенко // Реєстрація, зберігання і обробка даних. — 2010. — Т. 12, № 1. — С. 73-78. — Бібліогр.: 3 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50438 004.056.2 Розглянуто вимоги щодо величини контрольної основи в задачах захисту цілісності інформаційних об’єктів телекомунікаційних мереж в умовах застосування узагальненого коду умовних лишків. Рассмотрены требования к величине контрольного основания в задачах защиты целостности информационных объектов телекоммуникационных сетей в условиях применения обобщенного кода условных вычетов. Requirements to the size of control base in the tasks of protection of integrity for information objects of telecommunication networks in the conditions of application of the generalized conditional remainder code are considered. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Вибір величини контрольної основи для коду умовних лишків Выбор величины контрольного основания для кода условных вычетов Choice of Size of Control Base for the Conditional Remainder Code Article published earlier |
| spellingShingle | Вибір величини контрольної основи для коду умовних лишків Матов, О.Я. Василенко, В.С. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Вибір величини контрольної основи для коду умовних лишків |
| title_alt | Выбор величины контрольного основания для кода условных вычетов Choice of Size of Control Base for the Conditional Remainder Code |
| title_full | Вибір величини контрольної основи для коду умовних лишків |
| title_fullStr | Вибір величини контрольної основи для коду умовних лишків |
| title_full_unstemmed | Вибір величини контрольної основи для коду умовних лишків |
| title_short | Вибір величини контрольної основи для коду умовних лишків |
| title_sort | вибір величини контрольної основи для коду умовних лишків |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50438 |
| work_keys_str_mv | AT matovoâ vibírveličinikontrolʹnoíosnovidlâkoduumovnihliškív AT vasilenkovs vibírveličinikontrolʹnoíosnovidlâkoduumovnihliškív AT matovoâ vyborveličinykontrolʹnogoosnovaniâdlâkodauslovnyhvyčetov AT vasilenkovs vyborveličinykontrolʹnogoosnovaniâdlâkodauslovnyhvyčetov AT matovoâ choiceofsizeofcontrolbasefortheconditionalremaindercode AT vasilenkovs choiceofsizeofcontrolbasefortheconditionalremaindercode |