Реферат побудова породжує полінома циклічного коду по його корінню (ступенями коренів) - банк
менше. Використовуючи теорему 1 можна скласти послідовність пов'язаних елементів, таку послідовність в літературі ще називають ціклотоміческім класом. Безліч елементів, що входять в ціклотоміческій клас (пов'язані елементи) можна знайти за такою формулою:
Де, З - ціклотоміческій клас, s - ступінь елемента для якого знаходяться пов'язані елементи, p - показник основного поля, m - число елементів розширення поля.
Розглянемо приклад знаходження ціклотоміческого класу для елемента з GF (24). Тут і далі будемо представляти елемент, як його ступінь.
Отже, s = 1, p = 2, m = 4.
Таким чином, для елемента будуть сполученими елементи
Слід мати на увазі, що при побудові ціклотоміческого класу, ступінь елемента може бути вище максимальної міри, отриманої при побудові розширення поля, в цьому випадку необхідно розділити цей елемент на поліном, за яким було побудовано розширення поля і взяти залишок від ділення (так як група є циклічної, див. вище). Також потрібно мати на увазі, що при побудові ціклотоміческого класу, деякі елементи можуть виявитися однаковими, тоді такий елемент присутній в класі в одному екземплярі.
Слідство 2 з теореми 1:
Два сполучених між собою елемента матимуть один і той же мінімальний поліном.
Теорема 2. Мінімальний поліном елемента дорівнює
де поєднані елементи
Слідство з теореми 2: Всі елементи GF (pm) є корінням полиномов.
Побудуємо мінімальний поліном для елемента з GF (24). Парні елементи для знайдені вище.
Використовуючи теорему 2, запишемо мінімальний поліном в загальному вигляді:
Тепер потрібно розкрити дужки, за звичайними правилами, не наводячи подібні, пам'ятаючи що, операція віднімання визначена за правилами для поля GF (2), і вона еквівалента операції додавання.
Якщо один з елементів має ступінь вище, ніж максимальна ступінь елементів в таблиці 1 (циклічної групи), позначимо такий елемент як, то необхідно розділити на поліном, за яким було побудовано розширення, і взяти залишок від ділення, залишок буде шуканим елементом. Це забезпечується тим, що мультиплікативна група примітивного елемента утворює циклічну групу (див. Вище).
Тепер, потрібно замінити елементи розкладання на елементи з GF (pm), з урахуванням вищесказаного, розкрити дужки, привести подібні, не забуваючи, що операція додавання проводиться по модулю p (в даному прикладі по модулю два, так як в якості основного поля вибрано GF (2)).
Резюме: Для знаходження мінімального полінома для елемента з GF (pm) необхідно:
Побудувати розширення поля по модулю деякого приводиться над GF (p) полінома.
Побудувати ціклотоміческій клас для елемента, з огляду на те, що однакові елементи в класі враховуються тільки один раз і то, що ступінь елемента класу може перевищувати максимальну ступінь елементів розширення поля.
За допомогою теореми 2 записати розкладання мінімального полінома, використовуючи в якості коренів елементи ціклотоміческого класу.
Розкрити дужки розкладання, не наводячи подібні.
Перевірити, чи не перевищує ступінь максимальну ступінь елементів GF (pm) (див. Вище).
Замінити елементи на елементи поля.
Розкрити дужки, привести подібні, з огляду на той факт, що підсумовування ведеться по модулю p.
Розглянемо докладніше наслідок 2 з теореми 1:
Ціклотоміческій клас для елемента: для цих чотирьох елементів будуть однакові мінімальні поліноми.
Розглянемо більш докладно приклад знаходження мінімальних поліномів для GF (24).
Побудова GF (24) розглянуто вище, будемо користуватися готовим результатом.
Таблиця 2. Подання GF (24).
Почнемо з елементу. Виходячи з формули 1, запишемо безліч пов'язаних елементів:
Так як всі елементи вийшли однаковими, то ціклотоміческій клас буде складатися з одного елемента -.
За допомогою теореми 2 запишемо: m0 (a0) = (x - a0), замінимо a0 на елемент поля.
Мінімальна функція для елемента a0: m0 (a0) = (x + 1)
Використовуючи формулу 1, отримаємо ціклотоміческій клас. .
Використовуючи теорему 2, запишемо розкладання мінімального полінома.
Тепер замінимо a на елементи поля, після розкриття дужок і приведення подібних отримаємо мінімальний поліном для елементів зі ступенями 1, 2, 4, 8.
Виходячи з теореми 1 і наслідки з неї, для елемента мінімальний поліном буде дорівнює полиному для елемента.
Використовуючи формулу 1, запишемо ціклотоміческій клас: C =, як видно елемент зі ступенем 24 відсутня в поданні поля GF (24). Якщо розділити на поліном, по модулю якого вироблялося побудова GF (24), то отримаємо залишок.
Використовуючи теорему 2, запишемо розкладання мінімального полінома:
m3 (x) = (x - a3) (x - a6) (x - a9) (x - a12).
Тепер, розкривши дужки і привівши подібні, отримаємо поліном m3 (x) = x4 + x3 + x2 + x1 + 1.
Отже, це поліном для елементів зі ступенями 3,6,12,9.
Мінімальний поліном цього елемента дорівнює полиному елемента
Використовуючи формулу 1, запишемо ціклотоміческій клас: C =. Так як елементи класу збіглися, то в класі залишиться два елементи C =.
Використовуючи теорему 2, запишемо розкладання мінімального полінома:
m5 (x) = (x - a5) (x - a10) = x2 + x + 1
Мінімальний поліном цього елемента дорівнює полиному елемента
Використовуючи формулу 1, запишемо ціклотоміческій клас: C =. Так як, то C =
Використовуючи теорему 2, запишемо розкладання мінімального полінома:
m7 (x) = (x - a7) (x - a14) (x - a11) (x - a13) = x4 + x3 + 1
Неважко переконатися, що для інших елементів мінімальні поліноми вже знайдені вище.
2. Про циклічних кодах і коренях породжує полінома з точки зору кінцевих полів
Слід зазначити, що в даному розділі буде розглянуто опис циклічних кодів з точки зору кінцевих полів тільки в рамках перебування породжує полінома. Найбільш ясна повне розгляд циклічних кодів з точки зору кінцевих полів можна знайти в книзі [2].
Теорема 3. Циклічний код довжини n з породжує поліномом g (x) існує тоді і тільки тоді, коли g (x) ділить.
Слідство з теореми 3. Породжує поліном циклічного коду довжини n можна знайти, розклавши поліном на прості множники:
де s - число простих множників. Твір довільного підмножини цих множників дає породжує многочлен g (x). Якщо g (x) - породжує поліном, то він ділить, і, отже,. Поліном g (x) можна знайти, знайшовши всі його прості дільники.
Прості подільники є не що інше, як функції мінімуму або мінімальні поліноми. Таким чином, знаючи коріння мінімальних поліномів, можна легко знайти породжує поліном коду. Виходячи зі сказаного в попередніх розділах, можна зробити висновок, що поле якраз містить коріння мінімальних поліномів, а отже містить коріння породжує полінома.
Породжує поліном не що інше, як твір його простих дільників.
Нехай - корінь полінома. Тоді не що інше, як функція мінімуму для.
Маючи коріння полиномов - подільників g (x) можна знайти їх функції мінімуму, і отже знайти g (x).
містить коріння g (x).
Таким чином, перебування породжує полінома за ступенями його коренів зводиться до знаходження мінімальних поліномів для елементів поля з відповідним ступенем.
де мінімальний поліном.
2.1 Знаходження породжує полінома по послідовності ступенів коренів
У таблиці з додатка Г книги [1] містяться параметри циклічних кодів і послідовності ступенів коренів. Ми розглядаємо тільки коди тривіальної довжини. Частина цієї таблиці вказана в додатку А даної роботи. У таблиці з додатка В книги [1] вказані Непріводімие поліноми над GF (2). Вкорочене подання такої таблиці також є в додатку Б даної роботи.
Алгоритм знаходження породжує полінома:
Виходячи з довжини обраного коду, побудувати розширення поля по модулю неприводимого полінома над ступінь якого дорівнює m. Де m знаходиться з наступного співвідношення:.
Для кожного кореня побудувати ціклотоміческій клас.
Для кожного кореня знайти мінімальний поліном.
Перемножити отримані мінімальні поліноми за правилами для.
Розглянемо кожен крок більш докладно на прикладі коду (15,5,7). Для такого коду в таблиці циклічних кодів вказані наступні ступені коренів.
Крок 1. Побудова.
Довжина n заданого коду дорівнює 15. Так як, m = 4. Будемо будувати. Так як m = 4, то з таблиці непріводімих полиномов виберемо поліном четвертого ступеня, по модулю якого буде побудовано. Як побудувати розширення поля, було розглянуто в 1.4.3.
Крок 2. Побудова ціклотоміческіх класів.
Послідовність ступенів коренів для даного коду -. Для кожного елемента послідовності побудуємо ціклотоміческій клас, за допомогою формули. Детально побудова ціклотоміческіх класів описано в 1.4.4
Для кореня зі ступенем 1 це.
Для кореня зі ступенем 3 це.
Для кореня зі ступенем 5 це.
Крок 3. Знаходження мінімальних поліномів.
Виходячи з теореми 2, для кожного кореня знайдемо його мінімальний поліном, детально знаходження мінімальних поліномів описано вище.
Для кореня зі ступенем 1:
Для кореня зі ступенем 3: m3 (x) = (x - a3) (x - a6) (x - a9) (x - a12) = x4 + x3 + x2 + x1 + 1.
Для кореня зі ступенем 5: m5 (x) = (x - a5) (x - a10) = x2 + x + 1
Крок 4. Знаходження породжує полінома.
З 1.5, де це мінімальні поліноми для заданих коренів, то було отримано, що
У. Пітерсон, Е. Уелдон. «Коди, що виправляють помилки»: Київ: Світ, 1976.
Р. Блейхут. «Теорія і практика кодів виправляють помилки»: Київ: Світ, 1986. - 576с.
Додаток А. Таблиця непріводімих полиномов над GF (2).
Додаток Б. Таблиця довічних деяких циклічних кодів тривіальної довжини