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

Пристрій для додавання і віднімання чисел за модулем m модулярної системи числення на основі кільцевого зсуву з контролем помилок, що містить перший і другий вхідні регістри, вихідний регістр, дешифратор, кільцевий регістр зсуву (КРЗ), інвертор за модулем m (m - модуль, за яким працює пристрій), першу, другу та третю групи елементів І, першу групу елементів АБО, приймальний регістр, першу схему порівняння (СП), перший лічильник імпульсів (ЛІ), шифратор і елемент заборони, причому, перший і другий інформаційні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід першого вхідного регістра підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ, вихід вихідного регістра є першим виходом пристрою, вихід другого вхідного регістра підключено до першого входу інвертора U 2 56684 1 3 регістр зсуву (КРЗ), схему порівняння, чотири елементи І, причому, перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, виходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, виходи яких через елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, першу керуючу шину пристрою підключено до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до першого входу схеми порівняння, вихід якої підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу множник частоти, а виходи розрядів КРЗ підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістру. Недолік даного пристрою (аналогу) - низькі функціональні можливості пристрою (неможливість виявляти помилки під час реалізації арифметичних модульних операцій додавання та віднімання у МСЧ). Близьким за технічною суттю (аналогом) до запропонованої корисної моделі є а.с. №1259255, БВ №35, 1986p., G 06 F 7/72, де реалізується операція модульного додавання та віднімання (А±В) mod m. Пристрій містить перший і другий вхідні регістри, вихідний регістр, дешифратор, групу ключових елементів, групу елементів І, елемент АБО, генератор імпульсів, множник частоти, лічильник, кільцевий регістр зсуву, схему порівняння, чотири елементи І, причому, перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, виходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, виходи яких через елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, першу керуючу шину пристрою підключено до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до входу лічильника, вихід якого підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу множника частоти, а виходи розрядів кільцевого регістра зсуву підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістра, вихід другого вхідного регістра підключено до другого входу схеми порівняння, а вихід множника частоти є першими входами третього і четвертого елементів І, виходи яких підключено до відповідно першого і другого входів кільцевого регістру зсуву, а до других входів третього і четвертого елементів І підключено відповідно друга і третя керуючі шини пристрою. 56684 4 Недолік даного пристрою (аналогу) - низькі функціональні можливості пристрою (неможливість виявляти помилки під час реалізації арифметичних модульних операцій додавання та віднімання у МСЧ). Найбільш близьким за технічною суттю (прототипом) до запропонованої корисної моделі є корисна модель №u49712 України, БВ №9, від 11.05.2010р., G 06 F 7/00, де реалізується операція модульного додавання та віднімання (А±В) mod m у МСЧ. Пристрій містить перший і другий вхідні регістри, вихідний регістр, дешифратор, кільцевий регістр зсуву (КРЗ), інвертор за модулем m (m - модуль, за яким працює пристрій), першу, другу та третю групи елементів І, першу групу елементів АБО, прийомний регістр, першу схему порівняння (СП), перший лічильник імпульсів (ЛІ), шифратор і елемент заборони, причому, перший і другий інформаційні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід першого вхідного регістру підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ, вихід вихідного регістру є першим виходом пристрою, вихід другого вхідного регістру підключено до першого входу інвертору за модулем m і до перших входів елементів І першої групи, до другого входу інвертора за модулем m підключена шина подачі значення т, а до других входів елементів І першої групи підключена шина подачі сигналу ознаки "додавання", вихід інвертора за модулем m підключено до перших входів елементів І другої групи, до других входів яких підключена шина подачі сигналу ознаки "віднімання", виходи елементів І першої та другої груп, через групу елементів АБО, підключено до входу прийомного регістру, вихід якого підключено до перших входів першої СП, до других входів якої відключено виходи першого ЛІ, виходи розрядів КРЗ через перші входи відповідних елементів І третьої групи підключено до входів шифратора, вихід якого підключено до входу вихідного регістру, а керуючий вхід пристрою підключено до першого входу елемента заборони, вихід якого підключено до входу ЛІ і до керуючого входу КРЗ, а вихід першої СП підключено до других входів елементів І третьої групи, а також до другого (заборонного) входу елемента заборони. Недолік прототипу - низькі функціональні можливості пристрою за рахунок неможливості виявляти помилки під час реалізації арифметичних модульних операцій додавання та віднімання у МСЧ. В основу запропонованої корисної моделі поставлено задачу розширення функціональних можливостей пристрою для реалізації арифметичних модульних операцій додавання та віднімання у МСЧ за рахунок спроможності контролю помилок при реалізації арифметичних модульних операцій. Поставлене завдання вирішується тим, що пристрій для додавання і віднімання чисел за модулем m модулярної системи числення на основі кільцевого зсуву з контролем помилок, містить перший і другий вхідні регістри, вихідний регістр, дешифратор, кільцевий регістр зсуву (КРЗ), інвер 5 56684 тор за модулем m (m - модуль, за яким працює пристрій), першу, другу та третю групи елементів І, першу та другу групи елементів АБО, прийомний регістр, першу та другу схеми порівняння (СП), перший та другий лічильники імпульсів (ЛІ), шифратор і елемент заборони, причому, перший і другий інформаційні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів. Вихід першого вхідного регістру підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ, вихід вихідного регістру є першим виходом пристрою, вихід другого вхідного регістру підключено до першого входу інвертору за модулем m і до перших входів елементів І першої групи, до другого входу інвертора за модулем m підключена шина подачі значення m, a до других входів елементів І першої групи підключена шина подачі сигналу ознаки "додавання", вихід інвертора за модулем m підключено до перших входів елементів І другої групи, до других входів яких підключена шина подачі сигналу ознаки "віднімання", виходи елементів І першої та другої груп, через групу елементів АБО, підключено до входу прийомного регістру, вихід якого підключено до перших входів першої СП, до других входів якої відключено виходи першого ЛІ. Виходи розрядів КРЗ через перші входи відповідних елементів І третьої групи підключено до входів шифратора, вихід якого підключено до входу вихідного регістру, а керуючий вхід пристрою підключено до першого входу елемента заборони, вихід якого підключено до входу ЛІ і до керуючого входу КРЗ. Вихід першої СП підключено до других входів елементів І третьої групи, а також до другого (заборонного) входу елемента заборони. Виходи розрядів КРЗ через другу групу елементів АБО підключено до входів другого ЛІ, виходи якого підключено до перших входів другої СП, вихід якої другим виходом пристрою (вихід ознаки помилки), а до другого входу СП підключено другий інформаційний вхід пристрою. Введення вказаних ознак дозволяє виявляти помилки у результаті операції (A±B)mod m у МСЧ. Дійсно, у прототипі використовується принцип кільцевого зсуву (ПКЗ) для реалізації модульної арифметичної операції (A±B)mod m. В цьому випадку вміст КРЗ за модулем m можна представити у вигляді Pm  P0 P1  Pm1 , де Pi - i-й двійковий розряд ( Pi  0 або 1) КРЗ; - операція конкатенації. Для довільного модуля m МСЧ вага m 1  W Pi   1 (одна одиниця, що містяться у двійi0   кових розрядах Pi i  0, m  1 ), є величиною сталою, тобто 6 P0  10000  00 , W P0   1; P1  01000  00 , W P1   1; P2  00100  00 , W P2   1; P3  00010  00 , W P3   1; P4  00001  00 , W P4   1;  Pm 1  00000  01, W Pm 1   1. На основі властивості ПКЗ вміст (вага суми розрядів дорівнює одиниці) КРЗ залишається без змін при реалізації операції (A±B)mod m. Дана обставина дає змогу без введення додаткової інформаційної надмірності виявляти помилки шляхом порівняння другого В числа зі значення вмісту другого лічильника. Дана корисна модель достовірно визначає помилку, що не дорівнює значенню числа В, яке визначає кількість зсувів вмісту розрядів КРЗ. На рисунку (Фіг.1) представлена блок-схема корисної моделі, де 1, 2 - перший та другий інформаційні входи пристрою; 3, 4 - перший та другий вхідні регістри; 5 - дешифратор (пристрій для перетворення двійкового коду в унітарний); 6 - кільцевий регістр зсуву; 7 - вихід пристрою; 8 - вихідний регістр; 9 - інвертор за модулем m; 10 - перша група елементів І; 11 - шина подачі значення модуля m, 12 - шина подачі сигналу ознаки "додавання", 13 - друга група елементів І; 14 - шина подачі сигналу ознаки "віднімання"; 15 - група елементів АБО; 16 - прийомний регістр; 17 - перша схема порівняння; 18 - перший лічильник імпульсів; 19 - третя група елементів І; 20 - шифратор (пристрій для перетворення унітарного коду у двійковий); 21 - управляючий вхід пристрою (шина подачі імпульсів); 22 - елемент заборони; 23 - друга група елементів АБО; 24 - другий лічильник імпульсів; 25 - друга схема порівняння; 26 - другий вихід пристрою (вихід сигналу ознаки "помилка"). Перший 1 і другий 2 інформаційні входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів. Вихід першого 3 вхідного регістру підключено до входу дешифратора 5, виходи якого підключені до входів відповідних розрядів КРЗ 6. Вихід 7 вихідного регістру 8 є виходом пристрою. Вихід другого 4 вхідного регістру підключено до першого входу інвертора 9 за модулем m і до перших входів елементів І 10 першої групи. До другого входу інвертора 9 підключена шина 11 подачі значення модуля m. До других входів елементів І 10 першої групи підключена шина 12 подачі сигналу ознаки "додавання". Вихід інвертору 9 підключено до перших входів елементів І другої 13 групи, до других входів яких підключена шина 14 подачі сигналу ознаки "віднімання". Виходи елементів І першої 10 та другої 13 груп, через групу елементів АБО 15 підключено до входу прийомного 16 регістру, вихід якого підключено до перших входів СП 17, до других входів якої підключено виходи ЛІ 18. Розряди КРЗ 6 через перші входи відповідних елементів І третьої 19 групи 7 56684 підключено до входів шифратора 20, вихід якого підключено до входу вихідного 8 регістру. Управляючий вхід 21 пристрою підключено до входу елемента заборони 22, вихід якого підключено до входу ЛІ 18 і до керуючого входу КРЗ 6. Вихід СП 17 підключено до других входів елементів І третьої 19 групи, а також до другого (заборонного) входу елемента 22 заборони. Виходи розрядів КРЗ 6 через другу 23 групу елементів АБО підключено до входу другого 24 ЛІ, виходи якого підключено до перших входів другої 25 СП, вихід 26 якої є вихід сигналу ознаки "помилка". До других входів другої 25 СП підключено другий 2 інформаційний вхід пристрою. Пристрій функціонує наступним чином. На перший 1 та другий 2 вхід подаються перший А та другий В операнди в двійковому коді. З виходу дешифратора 5 операнд А в унітарному коді поступає на вхід А-го двійкового розряду КРЗ 6. Вихідний стан двійкових розрядів КРЗ 6, наприклад, для m=5, має вигляд (нульовий стан): . Двійкові розряди КРЗ 6 нумеруються з нульового (зліва) до (m-1)-гo (справа). Операнд А (0Аm-1) з виходу дешифратора 5 "записує" одиницю в А-й двійковий розряд КРЗ 6. Другий операнд В по шині 2 в двійковому коді поступає на регістр 4, з виходу якого поступає на перші входи елементів І першої 10 групи та на перший вхід інвертора 9 за модулем m. В залежності від типу операції операнд В (операція додавання, є сигнал шини 12) або операнд B  m  B (операція віднімання, є сигнал шини 14) через групу 15 елементів АБО поступає на вхід регістру 16. З початку роботи імпульси по шині 21 через відкритий елемент 22 заборони поступають на вхід 8 ЛІ 18 та на керуючий вхід КРЗ 6, що здійснює зсув вихідного вмісту двійкових розрядів КРЗ на В (або на B ) двійкових розрядів в негативному (за часовою стрілкою) напряму. При наявності у ЛІ 18 значення В ( B ) вихідний сигнал СП 17 закриває елемент 22 заборони і забороняє подачу імпульсів на ЛІ 18 та КРЗ 6 і одночасно відкриває елементи І третьої 19 групи. В цьому випадку вміст КРЗ 6 через відкриті елементи І третьої групи 19 поступає на вхід шифратора 20 з виходу якого значення (А±В) mod m результату модульної операції в МСЧ поступає на вхід вихідного регістру 8. Одноразово, після кожного зрушення вмісту розрядів 6 КРЗ, на один двійковий розряд, з виходів розрядів 6 КРЗ через другу 23 групу елементів АБО на входи другого 24 ЛІ поступають імпульси, що відповідають значенню одиниця в представленні вмісту розрядів 6 КРЗ. Значення вмісту ЛІ 24 дорівнює кількості зсувів КРЗ 6, тобто значенню другого числа В. Таким чином значення вмісту ЛІ 24 повинно дорівнювати числу В. Друга 25 схема порівняння порівнює значення вмісту ЛІ 24 і значення другого В числа. Якщо два числа рівні між собою, тоді на другому 26 виході пристрою вихідний сигнал СП 25 відсутній (помилки немає), а якщо два числа не рівні між собою, тоді на другому 26 виході пристрою присутній вихідний сигнал СП 25 "Помилка". Розглянемо приклад конкретної реалізації модульних операцій (A±B)mod m в МСЧ з контролем помилок для m=5. В цьому випадку вихідний вміст КРЗ 6 має вигляд: . Шифратор 20 має вигляд таблиці 1. Таблиця 1 Вхід шифратора 20 (m = 5). 10000 01000 00100 00010 00001 Вихід шифратора 20. (Результат операції (А±В) mod 5 у двійковому коді). 000 001 010 011 100 В таблиці 2 дано алгоритм контролю помилок. Таблиця 2 В 0 1 2 3 4 0 1 0 0 0 0 0 0 1 0 0 0 Вихідний стан розрядів 6 КРЗ 0 0 0 0 0 0 1 0 0 1 0 0 Нехай А3=011, В4=100. Необхідно визначити (A+B)mod 5. Перший операнд А3=011 по входу 1 через регістр 3 поступає на вхід дешифратора 5, з третього (А3=011) виходу якого сигнал поступає на 0 0 0 0 0 1 Значення вмісту ЛІ 24 000 001 010 011 100 третій двійковий розряд КРЗ 6, що переводить його із нульового стану в одиничний (розряди КРЗ 6 нумеруються з нульового до (m-1)-гo зліва направо). Стан КРЗ визначається наступним чином: 9 . Другий операнд В4=100 за входом 2 через регістр 4 поступає на перші входи елементів І першої 10 групи та на перший вхід інвертора 9. З виходу елементів І першої 10 групи значення В4=100, а з виходу елементів І другої 13 групи значення B1  101100  001, в залежності від типу операції, через елементи 15 АБО поступають до входу регістру 16. За входом 21 імпульси через відкритий елемент 22 поступають на вхід ЛІ 18 і на вхід зсуву КРЗ 6, що здійснює зсув двійкових розрядів КРЗ 6 на чотири (здійснюється операція додавання (3+4) mod 5, присутній сигнал шини 12) розряди в негативному (за часовою стрілкою) напрямі. В цьому випадку вміст КРЗ 6 буде мати наступний вигляд: . Якщо у ЛІ 18 буде знаходитися значення В4=100, тоді СП 17 видає сигнал "дорівнює", який закриває елемент 22 заборони та відчиняє елементи І третьої 19 групи, через які код 00100 КРЗ 6 поступає на вхід шифратора 20, з виходу якого 56684 10 (див. таблицю 1) значення (А+В) mod 5 = (3+4) mod 5 = 010 поступає на вхід регістра 8. Перевірка: (3+4) = 2 (mod 5). Одноразово, з виходів розрядів 6 КРЗ імпульси через елементи АБО групи 23 поступають до входу ЛІ 24. Якщо не було відмов (порушення роботи КРЗ 6) тоді ЛІ 24 містить значення 100, що поступає на перші входи СП 25, на другі входи яких поступає значення В4=100. В цьому випаду відсутній вихідний сигнал СП 25 (шина 26). Якщо, наприклад, за рахунок порушення функціонування пристрою ЛІ 24 містить значення, що відрізняється від значення В4=100, тоді присутній сигнал "Помилка" шини 26. Таким чином, запропонована корисна модель дозволяє розширити функціональні можливості пристрою за рахунок виявлення помилок при реалізації арифметичних операцій (A±B)mod m в МСЧ на основі ПКЗ. Це досягається за рахунок використання властивості ПКЗ - постійність структури вмісту розрядів КРЗ. Це досягається без введення додаткової інформаційної надмірності. З зростанням величини m модуля МСЧ ефективність застосування корисної моделі зростає. 11 Комп’ютерна верстка М. Ломалова 56684 Підписне 12 Тираж 23 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601