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

Пристрій для піднесення чисел до квадрата за модулями mi класу лишків (КЛ), що містить вхідний і вихідний регістри, перший дешифратор, першу групу із (m1-1)/2 елементів АБО (m1 - перший модуль КЛ, за яким працює пристрій), перший шифратор, при цьому вхід пристрою підключено до входу вхідного регістра, а вихід вихідного регістра є виходом пристрою, виходи першого дешифратора попарно (сума чисел, що надано кожній із пар виходів дорівнює значенню першого m1 модуля КЛ) підключено до входів відповідних елементів АБО першої групи, виходи яких підключено до відповідних входів першого шифратора, а нульовий вихід першого дешифратора безпосередньо підключено до нульового входу першого шифратора, який відрізняється тим, що введено другий та третій дешифратори, другу групу із m2/2 елементів АБО (m2 - другий модуль КЛ, за яким працює при U 2 (19) 1 3 Вхід пристрою підключено до входу вхідного регістра, вихід якого підключено до входу дешифраторів. Виходи дешифратора попарно, так, що сума чисел, що надана кожній із пар виходів, дорівнює значенню першого m1 модуля КЛ, підключено до входів відповідних елементів АБО групи. Вихід вихідного регістра є виходом пристрою. Виходи елементів АБО групи підключено до відповідних входів шифратора, вихід якого підключено до входу вихідного регістра. Нульовий вихід шифратора підключено до нульового входу шифратора. Недолік прототипу - низькі функціональні можливості. Це обумовлено тим, що операція піднесення чисел до квадрата за модулем mi КЛ реалізується тільки для mi непарного числа. Задача корисної моделі - розширення функціональних можливостей пристрою за рахунок виконання операції піднесення чисел до квадрата за усіма можливими модулями mi КЛ: для m непарного та m парного чисел. Технічний результат, який може бути отриманий при використанні корисної моделі, полягає в одержанні технічного засобу для піднесення чисел до квадрата за довільними модулями mi КЛ. Поставлена задача вирішується тим, що в пристрій, який містить вхідний і вихідний регістри, перший дешифратор, першу групу із (mi-1)/2 елементів АБО (mi - перший модуль КЛ, за яким працює пристрій), перший шифратор, введено другий та третій дешифратори, другу групу із m 2/2 елементів АБО (m2 - другий модуль КЛ, за яким працює пристрій), третю групу із (m3-2)/2 елементів АБО (m3 - третій модуль КЛ, за яким працює пристрій) та четверту групу елементів АБО, другий та третій шифратори, три групи елементів I. При цьому вхід пристрою підключено до входу вхідного регістра, а вихід вихідного регістра є виходом пристрою, виходи першого дешифратора попарно (сума чисел, що надано кожній із пар виходів, дорівнює значенню першого m1 модуля КЛ) підключено до входів відповідних елементів АБО першої групи, виходи яких підключено до відповідних входів першого шифратора, а нульовий вихід першого дешифратора безпосередньо підключено до нульового входу першого шифратора. Вихід вхідного регістра підключено до перших входів елементів I першої, другої та третьої груп, до других входів яких підключено шини подачі сигналів ознак відповідно першого m1, другого m2 та третього m3 модулів КЛ, а виходи елементів I першої, другої та третьої груп підключено до входів відповідно першого, другого та третього дешифраторів. Виходи другого дешифратора попарно (сума чисел, що надано парі виходів, дорівнює значенню другого m2 модуля КЛ, крім однієї пари виходів, значення шин якої є нульова та m2/2-я) підключено до входів відповідних елементів АБО другої групи, виходи яких підключено до відповідних входів другого шифратора. Виходи третього дешифратора попарно (сума чисел, що надано кожній із пар, дорівнює значенню третього m3 модуля КЛ) підключено до входів відповідних елементів АБО третьої групи, виходи яких підключено до відповідних входів третього шифратора, а нульовий та m3/2-й виходи третього дешифратора підключено безпосередньо до від 66645 4 повідних входів третього шифратора. Виходи першого, другого та третього шифраторів через елементи АБО четвертої групи підключені до входу вихідного регістра. При реалізації операції піднесення чисел до квадрата за парним mi модулем КЛ слід окремо розглянути два можливих варіанти: для mі/2 парного та mi/2 непарного чисел. Перший варіант. Для m2=2n парного та m2/2 m2 також парного чисел. В цьому випадку - ціле 2 2 m m  число і тому маємо  2   2  m 2  0modm 2 .  2  4   Для першого варіанта вихідна шина другого деm2 шифратора, що відповідає значенню 2 , одноразово з нульовою шиною, через нульовий елемент АБО підключені до нульового входу другого шифратора. Таким чином, алгоритм функціонування пристрою (корисної моделі), у відповідності до першого варіанта, визначається наступним математичним співвідношенням: 2  m2  (1)   2  =0(mod m2).    Вираз (1) покладено в основу алгоритму для 2 визначення значення A (mod m2). В таблиці 5 представлено приклад алгоритму визначення 2 A (mod m2) для модуля m2=12 (m2/2=6). Другий варіант для m3=2n парного та m3/2 непарного чисел. Для цього варіанта виконується умова: 2 m  m3  (2)    3 modm3 . 2  2  Дійсно, вираз (2) легко представити у вигляді: m3  m3 m      1  0 mod 3  2  (3)    2  2 2    . З теорії чисел відомо, що порівняння А  В (mod mі) двох чисел А и В за модулем mi рівнозначно подільності числа А-В на модуль mi. З виразу m (3) випливає, що число m 3  3  2 є дільник ви2 разу m3 2 m    3  1 .  2    Дійсно, перший співмножник m3 2 добутку (3) m3 m3 ділиться на , а другий 2 -1 співмножник 2 ділиться на два, так як за умовою (другий варіант) m3 значення - непарне число. Таким чином, рів2 няння (3) справедливе. Вираз (2) покладено в основу алгоритму для 2 визначення значення A (mod m3). В таблиці 6 представлено приклад алгоритму визначення зна2 чення А (mod mз) для модуля m3=14 (m3/2=7). 5 66645 На кресленні (фіг. 1) наведена блок-схема запропонованого пристрою, де: 1 - вхід пристрою; 2 вхідний регістр; 3, 4 і 5 - перша, друга і третя групи елементів І; 6, 7 і 8 - шини подачі сигналів ознак відповідно першого m1, другого m2 і третього m3 модулів КЛ; 9, 10 і 11 - перший, другий і третій дешифратори (пристрій для перетворення числа з двійкового коду в унітарний); 12 - перша група двох входових елементів АБО; 13 - перший шифратор (пристрій для перетворення унітарного коду числа в двійковий); 14 - друга група двох входових елементів АБО; 15 - другий шифратор; 16 - третя група двох входових елементів АБО; 17 - третій шифратор; 18 - четверта група елементів АБО; 19 - вихідний регістр; 20 - вихід пристрою. Вхід 1 пристрою підключено до входу вхідного регістра 2, вихід якого підключено до перших входів елементів І першої 3, другої 4 та третьої 5 груп, до других входів яких підключено шини 6, 7 і 8 подачі сигналів ознак відповідно першого m 1, другого m2 та третього m3 модулей КЛ. Виходи елементів І першої 3, другої 4 та третьої 5 груп підключено до входів відповідно першого 9, другого 10 та третього 11 дешифраторів. Виходи першого 9 дешифратора попарно (сума чисел, що надано кожній із пари виходів, дорівнює значенню першого m 1 модуля КЛ) підключено до входів відповідних елементів АБО першої 12 групи, виходи яких підключено до відповідних входів першого 13 шифратора, а нульовій вихід першого 9 дешифратора безпосередньо підключено до нульового входу першого 13 шифратора. Виходи другого 10 дешифратора попарно (сума чисел, що надано кожній із пари виходів, дорівнює значенню другого m2 модуля КЛ, крім однієї пари виходів, значення шин якої є нульова та m2/2-я) підключено до входів відповідних еле 6 ментів АБО другої 14 групи, виходи яких підключено до відповідних входів другого 15 шифратора. Виходи третього 11 дешифратора попарно (сума чисел, що надано кожній із пари виходів, дорівнює значенню першого m1 модуля КЛ) підключено до входів відповідних елементів АБО третьої 16 групи, виходи яких підключено до відповідних входів третього 17 шифратора, а нульовий та m2/2-й виходи третього 11 дешифратора підключено безпосередньо до нульового входу третього 17 шифратора. Виходи першого 13, другого 15 і третього 17 шифраторів через елементи АБО четвертої 18 групи підключені до входу вихідного регістра 19, вихід 20 якого є виходом пристрою. Розглянемо процес функціонування корисної моделі у трьох можливих режимах роботи. Перший режим. При m1 непарне число (прототип). Дивись креслення (фіг. 1, 2) і табл. 1. Присутній сигнал шини 6. Пристрій працює наступним чином. За входом 1 через регістр 2, відкриті елементи І першої 3 групи число А (0  А  m1-1) у двійковому коді надходить на вхід першого дешифратора 9 (фіг. 2). Дешифратор 9 перетворює число А в унітарний код, сигнал якого через відповідний елемент АБО першої 12 групи надходить на відповідний вхід першого 13 шифратора (табл. 1). Номери входів 2 шифратора 13 відповідають значенням: 0, 1, 2 2  m  2 2 (mod m), 3 (mod m), 4 (mod m),...,     (mod m).  2    2 З виходу шифратора 13 результат операції A (mod m1) в двійковому коді через четверту 18 групу елементів АБО, регістр 19 надходить на вихід 20 пристрою. Таблиця 1 Входи шифратора 13 (m1) Виходи шифратора 13 0 1 2 … і 2 A (mod m1) … (m1-1)/2 Таблиця 2 Входи шифратора 15 (m2) Виходи шифратора 15 0 1 2 … і 2 A (mod m2) … (m2-2)/2 Таблиця 3 Входи шифратора 17 (m3) Виходи шифратора 17 0 Другий режим. При m2 парне число (варіант 1). Дивись креслення (фіг. 1, 2) і табл. 2. Присутній сигнал шини 7. Пристрій працює наступним чином. За входом 1 через регістр 2, відкриті елементи І другої 4 групи число А (0  А  m2-1) у двійковому коді надходить на вхід другого дешифратора 10 (фіг. 2). Дешифратор 10 перетворює число А в унітарний код, сигнал якого через відповідний елемент АБО другої 14 групи надходить на відповідний вхід другого 15 шифратора (табл. 2). Номери входів шифрато2 ра 15 відповідають значенням A (mod m2). З вихо2 ду шифратора 15 результат операції А (mоd m2) в 1 2 … і 2 A (mod m3) … (mз)/2 двійковому коді через четверту 18 групу елементів АБО, регістр 19 надходить на вихід 20 пристрою. Третій режим. При m3 парне число (варіант 3). Дивись креслення (фіг. 1, 2) і табл. 3. Присутній сигнал шини 8. Пристрій працює наступним чином. За входом 1 через регістр 2, відкриті елементи І третьої 5 групи число А (0  А  m3-1) у двійковому коді надходить на вхід третього дешифратора 11 (фіг.2). Дешифратор 11 перетворює число А в унітарний код, сигнал якого через відповідний елемент АБО третьої 16 групи надходить на відповідний вхід третього 17 шифратора (табл. 3). Номери входів 7 66645 2 шифратора 13 відповідають значенням A (mod m3). З виходу шифратора 17 результат операції 2 A (mod m3) в двійковому коді через четверту 18 групу елементів АБО, регістр 19 надходить на вихід 20 пристрою. 8 Розглянемо приклади конкретного виконання 2 пристроєм операції А (mоd mі). Перший режим. При m1=11 - непарне число, А=8 (1000) дивись креслення (фіг. 3, 4) і табл. 4. Присутній сигнал шини 6. Таблиця 4 2 Реалізація операції A (mod 11) (прототип, m1) Номер пари вихідних шин дешифратора 9 0 1 2 3 4 5 Значення, що призначають Значення, що признача- Значення, що призначаютьпарі вихідних шин дешиф- ються вхідним шинам ся вихідним шинам шифраратора 9 шифратора 13 тора 13 0 0 0000 1,10 1 0001 2,9 4 0100 3,8 9 1001 4,7 5 0101 5,6 3 0011 Пристрій працює наступним чином. За входом 1 через регістр 2, відкриті елементи І першої 3 групи число А=1000 у двійковому коді надходить на восьмий вхід першого дешифратора 9. Дешифратор 9 перетворює число А в унітарний код А=8, сигнал якого через третій (табл. 4) елемент АБО першої 12 групи надходить на дев'ятий вхід першого 13 шифратора (табл. 4). З виходу шифрато ра 13 результат операції A (mod m1)=1001 у двійковому коді через четверту 18 групу елементів АБО, регістр 19 надходить на вихід 20 пристрою. Перевірка: A (mod m1)=8 (mod 11)=9. Другий режим. При m2 = 12 - парне число (варіант 1), А = 8 (1000). Дивись креслення (фіг. 3, 4) і табл. 5. Присутній сигнал шини 7. Таблиця 5 2 Реалізація операції А (mоd 12) (варіант 1, m2) 2 Значення, що призначають Значения A (mod 12), що Значення, що призначаНомер пари вихідних шин парі вихідних шин дешиф- призначаються вхідним ються вихідним шинам дешифратора 10 ратора 10 шинам шифратора 15 шифратора 15 0 0,6 0 0000 1 1,11 1 0001 2 2,10 4 0100 3 3,9 9 1001 4 4,8 4 0100 5 5,7 1 0001 Пристрій працює наступним чином. За входом 1 через регістр 2, відкриті елементи І другої 4 групи число А=1000 у двійковому коді надходить на восьмий вхід другого дешифратора 10. Дешифратор 10 перетворює число А в унітарний код А=8, сигнал якого через четвертий елемент АБО другої 14 групи надходить на четвертий вхід другого 15 шифратора (табл. 5). З виходу шифратора 15 ре 2 зультат операції А (mоd m2)=0100 в двійковому коді через четверту 18 групу елементів АБО, регістр 19 надходить на вихід 20 пристрою. Перевірка: A (mod m2)=8 (mod 12)=4. Третій режим. При m3=14 парне число (варіант 2), А=8 (1000) Дивись креслення (фіг. 3, 4) і табл. 6. Присутній сигнал шини 8. 9 66645 10 Таблиця 6 2 Реалізація операції A (mod 14) (варіант 2, m3) Номер пари вихідних шин дешифратора 11 0 1 2 3 4 5 6 7 Значення, що приз2 Значення, що признача- Значения A (mod 14), що призначаються вихідним ють парі вихідних шин начаються вхідним шинам шишинам шифратора дешифратора 11 фратора 17 17 0,6 0 0000 1,13 1 0001 2,12 4 0100 3,11 9 1001 4,10 2 0010 5,9 11 1011 6,8 8 1000 7 7 0111 Пристрій працює наступним чином. За входом 1 через регістр 2, відкриті елементи І третьої 5 групи число А=1000 у двійковому коді надходить на вхід третього дешифратора 11. Дешифратор 11 перетворює число А в унітарний код А=8, сигнал якого через шостий елемент АБО третьої 16 групи надходить на восьмий вхід третього 17 шифратора (табл. 6). З виходу шифратора 17 результат 2 операції A (mod m3)=1000 у двійковому коді через четверту 18 групу елементів АБО, регістр 19 надходить на вихід 20 пристрою. 2 2 Перевірка: A (mod m3)=A (mod 14)=8. Таким чином, запропонована корисна модель дозволяє розширити (у порівнянні з прототипом) функціональні можливості корисної моделі за ра 2 хунок виконання операції A (mod mi) піднесення чисел до квадрата за всіма можливими модулями mi КЛ. Це, у свою чергу, дає можливість підвищити коефіцієнт використання обладнання пристрою для піднесення чисел до квадрата за модулями mi класу лишків. Джерела інформації 1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.:Советское радио, 1968. - с. 327-340. 2. А.с. № 922731 СРСР, МПК G06F7/52, 1982, Бюл. № 15. 3. Патент на корисну модель № 51512, Україна, МПК G06F7/74, 2010, Бюл. № 14. 11 66645 12 13 Комп’ютерна верстка Л. Купенко 66645 Підписне 14 Тираж 23 прим. Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601