Основні операції над елементами поля

Основа (алфавіт) q коду може мати різні значення (q ≥ 2). Методика побудови багатьох кодів грунтується на використан­ні властивостей послідовностей двійкових чисел. Розглянемо деякі операції над елементами двійкових кодів (q = 2). Правила додавання за модулем 2 визначаються такими опе-раціями:

0 0 = 0;1 1=0;0 1 = 1;1 0=1.

Наприклад, при додаванні за модулем 2 двійкових послідо­вностей чисел 0111000 і 10010 матимемо

0101010

На відміну від звичайного арифметичного додавання опе­рація додавання двійкових чисел за модулем 2 полягає в тому, що в даному разі розглядають конкретну пару двійкових знаків незалежно від інших чисел двійкової послідовності. Тому ре­зультат попередніх операцій при додаванні чергової пари двій­кових знаків не враховують, тоді як при звичайних арифмети­чних операціях цей результат треба враховувати обов'язково, коли при додаванні двох двійкових чисел (наприклад, одиниць) записується 0, а 1 переноситься в старший розряд. Для прикла­ду, що розглядається, при арифметичній операції було б:

1001010

Операція віднімання за модулем 2 нічим не відрізняється від операції додавання.

Множення та ділення двійкових чисел за модулем 2 викону­ють за допомогою операції додавання за модулем 2. Так, при множенні за модулем 2 множене зсувають у бік старшого роз­ряду стільки разів, скільки розрядів є у множнику, а потім до­дають їх за модулем 2. Множене виписують тільки в тому разі, коли в множнику є 1. Якщо ж у множнику є 0, то черговий зсув виконують без виписування множеного:

^Х 1101

1111

1001011.

При діленні за модулем 2 дільник підписують під діленим так, щоб збігалися старші розряди. Якщо кількість розрядів діленого перевищує або дорівнює кількості розрядів дільника, то в частку переносять 1, після чого виконують додавання за модулем 2 й до здобутого числа дописують праворуч наступну цифру діленого. Якщо ж число остачі разом з дописаною циф­рою дорівнює кількості розрядів дільника, то до частки допи­сують ще одну 1, а якщо ні – то 0 доти, доки кількість розрядів остачі не дорівнюватиме кількості розрядів дільника. Після цього виконують додавання за модулем 2. Операцію повторю­ють стільки разів, поки всі розряди діленого не перенесуться до остачі. Наприклад:

1001011 1101 10101 1011

1111

1101 1011

1000 11

1101

1101

Дуже зручно операції додавання, віднімання, множення та ділення за модулем 2 виконувати з двійковими числами, запи­саними у вигляді поліномів. Так, двійкові комбінації 110010 і 100001 можна записати поліномами

V₁(х) = x⁵ + х⁴ + х; V₂(x) = x⁵ + 1.

Тоді додавання V₁(x) V₂(x) за модулем 2 дасть

V_x(x) K₂(jc) = x⁵ + x⁴ + x + x⁵ + 1 = x⁴ +x+ 1 →010011.

Результатом множення буде

V₁{x) V₂(x) = (x⁵ + x⁴ + x)(x⁵ + 1) = x⁰ + x⁹ + x⁶ + x⁵ + x⁴ + x →11001110010.

Після ділення цих поліномів дістанемо

V₁{x):V₂(x) = (x⁵ + x⁴ + x):(x⁵ + 1) =

Операції додавання, віднімання, множення та ділення при основі q > 2 коду мають свої особливості. Всі недвійкові коди (q-коди) поділяються на дві великі групи: коди з простою осно­вою q =p, д е р {3,5,7,11,13,...}, тобто з простими числами, що діляться тільки на самих себе; коди з розкладною основою q. Найбільший практичний інтерес становить підклас кодів з роз­кладною основою q - 2^і, елементи якого мають інформаційну ємність l бітів і можуть бути порівняні з усіма l -розрядними двійковими числами, що дає змогу використовувати двійкову техніку для виконання операцій додавання, ділення та множення.

