Пристрій для множення елементів скінченного поля gf(2m) на комбінаційних схемах

Реферат: m Пристрій для множення елементів скінченного поля GF(2 ) на комбінаційних схемах містить два регістри співмножників, входи яких є входами першого і другого співмножників пристрою, багатовходові суматори за модулем два, виходи яких є елементами І, що об'єднані в групи елементів І, перші входи яких в кожній групі об'єднані і підключені до відповідного виходу регістра першого співмножника, виходи регістра другого співмножника з'єднані з другими входами відповідних елементів І першої групи. В пристрій введено блок обчислення добутку і блок об'єднання загальних доданків, а також пристрій реалізовано на основі комбінаційних схем з використанням функціональних елементів схем І з двома входами, елементів АБО з двома входами та елементів НІ, причому виходи груп елементів І з'єднані з входами блока обчислення компонент множення, виходи якого підключені до входу блока обчислення добутку і входів блока об'єднання загальних доданків, а виходи блока обчислення добутку з'єднані з іншими входами блока об’єднання загальних доданків. UA 103490 U (54) ПРИСТРІЙ ДЛЯ МНОЖЕННЯ ЕЛЕМЕНТІВ СКІНЧЕННОГО ПОЛЯ GF(2 ) НА КОМБІНАЦІЙНИХ СХЕМАХ UA 103490 U UA 103490 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до галузі обчислювальної техніки і може бути використана в пристроях для кодування та декодування циклічних кодів, призначених для передачі повідомлень з високою достовірністю в системах доставки і обробки дискретної інформації. Відомий пристрій множення елементів скінченних полів, що містить два регістри співмножників, входи яких є входами першого і другого співмножників пристрою, багатовходові суматори за модулем два, виходи яких є виходами пристрою, елементи І, об'єднані в групи елементів І, перші входи яких в кожній групі об'єднані і підключені до відповідного виходу регістра першого співмножника, виходи регістра другого співмножника з'єднані з другими входами відповідних елементів І першої групи, причому виходи регістра другого співмножника з'єднані з другими входами відповідних елементів І всіх груп елементів І, починаючи з другої групи, виходи груп елементів І з'єднані з входами блока обчислення компонент множення, виходи якого підключені до входів багатовходових суматорів за модулем два і входів блока об'єднання загальних доданків, виходи якого з'єднані з іншими входами багатовходових суматорів за модулем два і входом блока об'єднання загальних доданків [1]. Такі пристрої мають великі апаратурні витрати на реалізацію операцій кодування та декодування та в цілому на реалізацію схем контролю і схем видачі результату. Найбільш близьким аналогом є [2] пристрій для множення елементів скінченних полів n GF(2 ), який містить блок формування часткових добутків, який складається з n груп по n елементів І кожній, (n-1) блоків матричного перетворення та блок додавання, виходи якого з'єднані з виходом результату пристрою, вхід 1-го розряду першого (I=1,…,n) співмножника якого з'єднаний з згрупованими першими входами елементів І і-ої групи блока формування часткових добутків, входи поточної суми j-гo блока матричного перетворення (j=2,…,n-1) з'єднані з виходами поточної суми (j-1)-гo блока матричного перетворення, а кожний блок матричного перетворення містить першу і другу групи із n та (n-1) суматорів по модулю два, першу і другу групи з (n2) та n елементів І та елемент АБО, причому входи блока множення з'єднані з відповідними входами коефіцієнтів утворюючого поліному пристрою і входами коефіцієнтів утворюючого поліному кожного з (n-1) блоків матричного перетворення, а виходи зі входами коефіцієнтів розширення k-го блока матричного перетворення (k=1,…, n-2), виходи поточної суми (n-1)-го блока матричного перетворення з'єднані з першими входами блока додавання, другі входи якого з'єднані з виходами відповідних елементів І, з першої по (n-1) групу якого з'єднані відповідно з входами часткових добутків з першого по (n-1) блок матричного перетворення, вхід і-го розряду другого співмножника пристрою з'єднаний з групованими другими входами і-их елементів І в кожній групі блока формування часткових добутків, при цьому в кожному блоці матричного перетворення перші входи суматорів по модулю два першої групи з'єднані з входами поточної суми блока, входи часткових добутків якого з'єднані з другими входами суматорів по модулю два першої групи, виходи яких, починаючи з другого, з'єднані відповідно з першими входами суматорів по модулю два другої групи, другі входи яких з'єднані з виходами з першого по (n-1)-ий елемент І другої групи, виходи суматорів по модулю два та вихід (n-2)-го елемента І другої групи з'єднані з відповідними виходами поточної суми блока, виходи суматорів по модулю два з першого по (n-2)-ий першої групи з'єднані відповідно з першими входами елементів І першої групи, другі входи яких з'єднані з відповідними входами коефіцієнтів розширення блока, а виходи з входами елемента АБО, вихід якого з'єднаний з групованими першими входами елемента І другої групи, другі входи яких з'єднані з відповідними входами коефіцієнтів утворюючого поліному блока. Недоліком даного пристрою є обмеженість функціональних можливостей за рахунок важких апаратурних витрат при виконанні операції виявлення та декодування помилок, за рахунок чого зростають часові витрати при кодуванні та декодуванні інформації. В основу корисної моделі поставлена задача удосконалення пристрою для множення n елементів скінченних полів GF(2 ) шляхом зменшення параметрів часу обчислення та шляхом реалізації пристрою на комбінаційних схемах. Це дозволяє забезпечити безпосереднє виконання операції множення елементів скінченних m полів GF(2 ) методами, що використовують логічні функції, тобто має широкі функціональні можливості застосування їх в процедурах кодування та декодування кодів. Поставлена задача вирішується тим, що в пристрої множення елементів скінченного поля m (2 ), що містить два регістри співмножників, входи яких є входами першого і другого співмножників пристрою, багатовходові суматори за модулем два, виходи яких є елементами І, що об'єднані в групи елементів І, перші входи яких в кожній групі об'єднані і підключені до відповідного виходу регістра першого співмножника, виходи регістра другого співмножника з'єднані з другими входами відповідних елементів І першої групи, а також, згідно з корисною моделлю, в пристрій введено блок обчислення добутку і блок об'єднання загальних доданків, а 1 UA 103490 U 5 10 також пристрій реалізовано на основі комбінаційних схем з використанням функціональних елементів схем І з двома входами, елементів АБО з двома входами та елементів НІ, причому виходи груп елементів І з'єднані з входами блока обчислення компонент множення, виходи якого підключені до входу блока обчислення добутку і входів блока об'єднання загальних доданків, а виходи блока обчислення добутку з'єднані з іншими входами блока об'єднання загальних доданків. Множення елементів скінченного поля, наприклад із застосуванням комбінаційної схеми множення, що реалізує алгоритм множення у відповідності з виразом ( A 1  P  A * )  B  A  B) , 2 має 1-ий рівень, на якому обчислюється матриця, що складається з наступних груп функціональних осередків   D   D  , , ( (1) (1) ( ) G11)  D11 ,D12 ,..., D11m 1 , , G(1) 2 G(1) m (1) (1) (1) 2 1,D 22 ,..., D 2, m 1 (1) (1) (1) m1,Dm2 ,..., Dm, m 1 2 де D(1) - блоки, що складаються з схем І та суматорів по модулю 2. Цей рівень містить m (mij 2 1)/2 схем І та m(m-1) /2 суматорів по модулю 2. Наявність схем І дає можливість змінювати 15 багаточлен р(х). При фіксованому багаточлені р(х) ці схеми не потрібні, оскільки значення p( j) i містяться в структурі 1-го рівня. 1 На другому рівні виконується множення матриць D2  B , що містить m схем І та m(m-1) суматорів по модулю 2. Комбінаційна схема множення для варіанта побудови з можливістю зміни багаточлена р(х) та зберіганням значень p( j) представлена на кресленні 2. i 20 Універсальна комбінаційна схема, що реалізує вираз ( A 1  P  A * )  B  A  B) побудована 2 на основі функціональних осередків, має також два рівня та представлена на кресленні 3. 1-й 25 30 35 40 45 рівень комбінаційної схеми складають блоки функціональних осередків ( Dij1) (1) (1) (1) ( i  1 m, j  1 m  1) , кожний з яких складається з одного (D11 , D21,..., Dm1) або декількох блоків. , , 2-й рівень складається з функціональних осередків Ci (i  0, m  1), , кожний з яких містить m блоків. Із застосуванням алгоритму при визначенні контрольних символів потрібно в 2 рази менше операцій модульного множення. В результаті це дозволяє забезпечити безпосередньо виконувати операції декодування одиночних недвійкових помилок, і як наслідок, розширення функціональних можливостей побудови комбінаційних схем. На креслені фіг. 1 зображена структурна схема пристрою множення елементів скінченних m полів GF(2 ) на комбінаційних схемах. На кресленні фіг. 2 - приклад схеми пристрою множення m елементів скінченних полів GF(2 ) на комбінаційній схемі з можливістю зміни багаточлена р(х) та зберіганням значень p( j) . На кресленні 3 - приклад схеми пристрою множення елементів i m скінченних полів GF(2 ) на універсальній комбінаційній схемі. m Пристрій для множення елементів скінченних полів GF(2 ) на комбінаційних схемах містить два регістри співмножників, входи яких є входами першого і другого співмножників пристрою Вх.1 та Вх.2, багатовходові суматори за модулем два 1 та 3, виходи яких є елементами І 2, що об'єднані в групи елементів І 2, перші входи 7 яких в кожній групі об'єднані і підключені до відповідного виходу регістра першого співмножника, виходи регістра другого співмножника 8 з'єднані з другими входами відповідних елементів І першої групи, а також, згідно з корисною моделлю, в пристрій введено блок обчислення добутку 5 і блок об'єднання загальних доданків 6, а також пристрій реалізовано на основі комбінаційних схем з використанням функціональних елементів схем І з двома входами елементів АБО з двома входами та елементів НІ, причому виходи груп елементів І 9 з'єднані з входами блока обчислення компонент множення 4, виходи якого 10 підключені до входу блока обчислення добутку 5 і входів 13 блока об'єднання загальних доданків 6, а виходи блока обчислення добутку 5 з'єднані з іншими входами 11 блока об'єднання загальних доданків 6. 2 UA 103490 U m 5 10 15 20 Пристрій для множення елементів скінченного поля GF(2 ) на комбінаційних схемах працює в такий спосіб. Перед початком множення значення потрапляють на входи співмножників пристрою Вх.1 та Вх.2, що являють собою багатовходові суматори за модулем два 1 та 3, результати яких надходять на виходи цих елементів І 2, що об'єднані в групи елементів І 2. Здійснюється множення матриць P  A * , результати яких потрапляють на входи 7, які в кожній групі об'єднані 2 і підключені до відповідного виходу регістра першого співмножника, виходи регістра другого співмножника 8 з'єднані з другими входами відповідних елементів І першої групи, причому виходи груп елементів І 9 з'єднані з входами блока обчислення компонент множення 4, де виконується додавання матриць A1  D1 , виходи якого 10 підключені до входу блока обчислення добутку 5 і входів 13 блока об'єднання загальних доданків 6, а виходи блока обчислення добутку 5 з'єднані з іншими входами 11 блока об'єднання загальних доданків 6. Остаточні результати множення матриць D2  B надходять на вихід пристрою. Таким чином, ефективність запропонованого пристрою визначається його багатофункціональними можливостями (запропоновано метод множення елементів скінченного поля, що базується на використанні логічних функцій), регулярністю структури та можливістю реалізації у вигляді ВІС або ПЛІС. Джерела інформації: 1. Патент Російської Федерації № 35930, кл. Н03М 13/05, 2004 2. Деклараційний патент на корисну модель № 43629, кл. Н03М 7/00, 2009. ФОРМУЛА КОРИСНОЇ МОДЕЛІ m 25 30 35 Пристрій для множення елементів скінченного поля GF(2 ) на комбінаційних схемах, що містить два регістри співмножників, входи яких є входами першого і другого співмножників пристрою, багатовходові суматори за модулем два, виходи яких є елементами І, що об'єднані в групи елементів І, перші входи яких в кожній групі об'єднані і підключені до відповідного виходу регістра першого співмножника, виходи регістра другого співмножника з'єднані з другими входами відповідних елементів І першої групи, який відрізняється тим, що в пристрій введено блок обчислення добутку і блок об'єднання загальних доданків, а також пристрій реалізовано на основі комбінаційних схем з використанням функціональних елементів схем І з двома входами, елементів АБО з двома входами та елементів НІ, причому виходи груп елементів І з'єднані з входами блока обчислення компонент множення, виходи якого підключені до входу блока обчислення добутку і входів блока об'єднання загальних доданків, а виходи блока обчислення добутку з'єднані з іншими входами блока об’єднання загальних доданків. 3 UA 103490 U 4 UA 103490 U Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5