Пристрій для множення двох лишків за довільним модулем класу лишків

Реферат: Пристрій для множення двох лишків за довільним модулем класу лишків, що містить перший і другий вхідні регістри, перший і другий дешифратори, першу, другу та третю групи елементів АБО, першу, другу і третю групи елементів І, комутатор, перший, другий, третій, четвертий і п'ятий елементи АБО, перший і другий елементи І, шифратор, причому перший і другий входи пристрою підключені до входів відповідно першого і другого вхідних регістрів, виходи яких підключено до входів відповідно першого і другого дешифраторів, перші групи виходів яких підключено до перших входів елементів АБО відповідно першої та другої груп і до входів першого і другого елементів АБО, а другі групи виходів дешифраторів підключено до других входів елементів АБО першої та другої груп і до входів третього і четвертого елементів АБО. Введено групу вентильних елементів і вихідний регістр, входи якого безпосередньо підключено до виходів елементів АБО третьої групи, а виходи підключено до входів шифратора, вихід якого є виходом пристрою, виходи комутатора підключено до перших (інформаційних) входів вентильних елементів групи, до других (заборонених) входів яких підключено вихід п'ятого елемента АБО, а виходи вентильних елементів групи підключено до відповідних входів елементів АБО третьої групи. UA 92403 U (12) UA 92403 U UA 92403 U 5 10 15 20 25 30 35 40 45 Корисна модель (пристрій) належить до області обчислювальної техніки та може бути призначена для множення двох чисел у непозиційній системі числення класу лишків (КЛ). Відомий пристрій (аналог) для множення по довільному модулю mi КЛ [А.с. СРСР № 922731, кл. МКП G06F 7/39, Б.В. № 15, 1982 р.], що містить вхідні регістри, дешифратори, групи елементів АБО, групи елементів І, суматор по модулю два, елементи І та АБО, комутатори та вихідний регістр. Недоліком відомого пристрою є його складність. Відомий пристрій (аналог) для множення по довільному модулю mi КЛ є пристрій для множення по довільному модулю [Пат. № 60078, Україна, МПК (2011.01) G06F 7/00. Опубл. 10.06.2011, Бюл. № 11]. Він містить вхідні регістри, дешифратори, групи елементів АБО, групи елементів І, суматор по модулю два, елементи І та АБО, комутатори та вихідний регістр. Недоліком відомого пристрою є його складність. Найбільш близьким аналогом (прототипом) за технічною суттю і результатом, що досягається, є пристрій для множення чисел за модулем [А.с. СРСР № 1030799, кл. МКП G06F 7/49, Б.В. № 27, 1983 р.]. Пристрій містить перший та другий входи, перший та другий вхідні регістри, суматор за модулем два, суматор за модулем mi , групи елементів АБО, групи елементів І, елементи АБО та І, комутатор і шифратор. Недоліком прототипу є його складність. Це обумовлено значною кількістю елементів та зв'язками між ними. В основу корисної моделі поставлено задачу спрощення пристрою. Поставлена задача вирішується тим, що у пристрій для множення двох лишків за довільним модулем класу лишків, що містить перший і другий вхідні регістри, перший і другий дешифратори, першу, другу та третю групи елементів АБО, першу, другу і третю групи елементів І, комутатор, перший, другий, третій, четвертий і п'ятий елементи АБО, перший і другий елементи І, шифратор, причому перший і другий входи пристрою підключені до входів відповідно першого і другого вхідних регістрів, виходи яких підключено до входів відповідно першого і другого дешифраторів, перші групи виходів яких підключено до перших входів елементів АБО відповідно першої та другої груп і до входів першого і другого елементів АБО, а другі групи виходів дешифраторів підключено до других входів елементів АБО першої та другої груп і до входів третього і четвертого елементів АБО, виходи першого і четвертого елементів АБО підключено до першого та другого входів першого елемента І, вихід якого з'єднаний з першим входом п'ятого елемента АБО, другий вхід якого підключено до виходу другого елемента І, перший і другий входи якого підключено до виходів відповідно другого і третього елементів АБО, виходи елементів АБО першої та другої груп підключено до перших входів елементів І відповідно першої та другої груп, до других входів яких підключена шина керування пристрою, а виходи елементів І першої та другої груп підключено до перших і других групам входів комутатора, виходи якого підключено до перших входів елементів І третьої групи, до других входів яких підключено вихід п'ятого елемента АБО, а виходи елементів І третьої групи підключено до відповідних входів елементів АБО третьої групи, введено групу вентильних елементів і вихідний регістр, входи якого безпосередньо підключено до виходів елементів АБО третьої групи, а виходи підключено до входів шифратора, вихід якого є виходом пристрою, виходи комутатора підключено до перших (інформаційних) входів вентильних елементів групи, до других (заборонених) входів яких підключено вихід п'ятого елемента АБО, а виходи вентильних елементів групи підключено до відповідних входів елементів АБО третьої групи. У запропонованій корисній моделі числа представляються у штучній формі (ШФ) a'  ai  mi , 2 mi . Результат операції модульного множення представляється у вигляді ai  bi '  ai'bi' bi'  bi  2 або ai  bi '  ai'bi'  mi . Вхідні числа пристрою для множення двох лишків за довільним модулем 2 КЛ лежать у числовому інтервалі 1  ai' bi'  mi  1 , а вхідні числа комутатора лежать у вдвічі  50   * * * * меншому інтервалі, тобто, 1  ai'  bi'   mi  2 для mi парного числа, або 1  ai'  bi'   mi  1     2 2     для mi , непарного числа. Кількість елементів І у вузлах таблиці комутатора для mi парного 1 UA 92403 U 2 2 m 2  m  1  , де числа дорівнює  i  , а для mi непарного числа дорівнює  i  mi - довільний  2   2  модуль КЛ, за яким працює корисна модель. Алгоритм отримання результату операції модульного множення визначається наступним чином. Якщо два числа ai і bi задані по модулю mi в коді табличного множення (КТМ) 5       * *   ai'    a ' , ai'  , bi'    b ' , bi'  , то для того, щоб отримати добуток цих чисел за модулем mi ,  i   i   ' * ' * досить отримати добуток ai  bi mod mi  та інвертувати його індекс  у КТМ у разі, якщо      a ' , відрізняється від  b ' . Так для mi непарного маємо, що i i  mi  1  ' ' 0, якщо 1  аі bi  2 ,  a' b'   i i m 1 1 якщо i ,  аі' bi'  mi. 2     10 15 На кресленні представлена структурна схема корисної моделі, де: 1, 2 - перший і другий входи пристрою; 3, 4 - перший і другий вхідні регістри; 5, 6 - перший і другий дешифратори (дешифратор служить для перетворення чисел з двійкового коду в унітарний); 7, 8 - перша та друга групи елементів АБО 9; 10, 11 і 12 - перший, другий, третій і четвертий елементи АБО; 13 - перший елемент І; 14 - п'ятий елемент АБО; 15 - другий елемент І; 16, 17 - перша та друга групи елементів І; 18 - шина керування пристрою; 19 - комутатор (табличний пристрій служить    * * * * m для визначення значень виду  ai'  bi'  mod mi  i або виду  ai'  bi'  mod mi ; вузли таблиці     2     * * m модульного множення двох лишків комутатора кодуються значеннями  ai'  bi'  mod mi  i   2    ' * ' * або ; таке кодування вузлів таблиці модульного множення двох лишків  ai  bi  mod mi   дозволяє безпосередньо встановити взаємно однозначну відповідність між кодами чисел у ШФ та кодами чисел у звичайному поданні); 20 - третя група елементів І; 21 - група вентильних елементів; 22 - третя група елементів АБО; 23 - вихідний регістр; 24 - шифратор (шифратор служить для перетворення чисел з унітарного коду в двійковий); 25 - вихід пристрою. Перший 1 і другий 2 входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів, виходи яких підключено до входів першого 5 та другого 6 дешифраторів, перші групи виходів яких підключено до перших входів елементів АБО відповідно першої 7 та другої 8 груп і до входів першого 9 і другого 10 елементів АБО, а другі групи виходів дешифраторів 5 і 6 підключено до других входів елементів АБО першої 7 та другої 8 груп і до входів 11 третього і четвертого 12 елементів АБО, виходи першого 9 і четвертого 12 елементів АБО підключено до першого та другого входів першого 13 елемента І, вихід якого підключено до першого входу п'ятого 14 елемента АБО, другий вхід якого підключено до виходу другого 15 елемента І, перший і другий входи якого підключено до виходів відповідно другого 10 і третього 11 елементів АБО. Виходи елементів АБО першої 7 та другої 8 груп підключено до перших входів елементів І відповідно першої 16 та другої 17 груп, до других входів яких підключена шина 18 керування пристрою. Виходи елементів І першої 16 та другої 17 груп підключено до перших і других групам входів комутатора 19, виходи якого підключено до перших входів елементів І третьої 20 групи та до перших (інформаційних) входів вентильних елементів групи 21. До других входів елементів І третьої 20 групи та до других (заборонених) входів вентильних елементів групи 21 підключено вихід п'ятого 14 елемента АБО. Виходи елементів І третьої 20 групи та вентильних елементів групи 21 підключено до відповідних входів елементів АБО третьої 22 групи, виходи яких підключено до входів вихідного регістра 23, виходи якого підключено до входів шифратора 24, вихід якого є виходом 25 пристрою. На кресленні представлена блок-схема корисної моделі. У таблиці 1 представлено числа у штучній формі для mi  14 .     20 25 30 35 40 2 UA 92403 U У таблиці 2 знаком (+) позначені вузли таблиці комутатора 19, яким присвоєно результат * *  ' * ' * , операції множення двох чисел ai' і bi' за модулем mi  14 KЛ. Вузлам  ai  bi  mod mi   таблиці комутатора 19, які не позначені знаком (+), присвоєно результат операції у виді mi .  ' * ' *  ai  bi  mod mi  2         5 Таблиця 1 Числа у штучній формі для mi  14 a    b     ai bi  -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 ' * i ' * i   ai' bi' a    b     ai bi    ai' bi' 0 0 0 0 0 0 1 2 3 4 5 6 1 2 3 4 5 6 8 9 10 11 12 13 1 1 1 1 1 1 6 5 4 3 2 1 a' i b i' ' * i ' * i  a' i b i'  Таблиця 2 Числові значення, що присвоєно вузлам таблиці комутатора 19 a  b  1 1 2 3 4 5 6 3 4 5 6 12 11 10 9 8 8 9 10 11 12 13 13 12 11 10 9 8 2 13 ' * i ' * i 9 11 13 8+ 10+ 12+ 10 13 9+ 12+ 8 11 11 8+ 12+ 9 13 10+ 12 10+ 8 13 11+ 9 13 12+ 11 10+ 9 8+ Пристрій для множення двох лишків за модулем КЛ працює наступним чином (креслення). 10 За входами 1 і 2 у ШФ вхідні числа ai' і bi' у двійковому коді надходять на відповідні вхідні регістри 3 і 4, з виходів яких вони надходять на відповідні дешифратори 5 і 6. З виходів дешифраторів 5 і 6 числа ai' і bi' в унітарному коді через відповідну пару елементів АБО груп 7 і 8, через відповідну пару елементів І 16 та 17 груп, яка одночасно відкриваються сигналом шини 18 керуванням пристроєм, надходять до входів комутатора 19. Вихідний сигнал комутатора 19,     15 * * * * m що відповідає значенню  ai'  bi'  mod mi  i або  ai'  bi'  mod mi , надходить до першого     2     (інформаційного) входи j-го вентильного елемента 21 та до першого входу j-го елемента 120 групи (j=1, 2,…, mі-1). Якщо  a '   b ' , тоді елементи І 13 та 15 закриті і вихідний сигнал елемента АБО 14 20 відсутній. Вентильні елементи 21 групи відкриті, а елементи І 20 групи закриті (на другий (заборонений) вхід вентильних елементів 21 сигнал з виходу елемента АБО 14 не надходить). У цьому випадку сигнал з виходу j-го вентильного елемента 21 групи надходить до входу j-го елемента АБО 22 групи, з виходу якого сигнал, що відповідає значенню результату операції в унітарному коді надходить до входу регістра 23 і далі надходить до входу шифратора 24, з i i 3 UA 92403 U   * * виходу якого результат операції  ai'  bi'  mod mi модульного множення у двійковому коді     надходить до виходу 25 пристрою. Якщо  '   ' , тоді сигнал з виходу елемента АБО 14 присутній. Цей сигнал закриває ai 5 bi вентильні елементи 21 групи і відкриває елементи І 20 групи. Це дозволяє проходженню сигналу, що відповідає значенню результату операції в унітарному коді, з виходу комутатора 19 до входу елемента I 20 групи. У цьому випадку сигнал з виходу j-гo елемента І 20 через (mj-j)-й елемент АБО 22 групи надходить до входу регістру 23, з виходу якого надходить до входу   10 * * шифратора 24, з виходу якого результат операції  ai'  bi'  mod mi модульного множення у     двійковому коді надходить до виходу 25 пристрою. Таким чином у запропонованому пристрою при реалізації операції модульного множення двох лишків у КТМ, що представлені у штучній формі, за рахунок кодування вузлів таблиці   15   * * * * m модульного множення комутатора значеннями  ai'  bi'  mod mi  i або  ai'  bi'  mod mi     2     відбувається самокорекція результату операції. За рахунок цього можливо спрощення прототипу. Спрощення пристрою досягається за рахунок виключення зі структурної схеми прототипу суматора за модулем mi групи елементів АБО, групи елементів І, а також зв'язків між ними. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 25 30 35 40 Пристрій для множення двох лишків за довільним модулем класу лишків, що містить перший і другий вхідні регістри, перший і другий дешифратори, першу, другу та третю групи елементів АБО, першу, другу і третю групи елементів І, комутатор, перший, другий, третій, четвертий і п'ятий елементи АБО, перший і другий елементи І, шифратор, причому перший і другий входи пристрою підключені до входів відповідно першого і другого вхідних регістрів, виходи яких підключено до входів відповідно першого і другого дешифраторів, перші групи виходів яких підключено до перших входів елементів АБО відповідно першої та другої груп і до входів першого і другого елементів АБО, а другі групи виходів дешифраторів підключено до других входів елементів АБО першої та другої груп і до входів третього і четвертого елементів АБО, виходи першого і четвертого елементів АБО підключено до першого та другого входів першого елемента І, вихід якого з'єднаний з першим входом п'ятого елемента АБО, другий вхід якого підключено до виходу другого елемента І, перший і другий входи якого підключено до виходів відповідно другого і третього елементів АБО, виходи елементів АБО першої та другої груп підключено до перших входів елементів І відповідно першої та другої груп, до других входів яких підключена шина керування пристрою, а виходи елементів І першої та другої груп підключено до перших і других групам входів комутатора, виходи якого підключено до перших входів елементів І третьої групи, до других входів яких підключено вихід п'ятого елемента АБО, а виходи елементів І третьої групи підключено до відповідних входів елементів АБО третьої групи, який відрізняється тим, що введено групу вентильних елементів і вихідний регістр, входи якого безпосередньо підключено до виходів елементів АБО третьої групи, а виходи підключено до входів шифратора, вихід якого є виходом пристрою, виходи комутатора підключено до перших (інформаційних) входів вентильних елементів групи, до других (заборонених) входів яких підключено вихід п'ятого елемента АБО, а виходи вентильних елементів групи підключено до відповідних входів елементів АБО третьої групи. 4 UA 92403 U Комп’ютерна верстка М. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5