ктн, доцент Василенко В. С., Дубчак О.В.
Національний
авіаційний університет (НАУ), Україна
Алгоритм
нулізації в задачах кодування-декодування коду умовних лишків
Одним із можливих
алгоритмів кодування-декодування при використанні коду умовних лишків (ЛУ –
коду) є алгоритм нулізації, який застосовується для виявлення чи виявлення та
виправлення спотворень в групах розрядів (в узагальнених символах). Ці
узагальнені символи в межах цього коду розглядаються як лишки αi від розподілу
умовного числа А на певну сукупність
взаємно простих чисел pi –
основ системи числення в лишкових класах, які повинні задовольняти умові pi 
αi (i = 1, 2, …).
Сутність алгоритму
нулізації зводиться до того, що як при кодуванні, так і при декодуванні по
першим n лишкам αi (i = 1, 2, …, n) числа
= (α1,
α2, …, {αi
+ Δαi } (mod pi),…,αn, αk)
послідовно
формуються, так звані мінімальні числа виду:
t1 = (α1, 
, 
,…, 
,
),
t2 = (0, (α2 - 
) (mod p2),
,…, 
,
),
t3 = (0, 0, (α3 - 
- 
) (mod p3),
,…, 
,
),
…………………………………………………………..
tn = (0, 0, 0, …,(αn - 
) (mod pn),
),
Звернемо увагу на те,
що кожне із таких мінімальних чисел, окрім лишків по першим n основам, має лишок і по надлишковій,
контрольній основі рk
і може бути представленим у вигляді:
ti = vі∙
.
З
урахуванням того, що в лишкових класах справедливими є рівняння:
ti (mod
pі) =
= {αі - 
} (mod pі)
= vі∙
(mod pі),
величину
vі можна визначити як
vі =
{
/
}(mod pі) = {(αі - 
)/
} (mod pі)
для
усіх лишків αі з
номерами і >1, а для першого із лишків
α1 значення v1
= 1.
Підсумок цих чисел Т
= 
має наступні дві
властивості. По - перше лишки цієї суми по всім основам, окрім рk, завжди дорівнюють лишкам
вихідного числа А. По-друге, величина цієї суми завжди є
меншою ніж величина робочого діапазону Т < Р, тобто величина Т лежить в межах робочого діапазону і для не
спотворених чисел Т = А.
При кодуванні із застосуванням ЛУ-коду до початкового
набору основ коду рi (i = 1, 2, …, n) вводять іще одну, надлишкову, контрольну основу рk,
величина якої, як відомо, при умові виявлення факту наявності спотворень
повинна задовольняти умові:
,
А
при умові не лише виявлення, але і виправлення спотворень повинна задовольняти
умові:
,
де
та 
– найбільші із набору основ рi.
Неважко помітити, що описаний вище процес формування величини
Т = А при попередньо
невизначеній величині лишку по контрольній основі pk є процесом кодування вихідного числа ЛУ-кодом. Дійсно, в процесі нулізації контрольна
ознака αk, що
розшукується, обраховується як сума проміжних величин 
(і = 1, 2, ..., n), які є
лишками за модулем рк від
складових Т. До того ж значення Т залежить лише від вихідного числа А і не залежить від невідомої при
кодуванні величини лишку по контрольній основі рк. Отже:
αk
= Т (mod рк) = (
) (mod рк).
При декодуванні здійснюється така ж процедура нулізації із
обчисленням величини T та із наступним відніманням із числа 
цієї величини T. Це
призводить до того, що отримана різниця
- T < kР
має по всім основам, окрім контрольної,
лишки, що дорівнюють нулю, а по контрольній – лишок, величина якого:
γ = (αk – (Т mod рk
)) (mod рk) = (kР) (mod рk),
тобто
- T = (0, 0, …, 0,
…0, (k·Р) (mod рk)),
де
k = 0, 1, 2, …, рk –1.
Для не спотворених
чисел, тобто при k = 0, величина
γ = 0, для спотворених γ ≠ 0.
Отже, визначений алгоритм надає змогу виявлення
факту наявності спотворень.
Для ілюстрації
можливостей алгоритму розглянемо приклади кодування та декодування при
виявленні наявності спотворень.
Приклад 1. Хай необхідно закодувати з використанням алгоритму
нулізації вихідний код 110110, вважаючи, що можлива довжина пакета спотворень b = 2. Тоді можливо розбиття вихідного
коду на три (n = 3) двохрозрядні
групи α1 =112,
α2 =012, α3
=102, s = 4, а в якості умовних основ можна
вибрати р1 =4, р2 = 5, р3 = 7. При цьому як значення контрольної основи можна
вибрати рк = 71
(нагадаємо, що контрольна основа повинна задовольняти умові рк > 2·рn ·рn-1
= 2·5·7 = 70), що потребує для свого відображення семи розрядів. В наслідок
цього для кодування формується код
А = 11.01.10.0000000.
Перше мінімальне
число t1 повинно мати лишок
по першій основі, що дорівнює 11(2) = 3(10). Таким числом
є t1 = 3 або при
представленні в СЛК з вибраними основами
t1 = 11.11.011.0000011.
Друге мінімальне
число t2 повинно мати
лишок по першій основі, який дорівнює нулю, а по другій
((α2 - 
) (mod p2)
= (1 – 3) (mod 5) = 11(2).
Мінімальним
числом, яке має такі лишки по першій і другій основам, є
t2
= 8, тобто
t2 = 00.11.001.0001000.
Трете мінімальне
число t3 повинно мати
нульові лишки по першим двом основам, а по третій
((α3 - 
- 
) (mod p3)
= (2 – 3 - 1) (mod 7) = 5 = 101(2).
Мінімальним
числом, що має такі лишки, є t3 = 40, тобто
t3 = 00.00.101.0101000.
Тоді сума цих чисел
Т= 
дорівнює 51, тобто
Т = 11.01.10.0110011.
Код Т =
А є результатом кодування.
Звернемо увагу на те,
що величини t1, t2, t3 формуються послідовно, а також на їх велику
розрядність.
Приклад 2. Декодувати з використанням алгоритму нулізації для
умов прикладу 2 код 
= 11.01.01.0110011, в
якому спотворена третя пара розрядів. Як і раніше
t1 = 11.11.011.0000011.
t2 = 00.11.001.0001000.
Для третього
мінімального числа t3
((α3 - 
- 
) (mod p3)
= (1 – 3 - 1) (mod 7) = 4 = 100(2).
Мінімальним
числом, що має такі лишки, є t3
= 60, тобто
t3 = 00.00.100. 0111100
При
цьому
Т = 
=71,
тобто
оскільки (Т) (mod 71) = 0, то
Т = 11.01.01.0000000
і
γ = (αk – (Т mod рк
)) (mod рк) = (0110011 -
0000000) (mod 71) = 51.
Оскільки γ
≠ 0, то робиться висновок про
наявність в числі, що декодується,
спотворення.