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

Реферат: UA 92239 U UA 92239 U 5 10 15 20 25 30 35 40 Корисна модель належить до автоматики та обчислювальної техніки і може бути використана для оброблення даних у схемах цифрової автоматики та цифрових обчислювальних машинах, що працюють в системі залишкових класів (СЗК). Системою залишкових класів (СЗК) називається система обчислення, в якій довільне число представляється у вигляді набору найменших залишків по модулях m1, m2,..., mn , тобто N N  [N(mod m1),N(mod m2 ),..., N(mod mn )] або N  (1, 2,..., n ) . Тут i  N(mod mi ) . При цьому, якщо усі цілі числа N належать діапазону [0,M) , об'єм якого дорівнює M  m1, m2,..., mn , а модулі mi взаємно прості, то кожному набору (1, 2,..., n ) відповідає тільки одне число N з цього діапазону. Переваги і недоліки СЗК детально розглянуті в [2]. Зокрема, показано, що виникають труднощі при реалізації немодульних операцій, які вимагають знання усього числа в цілому. До таких операцій належить, зокрема, порівняння чисел. Нехай N1 і N2 - числа, які порівнюються: N1  (1, 2,..., n ), N2  (1, 2,..., n ). Необхідно визначити результат N1  N2 , чи N1  N2 . За відомим способом порівняння чисел у СЗК [3], записаних, наприклад, на регістрах, на кожному такті порівняння для першого та другого чисел визначається максимальний залишок по всіх модулях та вибирається найменший з них, котрий віднімається з обох чисел. Процес триває доки одне з чисел не перетвориться на нуль. Недоліком цього способу порівняння є невисока швидкодія. Найбільш близькім по технічній суттєвості до корисної моделі є спосіб порівняння чисел, записаних, наприклад, на регістрах, за способом [4]. Нехай m1  m2  ...  mn . Якщо після ~ ~ першого такту, на якому одночасно виконуються операції N1  N1  n та N1  N2  n , отримуємо N1  N2 , то N1  N2 при n  n , та процес порівняння на цьому завершується. Якщо ж N1  N2 , то N1 та N2 , кратні mn та можуть бути кратними одному або декільком із решти модулів системи. Тому на наступних тактах із обох чисел одночасно віднімається деяке число r  (mn  s) . Процес триває доки одне із чисел не перетвориться на нуль. Але недоліком цього способу порівняння є також невисока швидкодія. В основу корисної моделі поставлено задачу: спосіб, функціонуючий у системі залишкових класів, шляхом введення додаткових операцій удосконалити таким чином, щоб забезпечити можливість виконання операції порівняння чисел. Для цього у способі порівняння чисел у системі залишкових класів, записаних, наприклад, на регістрах, що містить віднімання одного числа із іншого та зберігання, наприклад, на регістрах отриманої різниці, який відрізняється тим, що для чисел, що порівнюються, та різниці здійснюється визначення, наприклад, за допомогою спеціальної схеми, їх парності, а про результат порівняння судять по співвідношенню сигналів парностей чисел, що порівнюються, та їх різниці. Роботу способу розглянемо у системі непарних модулів. Будемо відрізняти числа першої та другої половини діапазону M1  R1(перша половина ), 0  N  2 , . N  M1  R2 ( друга половина ), NM 2  Складемо різницю чисел N1 та N2   N1  N2  Mk . Тут 45 0, якщо N1  N2 . k 1, якщо N1  N2 Справедливі наступні чотири твердження: Якщо N1 та N2 однакової парності, то парність  є умовою того, що N1  N2 . Якщо N1 та N2 однакової парності, то непарність  є умовою того, що N1  N2 . Якщо N1 та N2 різної парності, то парність  є умовою того, що N1  N2 . 1 UA 92239 U Якщо N1 та N2 різної парності, то непарність  є умовою того, що N1  N2 . Таким чином, про результат порівняння судять по співвідношенню сигналів парностей чисел, що порівнюються, та їх різниці згідно із таблицею. На цьому робота даного способу закінчується. 5 Таблиця Співвідношення сигналів парностей чисел та їх різниці N1 Результат  N2 Парне N1  N2 Непарне Парне N1  N2 Непарне Парне Парне N1  N2 Непарне Непарне Парне N1  N2 Парне Парне Непарне N1  N2 Парне Непарне Непарне N1  N2 Непарне Парне Непарне N1  N2 Непарне 15 Парне Парне 10 Парне Непарне Непарне N1  N2 Джерела інформації: 1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М: Советское радио, 1968.-440 с. 2. Червяков Н.И., Мезенцева О.С, Лавриненко И.Н. и др. Связность обобщенной позиционной системы счисления и системы остаточных классов и ее применение в модулярных нейрокомпьютерах. Сайт http://www.ncstu.ru/, 2005 3. Ю.Д.Полисский, М.Г.Факторович. Устройство для сравнения чисел в системе остаточных классов. Авт. свид. СССР № 618739 М. Кл G06F7/04, 1978. 4. М.Г.Факторович, Ю.Д.Полисский. Устройство для определения максимального и минимального из "n" чисел, представленных в системе остаточных классов. Авт. свид. СССР № 2 603987 М. Кл G06F7/04, 1978. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 25 Спосіб порівняння чисел у системі залишкових класів, записаних, наприклад, на регістрах, що містить віднімання одного числа із іншого та зберігання, наприклад, на регістрах отриманої різниці, який відрізняється тим, що для чисел, що порівнюються, та різниці здійснюється визначення, наприклад, за допомогою спеціальної схеми, їх парності, а про результат порівняння судять по співвідношенню сигналів парностей чисел, що порівнюються, та їх різниці. Комп’ютерна верстка В. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 2