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

Реферат: Винахід належить до області обчислювальної техніки та автоматики і призначений для множення лишків ai та bi числа за довільним модулем mi системи залишкових класів (СЗК). Пристрій для множення лишків ai та bi числа за довільним модулем mi системи залишкових класів містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, першу та другу групи елементів АБО, кожна з яких містить mi  1 елементів АБО, першу та 2 UA 110901 C2 (12) UA 110901 C2 другу групи елементів І, кожна з яких містить mi  1 елементів І, комутатор, перший, другий, 2 третій і четвертий елементи АБО, перший і другий елементи І, введені п'ятий і шостий елементи АБО, третю та четверту групи елементів І, групу ключових елементів, шифратор, суматор за модулем mi. Технічним результатом, що досягається даним винаходом, є розширення функціональних можливостей пристрою шляхом представлення результату операції множення безпосередньо у двійковому коді. UA 110901 C2 5 10 15 20 Винахід належить до області обчислювальної техніки та автоматики і призначена для множення лишків аi та bi числа за довільним модулем mi системи залишкових класів (СЗК). Відомий пристрій (аналог) для множення лишків аi та bi числа за довільним модулем mi СЗК [а.с. СРСР № 885999, кл G 06 F 7/72, Б.В. № 44, 1981 р.]. Він містить вхідні регістри, дешифратори, групи елементів АБО, групи елементів І, суматор за модулем два, елементи І та АБО, комутатори та вихідний регістр. Недоліком аналога є низькі функціональні можливості пристрою, які полягають в тому, що результат операції множення лишків аi та bi числа за довільним модулем mi СЗК представляється у коді табличного множення (КТМ). Дана обставина не дозволяє безпосередньо використовувати результат модульного множення у подальших загальних обчисленнях. Відомий пристрій (аналог) для множення лишків ai та bi числа за довільним модулем mi СЗК [а.с. СРСР № 896620 кл G 06 F 7/72, Б.В. № 1, 1982 р.]. Пристрій містить перший і другий вхідні та вихідний регістри, перший і другий дешифратори, першу та другу групи елементів АБО, першу та другу групи елементів І, елементи І та АБО, комутатор. Недоліком аналога є низькі функціональні можливості пристрою, які полягають в тому, що результат операції множення лишків ai та bi числа за довільним модулем mi СЗК представляється у КТМ. Дана обставина не дозволяє безпосередньо використовувати результат модульного множення у подальших загальних обчисленнях. Найбільш близьким за технічною суттю і результатом, що досягається (прототипом), є пристрій для множення у СЗК [а.с. СРСР № 922731, кл G 06 F 7/39, Б.В. № 15, 1982 р.]. Пристрій-прототип містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, першу та другу групи елементів АБО, кожна з яких містить АБО, першу та другу групи елементів І, кожна з яких містить 25 30 mi  1 елементів 2 mi  1 елементів І, комутатор, 2 перший, другий, третій і четвертий елементи АБО, перший і другий елементи І. При цьому перший і другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено до входів відповідно першого та другого дешифраторів. Перший та (mi-1)-й виходи першого та другого дешифраторів підключено до входів перших елементів АБО першої та другої груп елементів АБО, другий та (mi-2)-й виходи першого та другого дешифраторів підключено до входів других елементів АБО першої та другої груп елементів АБО і т.д., а виходи підключено до входів  mi  1 -го та  mi  1 -го першого та другого дешифраторів      2   2   mi  1 -х елементів АБО першої та другої груп елементів АБО. Виходи    2  елементів АБО першої та другої груп підключено до перших входів елементів І відповідно першої та другої груп, до других входів яких підключена керуюча шина пристрою. Виходи 35 40 45  mi  1 першого та другого дешифраторів підключено до входів першого та другого 1   2    m 1  елементів АБО, а виходи  i  mi  1 першого та другого дешифраторів підключені до  2  входів відповідно третього та четвертого елементів АБО. Виходи першого та другого елементів АБО підключено до входів першого елемента І, а виходи третього та четвертого елементів АБО підключено до входів другого елемента І. Виходи елементів І першої та другої груп підключені відповідно до першої та другої груп входів комутатора, а вихід вихідного регістра є виходом пристрою. Недоліком прототипу - низькі функціональні можливості пристрою, які полягають в тому що результат операції множення лишків ai та bi числа за довільним модулем mi C3K представляється у КТМ. Дана обставина не дозволяє безпосередньо використовувати результат модульного множення у подальших загальних обчисленнях. Поставлена задача: розширення функціональних можливостей винаходу за рахунок вдосконалення пристрою для множення лишків ai та bi числа за довільним модулем mi СЗК шляхом представлення результату операції множення безпосередньо у двійковому коді. 1 UA 110901 C2 Поставлена задача вирішується тим, що у пристрій для множення лишків ai та bi числа за довільним модулем mi СЗК, що містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, першу та другу групи елементів АБО, кожна з яких містить mi  1 mi  1 елементів АБО, першу та другу групи елементів І, кожна з яких містить 2 2 5 10 елементів І, комутатор, перший, другий, третій і четвертий елементи АБО, перший і другий елементи І, при цьому перший і другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено до входів відповідно першого та другого дешифраторів, перший та (mi-1)-й виходи першого та другого дешифраторів підключено до входів перших елементів АБО першої та другої груп елементів АБО, другий та (mi-2)-й виходи першого та другого дешифраторів підключено до входів других елементів АБО першої та другої груп елементів АБО і т.д., а виходи дешифраторів підключено до входів  mi  1 -го та  mi  1 -го першого та другого      2   2   mi  1 -х елементів АБО першої та другої груп елементів    2  АБО, виходи елементів АБО першої та другої груп підключено до перших Входів елементів І відповідно першої та другої груп, до других входів яких підключена керуюча шина пристрою, 15 20 25 30 35 40 mi  1 першого та другого дешифраторів підключено до входів відповідно першого 2 mi  1 та другого елементів АБО, а виходи  mi  1 першого та другого дешифраторів 2 виходи 1 підключені до входів відповідно третього та четвертого елементів АБО, виходи першого та другого елементів АБО підключено до входів першого елемента І, а виходи третього та четвертого елементів АБО підключено до входів другого елемента І, виходи елементів І першої та другої груп підключені відповідно до першої та другої груп входів комутатора, а вихід вихідного регістра є виходом пристрою, додатково введено п'ятий і шостий елементи АБО, третю та четверту групи елементів І, групу ключових елементів, шифратор, суматор за модулем mi, при цьому виходи комутатора підключено до входів шифратора, виходи якого підключено до перших (інформаційних) входів елементів І третьої групи та ключових елементів групи, виходи елементів І третьої групи підключено до першої групи входів суматора за модулем mi, до другої групи входів якого підключено виходи елементів І четвертої групи, до перших входів елементів І четвертої групи підключено шини подачі сигналів, що визначають значення модуля mi за яким працює пристрій, до других (керуючих) входів елементів І третьої та четвертої груп, а також до других (заборонених) входів ключових елементів групи підключено вихід п'ятого елемента АБО, до входу якого підключено виходи першого та другого елементів І, виходи суматора за модулем mi і виходи ключових елементів групи через п'ятий елемент АБО підключено до входу вихідного регістра. Введення вказаних ознак дозволяє розширити функціональні можливості винаходу за рахунок представлення результату операції множення лишків ai та bi числа за довільним модулем mi СЗК у двійковому коді. Що в свою чергу дозволяє безпосередньо використовувати результат операції модульного множення (який представлений у двійковому коді) у подальшій послідовності операцій. У винаході використовуються властивості симетрії повної арифметичної таблиці множення лишків ai та bi числа за модулем mi відносно вертикалі і горизонталі, що проходять між числами mi  1 і 2 mi  1 , 2 де mi - модуль таблиці, а також відносно лівої діагоналі цієї таблиці. Використання цих властивостей дає змогу зменшити на 75 % кількість елементів І у повної арифметичної таблиці множення лишків ai та bi числа за модулем mi комутатора пристрою. В таблиці 1 дана повна арифметична таблиця множення лишків ai та bi за модулем mi=11, в таблиці 2 дано представлення чисел ai та bi в коді a i   a ; a  та b i   b ; b  табличного i i  45 множення. 2 i   i  UA 110901 C2 Таблиця 1 Повна арифметична таблиця множення лишків ai та bi за модулем mi=11 ai bi 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 2 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 1 2 8 3 9 4 10 5 7 3 10 6 2 9 5 1 8 4 8 6 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 У винаході множення лишків ai та bi за модулем mi здійснюється у КТМ. Алгоритм множення наступний. Якщо множники представлені у КТМ a i   a ; a  та b i   b ; b  , тоді результат i i i i 5          множення c i  a i  b i   a ; a   b ; b   c ; c  цих чисел визначається наступним чином. По i i i i i i значеннях 0,25 повної таблиці 1 (за другим квадрантом) визначається результат множення виду ai  bi mod m i   c ; c i , i де 1  a,b та c   i i i mi  1 . 2 Після цього, якщо  a   b , тоді i i індекс  c не треба інвертувати, а якщо  a   b , тоді індекс  c треба інвертувати (0→1 або i i i i 1→0). 10 Таблиця 2 Представлення чисел у КТМ Представлення чисел ai(bi) у КТМ Представлення числа у десятковому коді Представлення числа у двійковому коді 1 2 3 4 5 6 7 8 9 10 Код табличного множення Символ  a  b Число a 0001 0010 0011 0100 0101 0100 0111 1000 1001 1010 i 0 0 0 0 0 1 1 1 1 1   i i bi  001 010 011 100 101 101 100 011 010 001 В загальному випадку індекс КТМ визначається наступним чином   ai  b i ,  c i 15  0, якщо 1  a i b i , c i   mi  1  2,   mi  1  a b , c   m  1  2. , i i i i 1 якщо 2  На кресленні представлена блок-схема пристрою множення лишків ai та bi числа за довільним модулем mi, СЗК, де: 1, 2 - перший та другий входи пристрою; 3, 4 - перший та другий вхідні регістри; 5, 6 - перший та другий дешифратори (пристрої для перетворення двійкового коду чисел ai та bi в унітарний); 7, 8 - перша та друга групи елементів АБО; 9, 10 - перша та 3 UA 110901 C2 друга групи елементів І; 11 - керуюча шина пристрою; 12, 13, 14 і 15 - перший, другий, третій і четвертий елементи АБО; 16, 17 - перший і другий елементи І; 18 - комутатор (табличний пристрій для визначення результату операції a  b mod mi ); 19 - вихід пристрою; 20 i i вихідний регістр; 21 - шифратор (пристрій для перетворення унітарного коду значення результату операції a  b mod mi у двійковий код); 22 - третя група елементів І; 23 - група i i ключових елементів; 24 - суматор за модулем mi (суматор призначений для інвертування значення a  b mod mi , тобто, на виході суматора отримуємо значення i i  5   10 15      mi  a  b mod mi ); 25 - четверта група елементів І; 26 - шини подачі значення модуля mi у i i двійковому коді; 27, 28 - п'ятий і шостий елементи АБО. Перший 1 і другий 2 входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів, виходи яких підключено до входів відповідно першого 5 та другого 6 дешифраторів, перший та (mi-1)-й виходи першого 5 та другого 6 дешифраторів підключено до входів перших елементів АБО першої 7 та другої 8 груп елементів АБО, другий та (mi-2)-й виходи першого 5 та другого 6 дешифраторів підключено до входів других елементів АБО  mi  1 -го та  mi  1 -го першого 5      2   2   m  1 -х елементів АБО першої 7 та другої та другого 6 дешифраторів підключено до входів  i   2  першої 7 та другої 8 груп елементів АБО і т.д., а виходи 8 груп елементів АБО, виходи елементів АБО першої 7 та другої 8 груп підключено до перших входів елементів І відповідно першої 9 та другої 10 груп, до других входів яких підключена керуюча шина 11 пристрою, виходи 1  20 mi  1 першого 5 та другого 6 дешифраторів 2 підключено до входів відповідно першого 12 та другого 13 елементів АБО, а виходи mi  1  mi  1 першого 5 та другого 6 дешифраторів підключені до входів відповідно третього 2 25 30 35 40 14 та четвертого 15 елементів АБО, виходи першого 12 та другого 13 елементів АБО підключено до входів першого 16 елемента І, а виходи третього 14 та четвертого 15 елементів АБО підключено до входів другого 17 елемента І, виходи елементів І першої 9 та другої 10 груп підключені відповідно до першої та другої груп входів комутатора 18, а вихід 19 вихідного регістра 20 є виходом пристрою, при цьому виходи комутатора 18 підключено до входів шифратора 21, виходи якого підключено до перших (інформаційних) входів елементів І третьої 22 групи та вентильних елементів 23 групи, виходи елементів І третьої 22 групи підключено до першої групи входів суматора 24 за модулем mi, до другої групи входів якого підключено виходи елементів І четвертої 25 групи, до перших (інформаційних) входів елементів І четвертої 25 групи підключено шини 26 подачі сигналів, що визначають значення модуля mi за яким працює пристрій, до других (керуючих) входів елементів І третьої 22 і четвертої 25 груп, а також до других (заборонених) входів вентильних елементів 23 підключено вихід п'ятого 27 елемента АБО, до входу якого підключено виходи першого 16 та другого 17 елементів І, виходи суматора 24 за модулем mi і виходи ключових елементів 23 групи через шостий 28 елемент АБО підключено до входу вихідного регістра 20. Пристрій функціонує наступним чином. За входами 1 і 2 до пристрою у двійковому коді надходять значення першого ai і другого bi чисел. З виходів першого 5 і другого 6 дешифраторів значення першого ai і другого bi чисел в унітарному коді, через відповідні елементи АБО першої 7 і другої 8 груп, надходять до входів відповідних елементів І першої 9 і другої 10 груп. Сигнал шини 11 відкриває відповідну пару елементів І 9 і 10 груп. З виходу елементів І 9 і 10 груп значення a  та b  надходять до входів комутатора 18, з виходу якого значення i ai  bi mod mi , в унітарному коді надходить до входу шифратора 21 з виходу якого значення ai  bi mod mi , у двійковому коді надходить до перших (інформаційних) входів елементів І 45 третьої 22 групи, а також вентильних елементів групи 23. Якщо  a   b , тоді відсутній i i вихідний сигнал елемента АБО 27 і значення ai  bi mod mi через відкриті вентильні елементи 23, елемент АБО 28 надходить до входу вихідного регістра 20. Якщо  a   b , тоді присутній i i 4 UA 110901 C2   вихідний сигнал елемента АБО 27 і значення a  b mod mi через відкриті елементи І групи 22 i i надходить до першої групи входів суматора 24 за модулем mi, до другої групи входів якого за шинами 26, через відкриті елементи І 25 у двійковому коді, надходить значення mi модуля. З виходу суматора 24 за модулем mi, значення mi  a  b mod mi через елемент АБО 28 i i надходить до входу вихідного регістра 20. Наведемо приклад роботи винаходу при реалізації множення лишків ai та bi числа за модулем mi=11 (табл. 1, 2). Нехай ai=1001 та bi=0011. Значення чисел ai=1001 та bi=0011 за входами 1 і 2 надходять до пристрою. З виходів відповідних дешифраторів 5 і 6 значення та a  010 a i   a ; a  1 010  ; i i  5 10 15      i   (див. табл. 2), які через відповідні елементи АБО 7 і 8, елементи І 9 і 10 надходять до входу комутатора 18. Так, як  a   b , тоді присутній сигнал на i i виході елемента АБО 27, який відкриває елементи І груп 22 і 25 і закриває ключові елементи 23. В цьому випадку з виходу комутатора 18 значення a  b  2  3  6 (див. табл. 1) в унітарному i i коді надходить до входу шифратора 21 з виходу якого значення 0110 через відкриті елементи І 22 надходять до першої групи входів суматора 24, до другої групи входів якого по шинах 26 у двійковому надходить значення модуля mi=1011 за яким працює пристрій. З виходу суматора значення 1011-0110=0101 через елемент АБО 28 надходить до входу регістра 20. Перевірка: a i  b i mod mi  1001  0011  0101 mod 1011 . Представлений винахід дозволяє розширити функціональні можливості пристрою за рахунок представлення результату операції множення лишків ai та bi числа за довільним модулем mi СЗК безпосередньо у двійковому коді. Це дозволяє використовувати результату операції множення лишків ai та bi безпосередньо у подальших обчисленнях.  20  b  010 b i   bi ; b  1 011 ; i i     ФОРМУЛА ВИНАХОДУ 25 Пристрій для множення лишків ai та bi числа за довільним модулем mi системи залишкових класів, що містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, першу та другу групи елементів АБО, кожна з яких містить АБО, першу та другу групи елементів І, кожна з яких містить 30 35 mi  1 елементів 2 mi  1 елементів І, комутатор, 2 перший, другий, третій і четвертий елементи АБО, перший і другий елементи І, при цьому перший і другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено до входів відповідно першого та другого дешифраторів, перший та (mi-1)-й виходи першого та другого дешифраторів підключено до входів перших елементів АБО першої та другої груп елементів АБО, другий та (mi-2)-й виходи першого та другого дешифраторів підключено до входів других елементів АБО першої та другої груп елементів АБО і т. д., а виходи підключено до входів  mi  1   -го та  2   mi  1   -го першого та другого дешифраторів  2   mi  1   -х елементів АБО першої та другої груп елементів АБО, виходи  2  елементів АБО першої та другої груп підключено до перших входів елементів І відповідно першої та другої груп, до других входів яких підключена керуюча шина пристрою, виходи 40 45 mi  1 першого та другого дешифраторів підключено до входів відповідно першого та 2 mi  1 другого елементів АБО, а виходи  mi  1 першого та другого дешифраторів підключені 2 1 до входів відповідно третього та четвертого елементів АБО, виходи першого та другого елементів АБО підключено до входів першого елемента І, а виходи третього та четвертого елементів АБО підключено до входів другого елемента І, виходи елементів І першої та другої груп підключені відповідно до першої та другої груп входів комутатора, а вихід вихідного 5 UA 110901 C2 5 10 регістра є виходом пристрою, який відрізняється тим, що введено п'ятий і шостий елементи АБО, третю та четверту групи елементів І, групу ключових елементів, шифратор, суматор за модулем mi, при цьому виходи комутатора підключено до входів шифратора, виходи якого підключено до перших інформаційних входів елементів І третьої групи та вентильних елементів групи, виходи елементів І третьої групи підключено до першої групи входів суматора за модулем mi, до другої групи входів якого підключено виходи елементів І четвертої групи, до перших інформаційних входів елементів І четвертої групи підключено шини подачі сигналів, що визначають значення модуля mi за яким працює пристрій, до других керуючих входів елементів І третьої та четвертої груп, а також до других заборонених входів ключових елементів підключено вихід п'ятого елемента АБО, до входу якого підключено виходи першого та другого елементів І, виходи суматора за модулем mi і виходи ключових елементів через п'ятий елемент АБО підключено до входу вихідного регістра. Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 6