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

Реферат: Пристрій для визначення дійсних лишків дійсних та комплексних чисел за модулями системи залишкових класів містить перший та другий регістри, блок множення двох чисел, шину подачі значення константи множення, суматор, при цьому перший і другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід другого вхідного регістра підключено до першого входу блока множення, до другого входу якого підключена шина подачі значення константи множення, виходи першого регістра та блоку множення підключено до входів суматора. Додатково введено першу та другу групи суматорів, першу та другу групи схем порівняння, перший, другий та третій елементи АБО. UA 119904 U (12) UA 119904 U UA 119904 U Корисна модель належить до області автоматики та обчислювальної техніки та може бути застосована в комп'ютерних системах та компонентах, що функціонують у системі залишкових класів (СЗК). Відомий пристрій (аналог), цю застосовується для перетворення позиційного двійкового 5 10 15 20 25 30 35 коду A у лишок за довільним модулем mi КЛ (а.с. СРСР № 864278, МПК G06F 5/02, 1978). Пристрій містить блок множення, блок порівняння, регістри, комбінаційний суматор, елементи І та АБО. Недолік аналога - низька швидкодія визначення лишків дійсних та комплексних чисел у системі залишкових класів. Відомий пристрій (аналог), що застосовується для перетворення позиційного двійкового коду A у лишок за довільним модулем mi , КЛ (а.с. СРСР № 1185339, МПК G06F 5/02, 1985). Даний пристрій містить блок порівняння, вхідний та вихідний регістри, суматор, елементи І та АБО. Недолік аналога - низька швидкодія визначення лишків дійсних та комплексних чисел у системі залишкових класів. Відомий пристрій (аналог), що застосовується для перетворення позиційного двійкового коду A у лишок за довільним модулем mi КЛ (а.с. СРСР № 1105895, МПК G06F 11/08, 1983). Пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем mi , містить лічильник, до першого входу якого підключено перший (установчий) вхід пристрою, блок порівняння та перший елемент І, причому перший вхід першого елемента І є другим (тактовим) входом пристрою, вихід першого елемента І підключено до другого (рахункового) входу лічильника, перший вхід блока порівняння є входом подачі значення модуля mi . Недолік аналога - низька швидкодія визначення лишків дійсних та комплексних чисел у системі залишкових класів. Близьким аналогом за технічною суттю до запропонованої корисної моделі є пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем m (патент України № 92155, МПК G06F 11/08, 2014 р.). Пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем mi , що містить: лічильник, до першого входу якого підключено перший установчий вхід пристрою, блок порівняння та перший елемент І, при цьому перший вхід першого елемента І є другим тактовим входом пристрою, вихід першого елемента І підключено до другого (рахункового) входу лічильника, перший вхід блока порівняння є входом подачі значення модуля mi , другий елемент І, блок пам'яті констант, блок множення, суматор і регістр, при цьому вихід суматора підключено до першого інформаційного входу регістра, вихід якого є виходом пристрою, який підключено до першого входу суматора та до другого входу блока порівняння, вихід якого є виходом ознаки кінця перетворення позиційного двійкового коду у лишок за довільним модулем mi , вихід лічильника підключено до входу блока пам'яті констант, вихід якого підключено до першого входу блока множення, до другого якого підключена шина подачі значення модуля mi , вихід блока множення підключено до другого 40 45 50 55 входу суматора, другий вихід якого підключено до другого входу першого елемента І і до першого входу другого елемента І, вихід якого підключено до другого входу регістра, другий вхід другого елемента І підключено до другого входу пристрою, шина подачі числа, що перетворюється, підключена до третього входу регістра. Недолік аналога - низька швидкодія визначення лишків дійсних та комплексних чисел у системі залишкових класів. Найближчим аналогом до запропонованої корисної моделі є пристрій для визначення лишків дійсних та комплексних чисел у системі залишкових класів (патент України № 114063, МПК G06F 7/72, Н03М 7/18, 2017, Бюл. № 7). Пристрій містить перший вхідний регістр, перший суматор, лічильник, перший блок пам'яті констант (БПК), блок порівняння (БП), при цьому перший (тактовий) вхід пристрою підключено до входу лічильника, а вихід першого регістра підключено до перших входів першого суматора. В пристрій додатково введено першу, другу та третю групи елементів АБО, другий БПК, першу, другу та третю групи елементів І, другий і третій вхідні регістри, блок множення, другий суматор, перший та другий елементи І, вентильний елемент, при цьому вихід лічильника підключено до першого входу вентильного елемента, вихід якого підключено до перших входів першого та другого елементів І, до других входів яких підключено відповідно перша та друга керуючі шини пристрою (шини подачі сигналів 1 UA 119904 U 5 10 15 20 25 30 35 40 45 ознак відповідно першого та другого режимів роботи пристрою). Виходи першого та другого елементів І підключено до входів відповідно першого та другого БПК, виходи яких через елементи АБО першої групи підключено до других входів першого суматора, вихід якого підключено до перших входів БП і до перших входів елементів І першої групи, виходи яких є виходом пристрою. Другий (інформаційний) вхід пристрою через елементи АБО другої групи підключено до входу першого регістра. Третій і четвертий (інформаційні) входи пристрою підключено до входів відповідно другого та третього вхідних регістрів, вихід третього вхідного регістра підключено до першого входу блока множення, до другого входу якого підключена шина подачі значення константи  множення, виходи другого регістра та блока множення підключено до входів другого суматора, вихід якого підключено до входів елементів АБО другої групи. До перших входів елементів І другої та третьої груп підключено шини подачі значень відповідно першого та другого модулів пристрою, до других (відкриваючих) входів елементів І другої та третьої груп підключено відповідно перша та друга керуючі шини пристрою, виходи елементів І другої та третьої груп через елементи АБО третьої групи підключено до других входів БП, перший вихід якого підключено до других (відкриваючих) входів елементів І першої групи, а другий вихід БП підключено до другого (забороненого) входу вентильного елемента. Недолік найближчого аналога - низька швидкодія визначення дійсних лишків дійсних та комплексних чисел у СЗК. Цей недолік обумовлено послідовним за порядком отриманням дійсних лишків дійсних та комплексних чисел, а також чітко послідовним функціонуванням суматорів і схем порівняння. Задача корисної моделі - підвищення швидкодії визначення дійсних лишків дійсних та комплексних чисел у СЗК. Поставлена задача вирішується тим, що в пристрій для визначення дійсних лишків дійсних та комплексних чисел за модулями системи залишкових класів, що містить перший та другий регістри, блок множення двох чисел, шину подачі значення константи множення, суматор, при цьому перший і другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід другого вхідного регістра підключено до першого входу блока множення, до другого входу якого підключена шина подачі значення константи множення, виходи першого регістра та блока множення підключено до входів суматора, додатково введено першу та другу групи суматорів, першу та другу групи схем порівняння (СП), перший, другий та третій елементи АБО, при цьому, третій вхід пристрою підключено до перших входів суматорів першої групи, до других входів яких підключено відповідні шини подачі констант першої групи, виходи суматорів першої групи підключено до перших входів відповідних СП першої групи, до других входів яких підключено шину подачі модуля mi , а виходи СП першої групи підключено до входів першого елемента АБО, вихід суматора підключено до перших входів суматорів другої групи, до других входів яких підключено відповідні шини подачі констант другої групи, виходи суматорів другої групи підключено до перших входів відповідних СП другої групи, до других входів яких підключено шину подачі модуля N , а виходи СП другої групи підключено до входів другого елемента АБО, виходи першого та другого елементів АБО підключено до входів третього елемента АБО, вихід якого є виходом пристрою. Введення вказаних ознак дозволяє підвищити швидкодію операції визначення дійсних лишків   A(mod mi ) дійсних чисел A за довільним дійсним модулем mi СЗК, а також  операції визначення дійсних лишків h комплексних чисел A  a  bi за довільним комплексним модулем m  p  qi СЗК.  Відповідно до наслідків першої фундаментальної теореми Гауса, за заданим комплексним N якого дорівнює N  p 2  q 2 , та при найбільшому загальному  дільнику (НЗД) чисел p і q ( p, q)  1 , комплексне число A  a  bi порівняно з одним і лише  одним лишком з ряду 0,1,2, , N  2, N  1 чисел. Тобто, A  h(mod m) , де h - дійсне ціле  модулем m  p  qi , норма  50 55 число. Ізоморфізм між комплексними числами та їх дійсними лишками дає можливість реалізувати процес визначення лишків комплексних чисел за допомогою алгоритму визначення лишків числа у дійсній області. З теорії чисел відомо, що для двох чисел p і q таких, що НЗД ( p, q)  1 , знайдуться два цілих числа u та v , такі, що виконується умова u  p  v  q  1 . (1) Крім цього відомо, що існує таке число h , що визначається з наступного порівняння 2 UA 119904 U [a  (u  q  v  p)  b]  h(mod N ) (2) або (a  b   )  h(mod N ) , (3) де вираз 5   uq v p (4) за допомогою якого установлюється відповідність між комплексними та дійсними лишками чисел, називають коефіцієнтом ізоморфізму. В цьому випадку дійсний лишок h комплексного  A визначається за алгоритмом визначення дійсного лишку  дійсного числа A , тобто h  Z (modN ) , (5) числа 10 де Za  b   ; N  p 2  q 2 . (6) На кресленні представлена блок-схема корисної моделі, де: 1, 2 - перший (шина подачі 15 20 25 30 35  дійсної частині а комплексного числа A  a  bi ) та другий (шина подачі уявної частини b комплексного числа) входи пристрою; 3, 4 - перший та другий вхідні регістри; 5 - блок множення двох чисел b і  ; 6 - шина подачі значення константи   u  q  v  p множення; 7 - суматор; 8 - шина третього входу пристрою; 9 - перша група суматорів; 10 - шини подачі констант першої групи; 11 - перша група схем порівняння (СП); 12 - шина подачі модуля mi ; 13 - перший елемент АБО; 14 - друга група суматорів; 15 - шини подачі констант другої групи; 16 - друга група СП; 17 - шина подачі модуля N ; 18 - другий елемент АБО; 19 - третій елемент АБО; 20 вихід пристрою. Перший 1 і другий 2 входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів, вихід другого 4 вхідного регістра підключено до першого входу блока 5 множення, до другого входу якого підключена шина 6 подачі значення  константи множення. Виходи першого 3 регістра та блока 5 множення підключено до входів суматора 7. Третій 8 вхід пристрою підключено до перших входів суматорів першої 9 групи, до других входів яких підключено відповідні шини 10 подачі констант першої групи. Виходи суматорів першої 11 групи підключено до перших входів відповідних СП першої 9 групи, до других входів яких підключено шину 12 подачі модуля mi . Виходи СП першої 11 групи підключено до входів першого 13 елемента АБО. Вихід суматора 7 підключено до перших входів суматорів другої 14 групи, до других входів яких підключено відповідні шини 15 подачі констант другої групи. Виходи суматорів другої 14 групи підключено до перших входів відповідних СП другої 16 групи, до других входів яких підключено шину 17 подачі модуля N , а виходи СП другої 16 групи підключено до входів другого 18 елемента АБО. Виходи першого 13 та другого 18 елементів АБО підключено до входів третього 19 елемента АБО, вихід 20 якого є виходом пристрою. Пристрій для визначення дійсних лишків дійсних та комплексних чисел у системі залишкових класів функціонує у двох режимах. Перший режим. Визначення дійсного лишку   A(mod mi ) дійсного числа A за дійсним модулем mi . 40 За третім 8 входом пристрою дійсне число A надходить до перших входів суматорів першої 9 групи, до других вході яких надходять відповідні значення 0  mi ,1  mi , , k  mi констант 10. Суматори 9 виконують операцію A  k  mi (k  0,1,2,) , результат якої надходить до перших входів СП 11, до других входів за шиною 12 надходить значення модуля mi . З виходу однієї СП 11, для якої виконується умова,   A  k  mi  mi , лишок   A(mod mi ) через елементи АБО 13 і 19 надходить до виходу 20 пристрою. 45 50   Другий режим. Визначення дійсного лишку h  A(mod m) комплексного числа A  a  bi за  комплексним модулем m  p  qi .  За першим 1 та другим 2 входами відповідно до першого 3 (дійсна a частина комплексного числа) і другого 4 (уявна b частина комплексного числа) регістрів надходить значення  комплексного числа A  a  bi . На перші та другі входи суматора 7 відповідно надходять значення a і b   (див. співвідношення (4) та (6)). З виходу суматора 7 значення Z (див. 3 UA 119904 U співвідношення (6)) надходить до перших входів суматорів 14, до других входів яких за шинами 15 надходять відповідні значення 0  N ,1 N ,2  N , . Суматори 14 виконують операцію 5 Z  l  N , результати якої надходять до перших входів СП 16, до других входів яких за шиною 17 надходить значення N  p 2  q 2 . В цьому випадку з виходу однієї СП 16 значення лишку h  Z (modN ) через елементи АБО 18 і 19 надходить до виходу 20 пристрою. Розглянемо процес функціонування корисної моделі для двох режимів роботи пристрою при конкретних значеннях модулів СЗК. Перший режим. Нехай A  20 і mi  3 . У таблиці 1 представлено спрощений алгоритм визначення дійсного лишку 10   A(mod mi ) дійсного числа A  20 за дійсним модулем mi  3 . За третім 8 входом пристрою дійсне число A  20 надходить до перших входів суматорів першої 9 групи, до других входів яких надходять відповідні значення 0  3,1  3,, k  3 констант 20  k  3 (k  0,1,2,) , результат якої надходить до перших входів СП 11, до других входів за шиною 12 надходить значення модуля mi  3 . З виходу однієї СП 11, для якої виконується умова,   20  k  3i  3i , ( A  6  mi  20  18  2) , лишок 2  20(mod3) (табл. 1) через елементи АБО 13 і 19 надходить до виходу 20 пристрою. 10. Суматори 9 виконують операцію 15 Таблиця 1 Перший режим при Значення констант k  mi шин 10 0 3 6 9 12 15 18 A  20 , mi  3 Виходи перших суматорів 9 Результати порівняння СП 11 20-0=20 20-3=17 20-6=14 20-9=11 20-12=8 20-15=5 20-18=2 20>3 17>3 14>3 11>3 8>3 5>3 25 6>5 1