Контрольне додавання

Контрольне додавання є одним з найпоширеніших методів контролю цілісності інформаційних об’єктів (виявлення спотворень в цих об’єктах).

При кодуванні початкові базові кодові слова розбиваються на s
b – розрядних узагальнених символів і записуються у вигляді α₁, α₂,... α_s, де
α_i ≤ 2^b – 1 а m = bs. Потім здійснюється додавання цих символів за певними правилами, наприклад, додавання по модулю (найчастіше використовується їх порозрядне додавання по модулю 2). Символи (у загальному випадку k) ознаки цілісності (контрольні ознаки) дописуються до початкового коду, за рахунок чого утворюється n − символьне БКС (n = m + k).

При декодуванні також здійснюється додавання m символів за тими ж правилами і знов обчислюються символи ознаки цілісності (контрольної ознаки) для прийнятого (зчитаного) інформаційного об’єкту. Знов розрахована ознака цілісності порівнюється з прийнятою (зчитаною) ознакою цілісності. У разі їх збігу робіться висновок про відсутність спотворень, інакше — про їх наявність.

Приклад. Нехай кодуванню підлягає послідовність А = 100111001010, в якій слід забезпечити виявлення (виявлення і виправлення) пакетних спотворень з кратністю b = 4, s = 2⁴ =16. Тоді така послідовність може бути представленою у вигляді:

І₁………. І₄, І₅……І₈ І₉ ……І₁₂

1 – й пакет 2 – й пакет 3 – й пакет

чи у вигляді: А = 1011.1100.1010, де крапками для наочності відокремлені чотирірозрядні пакети. Тоді процес кодування може бути представленим у вигляді:

порозрядне додавання по mod2 додавання по mod16

1011 11

1100 → 12

1010 10

1101→ {11+12+10}₁₆= 0001

Тоді в канал буде переданою послідовність А = 101111001010.1101 при виконанні операції порозрядного додавання по модулю 2, чи 101111001010.0001 при виконанні операції додавання по модулю s = 16, де крапками для наочності відокремлені чотирірозрядні надлишкові пакети.

Нехай на приймальному боці одержана послідовність, яка має спотворення = 011111001010.1101 (подвійне спотворення у першому пакеті). Тоді, при декодуванні (за тим же алгоритмом, що і при кодуванні) одержимо:

0111 7

1100 →12

1010 10

0001 → {7+12+10}₁₆= 1101

1101 → 0001

1100 ≠ 0 (mod2) 1110 ≠ 0 (mod16)

Порівняння одержаних контрольних символів із переданими 1101→0001 при виконанні операції порозрядного додавання по модулю 2, чи 0001→1101 при виконанні операції додавання по модулю s = 16, показує їх відмінність, що свідчить про наявність у прийнятій послідовності спотворення.