Устройство для формирования остатка по модулю семь

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ СЕМЬ(71) Заявитель Белорусский государственный университет(72) Авторы Авгуль Леонид Болеславович Булаш Юрий Леонидович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для формирования остатка по модулю семь, содержащее трехоперандный сумматор по модулю семь, выходы старшего, среднего и младшего разрядов которого соединены соответственно с выходами старшего, среднего и младшего разрядов устройства,9994 1 2007.12.30 отличающееся тем, что содержит три многовходовых одноразрядных сумматора по модулю семь, -й вход (1,4, 5, 6,3 - разрядность входного слова) первого из которых соединен с входом (3-2)-го разряда входного слова, вход (3-1)-го разряда которого соединен с -м входом второго многовходового одноразрядного сумматора по модулю семь, вход 3-го разряда соединен с -м входом третьего многовходового одноразрядного сумматора по модулю семь, выход старшего разряда которого соединен с первым входом группы входов средних разрядов трехоперандного сумматора по модулю семь,второй вход которой соединен с выходом младшего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом среднего разряда первого многовходового одноразрядного сумматора по модулю семь, выход старшего разряда которого соединен с первым входом группы входов старших разрядов трехоперандного сумматора по модулю семь, второй вход которой соединен с выходом среднего разряда второго многовходового одноразрядного сумматора по модулю семь,третий вход соединен с выходом младшего разряда третьего многовходового одноразрядного сумматора по модулю семь, выход среднего разряда которого соединен с первым входом группы входов младших разрядов трехоперандного сумматора по модулю семь,второй вход которой соединен с выходом старшего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом младшего разряда первого многовходового одноразрядного сумматора по модулю семь. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики. Известно устройство для формирования остатка по модулю 2-1, которое при 3 содержит шесть блоков вычисления фундаментальных симметрических булевых функций,девять элементов ИЛИ и сумматор унитарных кодов по модулю семь 1. При 3 устройство вычисляет свертку по модулю семь -разрядных двоичных чисел. Недостатками устройства являются высокая конструктивная сложность и низкое быстродействие, определяемое глубиной схемы. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для сложения по модулю семь, содержащее шесть элементов сложения по модулю два, три мажоритарных элемента с порогом два и двадцать четыре элемента И 2. Устройство выполняет сложение трех трехразрядных двоичных чисел по модулю семь и может быть использовано для формирования остатка по модулю семь девятиразрядного двоичного числа. Недостатком известного устройства является ограниченная разрядность сворачиваемых по модулю семь двоичных чисел. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет формирования остатка по модулю семь -разрядных двоичных чисел. Названный технический результат достигается путем введения в состав устройства трех многовходовых одноразрядных сумматоров по модулю семь. Устройство для формирования остатка по модулю семь содержит трехоперандный сумматор по модулю семь, выходы старшего, среднего и младшего разрядов которого соединены соответственно с выходами старшего, среднего и младшего разрядов устройства. В отличие от прототипа, устройство содержит три многовходовых одноразрядных сумматора по модулю семь, -й вход (1,4, 5, 6,3 - разрядность входного слова) первого из которых соединен с входом (3-2)-го разряда входного слова. Вход(3-1)-го разряда входного слова соединен с -м входом второго многовходового одноразрядного сумматора по модулю семь. Вход 3-го разряда входного слова соединен с -м входом третьего многовходового одноразрядного сумматора по модулю семь. Выход старшего разряда третьего многовходового одноразрядного сумматора по модулю семь соединен с первым входом группы входов средних разрядов трехоперандного 2 9994 1 2007.12.30 сумматора по модулю семь, второй вход которой соединен с выходом младшего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом среднего разряда первого многовходового одноразрядного сумматора по модулю семь. Выход старшего разряда первого многовходового одноразрядного сумматора по модулю семь соединен с первым входом группы входов старших разрядов трехоперандного сумматора по модулю семь, второй вход которой соединен с выходом среднего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом младшего разряда третьего многовходового одноразрядного сумматора по модулю семь. Выход среднего разряда третьего многовходового одноразрядного сумматора по модулю семь соединен с первым входом группы входов младших разрядов трехоперандного сумматора по модулю семь, второй вход которой соединен с выходом старшего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом младшего разряда первого многовходового одноразрядного сумматора по модулю семь. На фигуре представлена схема устройства для формирования остатка по модулю семь. Устройство содержит три многовходовых одноразрядных сумматора по модулю семь 1, 2 и 3, трехоперандный сумматор по модулю семь 4,входов 51-5 разрядов входного слова с номерами 3-2 (1,4, 5, 6,3 - разрядность входного слова),входов 61-6 разрядов входного слова с номерами 3-1,входов 71-7 разрядов входного слова с номерами 3, выходы старшего, среднего и младшего разрядов соответственно 8, 9 и 10. Поясним принцип работы устройства. Устройство вычисляет остаток по модулю семь -разрядного двоичного слова 2-1 х 2-2 х-12 х 2 х 1,0, 1,1,412237,(1) где 1, 2, 30, 1. Без потери общности полагаем, что 3,4, 5, 6,Представим (1) в виде 3 3 34123337, 1 , 3 , 30, 1. 2 3 2 31 Принимая во внимание (3)-(5), преобразуем (2) к виду 2 2 3(41211814 2231618 343 )71 2 3 2 2 3 9994 1 2007.12.30 где 1412111 2 2 2 2 24 22312 3 343213 . 3 2 Устройство для формирования остатка по модулю семь работает в соответствии с соотношениями (3)-(6). Многовходовые (-входовые) одноразрядные сумматоры по модулю семь 1, 2 и 3 вычисляют соответственно модулярные суммы 1, 2 и 3. Трехоперандный сумматор по модулю семь 4 выполняет сложение по модулю семь трех трехразрядных двоичных чисел С 1,С 2 и С 3 согласно (6). При этом кортеж двоичных переменных (1 ,2 , 3 ) поступает на 1 2 3 2 3 входы старших разрядов сумматора 4, кортеж (1 , 3 , 1 ) - на входы средних разрядов 2 2 сумматора 4, кортеж (1 , 1 , 3 ) - на входы младших разрядов сумматора 4. 3 2 Устройство для формирования остатка по модулю семь работает следующим образом. На входы 51, 52, , 5 подаются двоичные разряды х 1, х 4, , х-2 входного слова 2-1 х 2-2 х-12 х 21, на входы 61, 62, , 6 - разряды х 2, х 5, , х-1, на входы 71, 72, , 7 - разряды х 3, х 6, , х. На выходах 8, 9 и 10 формируются соответственно старший 1, средний 2 и младший 3 разряды результата 41223 свертки по модулю семь входного слова . Проиллюстрируем работу устройства на примере свертки по модулю семь двоичного словах 24 х 23 х 2 х 1111001011001011101101101 (24,8). Очевидно, что на входы первого восьмивходового одноразрядного сумматора по модулю семь 1 поступает вектор переменных (х 1, х 4 х 22)(1,1,1,1,1,1,1,1) на входы второго сумматора 2 - вектор (х 2, х 5 х 23)(0,0,0,1,0,1,0,1) на входы третьего сумматора 3 вектор (х 3, х 6 х 24)(1,1,1,0,0,0,0,1). На выходах первого сумматора 1 формируется кор 2 2 теж (1 , 1 , 1 )(0,0,1) на выходах второго сумматора 2 - кортеж (1 ,2 ,3 )(0,1,1) на 1 2 3 2 3 выходах третьего сумматора 3 - кортеж (1 , 3 ,3 )(1,0,0). 2 3 Тогда на входы старших разрядов трехоперандного сумматора по модулю семь 4 посту 2 3 пает кортеж (1 , 3 , 3 )(0,1,0) на входы средних разрядов - кортеж (1 ,3 , 1 )(0,1,1),1 2 3 2 2 на входы младших разрядов - кортеж (1 , 1 , 3 )(1,0,0). 3 2 На выходах 8, 9 и 10 устройства (выходах сумматора 4) формируются разряды соответственно 10, 21 и 30, составляющие позиционный двоичный код результата свертки по модулю семь входного слова 2 3 241223(4(123 )2(131 )113 )72. 1 2 3 2 3 2 В десятичной системе счисления 223 х 24222 х 232 х 2115046509. Следовательно, 715046509 72. Достоинствами устройства для формирования остатка по модулю семь являются простая конструкция и высокое быстродействие. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.