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

Пристрій для додавання і віднімання чисел за модулем m модулярної системи числення на основі кільцевого зсуву, що містить перший і другий вхідні регістри, вихідний регістр, перший дешифратор, перший шифратор, кільцевий регістр зсуву (КРЗ), першу, другу та третю групи елементів І, першу групу елементів АБО, схему порівняння (СП), лічильник імпульсів (ЛІ) і елемент заборони (ЕЗ), при цьому, перший і другий інформаційні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи розрядів КРЗ підключено до перших входів елементів І першої групи, а вихід вихідного регістра є виходом пристрою, керуючий вхід пристрою підключено до першого входу ЕЗ, вихід якого підключено до U 2 55454 1 3 тора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до першого входу схеми порівняння, вихід якої підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу множник частоти, а виходи розрядів КРЗ підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістру. Недолік даного пристрою (аналогу) - низька швидкодія реалізації арифметичних модульних операцій додавання та віднімання у МСЧ. Близьким за технічною суттю (аналогом) до запропонованої корисної моделі є а.с. №1259255, БВ №35, 1986p., G06F7/72, де реалізується операція модульного додавання та віднімання (А±В) mod m. Пристрій містить перший і другий вхідні регістри, вихідний регістр, дешифратор, групу ключових елементів, групу елементів І, елемент АБО, генератор імпульсів, множник частоти, лічильник, кільцевий регістр зсуву, схему порівняння, чотири елементи І, причому, перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, виходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, виходи яких через елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, першу керуючу шину пристрою підключено до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до входу лічильника, вихід якого підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу множника частоти, а виходи розрядів кільцевого регістра зсуву підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістра, вихід другого вхідного регістра підключено до другого входу схеми порівняння, а вихід множника частоти є першими входами третього і четвертого елементів І, виходи яких підключено до відповідно першого і другого входів кільцевого регістру зсуву, а до других входів третього і четвертого елементів І підключено відповідно друга і третя керуючі шини пристрою. Недолік даного пристрою (аналогу) - низька швидкодія реалізації арифметичних модульних операцій додавання та віднімання у МСЧ. Найбільш близьким за технічною суттю (прототипом) до запропонованої корисної моделі є корисна модель №u49712 України, БВ № 9, від 11.05.2010р., G06F7/00, де реалізується операція модульного додавання та віднімання (А±В) mod m у МСЧ. Пристрій містить перший і другий вхідні регістри, вихідний регістр, дешифратор, кільцевий регістр зсуву (КРЗ), інвертор за модулем m (m модуль, за яким працює пристрій), першу, другу та третю групи елементів І, першу групу елементів 55454 4 АБО, прийомний регістр, першу схему порівняння (СП), перший лічильник імпульсів (ЛІ), шифратор і елемент заборони, причому, перший і другий інформаційні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід першого вхідного регістру підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ, вихід вихідного регістру є першим виходом пристрою, вихід другого вхідного регістру підключено до першого входу інвертору за модулем m і до перших входів елементів І першої групи, до другого входу інвертора за модулем m підключена шина подачі значення т, а до других входів елементів І першої групи підключена шина подачі сигналу ознаки "додавання", вихід інвертора за модулем m підключено до перших входів елементів І другої групи, до других входів яких підключена шина подачі сигналу ознаки "віднімання", виходи елементів І першої та другої груп, через групу елементів АБО, підключено до входу прийомного регістру, вихід якого підключено до перших входів першої СП, до других входів якої відключено виходи першого ЛІ, виходи розрядів КРЗ через перші входи відповідних елементів І третьої групи підключено до входів шифратора, вихід якого підключено до входу вихідного регістру, а керуючий вхід пристрою підключено до першого входу елемента заборони, вихід якого підключено до входу ЛІ і до керуючого входу КРЗ, а вихід першої СП підключено до других входів елементів І третьої групи, а також до другого (заборонного) входу елемента заборони. Недолік прототипу - низька швидкодія реалізації арифметичних модульних операцій додавання та віднімання у МСЧ. Це зумовлено тим, що в послідовності обробки інформації є операція визначення значення (m-B)mod m. Тобто, пристрійпрототип для додавання та віднімання чисел по модулю m містить інвертор за модулем т, який і обумовлює основну часову затримку реалізації модульних арифметичних операцій у МСЧ. В основу запропонованої корисної моделі поставлено задачу підвищення швидкодії реалізації модульних арифметичних операцій додавання та віднімання у МСЧ. Поставлене завдання вирішується тим, що пристрій для додавання і віднімання чисел за модулем m модулярної системи числення на основі кільцевого зсуву, містить перший і другий вхідні регістри, вихідний регістр, перший дешифратор, перший шифратор, кільцевий регістр зсуву (КРЗ), першу, другу та третю групи елементів І, першу групу елементів АБО, схему порівняння (СП), лічильник імпульсів (ЛІ) і елемент заборони (ЕЗ), другий дешифратор, другий шифратор, другу групу елементів АБО, четверту та п'яту групи елементів І. При цьому, перший і другий інформаційні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи розрядів КРЗ підключено до перших входів елементів І першої групи, а вихід вихідного регістру є виходом пристрою, керуючий вхід пристрою підключено до першого входу ЕЗ, вихід якого підключено до першого входу ЕЗ, вихід якого підключено до керуючого входу КРЗ та до входу ЛІ, вихід якого під 5 ключено до перших входів СП, виходи якої підключено до других входів елементів І першої групи, а також до другого (забороненого) входу ЕЗ. Вихід другого вхідного регістру підключено до других входів СП, а виходи елементів І першої групи підключено до перших входів елементів І другої та третьої груп, виходи яких підключено до входів відповідно першого та другого шифраторів, виходи яких через елементи АБО першої групи підключено до входу вихідного регістру. Виходи першого вхідного регістру підключено до перших входів елементів І четвертої та п'ятої груп, виходи яких підключено до входів відповідно першого та другого дешифраторів, виходи яких через елементи АБО другої групи підключено до входів відповідних розрядів КРЗ. До других входів елементів І другої та четвертої груп підключена шина подачі сигналу ознаки операції "додавання", а до других входів елементів І третьої та п'ятої груп підключена шина подачі сигналу ознаки операції "віднімання". Введення вказаних ознак дозволяє підвищити швидкодію реалізації операції (A±B)mod m у МСЧ за рахунок вилучення із пристрою-прототипу інвертора за модулем m, який вносить основну часову затримку у визначенні результату модульної операції. На рисунку (Фіг.) представлена блок-схема корисної моделі, де 1, 2 - перший та другий інформаційні входи пристрою; 3, 4 - перший та другий вхідні регістри; 5 - кільцевий регістр зсуву; 6 - перша група елементів І; 7 - вихід пристрою; 8 - вихідний регістр; 9 - управляючий вхід пристрою (шина подачі імпульсів); 10 - елемент заборони; 11 - лічильник імпульсів; 12 - схема порівняння; 13, 14 друга та третя група елементів І; 15, 16 - перший та другий шифратори (пристрій для перетворення унітарного коду у двійковий); 17 - перша група елементів АБО; 18, 19 - четверта та п'ята групи елементів І; 20, 21 - перший і другий дешифратори (пристрій для перетворення двійкового коду в унітарний); 22 - друга група елементів АБО; 23 - шина подачі сигналу ознаки "додавання", а 24 - шина подачі сигналу ознаки "віднімання". Перший 1 і другий 2 інформаційні входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів. Виходи розрядів 5 КРЗ підключено до перших входів елементів І першої 6 групи, а вихід 7 вихідного регістру 8 є виходом пристрою. Керуючий 9 вхід пристрою підключено до першого входу ЕЗ 10, вихід якого підключено до керуючого входу КРЗ 5 та до входу ЛІ 11, вихід якого підключено до перших входів СП 12, виходи якої підключено до других входів елементів І першої 6 групи, а також до другого (забороненого) входу ЕЗ 10. Вихід другого 4 вхідного регістру підключено до других входів СП 12. Виходи елементів І першої 6 групи підключено до перших входів елементів І другої 13 та третьої 14 груп, виходи яких підключено до входів відповідно першого 15 та другого 16 шифраторів, виходи яких через елементи АБО першої 17 групи підключено до входу вихідного регістру 8. Виходи першого 3 55454 6 вхідного регістру підключено до перших входів елементів І четвертої 18 та п'ятої 19 груп, виходи яких підключено до входів відповідно першого 20 та другого 21 дешифраторів, виходи яких через елементи АБО другої 22 групи підключено до входів відповідних розрядів 5 КРЗ. До других входів елементів І другої 13 та четвертої 18 груп підключена шина 23 подачі сигналу ознаки операції "додавання", а до других входів елементів І третьої 14 та п'ятої 19 груп підключена шина 24 подачі сигналу ознаки операції "віднімання". Пристрій функціонує наступним чином. За першим 1 та другим 2 входами пристрою на перший 3 та другий 4 вхідні регістри подаються перший А та другий В операнди в двійковому коді. Вихідний стан двійкових розрядів КРЗ 5, наприклад, для m=5, має наступний вигляд: Двійкові розряди КРЗ 5 нумеруються з нульового (зліва) до (m-l)-ro (справа). Через відкриті елементи І 18 (присутній сигнал шини 23 "Додавання") з виходу дешифратора 20, через елементи АБО 22 (або через відкриті елементи І 19 (присутній сигнал шини 24 "Віднімання") з виходу дешифратора 21, через елементи АБО 22) операнд А в унітарному коді поступає на вхід А-го двійкового розряду КРЗ 5. Операнд А (0≤А≤m-1) з "записує" одиницю в А-й двійковий розряд КРЗ 5. Другий операнд В у двійковому коді по шині 2 поступає на регістр 4, з виходу якого він безпосередньо поступає на перші входи схеми порівняння 12. З початку роботи імпульси по шині 9 через відкритий елемент 10 заборони поступають на вхід ЛІ 11 та на керуючий вхід КРЗ 5, що здійснює зсув вихідного вмісту двійкових розрядів КРЗ 5 на В двійкових розрядів в негативному (за часовою стрілкою) напряму. При наявності у ЛІ 11 значення В вихідний сигнал СП 12 закриває елемент 10 заборони та забороняє подачу імпульсів на ЛІ 11 та на КРЗ 5 і одночасно відкриває елементи І першої 6 групи. В цьому випадку вміст КРЗ 5 через відкриті елементи І першої 6 групи, відкриті елементи І другої 13 групи (присутній сигнал шини 23 "Додавання") поступає на вхід шифратора 15, або вміст КРЗ 5 через відкриті елементи І першої 6 групи, відкриті елементи І третьої 13 групи (присутній сигнал шини 24 "Віднімання") поступає на вхід шифратора 16. Значення результату операції модульного додавання або віднімання (A±B)mod m у МСЧ через елементи АБО першої 17 групи поступає до входу вихідного 8 регістру. Розглянемо приклад конкретної реалізації модульних операцій (А±В) mod m в МСЧ для m=5. В цьому випадку вихідний вміст КРЗ 5 має вигляд: В таблицях 1-2 дано алгоритми кодування розрядів КРЗ 5 і вмісту шифраторів 15 і 16. В таблицях 3-5 дано приклади визначення результату операцій (А+В) mod 5 і (А-В) mod 5. 7 55454 8 Таблиця 1 Вихідний вміст розрядів КРЗ 5 А 000 001 010 011 100 0 1 0 0 0 0 0 0 0 Вміст розрядів КРЗ 5 Операція додавання 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 Операція віднімання 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 Таблиця 2 Додавання (шина 23) Вхід шифратора 15 Вхід шифратора 15 1 0 0 0 0 000 0 1 0 0 0 001 0 0 1 0 0 010 0 0 0 1 0 011 0 0 0 0 1 100 Віднімання (шина 24) Вхід шифратора 16 Вхід шифратора 16 0 0 0 0 1 000 0 0 0 1 0 001 0 0 1 0 0 010 0 1 0 0 0 011 1 0 0 0 0 100 Таблиця 3 m=5, А=2, В=4, (А+B)mod m Вихідний стан КРЗ 5 Стан КРЗ 5 при А=010 Стан КРЗ 5 при В=100 Вхід шифратора 15 Вихід шифратора 15 Результат операції (Вміст вихідного регістру 8) 01000 001 001 Перевірка: (2+4)=1(mod 5). Таблиця 4 m=5, А=2, В=4, (А-B)mod m Вихідний стан КРЗ 5 Стан КРЗ 5 при А=010 Стан КРЗ 5 при В=100 Вхід шифратора 16 Вихід шифратора 16 Результат операції (Вміст вихідного регістру 8) Перевірка: (2-4)=3(mod 5). 01000 011 011 9 55454 10 Таблиця 5 m=5, А=3, В=4, (A-B)mod m Вихідний стан КРЗ 5 Стан КРЗ 5 при А=011 Стан КРЗ 5 при В=100 Вхід шифратора 16 Вихід шифратора 16 Результат операції (Вміст вихідного регістру 8) 10000 100 100 Перевірка: (3-4)=4(mod 5). Таким чином, запропонована корисна модель дозволяє суттєво підвищити швидкодію реалізації арифметичних операцій (A±B)mod m в МСЧ на основі ПКЗ. Це досягається за рахунок використання властивості ПКЗ - постійність структури вмі Комп’ютерна верстка О. Рябко сту розрядів КРЗ, шляхом вилучення із пристроюпрототипу інвертора за модулем т, який вносить основну часову затримку у визначенні результату модульної операції. Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601