Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. Будь ласка, допоможіть поліпшити переклад.(грудень 2017)
Циклічний код — лінійний код, що володіє властивістю циклічності, тобто кожна циклічна перестановка кодового слова також є кодовим словом. Використовується для перетворення інформації, для захисту її від помилок (див. Виявлення і виправлення помилок).
Нехай — слово довжини n над алфавітом з елементів кінцевого поля та — поліном, що відповідає цьому слову, від формальної змінної . Видно, що ця відповідність не просто взаємно однозначна, а й ізоморфна. Оскільки «слова» складаються з літер з поля, то їх можна складати та множити (поелементно), причому результат буде в тому ж полі.
Поліном, що відповідає лінійній комбінації пари слів та , дорівнює лінійній комбінації поліномів цих слів .
Це дозволяє розглядати множину слів довжини n над кінцевим полем як лінійний простірполіномів зі ступенем не більше n-1 над полем.
Якщо — кодове слово, що виходить циклічним зрушенням на один розряд вліво зі слова , то відповідний йому поліном виходить з попереднього множенням на x:
, користуючись тим, що ,
Зрушення вправо та вліво відповідно на розрядів:
Якщо — довільний поліном над полем та — кодове слово циклічного коду, то теж кодове слово цього коду.
Визначення:
породжуючим поліномом циклічного коду називається такий ненульовий поліном з , ступінь якого найменша та коефіцієнт при старшому ступені .
Теорема 1
Якщо — циклічний код і — його породжуючий поліном, тоді ступінь дорівнює та кожне кодове слово може бути єдиним чином представлено у вигляді
,
де ступінь менше або дорівнює .
Теорема 2
— породжуючий поліном циклічного коду є дільником двочлена
Наслідки: таким чином як породжуючий поліном можна вибирати будь-який поліном, дільник .
Ступінь обраного полінома визначатиме кількість перевірочних символів , число інформаційних символів .
Як дільник виберемо породжуючий поліном третього ступеня , тоді отриманий код буде мати довжину , число перевірочних символів (ступінь породжуючого полінома) , число інформаційних символів , мінімальна відстань .
Породжуюча матриця коду:
,
де перший рядок є записом полінома коефіцієнтами по зростанню ступеня.
Решта рядків — циклічні зрушення першого рядка.
Перевірочна матриця:
,
де i-ий стовпець, починаючи з 1-го, являє собою залишок від ділення на поліном , записаний за зростанням ступенів, починаючи зверху.
Так, наприклад, 4-й стовпець виходить , або у векторному записі .