Пристрій для складання чисел за модулем m модулярної системи числення

Пристрій для складання чисел за модулем m модулярної системи числення (далі пристрій), що містить перший і другий вхідні регістри, вихідний регістр, перший дешифратор, групу з m ключових елементів, групу з m елементів І, чотири елементи І, генератор імпульсів, перемножувач частоти, лічильник, кільцевий регістр зсуву з m розрядів, схему порівняння, перший елемент АБО, причому перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом першого дешифратора, виходи якого є першими входами відповідних ключових елементів групи, виходи яких підключено до перших входів відповідно елементів І групи, виходи яких через перший елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, керуюча шина пристрою підключена до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до входу лічильника, вихід якого підключено до першого входу схеми порівняння, вихід якої підключено до других входів ключових U 2 50024 1 3 вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до першого входу схеми порівняння, вихід якої підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу перемножувача частоти, а виходи розрядів кільцевого регістра зсуву (КРЗ) підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістру. Недолік аналогу - значний час реалізації арифметичних операцій. Найбільш близьким за технічною суттю (прототипом) до запропонованої корисної моделі є деклараційний патент на корисну модель № 35147, де реалізується операція модульного складання A B modm . (Бюл. № 17, 10.09.2008). Пристрій містить перший і другий вхідні регістри, вихідний регістр дешифратор, групу ключових елементів, групу елементів І, елемент АБО, генератор імпульсів, перемножувач частоти, лічильник, кільцевий регістр зсуву, схему порівняння, чотири елементи І, причому, перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, виходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, виходи яких через елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, першу керуючу шину пристрою підключено до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до входу лічильника, вихід якого підключено до других входів ключових елементів групи та до других входів елементів l групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу перемножувача частоти, а виходи розрядів кільцевого регістра зсуву підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістра, вихід другого вхідного регістра підключено до другого входу схеми порівняння, а вихід перемножувача частоти є першими входами третього і четвертого елементів І, виходи яких підключено до відповідно першого і другого входів кільцевого регістра зсуву, а до других входів третього і четвертого елементів І підключено відповідно друга і третя керуючі шини пристрою. Недолік прототипу - значний час реалізації арифметичної операції складання A B modm . В основу запропонованої корисної моделі поставлено задачу зменшення у два рази максимального часу реалізації арифметичної операції складання A B modm у МСЧ. Поставлене завдання вирішується тим, що пристрій складання чисел за модулем m МСЧ містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратор, шифратор, групу з m ключових елементів, групу з m елементів І, чотири елемента І, генератор імпульсів, пере 50024 4 множувач частоти, лічильник, кільцевий регістр зсуву (КРЗ), схему порівняння, перший, другий та третій елементи АБО. Перший інформаційний вхід пристрою є входом першого вхідного регістру, вихід якого є входом першого дешифратора, виходи якого є першими входами відповідних ключових елементів групи. Виходи ключових елементів групи підключено до перших входів відповідних елементів І групи, виходи яких через перший елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою. Перша керуюча шина пристрою підключена до входу генератора імпульсів, вихід якого підключено до перших входів першого та другого елементів І. Вихід першого елемента І підключено до входу лічильника, вихід якого підключено до першого входу схеми порівняння, вихід якої підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого та другого елементів І. Вихід другого елемента І підключено до входу перемножувача частоти (ПЧ). Вихід розрядів КРЗ підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістра. Вихід ПЧ є першими входами третього та четвертого елементів І, виходи яких підключено відповідно до першого (позитивного, тобто, зсуву розрядів КРЗ проти часової стрілки) та другого (негативного, зсуву розрядів КРЗ - за часовою стрілкою) входів КРЗ. Вихід другого вхідного регістра підключено до входу другого дешифратора, група виходів, яким призначено значення m 3 , другого дешифратора підключена до 0 2 входів другого елемента АБО, а група виходів m 1 m 1 - підключена до входів третього 2 елемента АБО. Одночасно з цим, виходи другого дешифратора попарно (сума числових значень, що присвоєна кожній парі вихідних шин дорівнює значенню m-1) підключено до входів відповідних елементів АБО групи, виходи яких підключено до входів шифратора, вихід якого підключено до другого входу схеми порівняння. Вихід другого елемента АБО підключено до другого входу четвертого елемента І, а вихід третього елемента АБО підключено до другого входу третього елемента І. Введення вказаних ознак дозволяє у два рази зменшити максимальний час реалізації арифметичної операції A B modm , де за рахунок зменшення кількості зсувів розрядів КРЗ з максимальm 1 ного значення m 1 до значення (де m 2 непарне число). Зменшення у два рази кількості зсувів розрядів КРЗ базується на реалізації слідуючого співвідношення A m 1 mod m 2 B m 1 mod m mod m 2 A B mod m . Тобто вихідне значення розрядів КРЗ містить не значення першого рядка (стовпчика) матриці реалізації арифметичних операцій (табл. 1, для m=7), як у прототипі, а містить значення 5 m 1 2 50024 го рядка. Цей рядок містить сукупність значень Асер A m 1 modm; a 2 0, m 1 . Таблиця 1 А 0 1 2 3 4 5 6 0 1 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5 В 0 1 2 3 4 5 6 В цьому випадку розряди КРЗ містять, у вихідному стані, слідуючі дані (для m=7) У загальному випадку вихідний стан вмісту розрядів КРЗ має наступний вигляд На кресленні (Фіг.1) представлена блок-схема корисної моделі для m - непарного числа; де: 1 перший інформаційний вхід пристрою; 2 - перший вхідний регістр; 3 - перший дешифратор (пристрій для перетворення двійкового коду в унітарний); 4 група з m (0 m-1) ключових елементів; 5 - група з m (0 m-1) елементів І; 6 - перший елемент АБО; 7 – вихідний регістр; 8 - вихід пристрою; 9 - керуюча шина пристрою; 10 - генератор імпульсів; 11, 12 перший і другий елементи І; 13 - лічильник імпульсів; 14 - схема порівняння; 15 - перемножувач частоти (пристрій виконує операцію множення B log 2 m 1 1 ; B - другий операнд); 16 - кільцевий регістр зсуву (містить m (0 m-1) розрядів КРЗ; один розряд КРЗ містить log 2 m 1 1 двійкових розрядів); 17 - другий інформаційний вхід пристрою; 18 - другий вхідний регістр; 19, 20 - третій та четвертий елементи І; 21 - другий дешифратор; 22, 23 - другий та третій елементи АБО; 24 6 група елементів АБО; 25 - шифратор (пристрій для перетворення чисел з унітарного коду в двійковий). На кресленні (Фіг.1) представлена блок-схема запропонованого пристрою. Перший інформаційний вхід 1 пристрою є входом першого 2 вхідного регістру, вихід якого є входом першого 3 дешифратора, виходи якого є першими входами відповідних ключових елементів 4 групи. Виходи ключових елементів 4 групи підключено до перших входів відповідних елементів 5 І групи, виходи яких через перший 6 елемент АБО підключено до входу вихідного регістра 7, вихід якого є виходом 8 пристрою. Керуюча 9 шина пристрою підключена до входу генератора імпульсів 10, вихід якого підключено до перших входів першого 11 та другого 12 елементів І. Вихід першого 11 елемента І підключено до входу лічильника 13, вихід якого підключено до першого входу схеми порівняння 14, вихід якої підключено до других входів ключових елементів 4 групи та до других входів елементів 5 І групи, а також до других входів першого 11 та другого 12 елементів І. Вихід другого 12 елемента І підключено до входу перемножувача частоти 15, вихід розрядів кільцевого регістру зсуву 16 підключено до третіх входів відповідних5 елементів І групи, а другий 17 інформаційний вхід пристрою підключено до входу другого 18 вхідного регістра. Вихід перемножувача частоти 15 є першими входами третього 19 та четвертого 20 елементів І, виходи яких підключено відповідно до першого (позитивного) та другого (негативного) входів кільцевого регістру зсуву 16. Вихід другого вхідного регістра 18 підключено до входу другого дешифратора 21, група виходів якого, яким призначено значення m 3 , підключена до входів другого 22 елеме0 2 нта АБО, а група виходів, яким призначено знаm 1 чення m 1, підключена до входів третього 2 23 елемента АБО. Одночасно з цим, виходи другого 21 дешифратора попарно (сума числових значень, що присвоєно кожній парі вихідних шин дорівнює значенню m-1) підключено до входів відповідних елементів 24 АБО групи, виходи яких підключено до входів шифратора 25, вихід якого підключено до другого входу схеми порівняння 14. Вихід другого елемента АБО 22 підключено до другого входу четвертого 20 елемента І, а вихід третього 23 елемента АБО підключено до другого входу третього 19 елемента І, а (m-1/2) вихід дешифратора 21 підключено безпосередньо до нульового входу шифратора 25 (табл. 2). На кресленні (Фіг.2) представлена корисна модель для m=7. Пристрій функціонує наступним чином (Фіг.1). Нехай необхідно визначити операцію A B modm . Перший А операнд у двійковому коді по шині 1 поступає у регістр 2, з виходу якого він поступає до входу дешифратора 3, з виходу якого операнд А в унітарному коді поступає на перший вхід А-го ключового елемента 4, що визначає також А-й розряд КРЗ 16, (в якому містить 7 50024 m 1 A modm ). 2 Вихід А-го ключового елемента відкриває А-й елемент І групи. Другий В операнд у двійковому коді по шині 17, через другий вхідний регістр 18, поступає на вхід дешифратора 21, з виходу якого значення В в унітарному коді поступає до входу елеm 3 мента І 22 (якщо 0 B ), або до входу 2 m 1 елемента І 22 (якщо B m 1 ). Одночасно, 2 другий операнд В поступає на першій вхід елемента АБО 24, на другий вхід якого поступає операнд m-B-1. З виходу В-то елемента АБО 24 сигнал поступає на В-й вхід шифратора 25, з виходу якого операнд В (або m-B-1) в двійковому коді поступає на перші входи схеми 14 порівняння. Сигнал керування шини 9 запускає генератор 10 імпульсів, з виходу якого імпульси через відкритий елемент І 11 поступають на вхід лічильника 13 імпульсів, і одноразово через відкритий елемент І 12 поступають на вхід перемножувача 15 частоти, з виходу якого B log 2 m 1 1 імпульсів поступають на перші входи елементів І 19 та І 20. Якщо в лічильнику 13 є значення В (або m-B-1), тоді вихідний сигнал схеми 14 порівняння відкриває А-й ключовий елемент 4 групи та А-й елемент І 5, а також ся у двійковому коді значення 8 закриває елементи І 11, 12. Вихідний сигнал елемента АБО 22, або вихідний сигнал елемента АБО 23, відкривають елементи І відповідно 20 і 19. Якщо відкрито елемент І 19, тоді після зсуву в позитивному (проти часової стрілки) напряму В (або mB-1) розрядів 16 КРЗ (тобто B log 2 m 1 1 двійкових розрядів) зміст А-го розряду 16 КРЗ, значення (A+B)mod m, через відкритий А-й елемент І 5, елемент АБО 6 поступає на вхід регістра 7. Якщо відкрито елемент І 20, тоді після зсуву в негативному (за часовою стрілкою) напряму В (або m-B-1) розрядів 16 КРЗ зміст А-го розряду 16 КРЗ значення (A+B)mod m через відкритий А-й елемент І 5, елемент АБО 6 поступає на вхід регістра 7. Розглянемо приклади конкретного виконання операції (A+B)mod m для m=7 (Фіг.2). В цьому випадку вихідний зміст розрядів 16 КРЗ має вигляд 3-го рядка таблиці 1, тобто, вихідний стан КРЗ 16 має вигляд Таблиця 2 Значення вихідних шин дешифратора 21 0 1 2  (m-1)/2  m-2 m-1 Значення вхідних шин елементів АБО 24 0, m-1 1, m-2 2, m-3 [(m-1)/2-1], [m-1)/2+1] Значення вхідних шин шифратора 25 (m-1)/2 (m-3)/2 (m-5)/2 0 Таблиця 3 Значення вихідних шин дешифратора 21 0 1 2 3 4 5 6 Значення вхідних шин елементів АБО 24 0,6 1,5 2,4 Приклад 1. Необхідно визначити результат операції (A+B)mod m 7 для A=2, В=1 (див. табл. 310). Перший операнд А=010 на шині 1 поступає в регістр 2, з виходу якого через дешифратор 3 в унітарному коді, що відповідає значенню два, поступає на перший вхід третього ключового елемента 4, з виходу якого поступає на перший вхід третього елемента І 5. Другий операнд B=001 по шині Значення вхідних шин шифратора 25 3 2 1 0 17, через вхідний регістр 18 поступає на вхід дешифратора 21, з виходу якого значення один в унітарному коді поступає на вхід елемента АБО 22 (0