ктн, доцент Василенко В. С., Дубчак О.В., Василенко М.Ю.

Національний авіаційний університет (НАУ), Україна

Поновлення цілісності інформаційних об’єктів в коді умовних лишків

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

В наслідок операції нулізації із числа А^/, яке контролюється, віднімається число Т = А^/ - k×Р < P. Це число формується по всім символам числа А^/, окрім контрольних, і є таким, що не перевищує робочого діапазону коду. При цьому по контрольній основі p_k одержується результат γ такий, що відповідає лівій межі одного із контрольних піддіапазонів [k×Р, (k + 1)×Р) , тобто величині k×Р.

Отже маємо

.

Звідсіля, за правилами системи лишкових класів (СЛК), отримаємо

. (1)

Тобто, використовуючи вираз (1) завжди можна визначити номер того діапазону, в який потрапило спотворене число та результат нулізації - число k×Р.

Надалі врахуємо, що величина вектора спотворення:

ΔА = 0, 0, …, 0, Δα_і, 0,…, 0,

де Δα_і = ΔА_і (mod p_i), ΔА_і = – величина спотворення по основі , задовольняє умові:

.

Із врахуванням того, що Р = , розділимо усі частини цього виразу на величину :

. (2)

Тоді місцем спотворення (узагальненим символом із номером і чи – умовним лишком за основою ) є той узагальнений символ, для якого система нерівнянь (2) є справедливою із одночасною справедливістю вимоги: значення величини номера піддіапазону повинно бути цілочисельних і не повинно перевищувати величини відповідної основи: . Це місце спотворення можна знайти, хоча б перебором у виразі (2) основ.

Приклад. Хай з використанням алгоритму нулізації закодовано вихідний код 110110, вважаючи, що можлива довжина пакета спотворень b = 2. Тобто можливо розбиття вихідного коду на три (n = 3) двохрозрядні групи
α₁ = 11₂, α₂ = 01₂, α₃ = 10₂, s = 4, як умовні основи вибрані р₁ = 4, р₂ = 5, р₃ = 7, а як значення контрольної основи вибрано р_к = 71 (нагадаємо, що контрольна основа повинна задовольняти умові р_к > 2·р_n ·р_n-1 = 2·5·7 = 70), що потребує для свого відображення семи розрядів. В наслідок цього при кодуванні сформовано код

А = 11.01.10.0000000.

Нехай в цьому коді спотворена третя пара розрядів так, що
= 11.01.01.0110011. Неважко показати, що після декодування за алгоритмом нулізації буде одержаним значення γ = 51.

Визначимо номер піддіапазону k. Із виразу (2) витікає:

γ = (k·Р) (mod р_к) = (k·140) (mod 71) = 51,

чи:

,

де величина с підбирається так, що с = (0, 1, 2, …) доти, поки не буде одержаним ціле значення k. Неважко упевнитися, що при с = 9:

k = (51 +9·71)/69 = (51 + 639)/69= 690/69 = 10,

і що, оскільки , то спотворене число при цьому попало на ліву границю діапазону .

Тоді із врахуванням того, що , , , із системи нерівнянь (2) при k = 10 на першому кроці (по основі р₁) маємо:

.

Оскільки обидва нерівняння цієї системи не задовольняють вимозі щодо цілочисельних значень величини номера піддіапазону , робимо висновок про відсутність спотворень у першому символі. На другому кроці (по основі р₂) маємо:

.

Як і в першому випадку, робимо висновок про відсутність спотворень у другому символі. На третьому кроці (по основі р₃) маємо:

.

Оскільки ця система задовольняються при , робимо висновок про наявність спотворень у третьому символі, та про визначення номера піддіапазону, величина якого дорівнює одиниці: . Отже, спотворення має величину , лишок якого по модулю р₃ = 7 дорівнює .

Тепер виправлення виявленого спотворення не становить ніяких утруднень:

,

що і мало місце в початковому коді (α₁ = 11₂, α₂ = 01₂, α₃ = 10₂) ще на етапі кодування.

Таким чином, порівнявши отримане значення з вихідним, не спотвореним, упевнюємося в тому, що запропонований алгоритм забезпечує вірну корекцію.

Список джерел:

1. Василенко В.С. Алгоритм нулізації в задачах кодування-декодування коду умовних лишків. / В.С. Василенко, О.В. Дубчак // Матеріали VІІ міжнародної Науково – практичної конференції “Сучасні наукові досягнення – 2012, 27.01 – 05.02 2012 р.”. – Praha: “Publishing House” ”Edication and Science” s.r.o. 2012. –Т. 26, С. 81–85