Побудова кодів виправляють помилки з використанням арифметики полів Галуа
Ключові слова: коди Ріда-Соломона, поля Галуа, систематичне кодування.
Застосування кодування з виправленням помилок дозволяє відновлювати дані, втрачені як при передачі, так і в процесі зберігання. Використання кодів Ріда-Соломона з недвійковий символами дозволяє виправляти пакети помилок. Важливим моментом при кодуванні і декодуванні кодів Ріда-Соломона є розподіл поліномів. Використання арифметики полів Галуа робить процес кодування і декодування більш ефективним і простим.
Важливе сімейство кодів виправляють помилки утворюють лінійні двійкові блокові коди [1-3]. Ці коди представляють інформаційні та кодові слова у формі довічних векторів. Замість k біт інформаційного вектора в канал передається n біт кодового вектора. Кодування лінійного блокового (n, k) - коду задається породжує матрицею G розміром (k х n). Таким чином, кодове слово v та інформаційне слово u пов'язані співвідношенням v=u * G.
Блокові коди надзвичайно різноманітні, проте більшість з них не в змозі впоратися з пакетами помилок. Коди Боуза-Чоудхурі-Хоквенгема (БХЧ) дозволяють виправляти множинні помилки. Даний вид кодів надає велику свободу вибору довжини блоку, ступеня кодування, розмірів алфавіту і можливостей корекції помилок. Одним з підкласів кодів БХЧ з недвійковий символами є коди Ріда-Соломона (РС). Символи цих кодів являють собою многобітовие (m-бітові) послідовності. Коди РС здатні виправляти t =] (n - k)/2 [помилок.
Одна з труднощів у розумінні кодів РС полягає у використанні при їх побудові і декодуванні полів Галуа.
Полем називають безліч елементів, якщо для будь-яких елементів цієї множини визначені операції додавання і множення, а також виконується ряд аксіом (замкнутості, асоціативності, коммутативности, дистрибутивності ...) [2].
У каналах зв'язку безліч переданих сигналів завжди звичайно. Поля з кінцевим числом елементів q називають полями Галуа по імені їхнього першого дослідника Еваріста Галуа і позначають GF (q).
Важливим моментом при кодуванні і декодуванні кодів РС є розподіл поліномів. Проведення цієї операція за правилами звичайної алгебри на ЕОМ вкрай неефективно й складно. Це призводить до появи чисел з плаваючою комою. При використанні ж полів Галуа при будь-якій операції ми отримаємо число з цього поля. Збільшення розрядності і втрати точності не відбувається.
У вищій математиці доведено, що число елементів кінцевого поля q завжди задовольняє умові:
=p m, (1)
де р - просте число зване характеристикою поля, а m - позитивне ціле.
Якщо m=1, то таке поле називається простим, якщо m gt; 1, то таке поле називається розширеним. У простому полі операції додавання і множення виконуються за модулем р, а самі елементи утворюють послідовність, що складається з чисел {0, 1, 2, ..., р - 1}. У простому поле існує, принаймні, один примітивний елемент?, Такий, що кожен не нульовий елемент GF (р) може бути представлений як деяка ступінь? по модулю р.
Якщо просте поле утворюється з чисел, то розширене поле утворюється з многочленів. Таким чином, можна провести і аналогію формування поля. Елементи простого поля формуються зі ступенів примітивного елемента по модулю простого числа р, а елементи розширеного поля формуються зі ступенів примітивного елемента по модулю примітивного полінома [2]. В якості примітивного елемента зазвичай береться число 2.
Примітивний поліном - це нередуціруемого поліном f (X) порядку m, якщо найменшим позитивним цілим числом n, для якого X n +1 ділиться на f (X) без залишку, буде n=2 m - 1. нередуціруемого поліном - це поліном, який не можна представити у вигляді добутку поліномів меншого порядку.
Для побудови кодів БХЧ використовуються символи з поля розширення GF (2 m). Кожен елемент поля GF (2 m) можна представити у вигляді слова довжини m над полем GF (2) або многочлена з двійковими коефіцієнтами.
a=a (X)=am - 1 X m - 1 + ... + a 2 X 2 + a 1 X + a 0, (2)
де am - 1, ..., a2, a1, a0 - бінарні числа.
Враховуючи, що коефіцієнти am - 1, ..., a1, a2, a0 є або 0 або 1, кожен елемент кінцевого поля GF (2m) можна представити двійковим вектором або просто двійковим числом. У деяких випадках зручно представляти елементи поля десятковими, вісімковими або шестнадцатерічнимі числами.
Нескінченна безліч елементів утворюється з стартового множини {0, 1,? 1} додаванням додаткових елементів шляхом множення останнього елемента на? [3]. Тоді нескінченна безліч елементів поля буде представлено як {0,? 0,? 1,? 2,? ...
