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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯДВОИЧНЫХ ЧИСЕЛ В ПОСЛЕДОВАТЕЛЬНОМ КОДЕ ПО МОДУЛЮ ПЯТНАДЦАТЬ(71) Заявитель Белорусский государственный университет(72) Авторы Авгуль Леонид Болеславович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для сложениядвоичных чисел (2) в последовательном коде по модулю пятнадцать, содержащее четыре двухступенчатых синхронных -триггера, вход синхронизации -го (1, 2, 3, 4) из которых соединен с входом синхронизации устройства, вход обнуления соединен с входом начальной установки устройства, отличающееся тем, что содержит многовходовый одноразрядный сумматор по модулю пятнадцать, -й(1, ) вход которого соединен с -м информационным входом устройства, а -й выход с весом 24- соединен с информационным входом -го -триггера, прямой выход первого-триггера соединен с первым выходом устройства и входами многовходового одноразрядного сумматора по модулю пятнадцать с (1)-го по (4)-й, прямой выход второго-триггера соединен со вторым выходом устройства, (5)-м и (6)-м входами многовходового одноразрядного сумматора по модулю пятнадцать, прямой выход третьего-триггера соединен с третьим выходом устройства и (7)-м входом многовходового одноразрядного сумматора по модулю пятнадцать, прямой выход четвертого -триггера соединен с четвертым выходом устройства и входами многовходового одноразрядного сумматора по модулю пятнадцать с (8)-го по (15)-й. 10199 1 2008.02.28 Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики. Известен сумматор по модулю пятнадцать, содержащий восемь элементов И, шесть элементов равнозначности и семь элементов сложения по модулю два 1. Сумматор выполняет сложение по модулю пятнадцать двух четырехразрядных двоичных чисел. Недостатком сумматора является невозможность сложения по модулю пятнадцатьдвоичных чисел. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для сложения-разрядных двоичных чисел в последовательном коде, содержащее многовходовый одноразрядный сумматор и группу триггеров, объединенных всдвигающих регистров (2, где) 2. Недостатком известного устройства является невозможность сложениядвоичных чисел по модулю пятнадцать. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления остатка по модулю пятнадцать от суммы-разрядных двоичных чисел, поступающих на его входы в последовательном коде. Названный технический результат достигается путем введения в состав устройства многовходового одноразрядного сумматора по модулю пятнадцать. Устройство для сложениядвоичных чисел (2) в последовательном коде по модулю пятнадцать содержит четыре двухступенчатых синхронных -триггера, вход синхронизации -го (1, 2, 3, 4) из которых соединен с входом синхронизации устройства,вход обнуления соединен с входом начальной установки устройства. В отличие от прототипа, устройство содержит многовходовый одноразрядный сумматор по модулю пятнадцать, -й (1, ) вход которого соединен с -м информационным входом устройства,-й выход (с весом 24-) соединен с информационным входом -го-триггера. Прямой выход первого -триггера соединен с первым выходом устройства и входами многовходового одноразрядного сумматора по модулю пятнадцать с (1)-го по (4)-й. Прямой выход второго -триггера соединен со вторым выходом устройства,(5)-м и (6)-м входами многовходового одноразрядного сумматора по модулю пятнадцать. Прямой выход третьего -триггера соединен с третьим выходом устройства и(7)-м входом многовходового одноразрядного сумматора по модулю пятнадцать. Прямой выход четвертого -триггера соединен с четвертым выходом устройства и входами многовходового одноразрядного сумматора по модулю пятнадцать с (8)-го по(15)-й. На фигуре представлена схема устройства для сложениядвоичных чисел в последовательном коде по модулю пятнадцать. Устройство содержит многовходовый одноразрядный сумматор по модулю пятнадцать 1, четыре двухступенчатых синхронных -триггера 2, 3, 4 и 5,информационных входов 61 - 6, вход синхронизации 7, вход начальной установки 8 и четыре выхода 9, 10,11 и 12. Поясним принцип работы устройства. Устройство выполняет сложение по модулю пятнадцать-разрядных двоичных чисел 21,22,12, 2,1 ,,0, 1,1,,1,, поступающих одновременно на входы устройства в последовательном коде младшими разрядами вперед Из (2) следует, что разряды,1 ,,5 ,3 должны суммироваться по модулю пятнадцать с весом 20, разряды, 2 ,,6 ,2 - с весом 21, разряды,3 ,,7 ,1 - с весом 22, а разряды, 4 ,,8 ,- с весом 23,1,. Принимая во внимание (2), сумму по модулю пятнадцать 0, 1, 2, , 14 первых где 00. Частичную суммупо модулю пятнадцать представим четырехразрядным двоичным кодом 1 ,2 , 3 ,4 и будем вычислять с учетом весов ее разрядов на каждом шаге сложения 1 ,2 ,3 ,4 - веса разрядов суммы . Принимая во внимание (4), имеем при 1 10199 1 2008.02.28 Далее процесс вычисления частичных сумм по модулю пятнадцать аналогичен рассмотренному выше. Из (6)-(10) следует, что на каждом шаге сложения частичные суммы , а в конечном итоге и результат , могут быть вычислены путем сложения по модулю пятнадцать 15 одноразрядных двоичных чисел -одноименных разрядов 1 2, операндов 1,-1. При этом, независимо от величины , все участвующие в сложении числа имеют вес,равный 20 По коду 1 ,2 , 3 ,4 значениеможет быть вычислено по формуле (5) с учетом весов ее разрядов на данном шаге Соответствие кодов 1 ,2 , 3 ,4 значениям , полученное согласно (12)-(15), приведено в табл. 1. Таким образом, соотношение (11) определяет процедуру вычисления суммы по модулю пятнадцать-разрядных двоичных чисел Х как итерационный -шаговый процесс,на -м шаге которого (1) выполняется сложение по модулю пятнадцатьодноименных разрядов операндов 1 2 , и пятнадцати одноразрядных двоичных В устройстве сложение по модулю пятнадцать 15 одноразрядных двоичных чисел выполняется многовходовым одноразрядным сумматором по модулю пятнадцать 1, а для хранения разрядов 1 ,2 ,3 и 4 накапливаемой частичной суммыиспользуются тригге 5 10199 1 2008.02.28 ры 2, 3, 4 и 5 соответственно. При этом выход разряда сумматора 1 с весом 23 соединен с информационным входом первого триггера 2, выход разряда сумматора 1 с весом 22 с информационным входом второго триггера 3, выход разряда сумматора 1 с весом 21 с информационным входом третьего триггера 4, а выход разряда сумматора 1 с весом 20 с информационным входом четвертого триггера 5. тий триггер 4 - разряд 3 , а четвертый триггер 5 - разряд 4 частичной суммы . Сигнал с прямого выхода триггера 2 подается одновременно на четыре входа сумматора 1, сигнал с прямого выхода триггера 3 - одновременно на два входа сумматора 1, сигнал с прямого выхода триггера 4 - на один вход сумматора 1, а сигнал с прямого выхода триггера 5 - одновременно на восемь входов сумматора 1. В общем случае многовходовый одноразрядный сумматор по модулю пятнадцать выполняет сложение по модулю пятнадцатьодноразрядных двоичных чисел (с весом 20) 842234(12) 15,где , 2, 3, 40,1 - значения соответственно разрядов результата, формируемых на выходах сумматора с весами 23, 22, 21, 20 соответственно. Обозначим 11,21 , 31 и 41 - состояния соответственно первого 2, второго 3,третьего 4 и четвертого 5 триггеров перед началом -го шага сложения и 0 0 10,00, 30,00, 1. 2 4 Тогда с учетом (11) работа устройства может быть описана следующими соотношениями Устройство построено согласно соотношениям (16). Устройство для сложениядвоичных чисел в последовательном коде по модулю пятнадцать работает следующим образом. На вход начальной установки 8 подается импульс, обнуляющий триггеры 2, 3, 4 и 5. На информационные входы 61, 62, , 6 подаются последовательно во времени разряды 2 , , суммируемых по модулю пятнадцать чисел 1, 2, ,(начиная с младших разрядов х 1,1, х 2,1, , ,), сопровождаемые серией изтактовых импульсов, поступающих на вход синхронизации 7. После окончания последнего (-го) тактового импульса в триггерах 2, 3, 4 и 5 будут записаны соответственно двоичные разряды 1 ,,3 икода частичной суммы , оп 2 4 ределяющие результат операции Сигналы с прямых выходов триггеров 2, 3, 4 и 5 поступают соответственно на выходы 9, 10, 11 и 12 устройства. 10199 1 2008.02.28 Работу устройства проиллюстрируем на примере сложения по модулю пятнадцать семи восьмиразрядных двоичных чисел Х 110110101, Х 211010011, Х 311011101,Х 401011011, Х 510100111, Х 610001101, Х 711000101. В табл. 2 для каждого такта (шага) приведены значения сигналов на входе многовходового одноразрядного сумматора по модулю пятнадцать 1 и значения сигналов на его выходах на первом выходе (с весом 23) - 1 (поступает на вход первого триггера 2), на втором выходе (с весом 22) -2 (поступает на вход второго триггера 3), на третьем выходе(с весом 21) - 3 (поступает на вход третьего триггера 4), на четвертом выходе (с весом 20) -4(поступает на вход четвертого триггера 5). Кроме того, в таблице указаны веса 1 ,2 ,3 и 4 соответствующих разрядов для вычисления частичной суммы по модулю пятнадцатьв данном такте. Из табл. 2 видно, что в конце последнего (восьмого) такта сложения в первый триггер 2 8 будет записан логический ноль 10 , во второй триггер 3 - логический ноль 80 , в 2 8 Принимая во внимание данные табл.2, код 1 , 8 , 8 , 8(0, 0, 1, 1) соответствует 2 3 4 остатку, равному 9 В десятичной системе счисления суммируемые в рассмотренном примере числа имеют вид Х 1181, Х 2211, Х 3221, Х 491, Х 5167, Х 6141, Х 7197. 7 Тогда 151209159 . 1 Отметим, что из рассмотренного принципа работы устройства непосредственно следует, что устройство может выполнять сложение по модулю пятнадцать двоичных чисел и при их разрядности , не кратной четырем. Рассмотрим примеры сложения по модулю пятнадцать семи семи-, шести- и пятиразрядных двоичных чисел, которые могут быть получены из чисел в рассмотренном выше примере путем отбрасывания соответственно одного, двух и трех старших разрядов (в этом случае можно воспользоваться данными табл. 2). 1)7 10110101, Х 21010011, Х 31011101, Х 41011011, Х 50100111,Х 60001101, Х 71000101. 7 7 Из табл. 2 следует, что код 1 ,7 ,3 ,7(1, 0, 0, 1) соответствует остатку, равному 6 2 4 В десятичной системе счисления суммируемые числа имеют вид Х 153, Х 283,Х 393, Х 491, Х 539, Х 613, Х 769. 7 Тогда 15441156 . В десятичной системе счисления суммируемые числа имеют вид 153, Х 219,Х 329, Х 427, Х 539, Х 613, Х 75. 7 Тогда 15185155 . В десятичной системе счисления суммируемые числа имеют вид Х 121, Х 219,Х 329, Х 427, Х 57, Х 613, Х 75. 7 Тогда 15121151 . 1 Достоинствами устройства для сложениядвоичных чисел в последовательном коде по модулю пятнадцать являются простая конструкция, высокое быстродействие и широкие функциональные возможности. Таблица соответствия кодов формируемым остаткам по модулю пятнадцать Таблица 2 Работа устройства при сложении чисел по модулю пятнадцать младшими разрядами впередтакта 1,Сигналы на входах сумматора по модулю пятнадцать 12,Сигналы на входах триггеров Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.