Пристрій для табличної реалізації арифметичних операцій множення та додавання чисел за модулем mi класу лишків

Реферат: Винахід належить до області автоматики та обчислювальної техніки і може бути використаний у системах і засобах обробки цифрової інформації, що функціонують у непозиційній системі числення класу лишків. Пристрій для табличної реалізації арифметичних операцій множення та додавання чисел за модулем mi містить перший і другий вхідні регістри, дешифратори, першу групу елементів І, перший комутатор, суматор за модулем два, групи ключів, групи елементів АБО, елементи АБО, вихідний регістр, введено другу, третю, четверту і п'яту групи елементів І, третю групу елементів АБО, шість елементів І, два елементи І-НЕ, другий комутатор, третю групу ключів. Технічним результатом, що досягається даним винаходом є розширення функціональних можливостей пристрою за рахунок виконання, крім операції модульного множення двох чисел за довільним модулем mi класу лишків, ще додаткової операції додавання за довільним модулем mi класу лишків. UA 106343 C2 (12) UA 106343 C2 UA 106343 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід (пристрій) належить до області автоматики та обчислювальної техніки і може бути використано у системах і засобах обробки цифрової інформації, що функціонують у непозиційній системі числення класу лишків (КЛ). Відомий пристрій (аналог) для модульного множення за довільним модулем mi КЛ (а.с. № 550636 СРСР, МПК G 06 F 7/52, Б.В. № 10, 1977 р.). Пристрій містить перший та другий дешифратори, вентильні елементи, ключові елементи, матрицю реалізації модульної операції множення за модулем mi КЛ, логічні елементи І та АБО. Недолік аналога полягає в обмежених функціональних можливостях, щодо реалізації до операції модульного множення за модулем mi КЛ, додатково операції модульного додавання за модулем mi. Відомий пристрій (аналог) для множення за довільним модулем mi КЛ, що містить вхідні регістри, дешифратори, групи елементів АБО, групи елементів І, суматор за модулем два, елементи І та АБО, комутатори та вихідний регістр (а.с. № 896620 СРСР. МПК G 06 F 7/72, Б.В. № 1, 1982 р.). Недолік аналога полягає в обмежених функціональних можливостях, щодо реалізації додатково до операції модульного множення за модулем mi, ще операції модульного додавання за модулем mi КЛ. Найбільш близьким за технічною суттю (прототипом) до запропонованого винаходу є пристрій для множення двох чисел за довільним модулем mi КЛ за а.с. № 922731 СРСР, МПК G 06 F 7/49, Б.В. № 15, 1982. Пристрій містить вхідні регістри, дешифратори, ключі, комутатор, вихідний регістр, а також суматор за модулем два, групи елементів АБО, елементи І та АБО, причому перший і другий вхідні регістри послідовно через відповідні перший і другий дешифратори, першу і другу групи елементів АБО та перший і другий ключі підключені відповідно до першої та другої груп входів комутатора, перші і другі групи виходів першого і другого дешифраторів підключені відповідно до входів першого, другого, третього і четвертого елементів АБО, виходи яких підключені до відповідних входів суматора за модулем два, керуючі входи ключів є входами управління пристрою, перша група виходів комутатора підключена до входів п'ятого елемента АБО та перших входів шостого, сьомого, восьмого, дев'ятого і десятого елементів АБО, до других входів яких підключена друга група виходів комутатора і входи одинадцятого елемента АБО, вихід якого підключений до перших входів першого і другого елементів І, вихід п'ятого елемента АБО підключений до перших входів третього і четвертого елементів І, другі входи першого і третього елементів І та другого і четвертого елементів І підключені відповідно до нульового й одиничного виходам суматора за модулем два, а виходи першого і четвертого елементів І та відповідно другого і третього елементів І підключені до відповідних входів дванадцятого і тринадцятого елементів АБО, виходи шостого, сьомого, восьмого, дев'ятого, десятого, дванадцятого і тринадцятого елементів АБО з'єднані з відповідними входами вихідного регістра, вихід якого є виходом пристрою. Недоліком прототипу - обмежені функціональні можливості, що полягають у неможливості виконання даним пристроєм, додатково до операції модульного множення за довільним модулем mi КЛ, операції модульного додавання чисел за довільним модулем mi КЛ. Цей недолік обумовлений тим, що для виконання операції модульного додавання чисел недостатньо використовувати, як для операції модульного множення за довільним модулем mi КЛ, тільки 0,25 частину арифметичної таблиці виконання арифметичних операцій. В основу винаходу поставлена задача розширення функціональних можливостей пристрою за рахунок виконання, крім операції модульного множення двох чисел за довільним модулем mi КЛ, ще додаткової операції додавання за довільним модулем mi КЛ. Поставлена задача вирішується тим, що пристрій, що містить вхідні регістри, дешифратори, першу групу елементів І, перший комутатор, суматор за модулем два, групи ключів, групи елементів АБО, елементи АБО, вихідний регістр, при цьому перший і другий вхідні регістри послідовно через відповідні перший і другий дешифратори, першу і другу групи елементів АБО, першу і другу групи ключів підключені до входів першого комутатора, перші і другі групи виходів першого і другого дешифраторів підключені відповідно до входів першого і другого, третього і четвертого елементів АБО, виходи яких підключені до відповідних входів суматора за модулем два, керуючі входи ключів першої та другої груп з'єднані між собою і є керуючим входом пристрою, нульовий і одиничний виходи суматора за модулем два з'єднані відповідно з першими входами першого, третього і другого, четвертого елементів І першої групи, виходи першого і четвертого елементів І першої групи з'єднані з входами п'ятого елемента АБО, а виходи другого і третього елементів І першої групи з'єднані з входами шостого елемента АБО, другі входи першого і другого елементів І першої групи з'єднані між собою і з виходом сьомого елемента АБО, другі входи третього і четвертого елементів І першої групи з'єднані між собою і з 1 UA 106343 C2 5 10 15 20 25 30 35 виходом восьмого елемента АБО, містить другу, третю, четверту і п'яту групи елементів І, третю групу елементів АБО, шість елементів І, два елементи І-НЕ, другий комутатор, третю групу ключів, причому перша і друга групи виходів першого комутатора підключені відповідно до перших входів елементів І четвертою та п'ятою груп, виходи 1-го і (mi-1)-го ключів першої та другої груп (і=1,2,…, mi-1; mi - модуль за яким функціонує пристрій) підключені до входів відповідних ключів третьої групи, виходи яких підключені до входів другого комутатора, перша і друга групи mi-1/2 виходів якого підключені до перших mi-1/2 входів відповідно сьомого та восьмого елементів АБО, виходи і-х і (mi-і)-х елементів І четвертої групи підключені відповідно до перших і других входів елементів АБО третьої групи і до других mi-1/2 входів сьомого та восьмого елементів АБО, виходи і-го та (mi-і)-го елементів І п'ятої групи підключені відповідно до третіх та четвертих входів елементів АБО третьої групи і до третіх mi-1/2 входів сьомого та восьмого елементів АБО, а (і-2)-і та (mi-і)-і виходи другого комутатора підключені відповідно до п'ятих і шостих входів відповідних елементів АБО третьої групи, виходи яких підключені до перших входів вихідного регістра, перші входи елементів І другої і третьої групи об'єднані і підключені відповідно до виходів п'ятого та шостого елементів АБО, керуючі входи ключів третьої групи об'єднані і підключені до виходу першого елемента І, до першого входу другого елемента І, до других входів першого і четвертого елементів І, відповідно, другої і третьої груп, другі входи других елементів І другої та третьої, і п'ятої груп об'єднані та є входом ознаки операції "Множення" пристрою, другі входи третіх елементів І другої і третьої груп і перший вхід третього елемента І об'єднані і підключені до виходу четвертого елемента І, перший вхід якого підключений до першого входу п'ятого елемента І до другого входу першого елемента І та є входом ознаки операції "Додавання" пристрою, другі входи четвертого елемента І другої групи і першого елемента І третьої групи об'єднані і підключені до виходу третього елемента І, другий вхід якого об'єднаний з другими входами елементів І четвертої групи і підключений до виходу п'ятого елемента І, другий вхід якого підключений до нульового виходу суматора за модулем два, виходи першого, другого, четвертого елементів І другої групи і вихід третього елемента І третьої групи підключені до входів дев'ятого елемента АБО, вихід якого підключений до першого входу першого елемента І-НЕ, виходи третього елемента І другої групи і першого, другого, четвертого елементів І третьої групи підключені до входів десятого елемента АБО, вихід якого підключений до першого входу другого елемента І-НЕ, виходи першого і другого елементів І-НЕ підключені відповідно до (mi+1)-го і (mi+2)-го входів вихідного регістра, другі входи першого і другого елементів І-НЕ об'єднані і підключені до виходу другого елемента І, перший вхід шостого елемента І підключений до виходу четвертого елемента АБО, другі входи другого і шостого елементів І об'єднані і підключені до виходу другого елемента АБО, вихід шостого елемента І підключений до другого входу четвертого елемента І. Для прототипу у схемі модульного множення двох чисел використовуються властивості симетрії арифметичної таблиці множення щодо лівої і правої діагоналей, вертикалі і горизонталі, що проходять між числами mi-1/2 і mi+1/2. В якості прикладу у табл. 1 показана реалізація виконання операції модульного множення для mi=11. 40 Таблиця 1 bi 1 2 3 4 5 6 7 8 9 10 45 ai 1 1 2 3 4 5 6 7 8 9 10 2 2 4 6 8 10 1 3 5 7 9 3 3 6 9 1 4 7 10 2 5 8 4 4 8 1 5 9 2 6 10 3 7 5 5 10 4 9 3 8 2 7 1 6 6 6 1 7 2 8 3 9 4 10 5 7 7 3 10 6 2 9 5 1 8 4 8 8 5 2 10 7 4 1 9 6 3 9 9 7 5 3 1 10 8 6 4 2 10 10 9 8 7 6 5 4 3 2 1 Симетричність відносно лівої діагоналі визначається комутативністю операції множення, симетричність відносно правої діагоналі визначається тим, що (mi-аi)(mi-bi)=aibi(mod mi). Симетричність відносно вертикалі та горизонталі визначається тим, що сума симетричних чисел кратна mi, тобто 2 UA 106343 C2 5 aibi+ai(mi-bi)≡0(mod mi); aibi+(mi-ai)-bi≡0(mod mi). Це і визначає можливість реалізації у схемі табличного множення лише 0,25 частини таблиці. 1. Операція модульного множення виконується у спеціальному коді множення, що представлений у таблиці. 2. Таблиця 2 Цифра 1 2 3 4 5 6 7 8 9 10 10 15 γ 0 0 0 0 0 1 1 1 1 1 ai 1 2 3 4 5 5 4 3 2 1 У прототипу алгоритм отримання результату операції модульного множення визначається наступним чином. Якщо два числа А і В задані по модулю mi в коді табличного множення Ai=(γа, аi), Bi=(γb, bі) то для того, щоб отримати добуток цих чисел по модулю mi, досить отримати добуток ai, bi(mod mi) у коді табличного множення та інвертувати його індекс γ у разі, якщо γа відрізняється від γb, де mi  1  0, якщо 0  аі  2 . a   m 1 1 якщо 1 ,  a i  mi  1 2  Для запропонованого винаходу у схемі модульного додавання використовуються властивості симетрії арифметичної таблиці модульного додавання відносно лівої діагоналі. Це визначається комутативністю операції додавання. Операція модульного додавання також виконується у спеціальному коді множення, що представлений у таблиці. 2. У таблиці 3 показана реалізація виконання операції модульного додавання для mi=11. Таблиця 3 bi 1 2 3 4 5 6 7 8 9 10 ai 1 2 3 4 5 6 7 8 9 10 0 2 3 4 5 6 7 8 9 10 0 1 3 4 5 6 7 8 9 10 0 1 2 4 5 6 7 8 9 10 0 1 2 3 5 6 7 8 9 10 0 1 2 3 4 6 7 8 9 10 0 1 2 3 4 5 7 8 9 10 0 1 2 3 4 5 6 8 9 10 0 1 2 3 4 5 6 7 9 10 0 1 2 3 4 5 6 7 8 10 0 1 2 3 4 5 6 7 8 9 20 Це і визначає для запропонованого винаходу можливість реалізації у схемі табличного додавання тільки 0,5 частини табл. 3 за умови, що операція модульного додавання виконується у спеціальному коді множення. Визначені номери квадрантів арифметичної таблиці виконання арифметичної операції дано у табл. 4 25 Таблиця 4 II III I IV 3 UA 106343 C2 5 10 15 20 25 30 35 40 45 50 55 На рисунку представлена блок-схема запропонованого пристрою. Пристрій містить перший і другий вхідні регістри 1; перший і другий дешифратори 2; першу 3, другу 4 та третю 5 групи елементів АБО; перший 6, другий 7, третій 8, четвертий 9, п'ятий 10, шостий 11, сьомий 12, восьмий 13, дев'ятий 14 та десятий 15 елементи АБО; першу 16, другу 17 та третю 18 групи ключових елементів (ключів); перший 19 і другий 20 комутатори, що реалізують відповідно 0,25 таблиці модульного множення та 0,5 таблиці модульного додавання; першу 21, другу 22, третю 23, четверту 24 і п'яту 25 групи елементів І; суматор 26 за модулем два; перший 27, другий 28, третій 29, четвертий 30, п'ятий 31 і шостий 32 елементи І; перший 33 і другий 34 елементи І-НЕ; вихідний регістр 35; вихідну 36 шину пристрою (вихід); керуючий вхід 37 пристрою; шину 38 подачі сигналу ознаки "Множення"; шину 38 подачі сигналу ознаки "Додавання". Перший комутатор 19 визначає результат модульного множення табл. 1 і операції модульного складання для II і IV квадрантів табл. 3 (тобто для γa=0, yb=0, уа=1, уb=1). Залежно від коду операції (множення 38 або додавання 39) перший комутатор 19 визначає результат модульного множення або додавання, тобто перший комутатор поєднує виконання двох операцій. Перша і друга групи виходів першого комутатора 19 визначають результат m 1 модульного множення, причому перша група виходів визначає значення 1  i , а друга 2 mi+1/2÷mi-1. Третя і четверта групи виходів першого комутатора 19 визначають результат модульного додавання для II і IV квадрантів табл. 3, причому третя група виходів визначає значення 1÷mi-1/2, а четверта mi+1/2÷ mi-1. Величини 0 і mi не кодуються, оскільки при множенні на ці величини результат дорівнює нулю, і в цьому випадку операція виконується швидше простим аналізом чисел, при додаванні з цими величинами значення другого чисел не змінюється, він і визначає результат операції, при визначенні результату операції з другого комутатора (І, III квадранти) вихідна шина, що об'єднує елементи І, яким присвоєний результат модульного додавання 0 і mi (права діагональ табл. 3), через регістр 35 підключається безпосередньо до виходу 36 пристрою. При необхідності значення 0 і mi можуть бути також включені у табл. 2. Другий комутатор 20 визначає результат модульного додавання для І і III квадрантів (табл. 3). Перша група виходів другого комутатора визначає значення 1÷mi-1/2, а друга mi+1/2÷mі-1. Перший 19 і другий 20 комутатори (матриці відповідей) представляють набір елементів І. 2 Кількість елементів І кожного комутатора рівна (mi-1) /4. Елементи І, яким присвоєний однаковий результат операції, об'єднуються вихідною шиною. У комутаторах здійснюється операція в унітарному коді. Результат операції також представляється в унітарному коді. Кількість вихідних шин другого комутатора 20 рівно mi-1, він визначає результат модульного додавання для І і III квадрантів. Перша група виходів об'єднує шини, яким присвоєний результат модульного додавання 1÷mi-1/2, а друга група mi+1/2÷mi-1. Кількість вихідних шин першого комутатора 19 рівно 2·(mi-1), оскільки комутатор 19 визначає результат модульного множення (перша і друга групи виходів визначають, відповідно, значення 1÷mi-1/2 і mi+1/2÷mi-1 для множення) та результат модульного додавання для II і IV квадрантів (третя і четверта групи виходів визначають, відповідно, значення 1÷mi-1/2 і mi+1/2÷mi-1 додавання). Таким чином, кожному елементу І комутатора 19 присвоюється два значення: результат модульного множення і результат модульного додавання (для II і IV квадрантів). Кількість елементів першої, другої, і третьої груп елементів АБО 3, 4 та 5 рівно m i-1/2 в кожній групі. Кількість елементів І четвертою 24 та п'ятою 25 груп елементів І дорівнює mi-1 у кожній групі. Вихід елементу АБО 14 визначає значення γ=1, а вихід елементу АБО 15 - γ=0. Пристрій-винахід працює у трьох режимах роботи наступним чином. Перший режим роботи - визначення результату операції модульного множення. Присутній сигнал шини 38 ознаки "Множення" пристрою. На вхідні регістри 1 заносяться числа і послідовно через дешифратори 2, групи елементів АБО 3 і 4 та групи ключів 16 і 17 поступають на комутатор 19. Ключі 16 відкриваються сигналом з керуючого входу 37 пристрою. Вихідний сигнал комутатора 19 через один з елементів І 25 п'ятої групи поступає на один з шести входів визначеного елементу АБО 5 третьої групи. З виходу цього елемента сигнал поступає на відповідний вхід вихідного регістра 35. Елементи 12, 13, 21, 10, 11, 22, 23, 14, 15, 33 і 34 призначені для визначення індексу γ у записі результату модульної операції. Комутатор 20 закритий, оскільки відсутній сигнал шини 39 "Додавання" пристрою. Другий режим роботи - визначення результату операції модульного додавання для II і IV квадрантів таблиці модульного додавання (тобто γа=yb=0 та γа=yb=1). У цьому присутній сигнал шини 39 "Додавання" пристрою. Комутатор 20 закритий, оскільки відсутній сигнал з одиничного виходу суматора 26 по модулю два [γа+γb=0(mod 2)], елемент І 27 закритий і, отже, ключі 18 4 UA 106343 C2 5 10 15 20 третьої групи закриті. Група елементів І 25 п'ятої групи закрита (відсутній сигнал шини 38 "Множення"). Вихідний сигнал комутатора 19 по третій і четвертій групам виходів (по одній з шин цих груп) через один з елементів І 24 четвертих групи, елемент АБО 5 третьої групи поступає на вихідний регістр 35. Третій режим роботи - визначення результату операції модульного додавання для І і III квадрантів таблиці модульного додавання (тобто для γа=0, уb=1 та γa=1, γb=0). Присутній сигнал шини 39 "Додавання", а сигнал шини 38 "Множення" пристрою відсутній. Комутатор 20 відкритий, а на вихідних шинах комутатора 19 відсутній вихідний сигнал, оскільки елементи І 24 і 25 четвертої і п'ятої груп зачинені. Ключі 18 третьої групи відкриті (на виході елементу І 27 є присутнім сигнал) і комутатор 20 визначає результат модульного додавання для І і III квадрантів. Для γа=1, γb=0 значення індексу у запису результату модульного додавання визначається з виходів елементів АБО 14 та 15. Для γа=0, γb=1 значення у визначається інвертуванням вихідних сигналів елементів АБО 14 та 15. Таким чином, суттєво розширюються функціональні можливості пристрою-прототипу за рахунок виконання крім операції модульного множення двох чисел за довільним модулем mi КЛ ще додаткової операції модульного додавання за цим модулем КЛ. Тобто запропонований винахід має змогу одночасно поєднувати виконання операцій модульного множення і додавання чисел за довільним модулем mi КЛ. При цьому таблиця що реалізує операцію множення за довільним модулем mi КЛ, може бути конструктивно зменшена у чотири рази, а таблиця, що реалізовує операцію складання може бути конструктивно зменшена у два рази. ФОРМУЛА ВИНАХОДУ 25 30 35 40 45 50 55 60 Пристрій для табличної реалізації арифметичних операцій множення та додавання чисел за модулем mi класу лишків, що містить перший і другий вхідні регістри, перший і другий дешифратори, першу групу елементів І, перший комутатор, суматор за модулем два, групи ключів, групи елементів АБО, елементи АБО, вихідний регістр, при цьому перший і другий вхідні регістри послідовно через відповідні перший і другий дешифратори, першу і другу групи елементів АБО, першу і другу групи ключів підключені до входів першого комутатора, перші і другі групи виходів першого і другого дешифраторів підключені відповідно до входів першого і другого, третього і четвертого елементів АБО, виходи яких підключені до відповідних входів суматора за модулем два, керуючі входи ключів першої та другої груп з'єднані між собою і є керуючим входом пристрою, виходи суматора за модулем два з'єднані відповідно з першими входами першого, третього і другого, четвертого елементів І першої групи, виходи першого і четвертого елементів І першої групи з'єднані з входами п'ятого елемента АБО, а виходи другого і третього елементів І першої групи з'єднані з входами шостого елемента АБО, другі входи першого і другого елементів І першої групи з'єднані між собою і з виходом сьомого елемента АБО, другі входи третього і четвертого елементів І першої групи з'єднані між собою і з виходом восьмого елемента АБО, який відрізняється тим, що він містить другу, третю, четверту і п'яту групи елементів І, третю групу елементів АБО, шість елементів І, два елементи І-НЕ, другий комутатор, третю групу ключів, причому перша і друга групи виходів першого комутатора підключені відповідно до перших входів елементів І четвертої та п'ятої груп, виходи і-х і (mi-1)-х ключів першої та другої груп (і=1, 2, mi-1; mi - модуль класу лишків) підключені до входів відповідних ключів третьої групи, виходи яких підключені до входів другого комутатора, перша і друга групи mi-1/2 виходів якого підключені до перших mi-1/2 входів відповідно сьомого та восьмого елементів АБО, виходи і-х і (mi-і)-х елементів І четвертої групи підключені відповідно до перших і других входів елементів АБО третьої групи і до других mi-1/2 входів сьомого та восьмого елементів АБО, виходи і-х і (mi-і)-х елементів І п'ятої групи підключені відповідно до третіх і четвертих входів елементів АБО третьої групи і до третіх mi-1/2 входів сьомого та восьмого елементів АБО, (і-2)-і та (mi-і)-і виходи другого комутатора підключені відповідно до п'ятих і шостих входів відповідних елементів АБО третьої групи, виходи яких підключені до перших mi входів вихідного регістра, вихід якого є виходом пристрою, перші входи елементів І другої і третьої групи об'єднані і підключені відповідно до виходів п'ятого та шостого елементів АБО, керуючі входи ключів третьої групи об'єднані і підключені до виходу першого елемента І, до першого входу другого елемента І, до других входів першого і четвертого елементів І, відповідно, другої і третьої груп, другі входи других елементів І другої і третьої, і п'ятої груп об'єднані і є входом "Множення" пристрою, другі входи третіх елементів І другої і третьої груп і перший вхід третього елемента І об'єднані і підключені до виходу четвертого елемента І, перший вхід якого підключений до першого входу п'ятого елемента І, до другого входу першого елемента І і є входом "Додавання" пристрою, другі входи четвертого елемента І другої групи і 5 UA 106343 C2 5 10 першого елемента І третьої групи об'єднані і підключені до виходу третього елемента І, другий вхід якого об'єднаний з другими входами елементів І четвертої групи і підключений до виходу п'ятого елемента І, другий вхід якого підключений до нульового виходу суматора за модулем два, виходи першого, другого, четвертого елементів І другої групи і вихід третього елемента І третьої групи підключені до входів дев'ятого елемента АБО, вихід якого підключений до першого входу першого елемента І-НЕ, виходи третього елемента І другої групи і першого, другого, четвертого елементів І третьої групи підключені до входів десятого елемента АБО, вихід якого підключений до першого входу другого елемента І-НЕ, виходи першого і другого елементів І-НЕ підключені відповідно до (mi+1)-му і (mi+2)-му входам вихідного регістра, другі входи першого і другого елементів І-НЕ об'єднані і підключені до виходу другого елемента І, перший вхід шостого елемента І підключений до виходу четвертого елемента АБО, другі входи другого і шостого елементів І об'єднані і підключені до виходу другого елемента АБО, вихід шостого елемента І підключений до другого входу четвертого елемента І. 6 UA 106343 C2 Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7