АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. БАНКІВСЬКІ ОПЕРАЦІЇ
  2. Банківські операції
  3. Блок 17. КЛІМАТИЧНІ ПОЯСИ ТА ОСНОВНІ ТИПИ КЛІМАТУ.
  4. В1.1 Основні історіософські концепції походження українського народу.
  5. Валютні операції.
  6. Види, рівні та основні завдання моніторингу
  7. Визначте основні шляхи надання допомоги учням з особливостями психофізичного розвитку в адаптації серед здорових людей.
  8. Виконавчі комітети місцевих рад: формування, склад основні форми і методи діяльності
  9. Виконання завдань під час стабілізаційних, специфічних дій військ та у спеціальній операції
  10. Вказати, яка із бухгалтерських проводок відповідає здійсненій операції.
  11. Внутрішній аудит в системі управління суб'єктів господарювання. Основні завдання внутрішнього аудиту.
  12. Вопрос Основні положення досудового врегулювання господарського спору.

Основа (алфавіт) 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 можна записати поліномами

V1(х) = x5 + х4 + х; V2(x) = x5 + 1.

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

Vx(x) K2(jc) = x5 + x4 + x + x5 + 1 = x4 +x+ 1 →010011.

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

V1{x) V2(x) = (x5 + x4 + x)(x5 + 1) = x0 + x9 + x6 + x5 + x4 + x →11001110010.

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

V1{x):V2(x) = (x5 + x4 + x):(x5 + 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(21). Якщо взяти за основу поліномне подання елементів поля G= {0,1,2,..., q- 1} = {0,...0201, 0 l...0211,..., І l...121,}2 = {0,1,..., х l -1 +... + x+ 1}, то операція додавання двох елементів виконується як порозрядне додавання за модулем 2 двійкових елементів їх. Наприклад, при q = 8 = 23 матимемоG= {0,1,2,...,7}g= {000,001,010,...,111}2. Результати додавання за модулем 8 наведено в табл. 3.2.

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

               
                 
                 
                 
                 
                 
          .1      
                 
                 

 

Операція множення двох елементів алгоритмічно виконується як множення двох поліномів, що відповідають елементам поля, які множать за модулем незвідного полінома степеня. Так, при q = 8 = 23, l = 3 незвідний поліном степеня 1-3 вибираємо виду Р(х) = x3 + x + 1. Множимо два елементи поля; G= {0,1,2,...,7}8= {000,001,010,...,111}2. Здобуті значення ділимо на незвідний поліном і результати заносимо в табл. 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) на основі модульного полінома Р(х) = х4 + x + 1 (q = 16 = 24 –> l = 4), який задає розширювальне рівняння х4 = х + 1 і за аналогією рівняння β4 = β + 1.

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

β4 + β5 + β9 + β14 = β + 1 + β2 + β + β3 + β + β3 + l = β2 + β= β5=6.

Таблиця 3.4 - Форми подання елементів поля GF(16) на основі модульного полінома Р(х) = х4 + 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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)