Устройство для сложения N двоичных чисел в последовательном коде по модулю три

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯДВОИЧНЫХ ЧИСЕЛ В ПОСЛЕДОВАТЕЛЬНОМ КОДЕ ПО МОДУЛЮ ТРИ(71) Заявитель Белорусский государственный университет(72) Авторы Авгуль Леонид Болеславович Булаш Юрий Леонидович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для сложениядвоичных чисел (2) в последовательном коде по модулю три, содержащее многовходовый одноразрядный сумматор по модулю три, -й вход(1,) которого соединен с -м информационным входом устройства, два двухступенчатых синхронных -триггера, входы синхронизации которых соединены с входом синхронизации устройства, а входы обнуления - с входом начальной установки устройства, отличающееся тем, что информационный вход первого синхронного -триггера соединен с выходом старшего разряда многовходового одноразрядного сумматора по модулю три, а прямой выход - с первым выходом устройства и (1)-м входом многовходового одноразрядного сумматора по модулю три, выход младшего разряда которого соединен с информационным входом второго синхронного -триггера, прямой выход которого соединен со вторым выходом устройства и (2)-м и (3)-м входами многовходового одноразрядного сумматора по модулю три. 9837 1 2007.10.30 Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики. Известно устройство для сложениядвоичных чисел в последовательном коде, содержащее многовходовый одноразрядный сумматор и р сдвигающих регистров(2, где) 1. Недостатком устройства является невозможность вычисления остатка по модулю три от суммыдвоичных чисел. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для сложения шести -разрядных двоичных чисел в последовательно-параллельном коде, содержащее два семивходовых одноразрядных сумматора, полусумматор, блок суммирования и три двухступенчатых синхронных -триггера 2. Недостатком известного устройства является невозможность сложения по модулю три-разрядных двоичных чисел. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления остатка по модулю три от суммы-разрядных двоичных чисел. Названный технический результат достигается путем изменения связей между элементами устройства. Устройство для сложениядвоичных чисел (2) в последовательном коде по модулю три содержит многовходовый одноразрядный сумматор по модулю три, -й вход(1,) которого соединен с -м информационным входом устройства, и два двухступенчатых синхронных -триггера, входы синхронизации которых соединены с входом синхронизации устройства, а входы обнуления - с входом начальной установки устройства. В отличие от прототипа информационный вход первого -триггера соединен с выходом старшего разряда многовходового одноразрядного сумматора по модулю три, а прямой выход - с первым выходом устройства и (1)-м входом многовходового одноразрядного сумматора по модулю три. Выход младшего разряда многовходового одноразрядного сумматора по модулю три соединен с информационным входом второго -триггера, прямой выход которого соединен со вторым выходом устройства и (2)-м и (3)-м входами многовходового одноразрядного сумматора по модулю три. На чертеже (фиг. 1) представлена схема устройства для сложениядвоичных чисел в последовательном коде по модулю три. Устройство содержит многовходовый одноразрядный сумматор по модулю три 1, два двухступенчатых синхронных -триггера 2 и 3,информационных входов 41-4, вход синхронизации 5, вход начальной установки 6 и два выхода 7 и 8. Поясним принцип работы устройства. Устройство выполняет сложение по модулю три-разрядных двоичных чисел Х 2-1 х,2-2 х,-12 х,2 х,1, ,0,1,1,,1,, поступающих одновременно на входы устройства в последовательном коде младшими разрядами вперед 11 Из (2) следует, что нечетные разряды ,1, х,3, , х,-1 должны суммироваться по модулю три с весом 2, а четные разряды ,2, ,4, , , - с весом 21,1,. Принимая во внимание (2), сумму по модулю три 212 , 1 ,20, 1, первых где 00. Выравнивая веса суммируемых разрядов, перепишем (4) в виде Таким образом, соотношения (5) определяют процедуру вычисления суммы по модулю три-разрядных двоичных чисел Х как итерационный -шаговый процесс, на -м шаге которого (1) выполняется сложение по модулю триодноименных разрядов операндов 1 2 , , и трех разрядов накопленной частичной суммы-111 , 11 и 21 на нечетном шаге сложения и 11 ,21 и 21 на четном шаге сложения. При этом все участвующие в сложении по модулю три одноразрядные двоичные числа имеют одинаковые веса - 20 на нечетном шаге сложения и 21 на четном шаге сложения. В устройстве сложение по модулю три 3 одноразрядных двоичных чисел выполняется многовходовым одноразрядным сумматором по модулю три 1, а для хранения раз рядов 1 и 2 накапливаемой частичной суммыиспользуются триггеры 2 и 3. При этом выход старшего разряда (с весом 21) сумматора 1 соединен с информационным входом первого триггера 2, а выход младшего разряда (с весом 20) - с информационным входом второго триггера 3. Сигналы с прямых выходов триггеров 2 и 3 подаются на информационные входы сумматора 1, причем сигнал с выхода триггера 3 - в раздвоенном виде. Напомним, что в общем случае многовходовый одноразрядный сумматор по модулю три выполняет сложение по модулю триодноразрядных двоичных чисел (с весом 20) 9837 1 2007.10.30212(12)3,где 1, 20,1 - значения соответственно старшего и младшего разрядов результата,формируемых на выходах сумматора. Такой сумматор может выполнять и сложение по модулю три одноразрядных двоичных чисел, имеющих вес 21. Действительно,(2 у 12 у 22 у)3(2(212 3(4122) 3221.(6) Из (6) следует, что при сложении одноразрядных двоичных чисел с весом 21 старший разряд результата формируется на выходе младшего разряда сумматора, а младший разряд результата - на выходе старшего разряда сумматора. Предлагаемое устройство построено с учетом соотношений (5) и (6). Обозначим 11 и 21 - состояния соответственно первого 2 и второго 3 триггеров 0 перед началом -го шага сложения, 1 и 10 ,00 . 2 Тогда работа устройства может быть описана следующими соотношениями Распишем выполнение процедуры (7) по шагам (для четных значений ). Результат 212 и 112 , 21 . 2 Таким образом, после выполнения -го шага во втором триггере 3 будет записан старший разряд 1 результата, а в первом триггере 2 - младший разряд 2 результата вычисления остатка по модулю три от суммы-разрядных двоичных чисел. Очевидно, если разрядностьнечетная, то по окончании -шага старший разряд 1 результата будет записан в первом триггере 2, а младший разряд 2 - во втором триггере 3. Устройство для сложениядвоичных чисел в последовательном коде по модулю три работает следующим образом. На вход начальной установки 6 подается импульс, обнуляющий триггеры 2 и 3. На информационные входы 41,42, , 4 подаются последовательно во времени разряды 4 9837 1 2007.10.30 2 , , суммируемых по модулю три чисел 1, 2, ,(начиная с младших разрядов 1,1, 2,1, , ,), сопровождаемые серией изтактовых импульсов, поступающих на вход синхронизации 5. После окончания последнего (-го) тактового импульса в триггерах 2 и 3 будут запи саны двоичные разряды 1 и 2 результата операции 3 , которые поступают 1 на выходы 7 и 8 устройства. Работу устройства проиллюстрируем на примере сложения шести восьмиразрядных двоичных чисел 110111010, Х 201100111, Х 301001100, Х 410011110,Х 510100110, Х 600011101. В таблице (фиг. 2) для каждого такта (шага) приведены значения сигналов на входе многовходового одноразрядного сумматора по модулю три 1 и значения сигналов на выходах старшего (поступает на вход первого триггера 2) и младшего (поступает на вход второго триггера 3) разрядов сумматора 1 с указанием их принадлежности к старшему 1 или младшему 2 разрядам частичной суммы . Из фиг. 2 видно, что в конце последнего (восьмого) такта сложения в первый триггер 2 8 будет записана логическая единица (81 ), а во второй триггер 3 - логический ноль ( 10 ). 26 8 Следовательно,2123821801 . 21 В десятичной системе счисления суммируемые в рассмотренном примере числа имеют вид Х 1186, Х 2103, Х 376, Х 4158, Х 5166, Х 629.6 Тогда 3718301 .1 Отметим, что из рассмотренного принципа работы устройства непосредственно следует, что устройство может выполнять сложение по модулю три двоичных чисел, поступающих и старшими разрядами вперед. Если разрядностьсуммируемых чисел нечетная, то вес по модулю три старшего разряда равен 20, и в конце первого такта в триггеры 2 и 3 будут записаны соответственно значения 1 и 1 , а в конце -го такта - 1 и. 1 2 2 Если разрядностьсуммируемых чисел четная, то вес по модулю три старшего разряда равен 21, и в конце первого такта в триггеры 2 и 3 будут записаны соответственно зна чения 1 и 1 , а в конце -го такта - 1 и. 2 1 2 Иными словами, при подаче суммируемых по модулю три чисел старшими разрядами вперед на входы устройства независимо от величиныпо окончании последнего такта старший разряд результата будет записан в первый триггер 2, младший разряд результата- во второй триггер 3. Укажем, что при сложении по модулю три младшими или старшими разрядами вперед в общем случае накапливаемые частичные суммыпри 1-1 не совпадают, однако в любом случае на последнем такте 21212 . 2 Процесс сложения чисел (из рассмотренного выше примера) по модулю три старшими разрядами вперед иллюстрируется таблицей (фиг. 3). Из фиг. 3 следует, что в конце последнего (восьмого) такта сложения в первый триггер 8 2 будет записан логический ноль ( 10 ), а во второй триггер 3 - логическая единица 8(81 ). Таким образом, результат 821801 . 2 2 Достоинствами устройства для сложениядвоичных чисел в последовательном коде по модулю три являются простая конструкция, высокое быстродействие и широкие функциональные возможности. 9837 1 2007.10.30 Источники информации 1. Патент РБ 4931, МПК 06 7/50, 2003. 2. Патент РБ 5224, МПК 06 7/50, 2003 (прототип). Работа устройства при сложении чисел по модулю три младшими разрядами вперед Сигналы на вхо такСигналы на входах сумматора по модулю три 1 дах триггеров та 1 1 1 Фиг. 2 Работа устройства при сложении чисел по модулю три старшими разрядами вперед Сигналы на вхо такСигналы на входах сумматора по модулю три 1 дах триггеров та 1 1 1 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.