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

Пристрій складання і віднімання чисел за модулем m системи залишкових класів (далі пристрій), що містить перший і другий вхідні регістри, вихідний регістр, дешифратор, групу ключових елементів, групу елементів І, елемент АБО, генератор імпульсів, перемножувач частоти, лічильник, кільцевий регістр зсуву, схему порівняння, чотири елементи І, причому перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, ви ходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, ви ходи яких через елемент АБО підключено до входу вихідного регіс U 2 (19) 1 3 35147 нання, що обумовлено наявністю інвертора за модулем m та прийомного регістру. Задача корисної моделі - зменшення кількості обладнання пристрою прототипу за рахунок скорочення інвертора за модулем m, тобто пристрою для реалізації операції B = (m - B )mod m , та прийомного регістру. Поставлена задача досягається за рахунок того, що пристрій складання і віднімання чисел за модулем m системи залишкових класів (далі пристрій), містить перший і другий вхідні регістри, вихідний регістр, дешифратор, груп у ключови х елементів, групу елементів І, елемент АБО, генератор імпульсів, перемножувач частоти, лічильник, кільцевий регістр зсуву, схему порівняння, чотири елементи І, причому, перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, ви ходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, ви ходи яких через елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, першу керуючу шин у пристрою підключено до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до входу лічильника, вихід якого підключено до першого входу схеми порівняння, вихід якої підключено до других входів ключових елементів групи та до др уги х входів елементів І групи, а також до других входів першого і другого елементів І, вихід др угого елемента І підключено до входу перемножувача частоти, а виходи розрядів кільцевого регістра зсуву підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу др угого вхідного регістра, відрізняється тим, що вихід др угого вхідного регістра підключено до другого входу схеми порівняння, а вихід перемножувача частоти є першими входами третього і четвертого елементів І, ви ходи яких підключено до відповідно першого і другого входів кільцевого регістра зсуву, а до других входів третього і четвертого елементів І підключено відповідно друга і третя керуючи шини пристрою. Введення вказаних ознак дозволяє значно зменшити кількість обладнання прототипу, за рахунок скорочення блоку визначення значення B= (m - B )modm та прийомного регістру. На Фіг.1 представлено структурну схему пристрою за довільним модулем m, де: 1 - перший інформаційний вхід пристрою; 2 - перший вхідний регістр; 3 - дешифратор (пристрій перетворювання двійкового коду в унітарний); 4 - група з m ключових елементів; 5 - група з m трьовходових елементів І; 6 - елемент АБО; 7 - ви хідний регістр; 8 - вихід пристрою; 9 - другий інформаційний вхід пристрою; 10 - другий вхідний регістр; 11 - перша керуюча шина пристрою; 12 - генератор імпульсів; 13, 14 - перший і другий елементи І; 15 - лічильник; 16 - схема порівняння; 17 - перемножувач частоти; 18, 19 - третій і четвертий елементи І; 20 - кільцевий регістр зсуву; 21, 22 - друга („додавання") і третя („віднімання") керуючі шини пристрою. 4 На Фіг.2 представлено структурну схему пристрою за модулем m=5. На Фіг.3 представлено вихідний інформаційний зміст розрядів кільцевого регістру зсуву 20 у двійковому коді за довільним модулем m для операції модульного складання. На Фіг.4 представлено вихідний інформаційний зміст розрядів кільцевого регістру зсуву 20 у двійковому коді за довільним модулем m для операції модульного віднімання. На Фіг.5 представлено вихідний інформаційний зміст розрядів кільцевого регістру зсуву 20 у двійковому коді за модулем m=5 для операції модульного складання та віднімання. На Фіг.6 надано схему проведення операції модульного складання (A+B)mod 5, де А=0 і В=2. На Фіг.7 надано схему проведення операції модульного віднімання (A-B)mod 5, де А=0 і В=2. Перший I інформаційний вхід пристрою підключено до входу першого 2 вхідного регістра, вихід якого підключено до входу де шифратора 3, виходи дешифратора 3 підключено до перших входів відповідних ключових елементів 4 групи, виходи яких підключено до перших входів відповідних елементів І 5 групи, ви ходи яких через елемент АБО 6 підключено до входу ви хідного регістра 7, вихід 8 якого є виходом пристрою. Другий 9 інформаційний вхід пристрою підключено до входу другого 10 вхідного регістра. Перша 11 керуюча шина пристрою підключено до входу генератора імпульсів 12, вихід якого підключено до перших входів першого 13 і другого 14 елементів І. Вихід першого 13 елемента І підключено до входу лічильника 15, вихід якого підключено до першого входу схеми порівняння 16, до другого входу якої підключено вихід другого вхідного регістра 10. Вихід схеми порівняння 16 підключено до других входів ключови х елементів 4 групи та до других входів елементів І 5 групи, а також до других входів першого 13 і другого 14 елементів І. Вихід другого 14 елемента І підключено до входу перемножувача частоти 17, вихід якого підключено до перших входів третього 18 і четвертого 19 елементів І, ви ходи яких підключено до відповідно першого і другого входів кільцевого регістра зсуву 20, виходи розрядів 20 якого підключено до третіх входів відповідних елементів І 5 групи. До других входів третього 18 і четвертого 19 елементів І підключено відповідно друга 21 і третя 22 керуючі шини пристрою. Пристрій функціонує наступним чином (Фіг.1). Нехай необхідно визначити результат операції C=(A+B)mod m модульного додавання. В цьому випадку присутній сигнал шини 21. Кількість розрядів кільцевого регістра зсуву 20 дорівнює m. В кожному розряді кільцевого регістра зсуву 20 міститься одне зі значень: 0, 1,..., m-1 в двійковому коді. Тобто, вихідний інформаційний зміст розрядів кільцевого регістра зсуву 20 в двійковому коді має вигляд, що наданий на малюнку (Фіг.3). Кількість k двійкових розрядів в кожному розряді 20 дорівнює значенню k=[log2(m-1)]+1, де [c] ціла частина значення і його не більша. Перший А операнд (А може приймати одне зі значень 0, 1, 2,..., m-1) вказує на відповідний розряд 20 кільце 5 35147 вого регістра зсуву, з якого одержимо результат операції С. Другий В операнд (В може приймати одне зі значень 0, 1, 2,..., m-1) вказує на кількість k'=kВ двійкових розрядів, що необхідно зсунути в позитивному (проти часової стрілки, тобто вліво) напрямку, (тому, що присутній сигнал шини 21), зміст розрядів кільцевого регістра зсуву 20. Сигнал керування шини 11 запускає генератор імпульсів 12, з виходу якого імпульси поступають: через відкритий елемент І 13 на вхід лічильника 15; через відкритий елемент І 14 на вхід перемножувача частоти 17. З ви ходу перемножувача частоти 17 кількість k'=kB={[log2(m-1)]+1}В імпульсів через відкритий елемент І 18 (присутній сигнал шини 21) поступає на перший вхід кільцевого регістра зсуву 20. Перший А операнд в двійковому коді поступає по шині 1 до першого регістра 2, з виходу якого він поступає на вхід дешифратора 3, з виходу якого операнд А в унітарному коді поступає на перший вхід відповідного А-го ключового елемента 4, що визначає також А-й розряд кільцевого регістра зсуву 20, з якого результат операції C=(A+B)mod m через відповідний відкритий елемент І 5 і елемент АБО 6 поступає на вхід вихідного регістра 7. Другий В операнд в двійковому коді по шині 9 поступає на вхід другого вхідного регістра 10 і далі на другий вхід схеми порівняння 16, на перший вхід якої поступає кінцеве значення лічильника 15. Якщо в лічильнику 15 є значення В, то схема порівняння 16 видає сигнал, що відкриває А-й ключовий елемент 4, А-й елемент І 5, а також закриває елементи І 13 і 14, що обумовлює закінчення поступу імпульсів до входу лічильника 15 і до входу перемножувача частоти 17. Після зсуву в позитивному (проти часової стрілки) напрямку В розрядів кільцевого регістра зсуву 20 (k'=kB={[log2(m-1)+1}В двійкових розрядів), зміст I-го розряду (тобто значення C=(A+B)mod m) 20 кільцевого регістра зсуву через відкритий А-й елемент І 5, елемент АБО 6 поступає на вхід регістра 7. Нехай необхідно визначити C=(A-B)mod m. В цьому випадку присутній сигнал шини 22. Другий В операнд вказує на кількість k'=k В двійкових розрядів, що необхідно зсунути в негативному (за часовою стрілкою, тобто вправо) напрямку, що надано на малюнку (Фіг.4). Розглянемо пример конкретного виконання операції модульного додавання і віднімання за модулем m=5 (k=[log 2(m-1)]+1=3). В цьому випадку вихідний зміст розрядів 20 кільцевого регістра зсуву має вигляд що наданий на малюнку (Фіг.5). Приклад 1. А=0, В=2. Необхідно визначити C=(A+B)mod m. Перший операнд А=000 поступає 6 по шині 1 в регістр 2, з виходу якого через дешифратор 3 сигнал унітарного коду, відповідний значенню нуль, поступає на перший вхід першого ключового елемента 4. Другий операнд В=010 поступає по шині 9 на вхід регістра 10, з ви ходу якого операнд В=010 поступає на вхід схеми порівняння 16. Керуючий сигнал шини 11 запускає генератор імпульсів 12, і імпульси, через відкриті елементи І 13 і 14, поступають відповідно на вхід лічильника 15 і на вхід перемножувача частоти 17, з ви ходу якого, через відкритий елемент І 18 (присутній сигнал шини 21 „додавання") на перший вхід кільцевого регістра зсуву 20 поступають kВ=3×2=6 імпульсів, що зсувають вліво (проти часової стрілки) зміст розрядів кільцевого регістра зсуву 20 на шість двійкових розрядів (два розряди кільцевого регістра зсуву 20). Тобто, маємо виконання модульної операції, що надана на малюнку (Фіг.6). Коли зміст лічильника 15 дорівнює значенню В=010, то вихідний сигнал схеми порівняння 16 відкриває перший ключовий елемент 4 і перший елемент І 5 гр упи, через який значення 010 першого розряду кільцевого регістра зсуву 20 поступає через елемент АБО 6 в регістр 7. Перевірка: (0+2)=2(mod5)=010(mod5). Приклад 2. А=0, В=2. Необхідно визначити C=(A-B)mod m. Присутній сигнал шини 22 „віднімання". В цьому випадку вихідне положення кільцевого регістра зсуву 20 зсувається вправо (за часовою стрілкою) на kВ=3×2=6 двійкових розрядів (два розряди кільцевого регістра зсуву 20). Тобто, маємо виконання модульної операції, що надана на малюнку (Фіг.7). В цьому випадку значення 011 через перший відкритий елемент І 5 групи, через елемент АБО 6 поступає на вхід регістра 7. Перевірка: (0-2)mod5=(5-2)mod5=3(mod5), тобто, маємо результат операції у двійковому коді 011 (mod 5). Таким чином запропонована корисна модель дозволяє значно зменшити кількість обладнання пристрою складання і віднімання чисел за модулем m системи залишкових класів за рахунок скорочення інвертора за модулем m і прийомного регістра при збереженні всіх технічних характеристик пристрою. При цьому також зменшується час виконання арифметичних операцій складання та віднімання за рахунок скорочення часу який був потрібен для виконання операції визначення величини B = (m - B )mod m , а також часу, що був потрібен для запису у прийомний регістр значення другого операнду В. 7 35147 8 9 35147 10 11 Комп’ютерна в ерстка А. Крулевський 35147 Підписне 12 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601