До підкласу кодів з основою q = 2 ^l належать недвійкові коди, в яких q - {4,8,16,...}. Для таких кодів необхідно задати опера­ції над елементами поля GF(q) – GF(2¹). Якщо взяти за основу поліномне подання елементів поля G= {0,1,2,..., q- 1} = {0,...0₂0_1, 0 _l...0₂1₁,..., І _l...1₂1,}₂ = {0,1,..., х ^{l -1} +... + x+ 1}, то операція додавання двох елементів виконується як порозрядне додавання за модулем 2 двійкових елементів їх. Наприклад, при q = 8 = 2³ матимемоG= {0,1,2,...,7}_g= {000,001,010,...,111}₂. Результати додавання за модулем 8 наведено в табл. 3.2.

Таблиця 3.2 – Результати додавання за модулем 8

					.1

Операція множення двох елементів алгоритмічно виконується як множення двох поліномів, що відповідають елементам поля, які множать за модулем незвідного полінома степеня. Так, при q = 8 = 2³, l = 3 незвідний поліном степеня 1-3 вибираємо виду Р(х) = x³ + x + 1. Множимо два елементи поля_; G= {0,1,2,...,7}₈= {000,001,010,...,111}₂. Здобуті значення ділимо на незвідний поліном і результати заносимо в табл. 3.3.

Таблиця 3.3 - Результати ділення на незвідний поліном

Операція віднімання збігається з операцією додавання, а операції ділення та обернення (піднесення до степеня -1) еле­ментів виконуються як множення, оскільки обернення елемен­та а рівнозначне діленню: а^-1 = 1/а.

Нехай, наприклад, потрібно знайти результат від ділення 5/6 = β. Це рівнозначне запису 6β = 5. З табл. 3.3 знаходимо, що необхідно помножити 6 на 4 (β = 4), щоб дістати 5. Таким чи­ном, β = 4 й є результатом ділення 5/6.

Аналогічно можуть бути побудовані таблиці для операцій додавання та множення при інших основах кодів (q = 4,16,32,...). Так, для виконання розрахунків над полем GF(q) при q = 16 зручніше користуватися табл. 3.4, де наведено деякі форми подання елементів поля GF(16) на основі модульного полінома Р(х) = х⁴ + x + 1 (q = 16 = 2⁴ –> l = 4), який задає розширювальне рівняння х⁴ = х + 1 і за аналогією рівняння β⁴ = β + 1.

При додаванні за допомогою табл. 3.4 примітивних елемен­тів, наприклад β⁴ + β⁵ + β⁹ + β¹⁴, треба перевести їх з мультиплікативної форми в адитивну, скоротити повторення, а здо­бутий результат перенести знову в мультиплікативну (або де­сяткову) форму, тобто

β⁴ + β⁵ + β⁹ + β¹⁴ = β + 1 + β² + β + β³ + β + β³ + l = β² + β= β⁵=6.

Таблиця 3.4 - Форми подання елементів поля GF(16) на основі модульного полінома Р(х) = х⁴ + x + 1

Десяткове подання елементів поля GF(16)	Подання елементів поля GF(16) у формі двійкового вектора	Мульти -плікатив­на форма у вигляді степеня примітивного елемента	Адитивна форма β3 + bβ2 + c β1+ d β0, a,b,c,d {0,1} у базисах
23	22	21	20	β5	β2	β'	β"
					0 = β
					β°
					β'			+β
					β4			+β	+1
					β2		β2
					β8		β2		+1
					β5		β2	+β
					β10		β2	+β	+1
					β3	β3
					β14	β3			+ 1
					β9	β3		+β
					β7	β3		+β	+1
					β6	β3	β2
					β13	β3	β2		+1
					β11	β3	β2	+β
					β'2	β3	β2	+β	+ 1

Поиск по сайту: