3 ...}.
Розглянемо утворення кінцевого безлічі містить 2m елементів {0,? 0,? 1,? 2, ...,}. З (2) ми знаємо, що максимальний порядок полінома m - 1, але очевидно, що через m - 1 проведених множень на?, (Які еквівалентні зрушенню полінома) цей порядок буде перевищений. Отже, якщо у нас на черговому кроці формування елементів поля вийшло, що порядок полінома елемента дорівнює m - 1 (тобто, очевидно, що при зсуві отриманого полінома відбудеться вихід за обмеження порядку полінома), то при формуванні наступного елемента після зсуву полінома ми віднімаємо з результату примітивний поліном.
У цифрових системах передачі та зберігання даних найбільш природно застосування полів, число елементів яких укладається в 1 байт, тобто містять 28=256 елементів. Для побудови поля GF (28) візьмемо примітивний поліном f (X)=X8 + X5 + X3 + X + 1 (що еквівалентно двоичному вектору 100101011), який визначає кінцеве поле GF (2m), де ступінь полінома m=8. Поле, яке визначається обраним нами поліномом, має 2m=28=256 елементів від 0го до 255го. Для зручності розгляду процесу формування поля, рівним нулю позначені не 0ой елемент, а двісті п'ятьдесят п'ята.
Уявімо математичний опис процесу формування елементів поля:
А [0]=1, А [255]=0;
При А [i - 1] lt; {10000000} А [i]=А [i - 1] lt; lt; 1;
При А [i - 1]= gt; {10000000} А [i]=(А [i - 1] lt; lt; 1) +100101011.
Де символом lt; lt; позначений зрушення вліво двійкового представлення числа, а знак + означає операцію додавання по модулю 2.
Більш звично і компактно представляти елементи поля у вигляді десяткових чисел. Уявімо тепер математичний опис процесу формування елементів поля, представивши їх десятковими числами.
А [0]=1, А [255]=0;
При А [i - 1] lt; 128 А [i]=А [i - 1] * 2;
При А [i - 1]= gt; 128 А [i]=(А [i - 1] * 2) +299.
код помилка поле Галуа
Зауважимо, що підсумовування елементів поля GF (2 8), представлених у вигляді десяткових чисел, по модулю 2 необхідно проводити після їх переведення в двійковий вигляд. Операції вирахування і складання елементів поля зводяться до побітового додавання за модулем 2 їх довічних уявлень.
У таблиці 1 показані різні види представлення елементів поля GF (2 8) для перших 24 елементів.
Таблиця 1. Різні види представлення елементів поля GF (2 8)
ступінь? (номер елемента поля) Двійкове чіслоДесятічное чіслостепень? (номер елемента поля) Двійкове чіслоДесятічное число00000000111211100110230100000010213111001112312000001004141110010122930000100081511100001225400010000161611101001233500100000321711111001249601000000641811011001217710000000128191001100115380010101143200001100125901010110862100110010501010101100172220110010010011011100111152311001000200
Проводити операції множення і ділення з елементами поля GF (2 8) зручно, сформувавши зворотне поле. Основне поле, сформоване на підставі наведеного вище математичного опису, дозволяє за значенням ступеня примітивного елемента (перший і четвертий стовпці таблиці 1) знайти значення елемента поля. Зворотне поле дозволяє по заданому значенню елемента поля знайти ступінь примітивного елемента (числа 2). Зворотне поле - це поле логарифмів по підставі 2. Елементи оборотного поля обчислюються наступним чином:
L [А [i]]=i. (3)
Програмна реалізація процедури формування елементів поля GF (2 8) і зворотного поля в десятковому поданні на мові С ++:
[0]=1; [255]=0; (i=1; i lt;=254; i ++)
{if (A [i - 1] lt; 128) [i]=A [i - 1] * 2; [i]=show_summ (2 * A [i - 1], 299 ); } (i=0; i lt;=255; i ++)
{n=A [i]; [n]=i; }
Де show_summ - Звернення до функції складання елементів поля Галуа.
Тепер, маючи сформований основне і зворотне поле, визначимо проведення операції множення чисел Ma і Mb.
Якщо (L [Ma] + L [Mb]) lt; 255, то Ma * Mb=А [(L [Ma] + L [Mb])];
Якщо (L [Ma] + L [Mb])= gt; 255, то Ma * Mb=А [(L [Ma] + L [Mb] - 255)];
Визначимо проведення операції ділення чисел Dm і Dl.
Якщо (L [Dm] + L [Dl]) gt; 0, то Dm/Dl=А [(L [Dm] - L [Dl])];
Якщо (L [Dm] + L [Dl]) lt;=0, то Dm/Dl=А [(L [Dm] - L [Dl] +255)];
Програмна реалізація функції ділення аналогічна функції множення і приводити її немає сенсу. Далі розглянемо побудову систематичних кодів РС. Нехай M=(m 0, m 1, m 2, ..., mk - 1) - вектор інформаційного повідомлення. Тоді вектор кодового слова при систематичному кодуванні буде виглядати наступним чином:
