Табличний пристрій для множення двох чисел за модулем m класу лишків

Табличний пристрій для множення двох чисел за модулем m класу лишків, що містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, суматор за модулем два, першу, другу та третю групи елементів АБО, першу та другу групи ключових елементів, комутатор, перший, другий, третій, четвертий, п'ятий, шостий, сьомий та восьмий елементи АБО, перший, другий, третій і четвертий елементи І, при цьому вихід вихідного регістра є виходом пристрою, а перший та другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено відповідно до входів перm  1  шого та другого дешифраторів, перші  0   2   групи входів першого та другого дешифраторів підключені до входів першого та другого елементів  m 1  АБО, а другі   m  1 групи виходів першого  2  та другого дешифраторів підключені до входів третього та четвертого елементів АБО, виходи першого, другого, третього та четвертого елементів АБО підключені до відповідних входів суматора за модулем два, а виходи першого та другого дешифраторів попарно (сума значень, що присвоєна U 2 (19) 1 3 нта і логічного блока пошуку квадрантів відносно осей арифметичної таблиці призводить до необхідності введення в пристрій додаткових елементів: дешифратора номерів базових квадратів квадранта, пасивних трансформаторних лінійок і та ін. Недолік аналога - низькі функціональні можливості. Це обумовлено тим, що результат модульного множення двох чисел визначається тільки у позитивному числовому діапазоні. Найбільш близьким до корисної моделі (прототипом) є пристрій множення в системі залишкових класів (за а. с. (СССР) № 922731, МПК G06F7/52,1982 р., БВ № 15). Пристрій містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, суматор за модулем два, перша, друга та третя групи елементів АБО, перша та друга групи ключових елементів, комутатор, перший, другий, третій, четвертий, п'ятий, шостий, сьомий та восьмий елементи АБО, перший, другий, третій і четвертий елементи І, при цьому, перший та другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено відповідно до входів першого та другого дешифраторів, перші m  1  0   групи входів першого та другого де2   шифраторів підключені до входів першого та дру m 1  гого елементів АБО, а другі   m  1 групи  2  виходів першого та другого дешифраторів підключені до входів третього та четвертого елементів АБО, виходи першого, другого, третього та четвертого елементів АБО підключені до відповідних входів суматора за модулем два, а виходи першого та другого дешифраторів попарно (сума значень, що присвоєна кожній парі вихідних шин дешифратора дорівнює значенню модуля m ) підключені до входів відповідних елементів АБО першої та другої груп, виходи яких підключено до перших входів ключових елементів першої та другої груп, до других входів яких підключена керуюча шина пристрою, а виходи ключових елементів першої та другої груп підключено до першої та другої групи входів комутатора, виходи якого попарно (сума значень, що присвоєна кожній парі вихідних шин комутатора дорівнює значенню модуля m ) підключено до відповідних елементів АБО третьої групи, виходи яких підключено до входу вихідного регістра, одночасно перша  m  1  m 1   m  1 групи виходів 1   та друга  2    2  комутатора підключені до входів відповідно п'ятого та шостого елементів АБО, вихід п'ятого елемента АБО підключено до перших входів першого та другого елемента І, а вихід шостого елемента АБО підключено до перших входів третього та четвертого елементів І, одиничний вихід суматора за модулем два підключено до других входів першого та третього елементів І, а нульовий вихід суматора за модулем два підключено до других входів другого та четвертого елементів І, виходи першого та четвертого елементів І підключено до входу сьомого елемента АБО, а виходи другого та третього еле 62313 4 ментів І підключено до входу восьмого елемента АБО. Недолік прототипу - низькі функціональні можливості. Це обумовлено тим, що результат модульного множення двох чисел визначається тільки у позитивному числовому діапазоні. В основу запропонованої корисної моделі поставлено задачу розширення функціональних можливостей пристрою-прототипу, за рахунок представлення результату арифметичної операції AB mod m модульного множення як у позитивному, так і у від'ємному числових діапазонах. Поставлена задача вирішуєтьсятим, що табличний пристрій для множення чисел за модулем m класу лишків (КЛ) містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, суматор за модулем два, першу, другу, третю та четверту групи елементів АБО, першу, другу та третю групи ключових елементів, комутатор, перший, другий, третій, четвертий, п'ятий, шостий, сьомий та восьмий елементи АБО, перший, другий, третій і четвертий елементи І, шифратор, першу, другу та третю групи елементів І, інвертор за модулем m , схему додавання за модулем m . При цьому вихід вихідного регістра є виходом пристрою, а перший та другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено відповідно до входів першого та другого дешифраm  1  торів. Перші  0   групи входів першого та 2   другого дешифраторів підключені до входів першого та другого елементів АБО, а другі  m 1   m  1 групи виходів першого та другого   2  дешифраторів підключені до входів третього та четвертого елементів АБО, виходи першого, другого, третього та четвертого елементів АБО підключені до відповідних входів суматора за модулем два. Виходи першого та другого дешифраторів попарно (сума значень, що присвоєна кожній парі вихідних шин дешифратора дорівнює значенню модуля m ) підключені до входів відповідних елементів АБО першої та другої груп, виходи яких підключено до перших входів ключових елементів першої та другої груп, до других входів яких підключена керуюча шина пристрою. Виходи ключових елементів першої та другої груп підключено до першої та другої групи входів комутатора. Інформаційні виходи комутатора підключені до входу шифратора, виходи якого підключено до перших входів елементів І першої та другої груп, нульовий вихід суматора за модулем два підключено до других входів елементів І першої групи, а одиничний вихід суматора за модулем два підключено до других входів елементів І другої групи, виходи яких підключено до входів інвертора за модулем m , виходи якого одночасно з виходами елементів І першої групи, через елементи АБО третьої групи, підключено до перших входів елементів І третьої групи та до інформаційних входів ключових елементів третьої групи, виходи якої підключено до перших входів схеми додавання за модулем m, до 5 62313 других входів якої підключені шини подачі значення m/2, при n парному, або m  1 / 2 , при n непарному. До заборонених входів ключових елементів третьої групи і до других входів елементів І третьої групи підключена вихідна керуюча шина комутатора, а виходи ключових елементів третьої групи і схеми додавання за модулем m через четверту групу елементів АБО підключено до входів вихідного регістра. Введення вказаних ознак дозволяє розширити функціональні можливості прототипу, за рахунок представлення результату арифметичної операції AB mod m модульного множення як у позитивному, так і у від'ємному числових діапазонах при збереженні всіх технічних можливостей пристрою. В запропонованій корисній моделі використовуються властивості симетрії арифметичної таблиці множення (таблиця 1, для m=11) відносно діагоналі, вертикалі і горизонталей, які проходять m 1 m 1 між значеннями і (m - модуль таблиці, 2 2 тобто, модуль за яким працює пристрій, при m непарне число). Це і визначає можливість реалізації в схемі табличного модульного множення лише 0,25 частини таблиці 1 (таблиця 2, для m=11). При цьому на відміну від відомих, в запропонованому табличному пристрої операція множення виконується безпосередньо в коді табличного множення (таблиця 3, для m=11). Алгоритм отримання результату операції табличного модульного множення визначається наступним чином: якщо два числа А і В задані за основою (модулем) m в коді табличного множення виду A   ai , ai і B  bi , bi , де     ai  bi    m 1   0, якщо 0  ai bi   2 ,   1 якщо m  1  ai bi   m  1; ,  2  m 1  A B , якщо 0  A B   ,   2 ai bi    m  A B , якщо m  1  A B   m  1.  2  Тоді для того, щоб отримати добуток AB mod m цих чисел в коді табличного множення, достатньо отримати добуток ai  bi mod m в коді табличного множення і інвертувати отриманий для добутку ai  bi mod m індекс  у випадку, якщо  a i відрізняється від  b i . Тобто, індекс  значення AB mod m визначається наступним чином   , якщо  ai  bi mod 2  0,        1mod 2, якщо  ai  bi mod 2  1.   Для рішення задачі розширення функціональних можливостей пристрою-прототипу за рахунок виконання арифметичної модульної операції AB mod m табличного множення двох чисел за модулем m, як у позитивному, так і у від'ємному   6 числових діапазонах, необхідно представити вихідні операнди A і B у наступному вигляді A   A  m і B  B  m , для m - парного чи2 2 сла; A  A  m  1 і B  B  m  1 , для m - не2 2 парного числа. Якщо, наприклад, m парне число, тоді повинні виконуватися наступні співвідношення  m  A B  m , 2 2  ,  0  AB  m  1  m   A B  m ,  2 2  0  A  B  m  1.  Очевидно, що A  B  A  B  m 2 (1). Тоді запишемо A  Bmod m  A  m 2B  m 2mod m     AB modm  m 2  A  B  m 2mod m 2 (2). З виразу (2) видно, що  A  B  A  B  m  A  B  m 2 2  (3). Тоді підставивши вираз (3) до формули (1) отримаємо A  B  A  B  m 2  A  B  m 2 m 2 (4). У співвідношенні (4) є член, що має значення m/2, який обумовлює похибку обчислення значення A  B mod m . Таким чином формули для обчислення AB mod m будуть мати наступний вигляд для m парного A  Bmodm 2  A  Bmodm  m 2 (5) або A  Bmodm 2  A  Bmodm (6). Для m непарного  A  Bmodm  1   A  Bmodm  m  1  2 2   (7) або  A  Bmodm  1   A  Bmodm  2   (8). 7 В цьому випадку вузли (знак +) комутатора (таблиця 2), для яких виконуються умови (6) або (8), об'єднуються вихідною керуючою шиною. Наявність сигналу  вихідної керуючої шини свідчить, що нема необхідності в корекції результату a  b mod m операції, тобто не треба додаi i вати значення m/2 або m  1 / 2 . Відсутність сигналу  вихідної керуючої шини свідчить, що є необхідність в корекції результату операції, тобто до результату операції a  b mod m комутатора i i треба додавати значення m/2 або m  1 / 2 . На кресленні (лист 1, 2) представлена блоксхема корисної моделі, де: 1, 2 - перший та другий входи пристрою; 3, 4 - перший та другий вхідні регістри; 5, 6 - перший та другий дешифратори (пристрій для перетворення двійкового коду в унітарний); 7, 8, 9 та 10 - перший, другий, третій та четвертий елементи АБО; 11 - суматор за модулем два (пристрій реалізує алгоритм операції додавання за модулем два, що представлено таблицею 4); 12, 13 - перша та друга група елементів АБО; 14, 15 - перша та друга група ключових елементів; 16 - шина керування пристроєм; 17 - комутатор; 18 - шифратор (пристрій для перетворення унітарного коду в двійковий); 19, 20 - перша та друга група елементів І; 21 - інвертор за модулем m; 22 - третя група елементів АБО; 23 - третя група елементів І; 24 - третя група ключових елементів 25 - схема додавання за модулем m; 26 - шини подачі значення m/2 (або m  1 / 2 ); 27 - вихідна керуюча шина комутатора; 28 - четверта група елементів АБО; 29 - вихідний регістр; 30 - вихід пристрою. Перший 1 та другий 2 входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів, виходи яких підключено відповідно до входів першого 5 та другого 6 дешифратоm  1  рів. Перші  0   групи входів першого 5 та 2   другого 6 дешифраторів підключені до входів першого 7 та другого 8 елементів АБО, а другі  m 1   m  1 групи виходів першого 5 та другого   2  6 дешифраторів підключені до входів третього 9 та четвертого 10 елементів АБО. Виходи першого 7, другого 8, третього 9 та четвертого 10 елементів АБО підключені до відповідних входів суматора 11 за модулем два. Виходи першого 5 та другого 6 дешифраторів попарно (сума значень вихідних шин дорівнює значенню модуля m) підключені до входів відповідних елементів АБО першої 12 та другої 13 груп, виходи яких підключено до перших входів ключових елементів першої 14 та другої 15 груп, до других входів яких підключена керуюча шина 16 пристрою. Виходи ключових елементів першої 14 та другої 15 груп підключено до першої та другої групи входів комутатора 17. Інформаційні виходи комутатора 17 підключені до входу шифратора 18, виходи якого підключено до перших входів елементів І першої 19 та другої 20 груп. Нульовий вихід суматора 11 за модулем два підключено до других входів елементів І першої 19 групи, а 62313 8 одиничний вихід суматора 11 за модулем два підключено до других входів елементів І другої 20 групи, виходи якої підключено до входів інвертора 21 за модулем m, виходи якого одночасно з виходами елементів І першої 19 групи, через елементи АБО третьої 22 групи, підключено до інформаційних входів ключових елементів третьої 24 групи та до перших входів елементів І третьої 23 групи. Виходи ключових елементів 24 підключено до перших входів схеми 25 додавання за модулем m, до других входів якої підключені шини 26 подачі значення m/2 (або m  1 / 2 ). До заборонених входів ключових елементів третьої 24 групи і до других входів елементів І третьої 23 групи підключена вихідна керуюча шина 27 комутатора 17. Виходи елементів І третьої 23 групи і схеми 25 додавання за модулем m через четверту 28 групу елементів АБО підключено до входів вихідного 29 регістра, вихід 30 якого є виходом пристрою. Пристрій працює наступним чином. Входи 1 і 2 табличного пристрою модульного множення по кодових ланцюгах для операндів A  і B зв'язуються вхідними регістрами 3 і 4. З вхідних регістрів 3 і 4 числа A  і B у двійковому коді надходять на відповідні дешифратори 5 і 6. Сигнал, що відповідає значенню A B в унітарному коді, з виходу дешифратора 5 рядків (6 стовпців) надходить на один з двох елементів 7 чи 9 АБО (8 чи 10 АБО), одночасно, цей сигнал надходить на відповідний елемент АБО 12 (АБО 13). Сигнал, що відповідає значенню a b  в уніi i тарному коді, з виходу двовходового елемента АБО 12 (13) надходить на ключ 14 рядків (15 стовпців). Керуючий сигнал від пристрою управління по шині 16 одночасно надходить на два ключі (рядків 14 та стовпців 15). З виходу двох відповідних ключових елементів 14 і 15 два сигнали одночасно надходять на комутатор 17 (матрицю відповідей). В той же час сигнали з виходу двох елементів АБО 7 чи 9 і АБО 8 чи 10 (див. табл. 4) надходять на одиничні або нульові входи суматора 11 за модулем два. З одиничного або нульового виходу суматора 11 (у залежності від результату модульного додавання сигналів ознак   i і   i двох вхідних a b     операндів A   i , a і B   i , b у коді табличноa i b i го множення) сигнал відкриває елементи І 20 (або елементи І 19). Сигнал, що відповідає значенню a  b mod m , з виходу комутатора 17 надходить i i на вхід шифратора 18, з виходу якого значення a  b mod m у двійковому коді надходить на вхоi i ди елементів І 19 і 20. Якщо відкриті елементи І 20, тоді з виходу інвертора 21 значення m a  b mod m , (а, якщо відкриті елементи І 19, тоді i i значення a  b mod m ), через елементи АБО 22 i i надходить на перші входи елементів І 23 та на інформаційні входи ключових елементів 24. Якщо реалізуються співвідношення (6) або (8), тоді присутній сигнал  шини 27, що відкриває елементи І 23 і закриває ключові елементи 24. Якщо реалізуються співвідношення (5) або (7), тобто відсутній сигнал  шини 27, що тоді елементи І 23 закриті, 9 62313 а ключові елементи 24 відкриті, і в цьому випадку схема 25 формує на своєму виході значення a  b mod m  m (або a  b mod m  m  1 ). i i i i 2 2 При цьому до других входів схеми 25 по шинах 26 надходить значення m/2 (або m  1 / 2 ). Кінцеве значення результату операції модульного множення двох чисел, через елементи АБО 28, надходить до входу вихідного регістру 29. Приведемо приклади конкретного виконання операції модульного множення двох чисел для m=11 ( m  1 / 2  5 ). Дивись табл. 1-5. Приклад 1. Нехай A  3 ( A  0010 ; КТМ A   i , a  0,010 ) і B  4 ( B  0001; КТМ a i   B   , b   0,001 ), тобто a  010 і b  001. b i i i i По шині 1 значення першого операнда A  0010 надходить до входу регістра 3, з виходу якого він надходить до входу дешифратора 5, з виходу якого сигнал, що відповідає значенню A  2 в унітарному коді, надходить до входу елемента АБО 7  i  0 і до входу другого елемента a   АБО першої 12 групи. По шині 2 через регістр 4 до входу дешифратора 6 надходить значення другого операнда B  0001. З виходу дешифратора 6 сигнал, що відповідає значенню B  1 в унітарному коді, надходить до входу елемента АБО 8  i  0 b   і до входу першого елемента АБО другої 13 групи. Сигнали з виходів елементів АБО 7 і 8 надходять до нульових входів суматора 11 за модулем два (табл. 4). За рахунок цього присутній сигнал "0" на нульовому виході суматора 11 (  i   i  0,   0 ; a b табл. 4). Сигнал управління шини 16 одночасно відкриває другий 14 та перший 15 ключові елементи груп, через які сигнали, що визначають значення a  2 і b  1 , надходять на другий (рядок) та i i перший (стовпець) входів комутатора 17 (табл. 2). Вихідний сигнал (що відповідає унітарному значенню a  b mod m  2 ) комутатора 17 по другій i i (табл. 2) вихідній шині надходить до другого входу шифратора 18, з виходу якого значення a  b mod m  0010 у двійковому коді через відкi i риті елементи І 19   0 , елементи АБО 22, відкриті ключові елементи 24 (відсутній сигнал  , шини 27, табл. 2) надходить до перших входів схеми 25, на другі входи якої по шинах 26 надходить значення m  1 / 2  0101. Таким чином, з виходу схеми 25 значення 0010+0101=0111 через елементи АБО 28 надходить до входу вихідного регістра 29. Перевірка: Оскільки відсутній   0 сигнал (таблиця 2, значення 2) шини 27, тоді   m  1    A  Bmodm  m  1 . A  Bmod  2  2    В цьому випадку маємо (таблиця 5): A  Bmod m  1 2    3   4mod5  2 mod5 ,     10 A  Bmodm  2 1mod11  2mod11. 2  2  5  7 , 2  7 (табл. 5). Приклад 2. Нехай A  2 ( A  0111; KTM    , a  1100 ) і B  4 ( B  1001; KTM A , ai i   B   , b   1010 ), тобто a  100 і b  010 . , b i i i i По шині 1 значення першого операнда A  0111 надходить до входу регістра 3, з виходу якого він надходить до входу дешифратора 5, з виходу якого сигнал, що відповідає значенню A  7 в унітарному коді, надходить до входу елемента АБО 9  i  1 і до входу четвертого a   (7+4=11) елемента АБО першої 12 групи. По шині 2 через регістр 4 до входу дешифратора 6 надходить значення другого операнда B  1001. З виходу дешифратора 6 сигнал, що відповідає значенню B  9 в унітарному коді, надходить до входу елемента АБО 10  i  1 і до входу другого b   (9+2=11) елемента АБО другої 13 групи. Сигнали з виходів елементів АБО 9 і 10 надходять відповідно до першого і другого одиничних входів суматора 11 за модулем два (табл. 4). За рахунок цього присутній сигнал "0" на нульовому виході суматора 11 (табл. 4). Сигнал управління шини 16 одночасно відкриває четвертий 14 та другий 15 ключові елементи груп, через які сигнали, що визначають значення a  4 і b  2 , надходять i i на четвертий (рядок) та другий (стовпець) входів комутатора 17 (табл. 2). Вихідний сигнал (що відповідає унітарному значенню a  b mod m  8 ) i i комутатора 17 (табл. 2) по восьмій вихідній шині надходить до восьмого входу шифратора 18, з виходу якого значення a  b mod m  1000 у двійi i ковому коді через відкриті елементи І 19   0 , елементи АБО 22, відкриті елементи І 23 (присутній сигнал  шини 27, табл. 2, значення 8+), через елементи АБО 28 надходить до входу вихідного регістра 29. Перевірка: Оскільки присутній   1 сигнал (таблиця 2, значення 8+) шини 27, тоді   A  Bmod m  1 2    A  Bmod m .       В цьому випадку маємо (таблиця 5): A  Bmod m  1 2   2  4(mod 5)  3( mod5) ,     A  Bmodm  7  9mod11  8( mod11) . 3  8 (табл. 5). Таким чином, технічний результат від впровадження корисної моделі складається з розширення функціональних можливостей прототипу, за рахунок представлення результату арифметичної операції ABmodm модульного множення у двійковому коді як у позитивному, так і у від'ємному числових діапазонах при збереженні всіх технічних можливостей пристрою. Ця обставина дозволяє, при необхідності, безпосередньо використовувати 11 62313 результат модульного множення у подальшому ланцюгу обчислень. Ознакою корисної моделі, як і прототипу, є безпосереднє використання в алгоритмі виконання модульного множення спеціального коду множення. Завдяки цьому виникає можливість виключення з табличного пристрою модульного множення логічних блоків пошуку, що приво 12 дить також ще і до спрощення структури пристрою, скороченню обладнання та до підвищення надійності пристрою у цілому. Необхідно відзначити простоту реалізації в пристрої логічних елементів І та АБО та уніфікацію їх для довільного модуля m KЛ. Таблиця 1 А В 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 1 3 5 7 9 3 6 9 1 4 7 10 2 5 8 4 8 1 5 9 2 6 10 3 7 5 10 4 9 3 8 2 7 1 6 6 1 7 2 8 3 9 4 10 5 7 3 10 6 2 9 5 1 8 4 8 5 2 10 7 4 1 9 6 3 9 7 5 3 1 10 8 6 4 2 10 9 8 7 6 5 4 3 2 1 Таблиця 2 a i 1 2 3 4 5 10 9 8 7 6 10 1 2 3 4 5 9 2 4 6 8+ 10 8 3 6 9 1 4+ 7 4 8+ 1 5 9 6 5 10 4+ 9 3 b i 1 2 3 4 5 Таблиця 3 Число Десятковий код Двійковій код 1 2 3 4 5 6 7 8 9 10 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 Код табличного множення (КТМ) Число Значення індексу  Десятковий код 0 1 0 2 0 3 0 4 0 5 1 5 1 4 1 3 1 2 1 1 Двійковій код 001 010 011 100 101 101 100 011 010 001 Таблиця 4 Вихід елемента АБО 7  ai  0 Вихід елемента АБО 9  bi  1 Вихід елемента АБО 8 bi  0 0 1 Вихід елемента АБО 10  bi  1 1 0 13 62313 14 Таблиця 5 m=11 А (В) -5 -4 -3 -2 -1 0 1 2 3 4 5 А' = А + 5 (В' = В + 5) Десятковий код 0 1 2 3 4 5 6 7 8 9 10 Комп’ютерна верстка Л.Литвиненко Двійковій код 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 Підписне   КТМ  ai  bi a b  i i 0 0 0 0 0 0 1 1 1 1 1 000 001 010 011 100 101 101 100 011 010 001 Тираж 23 прим. Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601