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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ С НАКОПЛЕНИЕМ(72) Авторы Авгуль Леонид Болеславович Булаш Юрий Леонидович Терешко Сергей Михайлович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для формирования остатка по модулю пять, отличающееся тем, что выполнено с возможностью накопления остатка и содержит , где 1, 2, 3,4 - разрядность входного слова, блоков модулярного сложения унитарного кода с двоичной тетрадой, вход разряда двоичной тетрады с весом 20 -го, где 1,, из которых соединен с входом (4 - 3)-го разряда входного слова, вход разряда двоичной тетрады с весом 21 соединен с входом (4 - 2)-го разряда входного слова, вход разряда двоичной тетрады с весом 22 соединен с входом (4 - 1)-го разряда входного слова, вход разряда двоичной тетрады с весом 23 соединен с входом 4-го разряда входного слова, вход -го, где 1,5 , разряда входного унитарного кода соединен с входом равно- 1 первого блока, выход равно- 1-го блока соединен с выходом -го разряда выходного унитарного кода, при этом каждый блок модулярного сложения унитарного кода с двоичной тетрадой содержит четыре группы 11754 1 2009.04.30 элементов 2-2 И-2 ИЛИ по пять элементов в каждой и четыре элемента НЕ, выход первого из которых соединен с первым входом -го элемента 2-2 И-2 ИЛИ первой группы, второй вход которого соединен с входом первого элемента НЕ и входом разряда двоичной тетрады с весом 20, выход второго элемента НЕ соединен с первым входом -го элемента 2-2 И 2 ИЛИ второй группы, второй вход которого соединен с входом второго элемента НЕ и входом разряда двоичной тетрады с весом 21, выход третьего элемента НЕ соединен с первым входом -го элемента 2-2 И-2 ИЛИ третьей группы, второй вход которого соединен с входом третьего элемента НЕ и входом разряда двоичной тетрады с весом 22, выход четвертого элемента НЕ соединен с первым входом -го элемента 2-2 И-2 ИЛИ четвертой группы, второй вход которого соединен с входом четвертого элемента НЕ и входом разряда двоичной тетрады с весом 23, вход равно- 1, где 1,4 , блока соединен с третьим входом -го элемента 2-2 И-2 ИЛИ первой группы и четвертым входом (1)-го элемента 2-2 И-2 ИЛИ первой группы, вход равно четырем блока соединен с третьим входом пятого элемента 2-2 И-2 ИЛИ первой группы и четвертым входом первого элемента 2-2 И-2 ИЛИ первой группы, выход -го, где 1, 2, 3, элемента 2-2 И-2 ИЛИ первой группы соединен с третьим входом -го элемента 2-2 И-2 ИЛИ второй группы и четвертым входом (2)-го элемента 2-2 И-2 ИЛИ второй группы, выход четвертого элемента 2-2 И-2 ИЛИ первой группы соединен с третьим входом четвертого элемента 2-2 И-2 ИЛИ второй группы и четвертым входом первого элемента 2-2 И-2 ИЛИ второй группы, выход пятого элемента 2-2 И-2 ИЛИ первой группы соединен с третьим входом пятого элемента 2-2 И-2 ИЛИ второй группы и четвертым входом второго элемента 2-2 И-2 ИЛИ второй группы, выход первого элемента 2-2 И-2 ИЛИ второй группы соединен с третьим входом первого элемента 22 И-2 ИЛИ третьей группы и четвертым входом пятого элемента 2-2 И-2 ИЛИ третьей группы, выход (1)-го элемента 2-2 И-2 ИЛИ второй группы соединен с третьим входом(1)-го элемента 2-2 И-2 ИЛИ третьей группы и четвертым входом -го элемента 2-2 И 2 ИЛИ третьей группы, выход первого элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ четвертой группы и четвертым входом четвертого элемента 2-2 И-2 ИЛИ четвертой группы, выход второго элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом второго элемента 2-2 И-2 ИЛИ четвертой группы и четвертым входом пятого элемента 2-2 И-2 ИЛИ четвертой группы, выход (2)-го элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом (2)-го элемента 2-2 И 2 ИЛИ четвертой группы и четвертым входом -го элемента 2-2 И-2 ИЛИ четвертой группы,выход -го элемента 2-2 И-2 ИЛИ четвертой группы соединен с выходом равно- 1 блока. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики. Известен многовходовый одноразрядный сумматор по модулю пять, содержащий четыре элемента сложения по модулю два,групп элементов И по четыре элемента в каждой и 5 мажоритарных элементов, -й из которых имеет порог, равный 2 (101 разрядность входного слова 1, 2, 3,1, 2 5) 1. Сумматор формирует на своих выходах трехразрядный позиционный двоичный код суммы по модулю пять числа единиц, содержащихся во входном -разрядном двоичном слове. Недостатком многовходового одноразрядного сумматора по модулю пять является невозможность формирования остатка по модулю пять числа, представленного в позиционном двоичном коде. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для формирования остатка по модулю 2 11754 1 2009.04.30 пять, содержащее четыре блока вычисления симметрических булевых функций, двенадцать элементов ИЛИ, два сумматора по модулю пять и вычитатель по модулю пять 2. Недостатком известного устройства является высокая конструктивная сложность. Изобретение направлено на решение задачи упрощения конструкции устройства для формирования остатка по модулю пять. Названный технический результат достигается путем использования для построения устройства блоков модулярного сложения унитарного кода с двоичной тетрадой. Устройство для формирования остатка по модулю пять с накоплением содержит , где 1, 2, 3,4 - разрядность входного слова, блоков модулярного сложения унитарного кода с двоичной тетрадой. Вход разряда двоичной тетрады с весом 20 -го блока, где 1,, соединен с входом (4 - 3)-го разряда входного слова, вход разряда двоичной тетрады с весом 21 соединен с входом (4 - 2)-го разряда входного слова, вход разряда двоичной тетрады с весом 22 соединен с входом (4 - 1)-го разряда входного слова, вход разряда двоичной тетрады с весом 23 соединен с входом 4-го разряда входного слова. Вход -го разряда, где 1, 5 , входного унитарного кода соединен с входом равно- 1 первого блока. Выход равно- 1 -го блока, где 1,1 , соединен с входом равно- 1 (1)-го блока. Выход равно- 1 -го блока соединен с выходом -го разряда выходного унитарного кода. Каждый блок модулярного сложения унитарного кода с двоичной тетрадой содержит четыре группы элементов 2-2 И-2 ИЛИ по пять элементов в каждой и четыре элемента НЕ. Выход первого элемента НЕ соединен с первым входом -го элемента 2-2 И-2 ИЛИ первой группы, второй вход которого соединен с входом первого элемента НЕ и входом разряда двоичной тетрады с весом 20. Выход второго элемента НЕ соединен с первым входом -го элемента 2-2 И-2 ИЛИ второй группы, второй вход которого соединен с входом второго элемента НЕ и входом разряда двоичной тетрады с весом 21. Выход третьего элемента НЕ соединен с первым входом -го элемента 2-2 И-2 ИЛИ третьей группы, второй вход которого соединен с входом третьего элемента НЕ и входом разряда двоичной тетрады с весом 22. Выход четвертого элемента НЕ соединен с первым входом -го элемента 2-2 И-2 ИЛИ четвертой группы, второй вход которого соединен с входом четвертого элемента НЕ и входом разряда двоичной тетрады с весом 23. Вход равно- 1 блока, где 1, 4 , соединен с третьим входом -го элемента 2-2 И-2 ИЛИ первой группы и четвертым входом(1)-го элемента 2-2 И-2 ИЛИ первой группы. Вход равно четырем блока соединен с третьим входом пятого элемента 2-2 И-2 ИЛИ первой группы и четвертым входом первого элемента 2-2 И-2 ИЛИ первой группы. Выход -го, где 1, 2, 3, элемента 2-2 И-2 ИЛИ первой группы соединен с третьим входом -го элемента 2-2 И-2 ИЛИ второй группы и четвертым входом (2)-го элемента 2-2 И-2 ИЛИ второй группы. Выход четвертого элемента 2-2 И-2 ИЛИ первой группы соединен с третьим входом четвертого элемента 2-2 И-2 ИЛИ второй группы и четвертым входом первого элемента 2-2 И-2 ИЛИ второй группы. Выход пятого элемента 2-2 И-2 ИЛИ первой группы соединен с третьим входом пятого элемента 2-2 И-2 ИЛИ второй группы и четвертым входом второго элемента 2-2 И-2 ИЛИ второй группы. Выход первого элемента 2-2 И-2 ИЛИ второй группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ третьей группы и четвертым входом пятого элемента 2-2 И 2 ИЛИ третьей группы. Выход (1)-го элемента 2-2 И-2 ИЛИ второй группы соединен с третьим входом (1)-го элемента 2-2 И-2 ИЛИ третьей группы и четвертым входом -го элемента 2-2 И-2 ИЛИ третьей группы. Выход первого элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ четвертой группы и четвертым входом четвертого элемента 2-2 И-2 ИЛИ четвертой группы. Выход второго элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом второго элемента 2-2 И-2 ИЛИ четвертой группы и четвертым входом пятого элемента 2-2 И-2 ИЛИ четвертой группы. Выход(2)-го элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом (2)-го эле 3 11754 1 2009.04.30 мента 2-2 И-2 ИЛИ четвертой группы и четвертым входом -го элемента 2-2 И-2 ИЛИ четвертой группы. Выход -го элемента 2-2 И-2 ИЛИ четвертой группы соединен с выходом равно- 1 блока. На фиг. 1 представлена структурная схема устройства для формирования остатка по модулю пять с накоплением при 16 (44), на фиг. 2 - функциональная схема блока модулярного сложения унитарного кода с двоичной тетрадой. Устройство (фиг. 1) содержит 4 блоков модулярного сложения унитарного кода с двоичной тетрадой 1-4, пять входов разрядов входного унитарного кода 5-9,16 входов разрядов входного слова с первого по шестнадцатый 10-25 соответственно, пять выходов разрядов выходного унитарного кода 26-30. Каждый блок модулярного сложения унитарного кода с двоичной тетрадой (фиг. 2),входящий в состав предлагаемого устройства, содержит четыре группы элементов 2-2 И 2 ИЛИ по пять элементов в каждой (элементы 31-35 первой группы, элементы 36-40 второй группы, элементы 41-45 третьей группы, элементы 46-50 четвертой группы), четыре элемента НЕ 51-54, вход равно нулю 55, вход равно единице 56, вход равно двум 57,вход равно трем 58, вход равно четырем 59, вход 60 разряда двоичной тетрады с весом 20, вход 61 разряда двоичной тетрады с весом 21, вход 62 разряда двоичной тетрады с весом 22, вход 63 разряда двоичной тетрады с весом 23, выход равно нулю 64, выход равно единице 65, выход равно двум 66, выход равно трем 67, выход равно четырем 68. Поясним принцип работы устройства. Устройство для формирования остатка по модулю пять с накоплением выполняет сложение по модулю пять входного пятиразрядного унитарного двоичного кода 0 0 0 000 , 10 , 2 , 3 , 4 с вычисляемым остатком по модулю пять входного двоичного слова 2-12-2-1221(05)5,(1) 0 где 00, 1, 2, 3, 4 10, 11, 5. При этом 011 тогда и только тогда, когда 0- 1. Результат также представляется в виде пятиразрядного унитарного двоичного кода(0, , 2, 3, 4), -10, 1 и -11 тогда и только тогда, когда- 1. Для определенности полагаем, что 4,1, 2, 3, Представим (1) в виде 012222323452 452562672785 1, . Из (2) непосредственно следует, что вычисление результатаможет быть выполнено по рекуррентной формуле(-1) 5,(3) где(0 , 1 , 2 , 3 , 4 ) , 10, 1,1,и 1 тогда и только тогда, когда-1. Очевидно, что. Устройство для формирования остатка по модулю пять с накоплением построено в соответствии с соотношением (3). 11754 1 2009.04.30 Устройство содержитпоследовательно включенных блоков модулярного сложения унитарного кода с двоичной тетрадой, -й из которых выполняет сложение по модулю пять унитарного кода -1 с двоичной тетрадой . На выходе блока формируется пятиразрядный унитарный код , который поступает на соответствующие входы следующего блока. При этом на входы равно- 1 первого блока поступают разряды входного унитарного кода 0, а на выходах равно- 1 -го блока формируются разряды -1, выходного унитарного кода ,1, 5. Работа блоков модулярного сложения унитарного кода с двоичной тетрадой описывается таблицей (фиг. 3). Таким образом, на входы -го блока 1,поступают пятиразрядный унитарный код 101 , 11 , 21 , 31 , 41 , и разряды ( 4 3 ,42 ,4 1 ,4 ) двоичной тетрады . На выходах блока (выходах элементов 2-2 И-2 ИЛИ четвертой группы) формируется унитарный код 0 , 1 , 2 , 3 , 4 , суммы по модулю пять -1 и Х согласно (3). Введем обозначения-1 - сигнал на выходе -го элемента 2-2 И-2 ИЛИ первой группы,1, 5-1 - сигнал на выходе -го элемента 2-2 И-2 ИЛИ второй группы-1 - сигнал на выходе -го элемента 2-2 И-2 ИЛИ третьей группы. Тогда работу блоков модулярного сложения унитарного кода с двоичной тетрадой можно описать следующей системой булевых функций 11754 1 2009.04.30 Устройство для формирования остатка по модулю пять с накоплением при 16(фиг. 1) работает следующим образом. На входы 5, 6 9 поступают соответственно разряды 00 , 10 40 входного унитарно(0 , 1 , 2 , 3 , 4 )0 , 1 , 2 , 3 , 4 результата(05)5. Поясним работу устройства (164) на примере. Пусть 04 и 59763. 0 0 0 000 , 10 , 2 , 3 , 4(0, 0, 0, 0, 1)16 152 11110100101110011. Тогда на входы первого блока 1 поступают разряды унитарного кода 0 и разряды двоичной тетрады (х 1, х 2, х 3, х 4)(1, 1, 0, 0). На выходах блока 1 формируется унитарный код 1(01)5(01224334)5(43)52 1 1 1 1 1 10 , 1 , 2 , 3 , 4(0, 0, 1, 0, 0). На входы второго блока 2 поступают разряды унитарного кода 1 и разряды двоичной тетрады (х 5, х 6, х 7, х 8)(1, 1, 1, 0). На выходах блока 2 формируется унитарный код 2(1 Х 2) 5(15264738) 5(27)54 2 2 2 220 , 12 , 2 , 3 , 4(0, 0, 0, 0, 1). На входы третьего блока 3 поступают разряды унитарного кода 2 и разряды двоичной тетрады (х 9, х 10, х 11, х 12)(1, 0, 0,1). На выходах блока 3 формируется унитарный код 3(23)5(29210411312)5(44)53 3 3 3 330 , 13 , 2 , 3 , 4(0, 0, 0, 1, 0). На входы четвертого блока 4 поступают разряды унитарного кода 3 и разряды двоичной тетрады (13, 14, 15, 16)(0, 1, 1, 1). На выходах блока 4 (выходах устройства) формируется унитарный код 4(34)5(313214415316)5(39)52 4 4 4 440 , 14 , 2 , 3 , 4(0, 0, 1, 0, 0). Поскольку, то(0, 1, 2, 3, 4)4(0, 0, 1, 0, 0). Действительно,(05) 5(4597635) 7(43) 52. Достоинствами устройства для формирования остатка по модулю пять с накоплением являются простая конструкция и регулярная однородная структура. Таблица работы блока модулярного сложения унитарного кода с двоичной тетрадой Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.