Двійкові циклічні коди

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 12(3.2). Двійкові циклічні коди

Задачі

[1] Код проверки подлинности сообщения(message authentication code, MAC), известный также как код проверки подлинности данных (data authentication code, DAC), представляет собой однонаправленную хэш-функцию с добавлением секретного ключа

1.... Двійкові циклічні коди. 1

2.... Коди Боуза-Чоудхурі-Хоквінгема (БЧХ) 9

1. Жураковський Ю. П., Гніліцький В. В. Теорія інформації та кодування в задачах: Навчальний посібник. – Житомир: ЖІТІ, 2002, с. 153 - 165

Наступна тема присвячена двійковим циклічним кодам, які виявляють та виправляють помилки.

Строки последовательности бит удобно рассматривать в виде многочленов. Например, байт из 8 бит можно представить .

Показатель степени переменной указывает на порядковый номер бита – справа налево.

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

Так, сума двох двійкових поліномів виконується додаванням за модулем 2 коефіцієнтів за рівних степенів змінної . Наприклад, отримаємо суму за модулем 2 двох поліномів:

.

Множення виконується за звичайними правилами множення степеневих функцій, але коефіцієнти однакових степенів додаються за модулем 2. Так,

1.

Ділення також виконується як звичайне ділення поліномів, при цьому операція віднімання співпадає з операцією додавання . Наприклад,

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

(a₁, a₂, …, a_n) → (a_n, a₁, a₂, …, a_n−1)

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

Циклічні коди ‑ це ціле сімейство завадостійких кодів, що включає в себе в якості однієї з різновидів ‑ коди Хеммінга, але в цілому забезпечує більшу гнучкість з точки зору можливості реалізації кодів з необхідною здатністю виявлення та виправлення помилок, що виникають при передачі кодових комбінацій по каналу зв'язку. Циклічний код відноситься до систематичних блоковим -кодів, в яких перших розрядів є комбінацією первинного коду, а наступні розрядів є перевірочними.

В основі побудови циклічних кодів лежить операція ділення вихідної кодової комбінації на твірний незвідний поліном ступеня . Залишок від ділення використовується при формуванні перевірочних розрядів. При цьому операції ділення передує операція множення, що здійснює зрушення вліво -розрядної інформаційної кодової комбінації на розрядів.

При декодуванні прийнятої -розрядної кодової комбінації знову проводиться ділення на твірний незвідний поліном.

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

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

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