При побудові циклічних, кодів відповідальним етапом яв-ляется вибір утворює (що породжує) полінома.
Правила вибору полінома залежать від необхідної коректую-щей здатності коду, при цьому утворює поліном повинен забезпечувати якомога більшу кількість залишків при діленні на кодові комбінації. Вироблено і пропонуються наступні загальні правила вибору утворює полінома при побудові лю-бого циклічного коду:
1.Степень утворює полінома повинна бути не менше числа перевірочних символів r
2. Будь-який многочлен g (х) ступеня (n-к), який ділить без ос-татка двочлен X n +1 може бути породжує многочленом (n, k) циклічного коду.
3. Утворюючий поліном повинен бути якомога більш корот-ким.
4. Число ненульових членів чином полінома має бути не менше dмін.
Оскільки в циклічному коді опізнавач помилок є-ються залишки від ділення, то Р (х) повинен забезпечувати необхідну кількість розлитих залишків. Виявляє здатність циклічний-ського коду визначається не тільки ступенем обнаруживающего по-Ліном. але і числом його членів.
Чим більше залишків може бути утворено при розподілі ко-довой комбінації на який утворює поліном, тим вище коректив-рующая здатність коду.
Утворює поліном Р (х) циклічного коду повинен бути примітивним, тобто входити в якості сомножителя в розкладання
двочлена x n + 1 = x 2 ^ m +1, де n - загальне число розрядів в коді; m-будь-яке ціле позитивне число. Ознакою примітивних полі-номів є наявність залишку рівного одиниці тільки для полі-номів х = 1 і x n. тобто число різних залишків n-1. У загальному випадку при побудові циклічного (n, k)-коду з виправленням 4 помилок в якості утворює полінома вибирається твір з 4 з-множників старших ступенів, що входять в розкладання двочлена виду x n +1. У ролі сомножителей виступають Непріводімие Поліно-ми.
Непріводімие поліноми - це поліноми, які діляться без залишку тільки па себе або на одиницю.
Не всякий многочлен ступеня r, що входить в розкладання данно-го двочлена, може бути використаний для утворення потрібного (n, k)-коду.
Щоб з'ясувати, яке з творів може бути використано в якості утворює полінома, необхідно для кожного з них по-будувати так звану додаткову матрицю. Ця матриця будує-ся шляхом ділення циклічних зрушень одиниці з приписаними справа нулями на відповідний твір поліномів. При побудові додаткової матриці Сr, k. за обраним полиному необхідно також враховувати кількість рядків в циклі чергування перевірочних розрядів і вага кожного рядка (кількість одиниць).
Для отримання можливості виправлення необхідного числа помилок в якості утворює полінома вибирається то твір, додаткова матриця якого має всі рядки з вагою, не меншим, ніж dмін.-1
Боуз і Чоудхурн показали, що для будь-яких, цілих позитивними-них чисел m і tи існує циклічний код елементної
n = 2 m -1 або m = log2 (n-1) (5-2)
з кодовою відстанню
При цьому число перевірочних символів r не перевищує величи-ни mtu тобто
Такий код гарантовано виправляє помилки кратності tu і менш або виявляє помилки кратності t0 і менш. Крім того, код виявляє всі пакети помилок, довжина яких дорівнює і менше r.
Співвідношення (5,2) - (5.4) використовується для вибору утворює полінома.
Прим ер. Потрібно побудувати циклічний (n, k) -код. з исправ-ленням в кодових комбінаціях дворазовий помилок (tи = 2). Нехай загальне число елементів кодової комбінації n = 15. Згідно (5.2) - (5.4), m = 4, r = 8.
В цьому випадку двочлен x 2 ^ m + 1 = x n + 1 = x 15 + 1.
Можна показати, що в розкладання двочлена х 15 +1 як сомножителей старшого ступеня входять поліноми Р1 (х 4) = х 4 + х + 1 -> 10011; Р2 (х 4) = х 4 + х 3 + 1> 11001; Р3 (х 4) = х 4 + х 3 + х 2 + x + 1> 11111. У підручнику (таблиця 5.1) наведені утворюють (примітивні) поліноми до 10-го ступеня.
З трьох можливих парних творів полиномов четвертого ступеня отримаємо три полінома восьмому ступені r = 8
Р1 (х 4) Рз (х 4) = х 8 + х 7 + х 6 + х 4 +1 -> 111 010 001
Р2 (х 4) Рз (х 4) = х 8 + х 4 + х 4 + х + 1 -> 100 010 111
Р1 (х 4) Р2 (х 4) = х 8 + х 7 + х 5 + х 4 + х 3 + х + 1 -> 110 111 011
Щоб з'ясувати, який із трьох поліномів восьмому ступені може бути використаний в якості утворює, знайдемо для каж-дого з них додаткову матрицю С8.7 - (к = 15-8 = 7). Розподілом одиниці з приписаними справа нулями і її циклічних зрушень на 111010001 10001011 та 110111011 знаходимо відповідні до-полнітельние матриці
Для отримання можливості виправлення подвійних помилок до-полнігеяьние матриці повинні вибиратися таким чином, щоб вага м> кожного рядка породжує матриці був не менше п'яти одиниць dмін.> = 2tu +1
Так як кожен рядок одиничної матриці Е має вагу дорівнює одиниці, вага будь-якого рядка додаткової матриці повинен бути не менше чотирьох одиниць. Ця вимога, буде виконано, якщо в якост-стве утворює полінома для побудови циклічного (15, 7) -коду вибрати одне з двох творів: Р1 (х 4) Рз (х 4) або Р2 (х 4) Рз (х 4) =
У третій додатковій матриці С8.7 з семи рядків третя, четверта і п'ята не володіють необхідним вагою. Тому произве-дення Р1 (х 4) Р2 (х 4) не може бути використано в якості утворюють-ного полінома для побудови циклічного (.15, 7)-коду.