Конструктивний модуль суматора в залишках

1. Конструктивний модуль суматора в залишках, що містить перший та другий первинні входи переносу із молодших розрядів суматора, перший та другий первинні виходи переносу у старші розряди суматора, від першого до третього первинні входи операндів, первинний вихід результату, логічну схему формування сигналу SUB, першу та другу логічні схеми додавання за модулем 2, який відрізняється тим, що містить першу та другу схеми кодування вхідних сигналів операндів, схеми формування першого та другого сигналів переносу в старші розряди суматора, селекторну схему вибору результату, первинний вхід сигналу SUB, при цьому перший, другий та третій входи схем кодування вхідних сигналів підключені, відповідно, до першого, другого та третього первинних входів операндів, вихід першої логічної схеми кодування вхідних сигналів підключений до другого входу логічної схеми формування першого сигналу переносу у старші розряди суматора, вихід другої логічної схеми кодування вхідних сигналів підключений до першого входу логічної схеми формування першого сигналу переносу у старші розряди суматора, до третього та четвертого входів якої підключені відповідно перший та другий первинні бокові входи переносу із молодших розрядів суматора, а вихід цієї схеми підключений до першого первинного бокового виходу переносу в старші розряди суматора, перший первинний вхід переносу із молодших розрядів суматора підключений до четвертого входу першої схеми додавання за модулем 2, другий первинний боковий вхід сигналу переносу із молодших розрядів суматора підключений до третього входу другої схеми додавання за модулем 2 та до першого входу логічної схеми формування другого сигналу переносу в старші розряди, на другий та третій входи якої підключені, відповідно, перший та другий первинні 2 (19) 1 3 61654 4 схему формування сигналу SUB, при цьому вихід першої логічної схеми кодування вхідних сигналів підключений до третіх входів схем формування першого та другого сигналів переносу в молодші розряди, вихід другої логічної схеми кодування вхідних сигналів підключений до четвертих входів логічних схем формування першого та другого сигналів переносу в молодші розряди, на перші та другі входи цих схем підключені, відповідно, перший та другий первинні бокові входи переносу із старших розрядів суматора, а виходи цих схем підключені, відповідно, до першого та другого пер винних бокових виходів переносу у молодші розряди суматора, вихід схеми формування першого сигналу перенесення у старші розряди підключений до четвертого входу логічної схеми формування сигналу SUB, на третій вхід якої підключено вихід логічної схеми формування другого сигналу перенесення у старші розряди, на перший та другий входи цієї схеми підключені, відповідно, перший та другий первинні бокові входи переносу із старших розрядів суматора, а вихід схеми формування сигналу SUB підключено до первинного виходу сигналу SUB. Корисна модель належить до обчислювальної техніки і може бути використана у спеціалізованих обчислювальних пристроях для побудови швидкодіючих суматорів в залишках, системах асиметричних криптографічних перетворень, системах цифрового підпису. Найбільш близьким до запропонованої корисної моделі є комірка додавача за змінним модулем [Патент № UA 16568 А МПК 7G06F7/50 від 15.03.2004, бюл. № 3], яка містить логічну схему формування позики у старших розрядах, логічну схему формування переносу при додаванні, логічну схему формування переносу при відніманні, логічну схему формування вихідного сигналу "на один менше", логічну схему формування сигналу "дорівнює", логічну схему формування сигналу "більше", першу та другу логічні схеми додавання за модулем 2, логічну схему формування сигналу Sub, інвертор, першу схему логічного множення, другу схему логічного множення. Задачею даної корисної моделі є підвищення швидкості та зменшення апаратних затрат шляхом внесення змін до структури конструктивного модуля суматора в залишках. Поставлена задача вирішується тим, що конструктивний модуль містить першу та другу схеми кодування вхідних сигналів операндів, схеми формування першого та другого сигналу переносу в старші розряди суматора, селекторну схему вибору результату, первинний вхід сигналу SUB, при цьому перший, другий та третій входи схем кодування вхідних сигналів підключені, відповідно, до першого, другого та третього первинних входів операндів, вихід першої логічної схеми кодування вхідних сигналів підключений до другого входу логічної схеми формування першого сигналу переносу у старші розряди суматора, вихід другої логічної схеми кодування вхідних сигналів підключений до першого входу логічної схеми формування першого сигналу переносу у старші розряди суматора, до третього та четвертого входів якої підключені відповідно перший та другий первинні бокові входи переносу із молодших розрядів суматора, а вихід цієї схеми підключений до першого первинного бокового виходу переносу в старші розряди суматора, перший первинний вхід пере носу із молодших розрядів суматора підключений до четвертого входу першої схеми додавання за модулем 2, другий первинний боковий вхід сигналу переносу із молодших розрядів суматора підключений до третього входу другої схеми додавання за модулем 2 та до першого входу логічної схеми формування другого сигналу переносу в старші розряди, на другий та третій входи якої підключені, відповідно, перший та другий первинні входи операндів, а вихід цієї схеми підключено до другого первинного виходу переносу у старші розряди суматора, перший та другий первинні входи операндів піключені, відповідно, на перші та другі входи першої та другої схем додавання за модулем 2, а до третього входу другої схеми додавання за модулем 2 підключено третій первинний вхід операндів, вихід цієї схеми підключено до другого входу селекторної схеми, на третій вхід якої підключено вихід другої схеми додавання за модулем 2, до першого входу селекторної схеми підключено первинний вхід сигналу SUB, а вихід підключено до первинного виходу результату. Конструктивний модуль пояснюється кресленням на фіг. 1, де зображено функціональну схему конструктивного модуля суматора в залишках. Конструктивний модуль суматора у залишках містить першу логічну схему 22 кодування вхідних сигналів, другу логічну схему 24 кодування вхідних сигналів, логічну схему 21 формування першого сигналу переносу у старші розряди суматора, логічну схему 15 формування другого сигналу переносу у старші розряди суматора, селекторну схему 20 вибору результату, першу логічну схему 18 додавання за модулем 2, другу логічну схему 19 додавання за модулем 2, першу логічну схему 22 кодування вхідних сигналів, другу логічну схему 23 кодування вхідних сигналів, Конструктивний модуль також містить первинний вхід 1 сигналу SUB, перший та другий первинні бокові виходи переносу до старших розрядів 4 та 5, первинні входи операндів 6, 7, 8, перший та другий первинні бокові входи переносу з молодших розрядів 9 та 10, первинний вихід результату 13. Перший, другий та третій входи схем кодування вхідних сигналів 22 та 23 підключені до первинних входів операндів 6, 7, 8 у переліченій послідо 5 вності. Вихід логічної схеми 22 підключений до другого входу логічної схеми 21 формування першого сигналу переносу до старших розрядів суматора. Вихід другої логічної схеми 23 кодування вхідних сигналів підключений до першого входу логічної схеми 21 формування першого сигналу переносу у старші розряди суматора. Другий первинний боковий вхід 9 сигналу перенесення з молодших розрядів суматора підключений до першого входу схеми 15 формування другого сигналу перенесення в старші розряди та до третього входу другої схеми 19 додавання за модулем 2. Перший первинний боковий вхід переносу з молодших розрядів підключений до четвертого входу першої схеми 18 додавання за модулем 2, на перший, другий та третій вхід якої підключені, відповідно, перший, другий та третій первинні входи 6,7 та 9 операндів. Перший та другий первинні входи 6 та 7 операндів підключені до першого та другого входів другої схеми 19 додавання за модулем 2, а також до другого та третього входу другої логічної схеми 15 переносу в старші розряди. Вихід логічної схеми 15 підключений до другого первинного виходу перенесення в старші розряди. До першого первинного виходу перенесення в старші розряди підключено вихід логічної схеми 21 формування першого сигналу перенесення в старші розряди. Первинний вихід 14 результату підключений до селекторної схеми 20 вибору результату, на перший вхід якої підключено первинний вхід 1 сигналу SUB, а на другий та третій входи відповідно підключені виходи першої та другої схем 18 та 19 додавання по модулю 2. Запропонована корисна модель працює наступним чином. Для побудови n-розрядного суматора використовується п конструктивних модулів. На первинні входи операндів 6, 7 та 8 надходять значення розрядів з однаковою вагою (хі, уі, рі) (і=0, 1…n-і,) двійкових кодів, відповідно чисел X, Y, Р, а на виході 14 формується значення розряду з тією самою вагою числа Z (zі, і=0, 1…n-1,) де Z = (X+Y), якщо X+Y < Р (при цьому сигнал SUB активує вихід схеми 19), або Z = (X+Y- Р), якщо X+Y  Р (при цьому сигнал SUB активує вихід схеми 18). На вхід 1 надходить сигнал SUB ознаки віднімання при обчисленні значення Z. Побудований із конструктивних модулів суматор буде виконувати операцію Z=(X+Y) mod Р при умові 0  X,Y < P. Вказана умова виконується практично у всіх випадках застосування обчислень в залишках. Сигнал на вході 9 визначається переносом із молодших розрядів при додаванні без віднімання. Сигнал на вході 10 визначається переносом або позикою при додаванні з відніманням. Аналогічно, сигнал боковому виході 4 визначається переносом при додаванні без віднімання, а сигнал на виході 5 - наявністю переносу або позики при додаванні з відніманням. Вказане визначення сигналів перенесення із молодших розрядів дозволяє в випадку відсутності віднімання формувати результат на виході 14 як суму по модулю 2 значень сигналів на 6, 7 та 9 входах конструктивного модуля. При наявності віднімання результат на виході 14 формується як сума по модулю 2 значень сигналів на входах 6, 7, 8 та 10 конструктивного модуля. Логі 61654 6 чна схема 15 формує другий сигнал переносу при наявності одиничних значень принаймні на двох будь яких її входах, тобто згідно з формуванням сигналу переносу в суматорах двійкових чисел. Схеми 22 та 23 підготовлюють, а схема 21 формує одиничний сигнал при наявності запозичення або переносу при додаванні з відніманням. Функціонування схем 22 та 23 подано в Табл. 1, де виділяються випадки, коли хі, yі, pі хі + уі = рі - код 00, хі + уі, = рі + 1 - код 10, хі + уі = рі + 2 - код 01 та хі + уі < pі - код 10. Схема 21 формує на своєму виході перший сигнал переносу до старших розрядів у відповідності з таблицею 2. Таблиця 1 Формування кодованих сигналів операндів ПерПерПер- Вихід логіч- Вихід логівинний винний винний ної схеми чної схеми вхід 6 вхід 7 вхід 8 22 23 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 Таблиця 2 Формування першого сигналу переносу в старші розряди Сигнал на виході логічної схеми 23 0 0 1 1 Сигнал на виході логічної схеми 22 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 Значення на 1 0 1 0 0 1 первинних вхо1 1 0 1 1 0 дах 10 та 9. Вихід логічної Вхід 10 Вхід 9 схеми 21 При побудові суматорів вихід 4 із конструктивного модуля попереднього розряду підключається до входу 10 наступного, а вихід 5 - до входу 9. На входи 10 та 9 конструктивного модуля самого молодшого розряду подаються сигнали нульового значення. На входи 1 сигналу SUB всіх конструктивних модулів суматора подається нульове значення, якщо на первинному боковому виході 4 конструктивного модуля самого старшого розряду формується одиничне значення, а на виході 5 нульове., тобто сума чисел X та Y менша числа Р, що випливає з визначення цих сигналів. У всіх інших випадках на входи 1 конструктивних модулів подається одиничне значення. Розглянутий конструктивний модуль має порівняно незначні апаратні затрати. При реалізації на програмованих логічних інтегральних схемах (ПЛІС) на один модуль припадає 7 LUT - стандартних схем ПЛІС. Затримка сигналу в суматорі ви 7 61654 значається як nt1 + tsub, де t1 - затримка в формуванні сигналу переносу в одному модулі, яка, завдяки попередній підготовці даних на схемах 22 та 23 одночасно для всіх розрядів, відповідає швидкості одного LUT, tsub - час розповсюдження сигналу SUB по всіх розрядах. В конструктивних модулях за пп. 2 та 3 формули винаходу додатково формуються сигнали переносу в молодші розряди суматора та сигнал SUB. В склад конструктивного модуля по п.2 формули винаходу додатково введено логічну схему 24 формування першого сигналу переносу у молодші розряди суматора, логічну схему 25 формування другого сигналу переносу у молодші розряди суматора, логічну схему 26 формування сигналу SUB. Конструктивний модуль також містить перший та другий первинні бокові входи переносу зі старших розрядів 2 та 3, перший та другий первинні бокові виходи переносу до молодших розрядів 10 та 11, та первинний боковий вихід 13 сигналу SUB. Вихід логічної схеми кодування вхідних сигналів 22 підключений до третіх входів схем 24 та 25 формування першого та другого сигналів переносу в молодші розряди суматора. Вихід другої логічної схеми 23 кодування вхідних сигналів підключений четвертих входів логічних схем 24 та 25 формування першого та другого сигналу переносу в молодші розряди. До першого та другого входів схем 24 та 25 підключені відповідно перший та другий первинні бокові входи 2 та 3 переносу Із старших розрядів, а виходи підключені відповідно до першого і другого первинних бокових виходів 12 та 11 переносу в молодші розряди суматора, а також до третього та четвертого входу схеми 26 формування сигналу SUB. На перший та другий вхід цієї схеми підключені, відповідно, перший та другий первинні бокові входи перенесення 10 та 9 з молодших розрядів суматора. Сигнал на вході 3 має одиничне значення, якщо сума старших частин чисел X та Y більша або дорівнює старшій частині числа Z. Сигнал на вході 2 має одиничне значення, коли співвідношення менше або більше між числами X+Y та Р повністю визначено старшими частинами цих чисел і не залежить від значень молодших частин. Відповідним чином формуються сигнали на виходах 12 та 11 перенесення в молодші розряди. Для цього використовується попереднє кодування сигналів операндів згідно з Табл. 1. Відповідно схеми 24 та 25 формують на своїх виходах сигнали переносу у молодші розряди у відповідності з таблицею 3. Таблиця 3 Формування сигналів перенесення в молодші розряди Сигнал на виході логічної схеми 22 Сигнал на виході логічної схеми 23 Значення 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 8 на первинних входах 2 та 3 0 1 1 Вхід 2 1 0 1 Вхід 3 0 1 1 0 1 1 1 1 1 1 1 1 Вихід логічної схеми 24 1 1 1 0 0 0 0 0 1 1 1 1 Вихід логічної схеми 25 Схема 26 призначена для формування на своїх виходах сигналу віднімання SUB, який транслюється на первинний вихід 13. Вихідний код генерується у відповідності до значень вхідних кодів переносу з молодших розрядів та переносу у молодші розряди, що надходять на первинні входи 9 та 10, та генеруються на первинні виходи 11, 12. У таблиці 4 показані можливі значення сигналу на первинному виході 13, у випадку визначеності всіх вхідних даних. Конструктивний модуль за п. 3 формули винаходу відрізняється від конструктивного модуля за п. 2 формули винаходу тим, що на перший вхід логічної схеми 26 формування сигналу SUB підключено вихід схеми 21 формування першого сигналу перенесення у старші розряди, на другий вхід цієї схеми підключено вихід схеми 15 формування другого сигналу перенесення в старші розряди, а до третього та четвертого входів підключено відповідно перший та другий первинні бокові входи перенесення із старших розрядів. Функціонування схем 24, 25 та 26 аналогічно попередньому. Таблиця 4 Формування сигналу SUB Сигнал на виході логічної 0 0 1 1 схеми 24 Сигнал на виході логічної 0 1 0 1 схеми 25 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 Значення на 1 1 0 1 1 1 входах 10 та 9. Значення сигналу Вхід Вхід 9 SUB на первинному 10 боковому виходу 13 Використання конструктивних модулів за пп. 2 та 3 дає можливість гнучкої реалізації суматорів в залишках по затратах та швидкодії. На відміну від конструктивного модуля за п. 1 затрати при реалізації модулів за пп. 2 та 3 збільшуються на 3 LUT. Але виникає можливість суттєвого зменшення величини tsub часу на передачу сигналу SUB в різних конфігураціях. Найбільш швидка реалізація суматора в залишках визначається затримкою (n-2)t1 при найбільших затратах - 10 LUT на розряд. При цьому можливі проміжні реалізації з меншою швидкістю та меншими затратами, аж до вказаного раніше значення затримки nt1 + tsub та затратами 7 LUT на розряд. Достовірність роботи суматорів, побудованих на запропонованому конструктивному модулі, була перевірена шляхом моделювання за допомогою САПР ф. Хіlіnх WebPACK ISE. 9 61654 10 11 61654 12 13 Комп’ютерна верстка Г. Паяльніков 61654 Підписне 14 Тираж 23 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601