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

Реферат: Винахід належить до області обчислювальної техніки і призначений для модульного множення двох чисел, як в додатному, так і у від'ємному числових діапазонах, які представлені у непозиційній системі числення залишкових класів. Пристрій для реалізації операції модульного UA 108828 C2 (12) UA 108828 C2 множення двох чисел, які представлені у системі залишкових класів містить перший та другий вхідні прийомні регістри, вихідний прийомний регістр, регістр результату операції, суматор за модулем два, першу групу елементів АБО, групу з n пристроїв для множення двох лишків ai' та bi' чисел A 'СЗК та B'СЗК за відповідними модулями, першу групу елементів І, групу вентилів, n перший суматор за модулем M   mi , в який додатково введені перший та другий вхідні i1 регістри, вихідний регістр, другу, третю, четверту та п'яту групи елементів І, другу та третю групи елементів АБО, другий, третій, четвертий, п'ятий та шостий суматори за модулем n M   mi . i1 Технічним результатом, що досягається даним винаходом є розширення функціональних можливостей пристрою множення за рахунок виконання додаткових операції перетворення чисел представлених безпосередньо у СЗК, у числа представлені у штучній формі СЗК. UA 108828 C2 5 10 15 20 25 Винахід (пристрій) належить до області обчислювальної техніки і призначено для модульного множення двох чисел, як в додатному, так і у від'ємному числових діапазонах, які представлені у непозиційній системі числення залишкових класів (СЗК). Відомий пристрій (аналог) для множення по довільному модулю m i КЛ (А.с. СРСР № 922731, кл. МПК G06F 7/39, Б В. № 15, 1982 р.), що містить вхідні регістри, дешифратори, групи елементів АБО, групи елементів І, суматор по модулю два, елементи І та АБО, комутатор та вихідний регістр. Недоліком відомого пристрою є низькі функціональні можливості, які полягають в тому, що у даному пристрою неможливо реалізувати операцію перетворення чисел і BСЗК  b1,b2 ,..., bi ,..., bn  , представлених у СЗК, у числа A СЗК  a1, a2 ,..., ai ,..., an          ' ' ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК  b1,b'2 ,..., bi' ,..., bn , що представлені у штучній формі (ШФ) СЗК та навпаки. Відомий пристрій (аналог) для множення по довільному модулю m i КЛ є пристрій для множення по довільному модулю (Пат. № 60078, Україна, МПК (2011.01) G 06 F 7/00. Опубл. 10.06.2011., Б В. № 11). Він містить вхідні регістри, дешифратори, групи елементів АБО, групи елементів І, суматор по модулю два, елементи І та АБО, комутатор та вихідний регістр. Недоліком відомого пристрою є низькі функціональні можливості, які полягають в тому, що у даному пристрою неможливо реалізувати операцію перетворення чисел A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  , представлених у СЗК, у числа ' ' ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК  b1,b'2 ,..., bi' ,..., bn , що представлені у ШФ СЗК і навпаки. Відомий пристрій (аналог) - табличний пристрій для множення двох чисел у КЛ (Пат. № 70442 Україна, МПК G06F 7/52. Б В № 11 від 11.06.2012 р. (2006.01)). Табличний пристрій для множення двох чисел у класі лишків, якій містить перший та другий входи пристрою, перший та другий вхідні регістри, суматор за модулем два, групу елементів АБО, вихідний регістр, вихід пристрою, при цьому перший та другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, а вихід вихідного регістру є виходом пристрою. Недоліком аналогу є низькі функціональні можливості, які полягають в тому, що у даному пристрою неможливо реалізувати операцію перетворення чисел A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  , 30 35   представлених у СЗК, у числа  ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn  і ' ' B'СЗК  b1,b'2 ,..., bi' ,..., bn , що представлені у ШФ СЗК і навпаки. Найбільш близьким аналогом (прототипом) за технічною суттю і результатом, що досягається, є пристрій для реалізації операції множення двох чисел у класі лишків (Деклараційний патент на корисну модель № 91321 Україна, МПК G06F 7/52. БВ № 12 від 25.06.2014 р. (2006.01)). Пристрій містить перший та другий входи пристрою, перший та другий вхідні регістри, суматор за модулем два, групу елементів АБО, вихідний регістр, вихід пристрою, групу n пристроїв для множення двох лишків ai' та bi' чисел A ' та B ' за модулями m i ( i  1, n ; n - кількість модулів КЛ), прийомний регістр, групу елементів І, групу вентилів, суматор за n модулем M   mi . При цьому перший та другий входи пристрою підключено до входів i1 відповідно першого та другого вхідних регістрів, а вихід вихідного регістру є виходом пристрою. 40 45 50   Виходи i  x i  1, n підрегістрів першого та другого вхідних регістрів підключено до входів i-го пристрою для множення лишків ai та bi відповідно чисел А та В за модулем m i КЛ, виходи групи пристроїв множення лишків ai та bi за модулями m i підключено до входів відповідних i-х під регістрів прийомного регістру, вихід якого підключено до перших входів елементів І та вентильних елементів груп. Виходи елементів І групи підключено до перших входів суматора за n M модулем M   mi , до других входів якого підключена шина подачі значення , виходи 2 i1 суматора за модулем М і вентильних елементів групи через елементи АБО групи підключено до входу вихідного регістру, виходи перших (за модулем m1 КЛ) підрегістрів вхідних регістрів підключено до входів суматора за модулем два, вихід якого підключено до других входів елементів І групи та до других (заборонених) входів вентильних елементів групи. Недоліком прототипу є низькі функціональні можливості, які полягають в тому, що у даному пристрою неможливо реалізувати операцію перетворення чисел A СЗК  a1, a2 ,..., ai ,..., an  і 1 UA 108828 C2 BСЗК  b1,b2 ,..., bi ,..., bn  ,   представлених у СЗК, у числа  ' ' A '  а1, а'2 ,..., ai' ,..., аn  і ' ' B'  b1,b'2 ,..., bi' ,..., bn , що представлені у ШФ СЗК і навпаки. Дана обставина не дозволяє, коли є необхідність, безпосередньо контролювати та коректувати дані, що представлено у вигляді ' ' ' ' чисел і а також результат A 'СЗК  а1, а'2 ,..., ai' ,..., аn B'СЗК  b1,b'2 ,..., bi' ,..., bn , 5 C'СЗК A 'СЗК     ' ' c1, c '2 ,..., c i' ,..., c n ' ' а1, а'2 ,..., ai' ,..., аn  і   операції  модульного  множення  цих двох чисел ' ' B'СЗК  b1,b'2 ,..., bi' ,..., bn . В основу винаходу поставлено задачу розширення функціональних можливостей пристроюпрототипу за рахунок виконання додаткової операції перетворення чисел A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  , представлених безпосередньо у СЗК, у 10    15   ' ' ' ' числа A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК  b1,b'2 ,..., bi' ,..., bn , що представлені у ШФ СЗК і навпаки. Це дає можливість, при необхідності, безпосередньо контролювати та коректувати дані, що представлено у вигляді чисел A СЗК  a1, a2 ,..., ai ,..., an  , BСЗК  b1,b2 ,..., bi ,..., bn  ,      ' ' ' ' ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn , B'СЗК  b1,b'2 ,..., bi' ,..., bn і C'СЗК  c1, c '2 ,..., c i' ,..., c n . Поставлена задача вирішується тим, що пристрій для реалізації операції модульного множення двох чисел, які представлені у системі залишкових класів, містить перший та другий вхідні прийомні регістри, вихідний прийомний регістр, регістр результату операції, суматор за модулем два, першу групу елементів АБО, групу з n пристроїв для множення c i'  ai'  bi' mod mi   двох лишків ai' та bi' чисел A 'СЗК та B'СЗК за модулями m i ( i  1, n ; n - кількість модулів СЗК), n першу групу елементів І, першу групу вентилів, перший суматор за модулем M   mi . При 20  i1  цьому виходи і-х i  1, n підрегістрів першого та другого вхідних прийомних регістрів підключено до входів і-го пристрою для множення лишків ai' та bi' , відповідно чисел A 'СЗК та B'СЗК , за модулем m i СЗК, виходи групи пристроїв множення лишків ai' та bi' за модулями m i підключено до входів відповідних і-х підрегістрів вихідного прийомного регістру, вихід якого підключено до перших входів елементів І першої групи та вентильних елементів першої групи, виходи 25 n елементів І першої групи підключено до перших входів суматора за модулем M   mi , до i1 M других входів якого підключена шина подачі значення . Виходи суматора за модулем 2 n M   mi і вентильних елементів першої групи через елементи АБО першої групи підключено i1 30 до входу регістру результату операції, виходи перших (за модулем m1 КЛ) підрегістрів вхідних прийомних регістрів підключено до входів суматора за модулем два, вихід якого підключено до других входів елементів І першої групи та до других (заборонених) входів вентильних елементів першої групи. При цьому пристрій додатково містить перший та другий вхідні регістри, вихідний регістр, другу, третю, четверту та п'яту групи елементів І, другу та третю групи елементів АБО, n другий, третій, четвертий, п'ятий та шостий суматори за модулем M   mi . Перший вхід i1 35 пристрою підключено до входу першого вхідного регістру, вихід якого підключено до перших входів елементів І другої та третьої груп, виходи яких підключено до перших входів відповідно n другого та третього суматорів за модулем M   mi , виходи яких через елементи АБО другої i1 групи підключено до входу першого вхідного прийомного регістру, другий вхід пристрою підключено до входу другого вхідного регістру, вихід якого підключено до перших входів елементів І четвертої та п'ятої груп, виходи яких підключено до перших входів відповідно n 40 четвертого та п'ятого суматорів за модулем M   mi , виходи яких через елементи АБО третьої i1 групи підключено до входу другого вхідного прийомного регістру. Вихід регістру результату 2 UA 108828 C2 n операції підключено до перших входів шостого суматора за модулем M   mi , вихід якого i1 5 підключено до входу вихідного регістру, вихід якого є виходом пристрою, перша шина подачі сигналу ознаки "ДОДАВАННЯ 1" підключена до других входів елементів І другої групи, а друга шина подачі сигналу ознаки "ДОДАВАННЯ 2" підключена до других входів елементів І четвертої групи, перша шина подачі сигналу ознаки "ВІДНІМАННЯ 1" підключена до других входів елементів І третьої групи, а друга шина подачі сигналу ознаки "ВІДНІМАННЯ 2" підключена до других входів елементів І п'ятої групи, шина подачі значення M підключена до других входів 2 n другого, третього, четвертого, п’ятого та шостого суматорів за модулем M   mi . i1 10 Введення вказаних ознак дозволяє розширити функціональні можливості пристроюпрототипу за рахунок виконання додаткової операції перетворення чисел і BСЗК  b1,b2 ,..., bi ,..., bn  , представлених безпосередньо у СЗК, у A СЗК  a1, a2 ,..., ai ,..., an      ' ' ' ' числа A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК  b1,b'2 ,..., bi' ,..., bn , що представлені у ШФ СЗК. Це дає можливість, при необхідності, безпосередньо контролювати та коректувати дані, що ' ' ' ' представлено у вигляді чисел A 'СЗК  а1, а'2 ,..., ai' ,..., аn і і B'СЗК  b1,b'2 ,..., bi' ,..., bn 20     15 ' ' c1, c '2 ,..., c i' ,..., c n C'СЗК     .  У запропонованому пристрою процес виконання операції множення у СЗК, як у додатному, так і у від'ємному числових діапазонах, здійснюється над вхідними числами A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  , що представлені у ШФ, тобто у вигляді   ' ' ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК  b1,b'2 ,..., bi' ,..., bn . Штучна форма чисел АСЗК та ВСЗК, що представлені у СЗК, визначається наступним чином M  ' B'   A СЗК  B СЗК , если A СЗК B СЗК   0, A  СЗК СЗК 2 (1)  M ' ' A  СЗК B СЗК  2  A СЗК  B СЗК , если A СЗК B СЗК   0,  M M тобто, для додатних чисел A 'СЗК   A СЗК , а для від’ємних - A 'СЗК   A СЗК , де 2 2     n M   mi . i1 25 У цьому випадку, для m1  2 , алгоритм виконання операції множення у СЗК як у додатному, так і у від'ємному числових діапазонах, представлено у вигляді  A 'СЗК  B'СЗК , якщо A 'СЗК і B'СЗК однакової парності,  (2) A СЗК  BСЗК   ƒ  ' М ' ' '  A СЗК  ВСЗК  , якщо A СЗК і ВСЗК різної парності.  2 На малюнку (фіг. 1) представлена блок-схема пристрою для реалізації операції модульного множення двох чисел, які представлені у системі залишкових класів. На малюнку (фіг. 2) представлена блок-схема пристрою для реалізації операції модульного множення двох чисел, які представлені у системі залишкових класів, що задана основами m1  2 , m2  3 , m3  5 . В таблиці 1 представлено кодові слова для СЗК, що задана основами m1  2 , m2  3 , m3  5 . На фіг. 1 представлена блок-схема пристрою для реалізації операції модульного множення двох чисел, які представлені у системі залишкових класів, де: 1, 2 - перший та другий входи пристрою; 3, 4 - перший та другий вхідні регістри; 5, 6 - перший та другий вхідні прийомні регістри; 71-7n група пристроїв множення c i'  ai'  bi' mod mi лишків ai' та bi' за модулями m i ' 30 35    A 'СЗК ,B'СЗК    i  1, n ; 8 - вихідний прийомний регістр; 9 - перша група елементів І; 10 - група вентильних n елементів; 11 - перший суматор за модулем M   mi , 12 - перша група елементів АБО; 13 i1 40 регістр результату операції; 14 - суматор за модулем два; 15, 16 - друга та третя групи 3 UA 108828 C2 n елементів І; 17, 18 - другий та третій суматори за модулем M   mi ; 19 - друга група елементів i1 АБО; 20, 21 - четверта та п'ята групи елементів І; 22, 23 - четвертий та п'ятий суматори за n n i1 i1 модулем M   mi ; 24 - третя група елементів АБО; 25 - шостий суматор за модулем M   mi ; 26 - вихідний регістр; 5 Таблиця 1 Кодові слова у СЗК   А (В) у ПСЧ A ' B' у ПСЧ -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29  m1 = 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  A 'СЗК B 'СЗК у СЗК m2 = 3 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 m3 = 5 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 В таблиці 2 представлено алгоритм функціонування суматора за модулем два Таблиця 2 Алгоритм функціонування суматора 14 Входи суматора 14 Виходи суматора 14 ' a1 ' b1 0 0 1 1 0 1 0 1 4 a ' 1  '  b1 mod 2 0 1 1 0 UA 108828 C2 27 - вихід регістра; 281, 282 - шини подачі сигналу ознаки відповідно "ДОДАВАННЯ 1" та "ДОДАВАННЯ 2"; 291, 292 - шини подачі сигналу ознаки відповідно "ВІДНІМАННЯ 1" та "ВІДНІМАННЯ 2"; 30 - шина подачі значення M . 2 Перший 1 та другий 2 входи пристрою підключено до входів відповідно першого 3 та другого 5   4 вхідних регістрів. Виходи і-х i  1, n підрегістрів першого 5 та другого 6 вхідних прийомних регістрів підключено до входів і-го пристрою 71-7n для множення лишків ai' та bi' . Виходи групи 10 71-7n пристроїв множення лишків ai' та bi' за модулями m i підключено до входів відповідних і-х підрегістрів вихідного прийомного регістру 8, вихід якого підключено до перших входів елементів І першої 9 групи та до перших (інформаційних) входів вентильних елементів групи 10. Виходи елементів І першої 9 групи підключено до перших входів першого 11 суматора за n n i1 i1 модулем M   mi , а виходи першого 11 суматора за модулем M   mi 15 і вентильних елементів групи 10 через елементи АБО першої 12 групи підключено до входу регістру 13 результату операції. Виходи перших (за модулем m1 СЗК) підрегістрів вхідних прийомних регістрів 5 і 6 підключено до входів суматора 14 за модулем два, вихід якого підключено до других входів елементів І першої 9 групи та до других (заборонених) входів вентильних елементів групи 10. Вихід першого 3 вхідного регістру підключено до перших входів елементів І другої 15 та третьої 16 груп, виходи яких підключено до перших входів відповідно другого 17 та n третього 18 суматорів за модулем M   mi , виходи яких, через елементи АБО другої 19 групи i1 20 підключено до входу першого 5 вхідного прийомного регістру. Вихід другого 4 вхідного регістру підключено до перших входів елементів І четвертої 20 та п'ятої 21 груп, виходи яких підключено n до перших входів відповідно четвертого 22 та п'ятого 23 суматорів за модулем M   mi , i1 виходи яких через елементи АБО третьої 24 групи підключено до входу другого 6 вхідного прийомного регістру. Вихід регістру 13 результату операції підключено до перших входів n шостого 25 суматора за модулем M   mi , вихід якого підключено до входу вихідного 26 i1 25 30 регістру, вихід 27 якого є виходом пристрою. Перша 281 шина подачі сигналу ознаки "ДОДАВАННЯ 1" підключена до других входів елементів І другої 15 групи, а друга 28 2 шина подачі сигналу ознаки "ДОДАВАННЯ 2" підключена до других входів елементів І четвертої 20 групи. Перша 291 шина подачі сигналу ознаки "ВІДНІМАННЯ 1" підключена до других входів елементів І третьої 16 групи, а друга 292 шина подачі сигналу ознаки "ВІДНІМАННЯ 2" M підключена до других входів елементів І, а п'ятої 21 групи. Шина 30 подачі значення 2 підключена до других входів першого 11, другого 17, третього 18, четвертого 22, п'ятого 23 та n шостого 25 суматорів за модулем M   mi . i1 35 Пристрій функціонує наступним чином (фіг. 1). За першим 1 та другим 2 входами пристрою до першого 3 та другого 4 вхідних регістрів поступають значення чисел A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  у КЛ. У відповідності зі співвідношенням (1) маємо, що коли A СЗК BСЗК   0 , тоді відкриті елементи І груп 15 і 20 (присутній сигнал шин 28 1 і     M  A СЗК  B СЗК  (присутній сигнал шини 2 30). Якщо A СЗК BСЗК   0 тоді відкриті елементи І груп 16 і 21 (присутній сигнал шин 29 1 і 292). 282). На виході суматорів 17 і 22 маємо A 'СЗК B 'СЗК  M  A СЗК  B СЗК  (присутній сигнал шини 2 30). В цьому випадку до регістрів 5 і 6, через відповідні групи 19 і 24, поступає значення ' ' ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК  b1,b'2 ,..., bi' ,..., bn . З виходу регістрів 5 і 6 пара лишків ai' та bi' На виході суматорів 18 і 21 маємо, що A 'СЗК B 'СЗК  40       ' ' поступає до входів відповідного i-го пристрою 7i для множення c '  a1  b1 mod mi , лишків ai та bi , відповідно чисел A 'СЗК   ' ' а1, а'2 ,..., ai' ,..., аn і B'СЗК 5   ' ' b1,b'2 ,..., bi' ,..., bn  , за модулем m i КЛ. З UA 108828 C2   входу і-го підрегістру прийомного регістру 8, з виходу якого значення C'СЗК ' ' виходу пристрою 7i для множення лишків ai' та bi' значення c '  a1  b1 mod mi , поступає до  5      A 'СЗК  B'СЗК , тобто ' ' ' ' ' ' C'СЗК  c1, c '2 ,..., c i' ,..., c n  а1, а'2 ,..., ai' ,..., аn  b1,b'2 ,..., bi' ,..., bn , поступає до перших входів елементів І 9 та вентильних елементів 10 груп, до других входів яких, з виходу суматора 14 за ' ' ' ' модулем два, поступає значення a1  b1 mod 2 (табл. 2). Якщо a1  b1 mod 2  1 (присутній вихідний сигнал суматора 14), тоді через відкриті елементи І 9 першої групи значення       n ' ' C'СЗК  c1, c '2 ,..., c i' ,..., c n поступає до перших входів першого суматора 11 за модулем M   mi , 10 i1 на другі входи якого за шиною 30 поступає значення M . З виходу суматору 11 значення 2 M  ' CРСЗК   C'СЗК   mod M через елементи АБО першої групи 12 поступає до входу регістру 13 2  ' ' результату операції. Якщо a1  b1 mod 2  0 (відсутній вихідний сигнал суматора 14), тоді через відкриті вентильні елементи групи 10 (відсутній сигнал заборони) значення ' ' ' ' ' CСЗК  c1, c 2 ,..., c i ,..., c n через елементи АБО першої групи 12 поступає до входу регістру 13 результату операції (див. співвідношення (2)). З виходу регістру 13 результату операції поступає     n до перших входів шостого 25 суматора за модулем M   mi , до других входів якого за шиною i1 15 20 n M 30 поступає значення . З виходу шостого 25 суматора за модулем M   mi , до входу 2 i1 ' вихідного регістру 26 поступає М результат CРСЗК   CРСЗК  M  mod M операції множення двох   2  чисел A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  у СЗК. Розглянемо процес функціонування запропонованого винаходу для СЗК, що задана M основами m1  2 , m2  3 , m3  5 (див. фіг. 2, табл. 1, 2). При цьому: М = 30;  15 ; у даній 2 M СЗК значення  15 дорівнює 1 0 0  . 2 Приклад 1. Треба провести операцію модульного множення двох чисел А ПСЧ  3 , ВПСЧ  4 , що задано у СЗК у наступному вигляді A СЗК  1 0 3  і В СЗК  0 1 4  . В цьому випадку присутні сигнали шин 281 і 282. За входами 1 і 2 пристрою в регістри 3 і 4 відповідно поступають числа A СЗК  1 0 3  і В СЗК  0 1 4  . Значення A СЗК  1 0 3  через відкриті елементи І другої 15 25 n групи поступає до перших входів другого 17 суматора за модулем M   mi , до других входів i1 якого за шиною 30 поступає значення M . З виходу суматора 17, через елементи АБО другої 19 2 M  A СЗК  1 0 0   1 0 3   0 0 3  поступає до входу регістру 5. 2  0 1 4  через відкриті елементи І четвертої 20 групи поступає до перших групи, значення A 'СЗК  Значення В СЗК n входів четвертого 22 суматора за модулем M   mi , до других входів якого за шиною 30 i1 30 M поступає значення . З виходу суматора 22, через елементи АБО третьої 24 групи, значення 2 M В 'СЗК   В СЗК  1 0 0   0 1 4   1 1 4  поступає до входу регістру 6. Значення підрегістрів 2 регістрів 5 і 6 поступають на відповідні пристрої 71÷73 для множення двох лишків ai' та bi' . На виходах групи 71÷73 пристроїв множення отримуємо наступні значення: 71  0  1mod 2  0 ; 72  0  1mod 3  0 і 73  3  4 mod 5  2 . Таким чином до входу регістру 8 поступає значення 6 UA 108828 C2 C'СЗК  0 0 2  A 'СЗК  0 0 3  результату множення двох чисел   і B 'СЗК  1 1 4  , що ' ' представлено у ШФ СЗК. Так як a1  b1 mod 2  0  1mod 2  1 (табл. 2), тоді вихідний сигнал суматора 14 відкриває елементи І групи 9 (вентильні елементи групи 10 закриті). У цьому випадку з регістру 8 значення C'СЗК  0 0 2  через відкриті елементи І першої групи 9 поступає 5 n до перших входів першого суматора 11 за модулем M   mi , до других входів якого за шиною i1 30 поступає значення M  1 0 0  . З виходу суматора 11 результат множення двох чисел 2 ' і представлений у вигляді A СЗК  0 0 3  B 'СЗК  1 1 4  , 10 M  ' CРСЗК   C'СЗК    0 0 2  1 0 0   1 0 2 , через елементи АБО першої 12 групи поступає 2  до входу регістра 13, з виходу якого він поступає до перших входів шостого 25 суматора за n модулем M   mi , до других входів якого за шиною 30 поступає значення M . З виходу 2 i1 ' суматора 25 результат CРСЗК   CРСЗК  M   1 0 2  1 0 0   0 0 2 модульного множення   2  двох чисел у СЗК A СЗК  1 0 3  і ВСЗК  0 1 4  поступає до входу вихідного 26 регістру. У ПСЧ значення 0 0 2  дорівнює 12. Перевірка. Зробимо перевірку правильності отриманого результату 15 ' CРСЗК  1 0 2  ' множення двох чисел A 'СЗК  0 0 3  (у ПСЧ A ПСЧ  18 і A ПСЧ  3 ) та B 'СЗК  1 1 4  (у ПСЧ ' BПСЧ  19 і BПСЧ  4 ) у ШФ СЗК. Результат CРСЗК  0 0 2  множення у СЗК двох чисел 20 A СЗК  1 0 3  і BСЗК  0 1 4  у ПСЧ дорівнює значенню 12. У відповідності з ознакою ШФ чисел у КЛ для перевірки отриманого результату маємо наступну умову, що представлена рівнянням: ' AПСЧ  BПСЧ '   M  AПСЧ  BПСЧ  mod M  CРСЗК або 2    ' A ПСЧ  BПСЧ '  15  A ПСЧ  BПСЧ mod 30  CРСЗК . ' Таким чином маємо 3  4 '  15  3  4   27  CРСЗК . Значення добутку чисел A ПСЧ  3 і BПСЧ  4 дорівнює 12, що відповідає значенню 27 у ШФ СЗК (див. табл. 1). Приклад 2. Треба провести операцію модульного множення двох чисел AПСЧ  3 , 25 BПСЧ  4 , (у СЗК A СЗК  1 0 3  і ВСЗК  0 1 4  ). В цьому випадку присутні сигнали шин 291 і 292. За входами 1 і 2 пристрою в регістри 3 і 4 відповідно поступають числа A СЗК  1 0 3  ) і ВСЗК  0 1 4  . Значення A СЗК  1 0 3  через відкриті елементи І третьої 16 групи поступає до n перших входів третього 18 суматора за модулем M   mi , до других входів якого за шиною 30 i1 30 M поступає значення . З виходу суматора 18, через елементи АБО другої 19 групи, значення 2 M A 'СЗК   A СЗК  1 0 0   1 0 3   0 0 2  поступає до входу регістру 5. Значення 2 ВСЗК  0 1 4  через відкриті елементи І п'ятої 21 групи поступає до перших входів п'ятого 23 n M .З 2 значення суматора за модулем M   mi , до других входів якого за шиною 30 поступає значення виходу 35 п'ятого 23 i1 суматора, через елементи АБО третьої 24 групи, M B 'СЗК   B СЗК  1 0 0   0 1 4   1 2 1 поступає до входу регістру 6. Значення підрегістрів 2 регістрів 5 і 6 поступають на відповідні пристрої 71÷73 для множення двох лишків ai' та bi' . З 7 UA 108828 C2 виходів групи 71÷73 пристроїв множення отримуємо наступні значення: 71  0  1mod 2  0 ; 72  0  2mod 3  0 і 73  2  1mod 5  2 . Таким чином до входу регістру 8 поступає значення C 'СЗК  0 0 2  . Так, як 5 a ' 1  '  b1 mod 2  0  1mod 2  1 , тоді вихідний сигнал суматора 14 присутній. Він відкриває елементи І першої 9 групи, через які значення C 'СЗК  0 0 2  поступає до перших входів суматора 11, до других входів якого за шиною 30 поступає значення M M  '  1 0 0  . З виходу суматора 11 значення CРСЗК   C'СЗК    0 0 2  1 0 0   1 0 2 2 2  через елементи АБО першої 12 групи поступає до входу регістра 13, з виходу якого він поступає n до перших входів шостого 25 суматора за модулем M   mi , до других входів якого за шиною i1 30 10 15 поступає M . 2 значення З виходу суматора 25 результат M  ' CРСЗК   CРСЗК    1 0 2  1 0 0   0 0 2 модульного множення двох чисел у СЗК 2  ' поступає до входу вихідного 26 регістру. (Результат значення CРСЗК  1 0 2  у ПСЧ дорівнює 27). ' Перевірка.  3    4 '  15   3    4   15  12  27  CРСЗК . Значення добутку чисел AПСЧ  3 і BПСЧ  4 дорівнює 12, що відповідає значенню 27 у ШФ СЗК (див. табл. 1). Приклад 3. Треба провести операцію модульного множення двох чисел A ПСЧ  3 , BПСЧ  4 (у СЗК A СЗК  1 0 3  і BСЗК  0 1 4  ). В цьому випадку присутні сигнали шин 281 і 292. За входами 1 і 2 пристрою в регістри 3 і 4 відповідно поступають числа A СЗК  1 0 3  і BСЗК  0 1 4  . Значення A СЗК  1 0 3  через відкриті елементи І другої 15 групи поступає до n перших входів другого 17 суматора за модулем M   mi , до других входів якого за шиною 30 i1 20 M поступає значення . З виходу суматора 17, через елементи АБО другої 19 групи, значення 2 M A 'СЗК   A СЗК  1 0 0   1 0 3   0 0 3  поступає до входу регістру 5. Значення 2 BСЗК  0 1 4  через відкриті елементи І п'ятої 21 групи поступає до перших входів п'ятого 23 n M .З 2 значення суматора за модулем M   mi , до других входів якого за шиною 30 поступає значення виходу 25 п'ятого i1 суматора 23, через елементи АБО третьої 24 групи, M  B СЗК  1 0 0   0 1 4   1 2 1 поступає до входу регістру 6. Значення підрегістрів 2 регістрів 5 і 6 поступають на відповідні пристрої 7 1÷73 для множення двох лишків ai' та bi' . З виходів групи 71÷73 пристроїв множення отримуємо наступні значення: 71  0  1mod 2  0 ; B 'СЗК  72  0  2mod 3  0 і 73  3  1mod 5  2 . Таким чином до входу регістру 8 поступає значення C'СЗК  0 0 3  . Так, як 30 a ' 1  '  b1 mod 2  0  1mod 2  1 , тоді вихідний сигнал суматора 14 присутній. Він відкриває елементи І першої 9 групи, через які значення C'СЗК  0 0 3  поступає до перших входів першого суматора 11, до других входів якого за шиною 30 поступає значення M M  '  1 0 0  . З виходу суматора 11 значення CРСЗК   C'СЗК    0 0 3   1 0 0   1 0 3  2 2  через елементи АБО першої 12 групи поступає до входу регістра 13, з виходу якого воно n поступає до перших входів шостого 25 суматора за модулем M   mi , до других входів якого i1 35 за шиною 30 поступає значення M . 2 8 З виходу суматора 25 результат UA 108828 C2 M  ' CРСЗК   CРСЗК    1 0 3   1 0 0   0 0 3  операції модульного множення двох чисел у 2  ' СЗК поступає до входу вихідного 26 регістру (значення CРСЗК  1 0 3  у ПСЧ дорівнює 3). 5 ' Перевірка. 3   4 '  15  3   4   15  12  3  CРСЗК . Значення добутку чисел A ПСЧ  3 і BПСЧ  4 дорівнює -12, що відповідає значенню 3 у ПІФ СЗК (див. табл. 1). Приклад 4. Треба провести операцію модульного множення двох чисел AПСЧ  3 , BПСЧ  4 (у СЗК A СЗК  1 0 3  і BСЗК  0 1 4  ). В цьому випадку присутні сигнали шин 291 і 282. За входами 1 і 2 пристрою в регістри 3 і 4 відповідно поступають числа A СЗК  1 0 3  і BСЗК  0 1 4  . Значення A СЗК  1 0 3  через відкриті елементи І третьої 16 групи поступає до n перших входів третього 18 суматора за модулем M   mi , до других входів якого за шиною 30 i1 10 M поступає значення . З виходу суматора 18, через елементи АБО другої 19 групи, значення 2 M ' поступає до входу регістру 5. Значення A КЛ   A КЛ  1 0 0   1 0 3   0 0 2  2 BСЗК  0 1 4  через відкриті елементи І четвертої 20 групи поступає до перших входів n четвертого 22 суматора за модулем M   mi , до других входів якого за шиною 30 поступає i1 15 M значення . З виходу суматора 22, через елементи АБО третьої 24 групи, значення 2 M B 'СЗК   B СЗК  1 0 0   0 1 4   1 1 4  поступає до входу регістру 6. Значення підрегістрів 2 регістрів 5 і 6 поступають на відповідні пристрої 7 1÷73 для множення двох лишків ai' та bi' . З пристроїв множення отримуємо наступні значення: 71  0  1mod 2  0 ; і 73  2  4 mod 5  2 . Таким чином до входу регістру 8 поступає значення 72  0  1mod 3  0 виходів групи 71÷73 C 'СЗК  0 0 3  . Так, як 20 25 ' 1  '  b1 mod 2  0  1mod 2  1 , тоді вихідний сигнал суматора 14 присутній. Він відкриває елементи І першої 9 групи, через які значення C 'СЗК  0 0 3  поступає до перших входів суматора 11, до других входів якого за шиною 30 поступає значення M M  '  1 0 0  . З виходу суматора 11 значення CРСЗК   C'СЗК    0 0 3   1 0 0   1 0 3  2 2  через елементи АБО першої 12 групи поступає до перших входів шостого 25 суматора за n M модулем M   mi , до других входів якого за шиною 30 поступає значення . З виходу 2 i1 ' суматора 25 результат CРСЗК   CРСЗК  M   1 0 3   1 0 0   0 0 3  модульного множення   2  двох чисел у СЗК поступає до входу вихідного 26 регістру.  3   4' '  15   3   4  15  12  3  CРСЗК . Значення добутку чисел AПСЧ  3 і BПСЧ  4 дорівнює -12, що відповідає значенню 3 у ШФ СЗК (див. табл. 1). Таким чином запропонований винахід дозволяє суттєво розширити функціональні можливості пристрою-прототипу за рахунок виконання додаткової операції перетворення чисел A СЗК  a1, a2 ,..., ai ,..., an  і BСЗК  b1,b2 ,..., bi ,..., bn  , представлених безпосередньо у СЗК, у Перевірка. 30 a  ' ' числа A 'СЗК  а1, а'2 ,..., ai' ,..., аn  і навпаки, перетворення результату C'СЗК  ' 1 ' 2 ' i ' n ' ' ' ' ' ' A 'СЗК  а1, а'2 ,..., ai' ,..., аn і B'СЗК 1 2 i n безпосередньо у СЗК CСЗК  c1, c 2 ,..., c i ,..., c n  . Це дає можливість, при необхідності у подальшому, безпосередньо контролювати та коректувати дані, що представлено у вигляді чисел 35     c , c ,..., c ,..., c  операції модульного множення двох  b ,b ,..., b ,..., b  , що представлені у ШФ СЗК, ' ' B'СЗК  b1,b'2 ,..., bi' ,..., bn , що представлені у ШФ СЗК та 9 UA 108828 C2 чисел A СЗК  a1, a2 ,..., ai ,..., an  , BСЗК  b1,b2 ,..., bi ,..., bn  і CСЗК  c1, c 2 ,..., c i ,..., c n  . Наведені приклади застосування представленого винаходу для конкретної СЗК підтверджують достовірність і практичну цінність отриманих результатів. 5 ФОРМУЛА ВИНАХОДУ 10 Пристрій для модульного множення двох чисел, які представлені у системі залишкових класів (СЗК), який містить перший та другий вхідні прийомні регістри, вихідний прийомний регістр, регістр результату операції, суматор за модулем два, першу групу елементів АБО, групу з n ' ' пристроїв для множення c '  a1  b1 mod mi двох лишків ai' та bi' чисел A 'СЗК та B'СЗК за   відповідними модулями m i ( i  1, n ; n - кількість модулів СЗК), першу групу елементів І, групу  n  вентилів, перший суматор за модулем M   mi , при цьому виходи і-х i  1, n підрегістрів i 1 першого та другого вхідних прийомних регістрів підключено до входів і-го пристрою для множення лишків ai' та bi' , відповідно чисел A 'СЗК та B'СЗК , за модулем m i СЗК, виходи групи 15 пристроїв множення лишків ai' та bi' за модулями m i підключено до входів відповідних i-х підрегістрів вихідного прийомного регістру, вихід якого підключено до перших входів елементів І першої групи та до перших (інформаційних) входів вентильних елементів групи, виходи n елементів І першої групи підключено до перших входів першого суматора за модулем M   mi , i 1 M до других входів якого підключена шина подачі значення , виходи першого суматора за 2 n 20 модулем M   mi і вентильних елементів групи через елементи АБО першої групи підключено 25 до входу регістру результату операції, виходи перших (за модулем m1 СЗК) підрегістрів вхідних прийомних регістрів підключено до входів суматора за модулем два, вихід якого підключено до других входів елементів І першої групи та до других входів вентильних елементів групи, який відрізняється тим, що в пристрій додатково введено перший та другий вхідні регістри, вихідний регістр, другу, третю, четверту та п'яту групи елементів І, другу та третю групи елементів АБО, i1 n другий, третій, четвертий, п'ятий та шостий суматори за модулем M   mi , при цьому, перший i1 вхід пристрою підключено до входу першого вхідного регістру, вихід якого підключено до перших входів елементів І другої та третьої груп, виходи яких підключено до перших входів n відповідно другого та третього суматорів за модулем M   mi , виходи яких через елементи i1 30 АБО другої групи підключено до входу першого вхідного прийомного регістру, другий вхід пристрою підключено до входу другого вхідного регістру, вихід якого підключено до перших входів елементів І четвертої та п'ятої груп, виходи яких підключено до перших входів відповідно n четвертого та п'ятого суматорів за модулем M   mi , виходи яких через елементи АБО третьої i1 групи підключено до входу другого вхідного прийомного регістру, вихід регістру результату n 35 операції підключено до перших входів шостого суматора за модулем M   mi , вихід якого i1 40 підключено до входу вихідного регістру, вихід якого є виходом пристрою, перша шина подачі сигналу ознаки "ДОДАВАННЯ 1" підключена до других входів елементів І другої групи, а друга шина подачі сигналу ознаки "ДОДАВАННЯ 2" підключена до других входів елементів І четвертої групи, перша шина подачі сигналу ознаки "ВІДНІМАННЯ 1" підключена до других входів елементів І третьої групи, а друга шина подачі сигналу ознаки "ВІДНІМАННЯ 2" підключена до M других входів елементів І п'ятої групи, шина подачі значення підключена до других входів 2 n другого, третього, четвертого, п'ятого та шостого суматорів за модулем M   mi . i1 10 UA 108828 C2 11 UA 108828 C2 Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 12