Узагальнені завадостійкі коди. Контрольне додавання

Під узагальненими розумітимемо коди, призначені для виявлення (виявлення і виправлення) пакетних спотворень з кратністю b, в яких використовуються алгоритми кодування і декодування, аналогічні відповідним алгоритмам двійкових кодів, але по відношенню до узагальненого b − розрядного символу.

Для побудови цих кодів початкова кодова послідовність І₁ І₂ …І_m розбивається на n = m/b груп з розрядністю b, усередині яких групуються помилки:

І₁………. І_b, І_b+1………І₂ ........ І_m-b+1 ……І_k

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

Двійкові символи, що входять в один пакет, розглядаються як b - значний символ, який може приймати будь-яке із s значень від 0 до 2^{b – 1}, де

s = 2^b.

Як буде показано нижче операція над узагальненими символами виконуються до деякому модулю, тобто шукається лишок або найменший залишок від розподілу результату операції на деякий модуль. Це дало можливість для відмінності відповідних узагальнених кодів від двійкових ввести в їх назву слово “лишок”, тобто говорити про лишково - Хеммінгових (ЛХ), лишково - матричні (ЛМ), лишково - рекурентні (ЛР) коди. Слід зазначити, що лишкові – циклічні коди відомі під назвою кодів Ріда - Соломона – на ім’я авторів цих кодів.

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

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

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

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

І₁ І₂ І₃ І₄, І₅ І₆ І₇І₈ І₉ І₁₀ І₁₁І₁₂,

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

чи у вигляді: А = 1011.1000.1001. Тоді результатом кодування цим кодом при використанні порозрядного додавання по модулю 2 набуде значення:

,

тобто дає контрольну ознаку 1010, а при використанні додавання по модулю
s = 16 дасть контрольну ознаку (11+8+9 (mod 16) = 28 (mod 16) = 12₁₀ = 1100₂:

.

Одержана тим чи іншим чином контрольна ознака передається разом із вихідною комбінацією, тобто передається А = 1011.1000.1001.1010 чи
А = 1011.1000.1001.1100.

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

,

тобто дає контрольну ознаку 0101, а при використанні додавання по модулю
s = 16 дасть контрольну ознаку (4+8+9 (mod 16) = 21 (mod 16) = 5₁₀ = 0101₂:

.

Оскільки в обох випадках передана та прийнята контрольні ознаки є різними (1010 ≠ 0101 чи 1100 ≠ 0101) робиться висновок про наявність спотворень.