Устройство для формирования остатка по модулю 2n-1

ГОСУДАРСТВЕННЫЙ ПАТЕНТНЫЙ комитвт РЕСПУБЛИКИ БЕПАРУСЬ54 УСТРОЙСТВО для ФОРМИРОВАНИЯ ОСТАТКА по модулю 2-1-1 в(71) Заявитель Белорусский государственный университет (ВТ)(73) Патентообладатель Белорусский государ ственный университет (ВУ)(57) Устройство для формирования остатка по модулю 2 1, содержащее сумматор унитарных кодов по модулю 2 1, выходы которого соединены соответственно с выходами устройства, ОТЛИЧЕНОЩЕВСЯ ТСМ, ЧТО ДОПОЛНИТЕЛЬНО ВВЕДЕНЫ ДВЕ ГРУППЬЕ ОЛОКОВ ВЫЧИСЛЕНИЯ фундаментальнь 1 х симметрических булевых функций по п блоков в каждой и п групп элементов ИЛИ по п элементов в каждой, при этом вход (п(1-1)3)-го разряда устройства (ЕЙ, РЕ , ЬЫ/п,Ы - разрядность входного слова) соединен с Е-м входом 3-го блока вычисления фундаментальных симметрических булевых функций первой группы, входы 1-го элемента ИЛИ 3-й группы(1 П ) соединены с А-ми выходами 3-го блока вычисления фундаментальных симметрическихП булевых функций первой группы (15 А 5 1., (214 А)шо 1(2 -1) 2 214, ад Е 01 и а 1,1), вы 31 ход К-го элемента ИЛИ 3-й группы соединен с 3-м входом 14-го блока вычисления фундаментальных симметричных булевых функций второй группы, выходы которого соединены соответственно со входами 1-го операнда сумматора унитарных кодов по модулю 2 -1.Изобретение относится к области вычислительной техники и микроэлектроники и может быть использовано для построения средств аппаратурного контроля и цифровых устройств, работающих в системе остаточных классов.Известно устройство для формирования остатка по модулю три, содержащее линейки триггеров и сумматоров по модулю три 1.Недостатком устройства являются ограниченные функциональные возможности, поскольку устройство формирует остаток только по модулю три.Наиболее близким техническим решением к предлагаемому является устройство для преобразования двоичного кода в код системы счисления остаточных классов, содержащее дешифратор и группу последовательно включенных сумматоров унитарного кода по модулю 2.Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.Изобретение направлено на решение задачи повышения быстродействия устройства для формирования остатка по модулю 2 П-1.Поставленная задача решается тем, что в устройство для формирования остатка по модулю 211-1, содержащее сумматор унитарных кодов по модулю 2 П-1, выходы которого соединены соответственно с выходами устройства, согласно изобретению дополнительно введены две группы блоков вычисления фундаментальных симметрических булевых функций по п блоков в кахщой и п групп элементов ИЛИ по п элементов в каждой, при этом вход (п(г-1)3)-то разрядаустройства (3 1 Е, 111/11, Ы - разрядность входного слова и Ы 111.) соединен с г-м входом 3-го блока вычисления фундаментальных симметрических булевых фУЪПЩий первой группы, входы К-го элемента ИЛИ 3-й группы (1 Й) соединены с А-ми выходами 3-го блока вычисления фундаментальных симметрических булевых функций первой группы (1 5 А 5 Ь, Пединен с 3-м входом 1-го блока вычисления фундаментальных симметрических булевых функций второй группы, выходы которого соединены соответственно с входами 1 го операнда сумматора унитарных кодов по модулю 211-1. -На чертеже представлена схема устройства для формирования остатка по модулю 2-1.Устройство содержит п блоков вычисления фундаментальных симметрических булевых функций первой группы 11, 12,, 1, п блоков вычисления фундаментальных симметрических булевых функций второй группы 21, 22,, 21 п групп элементов ИЛИ по п элементов в каждой (на чертеже обозначены элементы первой группы 311, 312, 31 элементы второй группы 321, 322, . . . . 32,1 элементы п-й группы 31,1, 32, Зин ), сумматор унитарных кодов по модулю 2-1 4, Ы входов 51, 52, 5,1, п выходов 61, б 2, 6,1.Устройство для формирования остатка по модулю 211-1 работает следующим образом. На входы 515 устройства поступают соответственно разряды Х 1 Х входного двоичного словаХ Хы Хыд Хыд . . . Х 1, причем Х 1 - младший разряд. На выходах 61, б 2, 6 формируется п-разрядный двоичныйкод результата К Хто 1(2-1) г 1 21-2 21 г свертки по модулю 2 П-1 входного слова Х, 213 е 0,1, 1,11, и В е О, 1,, 2 П-2. Причем на выходе 61 реализуется младцшй разряд 11, на выходе 6,1 - старший разряд 13, результата К.Рассмотрим принцип работы устройства для формирования остатка по модулю 2 П-1.Пусть Х хм хм хмх 1 - Ы-разрядное двоичное слово и х 1 - младший разряд. Без потери общности рассуждений полагаем, что Ы 111., гдс Ь - целое (в противном случае старшие разряды входного слова дополняются нулями).Результат свертки по модулю 2 П-1 входного слова Х мохсно представить в виде К Хшо 1(2 д-1) т 1 2 т 2 2 П 1 г (131 шос 1(2-1)(21 Э 2)п 1 оа(2-1)(2 ПВ)П П Пусть 211 д, ш, ш О,п. Тогда величине (212 с 15 к)шос 1(2 1) можно поставить в 11 11 соответствие (п 1) - разрядный унитарный двоичный код Вк (ЬШ, ЬК 2,,ЬК) в котором компоненты Ьд, 1 тогда и только тогда, когда у т, у . При этом вес разряда Ь 1 составляетВыражение (5) означает суммирование п унитарных двоичных кодов Вк по модулю 211-1,причем единичные разряды кодов ВК имеют различные веса согласно (4). Значения ад, в (2) вычисляются через фундаментальные симметрические булевы функциигде АЕ и фундаментальные симметрические булевы функции Р определяются сле дующим образомПороги А фундаментальных симметрических булевых функций Р в (6) находятся из услотУнитарный двоичный код Вк также может быть сформирован с помощью фундаментальных симметрических булевых функций Е которые определяются следующим образом51 О, в противном случае. Следовательно, В, (ЬК,ЬК,ЬКШ)(ФФ 1 Щи (5) примет вид КХшос 1(2 -1(2 Ф,Ф,Фшос 1(2 41). (9) к 1Устройство для формирования остатка по модулю 2-1 работает в соответствии с вышеиз ложенным. На входы 3-го блока вычисления фундаментальных симметрических булевых функций первой группы 11 поступают переменные из множества хп(11)1. На выходах блока 11 формируют ся фундаментальные симметрические булевы функции Р согласно (7). Эти функции объеди няются элементами ИЛИ 3-й группы 311, 312 ,.., 31 согласно (б). При этом на выходе элемента ИЛИ 3111 формируется значение ад в соответствии с (2).На входы блока вычисления фундаментальных симметрических булевых функций второй группы 211 поступают значения (111 с выходов элементов ИЛИ 3111, 3211 31,11. Этот блок форми рует фундаментальные симметрические булевы функции Ф . Вектор сигналов на выходе блока 211 представляет собой (п 1) - разрядный унитарный двоичный код В 11. Суммирование по модулю 211-1 унитарных кодов Вк, согласно (9), осушбстдпяетс сУмматором 4, На выходах КОторого 61,62, 6 формируются соответственно разряды 11 1 гл результата свертки по модулю 211-1 входного М-разрядного двоичного слова. .Поясним работу устройства на примере формирования остатка по модулю семь (п 3) при 1 Т 18 для входного слова Х (х 13, х 17 х 15,, х 1) (101101110110011101).Очевидно, что блоки вычисления фундаментальных симметрических булевых функций первой группы 11, 1 и 13 имеют по Ь Ы/п 6 входов. Тогда на входы первого блока вычисления фундаментальных симметрических булевых функций 11 поступает вектор двоичных переменных Х 1 (х 1 х 4 х 15) (11 О 011) на входы второго блока вычисления Фундаментальныхсимметрических булевых функций 12 - вектор двоичных переменных Х (х 2 х 5 х 17)(011100) на входы третьего блока вычисления фундаментальных симметрических булевыхфункций 13 - вектор двоичных переменных Х (хдхбх 13) (101111).На выходе блока 11 фундаментальные симметрические булевы функции принимают значенияНа выходе блока 12 фундаментальные симметрические булевы функции принимают значенияНа выходе блока 13 фундаментальные симметрические булевы функции принимают значеНИЯ35 1 иР 0 сО 6,с 5. Сигналы ад на выходе элементов ИЛИ 3114, согласно (6), имеют значения а Р, у 11 у 1 д,5 о 1 РЕ увдувгы) аг,4 ув 5 ув 61 с 1 ву 1 ув 5 с 11 уР/г 1 аву 1 ув 6 с 11 уР/1 оавугу 11Тогда на входы первого блока вычисления фундаментальных симметрических булевых функций второй группы 21 поступает двоичный вектор 111, 0121, (131) (000), на входы второгоблока вычисления фундаментальных симметрических булевых функций второй группы 22 Двоичный вектор (6112, ад, 432) (011), на входы третьего блока вычисления фундаментальныхсимметрических булевых функций второй группы 23 двоичный вектор (613, 623, с 133) (111). На выходе блока 21 фундаментальные симметрические булевы функции принимают значенияНа ВЫХОДЕ блока 22 фундаментальные СИММСТРИЧВСКИС бУЛЕВЫпринимают значеНИЯ1 иФ 0,аБ 2 На выходе блока 23 фундаментальные симметрические булевы функции принимают значения 1