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

Вступ

Література.

Час – 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})

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

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

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

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

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

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

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

Дата добавления: 2013-12-12