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

Реферат: Пристрій для визначення лишків натурального числа за довільним модулем системи залишкових класів (СЗК) містить перший, другий та третій входи і вихід пристрою, регістр. Додатково введено групу з n  1 суматора (n  [N / m]; [0  N] - числовий діапазон обробки даних у СЗК; m - модуль за яким працює пристрій), групу з n  1 схем порівняння (СП), групу з n  1 елементів І та елемент АБО, вихід якого є виходом пристрою. UA 119758 U (12) UA 119758 U UA 119758 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель (пристрій) належить до галузі автоматики й обчислювальної техніки і може бути використана в системах та засобах, що функціонують у непозиційній системі числення залишкових класів (СЗК). Відомий пристрій (аналог), що містить вхідний та вихідний регістри, суматори, елементи АБО та І, групи елементів І та АБО [а.с. № 1124310 СРСР МПК G06F 11/00, 1983р.]. Даний пристрій дозволяє виконувати операцію визначення лишків за модулем. Недоліком пристрою - значний час виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Близьким за технічною суттю і результатом, що досягається (аналогом), вибраний пристрій для згортки за довільним модулем [а.с. СРСР № 1509903, кл. G06F 11/08, Б.В. № 35, 1989 p.], що містить групу суматорів, групу комутаторів, дві групи елементів І, дві групи елементів АБО та вихідний регістр. Недоліком пристрою - значний час виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Близьким за технічною суттю і результатом, що досягається (аналогом), вибраний пристрій для перетворення позиційного двійкового коду у лишки за двома довільними модулями [патент України № 91894, МПК G06F 5/00, Бюл. № 14 від 25.07.2014 р.], що містить регістри, суматори, блок множення, елементи І та ін. Недолік пристрою - значний час виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Найближчим аналогом за технічною суттю і результатом, що досягається, вибраний пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем [патент України № 92155, МПК G06F 11/08, Бюл. № 15 від 11.08.2014 р.]. Пристрій містить: лічильник, елементи І, блок порівняння, суматор, блок пам'яті констант, блок множення, регістр, перший та другий входи пристрою, вихід пристрою. Недоліком найближчого аналога є значний час виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Цей недолік обумовлено в основному тим, що формування значень xi  X  k  m , а також проведення операцій порівняння величин xi та m здійснюється послідовно у часі. В основу корисної моделі поставлена задача - зменшення часу виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Поставлена задача вирішується тим, що пристрій містить перший, другий та третій входи і вихід пристрою, регістр, відповідно до корисної моделі, додатково введено групу з n  1 суматора (n  [N / m]; [0  N] - числовий діапазон обробки даних у СЗК; m - модуль, за яким працює пристрій), групу з n  1 схем порівняння (СП), групу з n  1 елементів І та елемент АБО, при цьому перший вхід пристрою підключено до перших входів суматорів групи, до других входів яких підключено відповідні шини другого входу, виходи суматорів групи підключено до перших входів відповідних СП групи та до перших входів елементів І групи, до других входів СП групи підключено третій вхід пристрою, а виходи СП підключено до других входів відповідних елементів І, виходи яких через елемент АБО підключено до входу регістра, вихід якого є виходом пристрою. Введення вказаних ознак дозволяє значно зменшити час виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Це досягається за рахунок організації паралельного обчислювального процесу реалізації арифметичних операцій xi  X  k  m (k  0, n) та порівняння значень xi та модуля m . На графічному зображенні наведена блок-схема корисної моделі, де: 1 - перший вхід пристрою (шина подачі натурального числа X , лишок x за модулем m якого необхідно визначити); 2 - група суматорів, що реалізують операції знаходження величин xi  X  k  m (k  0, n) ; 3 - другий вхід пристрою (кількість n шин другого входу дорівнює n  [N / m]; [0  N] числовий діапазон обробки даних у СЗК (0  X  N) ; 4 - група схем порівняння, що здійснюють операцію порівняння значень х та модуля m; 5 - група елементів І; 6 - третій вхід пристрою (шина подачі значення модуля m, за яким працює пристрій); 7 - елемент АБО; 8 - регістр; 9 вихід пристрою. Перший 1 вхід пристрою підключено до перших входів суматора 2 групи, до других входів яких підключено відповідні шини другого 3 входу. Виходи суматорів 2 групи підключено до перших входів відповідних СП 4 групи та до перших входів елементів І 5 групи, до других входів СП 4 групи підключено третій 6 вхід пристрою. Виходи СП 4 підключено до других входів 1 UA 119758 U 5 10 15 20 відповідних елементів І 5, виходи яких через елемент АБО 7 підключено до входу регістра 8, вихід якого є виходом 9 пристрою. Пристрій функціонує наступним чином. До першого 1 входу пристрою надходить значення числа X і далі до перших входів суматорів 2, до других входів яких за шиною 3 надходять відповідні значення констант виду k  m (k  0, n) . З виходів суматорів 2 значення xk  X  k  m надходять до перших входів відповідних СП 4 і елементів І групи 5. До других входів СП 4, за шиною 6, надходить значення m модуля пристрою. З виходу СП 4, для якої xk  m , значення x k через елемент 7 АБО надходить до входу регістра 8. Таким чином на виході регістра 9 міститься результат операції визначення лишку xk  X(mod m) натурального числа X за довільним модулем m СЗК. Розглянемо приклад визначення лишку х натурального числа X  13 за модулем m  3 . При цьому n  [N / m]  [20 / 3]  6 . За першою 1 шиною значення X  13 надходить на перші входи всіх суматорів 2, на другі входи яких за входом 3 надходять відповідні значення k  m (k  0,6) , тобто 0×3=0; 1×3=3; 2×3=6; 3×3=9; 4×3=12; 5×3=15; 6×3=18. Дані значення надходять на перші входи відповідних СП 4, на другі входи яких за шиною 6 надходить значення модуля m  3 . Таким чином тільки з виходу четвертої СП 4 значення x 4  X  4  13  4  3  13  12  1  m  3 через відповідний четвертий елемент І 5 через елемент АБО 7 надходить до входу 9 регістра 8. Перевірка: 13  1(mod 3) . Таким чином, корисна модель дозволяє суттєво зменшити час виконання операцій визначення лишків натурального числа за довільним модулем СЗК. Це досягається за рахунок паралельного одночасного формування значень xi  X  k  m , а також паралельного проведення операцій порівняння величин xi та m . 25 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 Пристрій для визначення лишків натурального числа за довільним модулем системи залишкових класів (СЗК), що містить перший, другий та третій входи і вихід пристрою, регістр, який відрізняється тим, що додатково введено групу з n  1 суматора (n  [N / m]; [0  N] числовий діапазон обробки даних у СЗК; m - модуль за яким працює пристрій), групу з n  1 35 схем порівняння (СП), групу з n  1 елементів І та елемент АБО, при цьому перший вхід пристрою підключено до перших входів суматорів групи, до других входів яких підключено відповідні шини другого входу, виходи суматорів групи підключено до перших входів відповідних СП групи та до перших входів елементів І групи, до других входів СП групи підключено третій вхід пристрою, а виходи СП підключено до других входів відповідних елементів І, виходи яких через елемент АБО підключено до входу регістра, вихід якого є виходом пристрою. 2 UA 119758 U Комп’ютерна верстка В. Мацело Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3