Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Циклічні коди. Коди БЧХ »
МІНСЬК, 2009
Циклічні коди
Циклічним кодом називається лінійний блоковий (n, k)-код, який характеризується властивістю циклічності, тобто зсув вліво на один крок будь-який дозволений кодового слова дає також дозволене кодове слово, що належить цьому ж коду і в якого, безліч кодових слів представляється сукупністю многочленів ступеня (n-1) і менш, що діляться на деякий многочлен g (x) ступеня r = nk , що є співмножником двочлена x n +1.
Многочлен g (x) називається породжує.
Як випливає з визначення, в циклічному коді кодові слова представляються у вигляді многочленів
де n - довжина коду;
- Коефіцієнти з поля GF (q).
Якщо код побудований над полем GF (2), то коефіцієнти приймають значення 0 або 1 і код називається двійковим.
Приклад. Якщо кодове слово циклічного коду
то відповідний йому многочлен
Наприклад, якщо код побудований над полем GF (q) = GF (2 3), яке є розширенням GF (2) по модулю неприводимого многочлена f (z) = z 3 + z +1, а елементи цього поля мають вигляд, представлений у таблиці 1,
то коефіцієнти приймають значення елементів цього поля і тому вони самі відображаються у вигляді многочленів наступного виду
де m - ступінь многочлена, за яким отримано розширення поля GF (2); \ a i - коефіцієнти, які беруть значення елементів GF (2), тобто 0 і 1. Такий код називається q-ним.
Довжина циклічного коду називається примітивною і сам код називається примітивним, якщо його довжина n = q m -1 на GF (q).
Якщо довжина коду менше довжини примітивного коду, то код називається укороченим або непрімітівним.
Як випливає з визначення загальна властивість кодових слів циклічного коду - це їх подільність без залишку на деякий многочлен g (x), званий породжує.
Результатом розподілу двочлена x n +1 на многочлен g (x) є перевірочний многочлен h (x).
При декодуванні циклічних кодів використовуються многочлен помилок e (x) і синдромних многочлен S (x).
Многочлен помилок ступеня не більше (n-1) визначається з виразу де - Многочлени, що відображають відповідно прийняте (з помилкою) і передане кодові слова.
Ненульові коефіцієнти в е (x) займають позиції, які відповідають помилок.
Приклад.
Синдромний многочлен, використовуваний при декодуванні циклічного коду, визначається як залишок від ділення прийнятого кодового слова на породжує многочлен, тобто
або
Отже, синдромних многочлен залежить безпосередньо від многочлена помилок е (х). Це положення використовується при побудові таблиці синдромів, застосовуваної в процесі декодування. Ця таблиця містить список многочленів помилок і список відповідних синдромів, обумовлених з виразу (Див. таблицю 2).
У процесі декодування за прийнятим кодовому слову обчислюється синдром, потім в таблиці знаходиться відповідний многочлен е (х), підсумовування якого з прийнятим кодовим словом дає виправлене кодове слово, тобто Перераховані многочлени можна складати, множити і ділити, використовуючи відомі правила алгебри, але з приведенням результату по mod 2, а потім по mod x n +1, якщо ступінь результату перевищує ступінь (n-1).
Приклади.
Припустимо, що довжина коду n = 7, то результат наводимо по mod x 7 +1.
При побудові і декодуванні циклічних кодів в результаті ділення многочленів звичайно необхідно мати не приватна, а залишок від ділення.
Тому рекомендується більш простий спосіб розподілу, використовуючи не многочлени, а тільки його коефіцієнти (варіант 2 у прикладі).
Приклад.
1.
2.
При побудові матриці H (n, k) старший коефіцієнт многочлена h (x) розташовується праворуч.
Приклад. Для циклічного (7,4)-коду з породжує многочленом g (x) = x 3 + x +1 матриці G (n, k) і H (n, k) мають вигляд: де
Для систематичного циклічного коду матриця G (n, k) визначається з виразу де I k - одинична матриця; R k, r - прямокутна матриця. Рядки матриці R k, r визначаються з виразів або де a i (x) - значення i-того рядка матриці I k; i - номер рядка матриці R k, r.
Приклад. Матриця G (n, k) для (7,4)-коду на основі породжує многочлена g (x) = x 3 + x +1, будується в такій послідовності
або
Визначається R 4,3, використовуючи так як
Аналогічним способом визначається
У результаті отримуємо або
Використовуючи вираз отримаємо той самий результат.
Рядки матриці G (n, k) можна визначити безпосередньо з виразу
де
Перевірочна матриця в систематичному вигляді будується на основі матриці G (n, k), а саме: де I r - одинична матриця; - Матриця з G (n, k) в транспонованої вигляді.
Приклад. Для (7,4)-коду матриця H (n, k) буде мати вигляд:
Одна з основних задач, що стоять перед розробниками пристроїв захисту від помилок при передачі дискретних повідомлень по каналах зв'язку є вибір породжує многочлена g (x) для побудови циклічного коду, що забезпечує необхідну мінімальну кодова відстань для гарантійного виявлення та виправлення t-кратних помилок.
Існують спеціальні таблиці з вибору g (x) в залежності від пропонованих вимог до коригуючих можливостям коду. Однак у кожного циклічного коду є свої особливості формування g (x). Тому при вивченні конкретних циклічних кодів будуть розглядатися відповідні способи побудови g (x).
Коди БЧХ
Одним з класів циклічних кодів, здатних виправляти багаторазові помилки, є коди БЧХ.
Примітивним кодом БЧХ, виконуючим t u помилок, називається код довжиною n = q m -1 над GF (q), для якого елементи є корінням породжує многочлена.
Тут a - примітивний елемент GF (q m).
Породжує многочлен визначається з виразу
де f 1 (x), f 2 (x )...- мінімальні многочлени коренів g (x).
Число перевірочних елементів коду БЧХ задовольняє співвідношенню
Приклад. Визначити значення породжує многочлена для побудови примітивного коду БЧХ над GF (2) довжини 31, виправляє двох кратні помилки (t u = 2).
Виходячи з визначення коду БЧХ корінням многочлена g (x) є: , Де a - примітивний елемент GF (q m) = GF (2 5).
Породжує многочлен визначається з виразу де f 1 (x), f 2 (x), f 3 (x), f 4 (x) - мінімальні многочлени коренів відповідно .
Примітка.
Мінімальний многочлен елемента b поля GF (q m) визначається з виразу , Де - Найменше ціле число, при якому .
Значення мінімальних многочленів будуть наступними:
Так як f1 (x) = f2 (x) = f4 (x), то
На практиці при визначенні значень породжує многочлена користуються спеціальною таблицею мінімальних многочленів (див. таблицю 8 додатка), і виразом для породжує многочлена При цьому робота здійснюється в такій послідовності.
По заданій довжині коду n і кратності виправляє помилок t u визначають:
- З виразу n = 2 m -1 значення параметра m, який є максимальним ступенем співмножників g (x); - з виразу j = 2t u -1 максимальний порядок мінімального многочлена, що входить до числа співмножників g (x).
- Користуючись таблицею мінімальних многочленів, визначається вираз для g (x) в залежності від m та j. Для цього з колонки, відповідної параметру m, вибираються многочлени з порядками від 1 до j, які в результаті перемножування дають значення g (x).
У виразі для g (x) утримуватися мінімальні многочлени тільки для непарних ступенів a, так як зазвичай відповідні їм мінімальні многочлени парних ступенів a мають аналогічні вирази.
Наприклад, мінімальні многочлени елементів відповідають мінімальному многочлену елемента a 1, мінімальні многочлени елементів відповідають мінімальному многочлену a 3 та т.п.
Приклад. Визначити значення породжує многочлена для побудови примітивного коду БЧХ над GF (2) довжини 31, що забезпечує t u = 3.
Визначаємо значення m і j.
З таблиці мінімальних многочленів відповідно до m = 5 і j = 5 отримуємо
Задані вихідні дані: n і t u або k і t u для побудови циклічного коду часто призводять до вибору завищеного значення m і як наслідок до невиправданого збільшення довжини коду. Таке положення знижує ефективність отриманого коду, тому що частина інформаційних розрядів взагалі не використовується.
Приклад. Потрібно побудувати циклічний код, що виправляє двох кратні помилки, якщо довжина інформаційної частини коду k = 40.
Згідно зі слів для примітивного коду n = 2 m -1, найближча довжина коду дорівнює 63, для якої m = 6, а r = mt u = 12. Отже, код буде мати n = 63, k = 51. Невикористаних інформаційних розрядів буде 11 (51-40).
Подібне невідповідність у ряді випадків можна усунути, застосовуючи непрімітівний код БЧХ.
Непрімітівним кодом БЧХ, виконуючим t u помилок, називається код довжини n над GF (q), для якого елементи є корінням породжує многочлена.
Тут b i-непрімітівний елемент GF (q m), а довжина коду n дорівнює порядку елемента b i.
Примітка.
Порядком елемента b i є найменше n, для якого .
Приклад. Порядок елемента b 3 поля GF (2 6) дорівнює 21, так як .
Породжує многочлен непрімітівного коду БЧХ, за аналогією з примітивним кодом, визначається з виразу - Мінімальні многочлени елементів поля GF (q m), які є корінням g (x); i - ступінь непрімітівного елемента b.
Приклад. Визначити значення g (x) для побудови непрімітівного коду БЧХ над GF (2) довжини n = 20, що виправляє двох кратні помилки.
З таблиці непрімітівних елементів GF (2 m) (див. таблицю 7 додатка) вибираємо поле, елемент b якого має порядок більший, але близький до заданого n.
Додаток
Таблиця 1
Розкладання бінома х n +1 на Непріводімие співмножники
Примітка. У розкладання всіх биномом входить співмножник 03 з коренем 00. Всі співмножники представлені в вісімковій формі.
Таблиця 2
Елементи поля GF (16) як розширення GF (2) за примітивним многочлену a (z) = z 4 + z +1
Таблиця 3
Елементи поля GF (16) як розширення GF (4) за примітивним многочлену f (z) = z 2 + z +2
Таблиця 4
Елементи поля GF (4) як розширення GF (2) за примітивним многочлену f (z) = z 2 + z +1
Таблиця 6
Елементи поля GF (8) як розширення GF (2) за примітивним многочлену f (z) = z 3 + z +1
Таблиця 7
Непрімітівние елементи поля GF (2 m)
Таблиця 8
Мінімальні Непріводімие многочлени в полі GF (2 m)
Такими є GF (2 6) і b 3, порядок якого n = 21.
Так як j = 2t u -1 = 2 (2-1 = 3, то вираз для g (x) матиме вигляд
де f 3 (x) і f 9 (x) - мінімальні многочлени елементів b 3 та b 9 поля GF (2 6).
Значення цих многочленів наступні:
Вирази для f 3 (x) і f 9 (x) можна визначити з таблиці мінімальних многочленів, використовуючи для цього параметр m вибраного поля GF (2 m) і порядкові номери співмножників g (x).
Для розглянутого прикладу m = 6, а порядкові номери рівні 3 і 9. Тому
.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
кафедра РЕЗ
реферат на тему:
«Циклічні коди. Коди БЧХ »
МІНСЬК, 2009
Циклічні коди
Циклічним кодом називається лінійний блоковий (n, k)-код, який характеризується властивістю циклічності, тобто зсув вліво на один крок будь-який дозволений кодового слова дає також дозволене кодове слово, що належить цьому ж коду і в якого, безліч кодових слів представляється сукупністю многочленів ступеня (n-1) і менш, що діляться на деякий многочлен g (x) ступеня r = nk , що є співмножником двочлена x n +1.
Многочлен g (x) називається породжує.
Як випливає з визначення, в циклічному коді кодові слова представляються у вигляді многочленів
де n - довжина коду;
- Коефіцієнти з поля GF (q).
Якщо код побудований над полем GF (2), то коефіцієнти приймають значення 0 або 1 і код називається двійковим.
Приклад. Якщо кодове слово циклічного коду
то відповідний йому многочлен
Наприклад, якщо код побудований над полем GF (q) = GF (2 3), яке є розширенням GF (2) по модулю неприводимого многочлена f (z) = z 3 + z +1, а елементи цього поля мають вигляд, представлений у таблиці 1,
Таблиця 1 | |||||
0 | 000 | 0 | a 3 | 011 | Z +1 |
a 0 | 001 | 1 | a 4 | 110 | Z 2 + Z |
a 1 | 010 | Z | a 5 | 111 | Z 2 + Z +1 |
a 2 | 100 | Z 2 | a 6 | 101 | Z 2 +1 |
де m - ступінь многочлена, за яким отримано розширення поля GF (2); \ a i - коефіцієнти, які беруть значення елементів GF (2), тобто 0 і 1. Такий код називається q-ним.
Довжина циклічного коду називається примітивною і сам код називається примітивним, якщо його довжина n = q m -1 на GF (q).
Якщо довжина коду менше довжини примітивного коду, то код називається укороченим або непрімітівним.
Як випливає з визначення загальна властивість кодових слів циклічного коду - це їх подільність без залишку на деякий многочлен g (x), званий породжує.
Результатом розподілу двочлена x n +1 на многочлен g (x) є перевірочний многочлен h (x).
При декодуванні циклічних кодів використовуються многочлен помилок e (x) і синдромних многочлен S (x).
Многочлен помилок ступеня не більше (n-1) визначається з виразу де - Многочлени, що відображають відповідно прийняте (з помилкою) і передане кодові слова.
Ненульові коефіцієнти в е (x) займають позиції, які відповідають помилок.
Приклад.
Синдромний многочлен, використовуваний при декодуванні циклічного коду, визначається як залишок від ділення прийнятого кодового слова на породжує многочлен, тобто
або
Отже, синдромних многочлен залежить безпосередньо від многочлена помилок е (х). Це положення використовується при побудові таблиці синдромів, застосовуваної в процесі декодування. Ця таблиця містить список многочленів помилок і список відповідних синдромів, обумовлених з виразу (Див. таблицю 2).
Таблиця 2 | |
(X) | S (x) |
1 | R g (x) [1] |
X | R g (x) [x] |
X 2 | R g (x) [x2] |
· | · |
· | · |
· | · |
X +1 | R g (x) [x +1] |
X 2 +1 | R g (x) [x2 +1] |
· | · |
· | · |
· | · |
Приклади.
При побудові і декодуванні циклічних кодів в результаті ділення многочленів звичайно необхідно мати не приватна, а залишок від ділення.
Тому рекомендується більш простий спосіб розподілу, використовуючи не многочлени, а тільки його коефіцієнти (варіант 2 у прикладі).
Приклад.
1.
2.
Матричне завдання кодів
Циклічний код може бути заданий породжує і перевірочної матрицями. Для їх побудови досить знати породжує g (x) і перевірочний h (x) многочлени. Для несистематичного циклічного коду матриці будуються циклічним зсувом породжує і перевірочного многочленів, тобто шляхом їх множення на x іПри побудові матриці H (n, k) старший коефіцієнт многочлена h (x) розташовується праворуч.
Приклад. Для циклічного (7,4)-коду з породжує многочленом g (x) = x 3 + x +1 матриці G (n, k) і H (n, k) мають вигляд: де
Для систематичного циклічного коду матриця G (n, k) визначається з виразу де I k - одинична матриця; R k, r - прямокутна матриця. Рядки матриці R k, r визначаються з виразів або де a i (x) - значення i-того рядка матриці I k; i - номер рядка матриці R k, r.
Приклад. Матриця G (n, k) для (7,4)-коду на основі породжує многочлена g (x) = x 3 + x +1, будується в такій послідовності
або
Визначається R 4,3, використовуючи так як
Аналогічним способом визначається
У результаті отримуємо або
Використовуючи вираз отримаємо той самий результат.
Рядки матриці G (n, k) можна визначити безпосередньо з виразу
де
Перевірочна матриця в систематичному вигляді будується на основі матриці G (n, k), а саме: де I r - одинична матриця; - Матриця з G (n, k) в транспонованої вигляді.
Приклад. Для (7,4)-коду матриця H (n, k) буде мати вигляд:
Одна з основних задач, що стоять перед розробниками пристроїв захисту від помилок при передачі дискретних повідомлень по каналах зв'язку є вибір породжує многочлена g (x) для побудови циклічного коду, що забезпечує необхідну мінімальну кодова відстань для гарантійного виявлення та виправлення t-кратних помилок.
Існують спеціальні таблиці з вибору g (x) в залежності від пропонованих вимог до коригуючих можливостям коду. Однак у кожного циклічного коду є свої особливості формування g (x). Тому при вивченні конкретних циклічних кодів будуть розглядатися відповідні способи побудови g (x).
Коди БЧХ
Одним з класів циклічних кодів, здатних виправляти багаторазові помилки, є коди БЧХ.
Примітивним кодом БЧХ, виконуючим t u помилок, називається код довжиною n = q m -1 над GF (q), для якого елементи є корінням породжує многочлена.
Тут a - примітивний елемент GF (q m).
Породжує многочлен визначається з виразу
де f 1 (x), f 2 (x )...- мінімальні многочлени коренів g (x).
Число перевірочних елементів коду БЧХ задовольняє співвідношенню
Приклад. Визначити значення породжує многочлена для побудови примітивного коду БЧХ над GF (2) довжини 31, виправляє двох кратні помилки (t u = 2).
Виходячи з визначення коду БЧХ корінням многочлена g (x) є: , Де a - примітивний елемент GF (q m) = GF (2 5).
Породжує многочлен визначається з виразу де f 1 (x), f 2 (x), f 3 (x), f 4 (x) - мінімальні многочлени коренів відповідно .
Примітка.
Мінімальний многочлен елемента b поля GF (q m) визначається з виразу , Де - Найменше ціле число, при якому .
Значення мінімальних многочленів будуть наступними:
Так як f1 (x) = f2 (x) = f4 (x), то
На практиці при визначенні значень породжує многочлена користуються спеціальною таблицею мінімальних многочленів (див. таблицю 8 додатка), і виразом для породжує многочлена При цьому робота здійснюється в такій послідовності.
По заданій довжині коду n і кратності виправляє помилок t u визначають:
- З виразу n = 2 m -1 значення параметра m, який є максимальним ступенем співмножників g (x); - з виразу j = 2t u -1 максимальний порядок мінімального многочлена, що входить до числа співмножників g (x).
- Користуючись таблицею мінімальних многочленів, визначається вираз для g (x) в залежності від m та j. Для цього з колонки, відповідної параметру m, вибираються многочлени з порядками від 1 до j, які в результаті перемножування дають значення g (x).
У виразі для g (x) утримуватися мінімальні многочлени тільки для непарних ступенів a, так як зазвичай відповідні їм мінімальні многочлени парних ступенів a мають аналогічні вирази.
Наприклад, мінімальні многочлени елементів відповідають мінімальному многочлену елемента a 1, мінімальні многочлени елементів відповідають мінімальному многочлену a 3 та т.п.
Приклад. Визначити значення породжує многочлена для побудови примітивного коду БЧХ над GF (2) довжини 31, що забезпечує t u = 3.
Визначаємо значення m і j.
З таблиці мінімальних многочленів відповідно до m = 5 і j = 5 отримуємо
Задані вихідні дані: n і t u або k і t u для побудови циклічного коду часто призводять до вибору завищеного значення m і як наслідок до невиправданого збільшення довжини коду. Таке положення знижує ефективність отриманого коду, тому що частина інформаційних розрядів взагалі не використовується.
Приклад. Потрібно побудувати циклічний код, що виправляє двох кратні помилки, якщо довжина інформаційної частини коду k = 40.
Згідно зі слів для примітивного коду n = 2 m -1, найближча довжина коду дорівнює 63, для якої m = 6, а r = mt u = 12. Отже, код буде мати n = 63, k = 51. Невикористаних інформаційних розрядів буде 11 (51-40).
Подібне невідповідність у ряді випадків можна усунути, застосовуючи непрімітівний код БЧХ.
Непрімітівним кодом БЧХ, виконуючим t u помилок, називається код довжини n над GF (q), для якого елементи є корінням породжує многочлена.
Тут b i-непрімітівний елемент GF (q m), а довжина коду n дорівнює порядку елемента b i.
Примітка.
Порядком елемента b i є найменше n, для якого .
Приклад. Порядок елемента b 3 поля GF (2 6) дорівнює 21, так як .
Породжує многочлен непрімітівного коду БЧХ, за аналогією з примітивним кодом, визначається з виразу - Мінімальні многочлени елементів поля GF (q m), які є корінням g (x); i - ступінь непрімітівного елемента b.
Приклад. Визначити значення g (x) для побудови непрімітівного коду БЧХ над GF (2) довжини n = 20, що виправляє двох кратні помилки.
З таблиці непрімітівних елементів GF (2 m) (див. таблицю 7 додатка) вибираємо поле, елемент b якого має порядок більший, але близький до заданого n.
Додаток
Таблиця 1
Розкладання бінома х n +1 на Непріводімие співмножники
Ступінь бінома | Послідовності ступенів коренів непріводімих співмножників | Непріводімие співмножники |
7 | 1 2 4 3 6 5 | 13 15 |
15 | 01 02 04 08 03 06 12 09 10 травня 07 14 13 11 | 023 037 007 031 |
31 | 01 02 04 08 16 03 06 12 24 17 05 10 20 09 18 07 14 28 25 19 11 22 13 26 21 15 30 29 27 23 | 045 075 067 057 073 051 |
63 | 01 02 04 08 16 32 03 06 12 24 48 33 05 10 20 40 17 34 07 14 28 56 49 35 18 вересня 1936 11 22 44 25 50 37 13 26 52 41 19 38 15 30 60 57 51 39 21 42 23 46 29 58 53 43 27 54 45 31 62 61 59 55 47 | 103 127 147 111 015 155 133 165 007 163 013 141 |
Таблиця 2
Елементи поля GF (16) як розширення GF (2) за примітивним многочлену a (z) = z 4 + z +1
У двійковому вигляді | У вигляді многочлена | У вигляді ступеня |
0000 | 0 | 0 |
0001 | 1 | a 0 |
0010 | z | a 1 |
0100 | z 2 | a 2 |
1000 | z 3 | a 3 |
0011 | z +1 | a 4 |
0110 | z 2 + z | a 5 |
1100 | z 3 + z 2 | a 6 |
1011 | z 3 + z +1 | a 7 |
0101 | z 2 +1 | a 8 |
1010 | z 3 + z | a 9 |
0111 | z 2 + z +1 | a 10 |
1110 | z 3 + z 2 + z | a 11 |
1111 | z 3 + z 2 + z +1 | a 12 |
1101 | z 3 + z 2 +1 | a 13 |
1001 | z 3 +1 | a 14 |
Елементи поля GF (16) як розширення GF (4) за примітивним многочлену f (z) = z 2 + z +2
У четвертинному вигляді | У десятковому вигляді | У вигляді многочлена | У вигляді ступеня |
00 | 0 | 0 | 0 |
01 | 1 | 1 | a 0 |
10 | 4 | z | a 1 |
12 | 6 | z +2 | a 2 |
32 | 14 | 3z +2 | a 3 |
11 | 5 | z +1 | a 4 |
02 | 2 | 2 | a 5 |
20 | 8 | 2z | a 6 |
23 | 11 | 2z +3 | a 7 |
13 | 7 | z +3 | a 8 |
22 | 10 | 2z +2 | a 9 |
03 | 3 | 3 | a 10 |
30 | 12 | 3z | a 11 |
31 | 13 | 3z +1 | a 12 |
21 | 9 | 2z +1 | a 13 |
33 | 15 | 3z +3 | a 14 |
Елементи поля GF (4) як розширення GF (2) за примітивним многочлену f (z) = z 2 + z +1
У двійковому вигляді | У вигляді многочлена | У вигляді ступеня | У десятковому вигляді |
00 | 0 | 0 | 0 |
01 | 1 | a 0 | 1 |
10 | z | a 1 | 2 |
11 | z +1 | a 2 | 3 |
Елементи поля GF (8) як розширення GF (2) за примітивним многочлену f (z) = z 3 + z +1
У двійковому вигляді | У вигляді многочлена | У вигляді ступеня |
000 | 0 | 0 |
001 | 1 | a 0 |
010 | z | a 1 |
100 | z 2 | a 2 |
011 | z +1 | a 3 |
110 | z 2 + z | a 4 |
111 | z 2 + z +1 | a 5 |
101 | z 2 +1 | a 6 |
Таблиця 7
Непрімітівние елементи поля GF (2 m)
№ | m | GF (2 m) | b | n |
1 | 4 | GF (2 4) | b 3 | 5 |
b 5 | 3 | |||
2 | 6 | GF (2 6) | b 3 | 21 |
b 7 | 9 | |||
b 9 | 7 | |||
3 | 8 | GF (2 7) | b 3 | 85 |
b 5 | 51 | |||
b 15 | 17 | |||
b 17 | 15 | |||
4 | 9 | GF (2 9) | b 7 | 73 |
5 | 10 | GF (2 10) | b 3 | 341 |
b 11 | 93 | |||
b 31 | 33 | |||
b 33 | 31 | |||
6 | 12 | GF (2 12) | b 3 | 1365 |
b 5 | 819 | |||
b 7 | 585 | |||
b 9 | 455 | |||
b 13 | 315 | |||
b 15 | 273 | |||
b 21 | 195 | |||
b 45 | 91 | |||
b 63 | 65 | |||
b 65 | 63 |
Таблиця 8
Мінімальні Непріводімие многочлени в полі GF (2 m)
2t u -1 | m | ||||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 | 7 | 13 15 | 31 37 07 31 | 45 75 67 57 73 | 103 127 147 111 015 155 | 211 217 235 367 277 325 203 | 435 567 763 551 675 747 453 727 023 545 613 543 433 477 615 435 537 771 | 1021 1131 1461 1231 1423 1055 1167 1541 1333 1605 1027 1751 1743 1617 1401 | 2011 2017 2415 3771 2257 2065 2157 2653 3515 2773 3753 2033 2443 3573 2461 3041 75 3023 |
Так як j = 2t u -1 = 2 (2-1 = 3, то вираз для g (x) матиме вигляд
де f 3 (x) і f 9 (x) - мінімальні многочлени елементів b 3 та b 9 поля GF (2 6).
Значення цих многочленів наступні:
Вирази для f 3 (x) і f 9 (x) можна визначити з таблиці мінімальних многочленів, використовуючи для цього параметр m вибраного поля GF (2 m) і порядкові номери співмножників g (x).
Для розглянутого прикладу m = 6, а порядкові номери рівні 3 і 9. Тому
.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,