Преобразователь кода системы остаточных классов в позиционный код

(71) Институт кибернетики им, В. М, Гва и Институт проблем моделировэнергетике АН УССР(56) Авторское свидетельство СССРВ 1228290, кл. Н 03 М 7/18, 1984.Авторское свидетельство СССРМ. 1388997, кл. Н 03 М 7/18, 1986,Авторское свидетельство СССРР 1624699, кл, Н 03 М 7/18, 1988,оания ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ И(54) ПРЕОБРАЗОВАТЕЛЬ КОДА СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ В ПОЗИЦИОННЫЙ КОД(57) Изобретение относится. к области вычислительной техники и предназначено для преобразования кода системы остаточных классов в позиционный код. Целью изобретения является повышение быстродействия. Преобразователь содержит выходной регистр 10, сдвигатель 11, сумматоры 1, 2, 3, вычитатели 4 и 5, группу мультиплексоров 12, группу элементов И 13, элемент И 6, элемент ИЛИ 14, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7, элементы 8, 9 задержки. 1 ил,77 )7 171737735 10 15 20 Цель изобретения - повышение быстродействия преобразования,Поставленная цель достигается тем, что преобразователь кода системы остаточ 25 30 35 40 45 50 55 ных классов в позиционный код, содержащий с первого по третий сумматоры, первый и второй вычитатели, элемент И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и первый и второй элементы задержки, причем входы разрядов вычитаемого и уменьшаемого первого вычитателя соединены соответственно с входами разрядов первого и второго информационных входов преобразователя, входы разрядов первого и второго слагаемых первого сумматора соединены соответственно с входами разрядов первого и второго информационных входов преобразователя,первый и второй входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с входами младших разрядов первого и второго информационных входов преобразователя, содержит выходной регистр, сдвигатель, группу мультиплексоров, группу элементов И и элемент ИЛИ, причем выходы с первого по и-й (и - разрядность информации) разрядов выхода первого вычитателя соединены с соответствующими входами элемента ИЛИ и входами соответствующих разрядов входа первого слагаемого третьего сумматора, вход первого разряда входа второго слагаемого которого соединен с входом "0" преобразователя, входы с второго по (и+1)-й разрядов входа второго слагаемого третьего сумматора соединены соответственно с выходами с первого по и-й разрядов выхода первого вычитателя, прямой выход (и+1)-го разряда выхода которого соединен с входом (и+1)-го разряда входа первого слагаемого и входами (и+2)-го и (и+3)-го разрядов входов первого и второго слагаемых третьего сумматора, выход которого соединен с информационными входом сдвигателя, входы разрядов входа задания величины сдвига которого соединены с входами соответствующих разрядов входа задания основания преобразователя, выходы разрядов выхода первого сумматора соединены с входами соответствующих разрядов входа первого слагаемого второго сумматора, инверсный выход (и+1)-го разряда выхода первого вычитателя и выход элемента ИЛИ соединены соответственно с первым и вторым входами элемента И, входы с первого по 2 п-й разрядов входа задания диапазона преобразователя соединены с первыми информационными входами соответствующих мультиплексоров группы и с первыми входами соответствующих элементов И группы, вторые входы которых соединены с выходом элемента И, первый информационный вход (2 п+1)-го мультиплексора и второй информационный вход первого мультиплексора группы соединены с входом логического нуля преобразователя, вторыеинформационные входы с второго по(2 п+1)- й мультиплексоров группы соединены соответственно с выходами с первого по 2 п-й элементов И группы, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с управляющими входами мультиплексоров группы, выходы которых соединены с входами соответствующих разрядов входа второго слагаемого второго сумматора, выход сдвигателя соединен с входом вычитаемого второго вычитателя, выход которого соединен с информационным входом выходного регистра, вход установки в нуль которого соединен с входом начальной установки преобразователя, вход запуска преобразователя через первый элемент задержки соединен с третьим входом элемента И, выход первого элемента задержки через второй элемент задержки соединен с входом разрешения записи выходного регистра, выходы разрядов с второго по (2 п+1)-й выхода второго сумматора соединены соответственно с входами с первого по 2 п-й разрядов входа уменьшаемого второго вычитателя, входы с (и+2)-го по (2 п+1)-й разрядов входа первого слагаемого второго сумматора, входы (и+1)- х разрядов входов первого и второго слагаемых первого сумматора, входы (и+1)-х разрядов входов уменьшаемого и вычитаемого первого вычитателя соединены с входом "0" преобразователя.На чертеже изображена структурная схема преобразователя кода системы остаточных классов в позиционный код.Преобразователь кода системы остаточных классов в позиционный код содержит сумматоры 1-3, вычитатели 4 и 5, элемент И 6, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7, элементы 8 и 9 задержки, выходной регистр 10, сдвигатель 11, группу мультиплексоров 121-12(2+1), группу элементов И 13(1) - 12(2 п), элемент ИЛИ 14, информационные входы 15(1) - 15(п) и 16(1) - 16, входы 17(1)-17 задания основания, входы 18(1)- 18(2 п) задания диапазона, вход 19 начальной установки и вход 20 запуска преобразователя.Входы разрядв первого и второго слагаемых сумматора 1 соединены соответственно с входами разрядов информационных входов 15(1)-15(п) и 16(1) - 16(п) преобразователя (где и - количество разрядов представления остатков). Входы разрядов вычитаемого и уменьшаемого вычитателя 4 соединены соответственно с входами разрядов информационных входов 15(1)-15(п) и 16(1) - 16(п) преобразователя, Выходы разрядов выхода сумматора 1 соединены с входами соответствующих разрядов входа первого слагаемого сумматора 2. Инверсный выход (и+1)-го разряда выхода вычитателя 4 и выход элемента ИЛИ 14 соединены соответственно с первым и вторым входами элемента И 6. Первый и второй входы эле мента ИСКЛЮЧАЮЩЕЕ ИЛИ 7 соединеныс входами младших разрядов информационных входов 15(1) и 16(1) преобразователя.Выходы с первого по и-й разрядов выхода вычитателя 4 соединены с соответствующи ми входами элемента ИЛИ 14 и входамисоответствующих разрядов входа первого слагаемого сумматора 3, вход первого разряда входа второго слагаемого которого соединен с входом "0" преобразователя.15 Входы с второго по (и+1)-й разрядов входавторого слагаемого сумматора 3 соединены соответственно с выходами с первого по и-й разрядов выхода вычитателя 4, прямой выход (и+1)-го разряда выхода которого сое динен с входом (и+1)-го разряда входапервого слагаемого и входами (п+2) и (и+3)- го разрядов входов первого и второго слагаемых сумматора 3, выход которого соединен с информационным входом сдви гателя 11, входы разрядов входа заданиявеличины сдвига которого соединены с входами соответствующих разрядов входа 17 задания основания преобразователя. Входы с первого по 2 п-й разряд входа 18 зада ния диапазона преобразователя соединеныс первыми информационными входами соответствующих мультиплексоров 12(1) - 12 группы и первыми входами соответствующих элементов И 13(1) - 13(2 п) группы, вторые 35 входы которых соединены с выходом элемента И 6, Первый информационный вход мультиплексора 12(2 п+1) и второй информационный вход мультиплексора 12(1) группы соединены с входом "0" преобразователя.40 Вторые информационные входы мультиплексоров с 12(2) по 12(2+1) группы соединены соответственно с выходами элементов И 13(1) - 13(2) группы. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 7 соединен с управляю щими входами мультиплексоров группы12(1) - 12(2 п+1), выходы которых соединены с входами соответствующих разрядов входа второго слагаемого сумматора 2. Выход сдвигателя 11 соединен с входом вычитае мого вычитателя 5, выход которого соединен с информационным входом выходного регистра 10, вход установки в "0" которого соединен с входом 19 начальной установки преобразователя, Вход запуска 20 преобра зователя через элемент 8 задержки соединен с третьим входом элемента И 6, Выход элемента 8 задержки через элемент 9 задержки соединен с входом разрешения записи выходного регистра 10. Выходы с второго по (2 п+1)-й разрядов выхода сумматора 2 соединены соответственно со входами с первого по 2 п-й разрядов входа уменьшаемого вычитателя 5. Входы с (и+2)-го по (2 п+1)-й разрядов входа первого слагаемого сумматора 2, входы (и+1)-х разрядов входов первого и второго слагаемых сумматора 1, входы (и+1)-х разрядов входов уменьшаемого и вычитаемого вычитателя 4 соединены с входом "О" преобразователя.Преобразователь кода системы остаточных классов в позиционный код работает следующим образом.В исходном состояни на вход 19 начальной установки преобразователя подают сигнал установки выходного регистра 10 в нулевое состояние, На информационные входы 15(1) - 15(п) и 16(1) - 16(п) подают соответственно параллельные и-разрядные двоичные коды остатков а 1 и а 2 по основаниям Р 1=6 2-1 и Р 2=6 2 +1, где п 1 =0,1,2, 3, На входы 18(1) - 18(п) задания диапазона представления чисел подают параллельный 2 п-разрядный двоичный код произведения оснований Р 1 Р 2. На входы 17(1) - 17(а) задания основания остаточных классов подают параллельный и-разрядный двоичный код величины гп, определяющий основания Р 1= =6 2 -1 иР 2=6 2 +1.Запуск преобразователя осуществляется путем подачи сигнала "1" на вход 20 запуска преобразователя. Спустя время, равное времени выполнения операции вычитания в параллельном (и+1)-разрядном вычитателе 4, на выходе элемента 8 задержки устанавливается сигнал "1", снимающий блокировку элемента И 6.Параллельный (и+1)-разрядный вычитатель 4 формирует двоичный код разности а 2 - а 1. Параллельный (и+1)-разрядный сумматор 1 формирует двоичный код суммы а 1 +а 2 Элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7 формирует из сигналов младших разрядов остатков а 1 и а 2 единичный управляющий сигнал в случае комбинации кодов 0 - 1 и 1 - 0 и нулевой сигнал при комбинациях 0 - О и 1 - 1, Если оба остатка а 1 и б - четные или нечетные, то на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 7 действует нулевой сигнал, Если один остаток - четный, а другой - нечетный, и наоборот, то элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7 формирует сигнал "1", при котором мультиплексоры 12(1) - 12 рп) пропускают на свои выходы параллельный 2 п-разрядный двоичный код величины, действующий на входах 18(1) - 18 рп) задания диапазона преобразователя.Дальнейшая работа преобразователя зависит от значения величины а 2 - а 1, формируемой вычитателем 4, Если а 2 а 1, то10 а 2 - а 10 и в знаковом (и+1)-м разряде наего инверсном выходе действует единичный сигнал. В этом случае а 2 - й 1О, хотя бы в одном разряде вычитателя 4 действует единичный сигнал, который проходит на выход элемента ИЛИ 14, В результате на выходе элемента И 6 формируется единичныйсигнал, снимающий блокировку элемента И 13(1) - 13 р), В случае нулевого сигнала на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (2 п+1)-разрядный двоичный код величины 2 Р 1 Р 2, действующий на выходах мультиплексоров 12(1) - 12(2 п+1), подается на входысумматора 2, на выходе которого формиру"5 ется (2 п+1)-разрядный двоичный код величин ы 2 Р 1 Р 2+ ( а 2 + а 1),Если имеет место а 2 а 1, тоа 2 - а 10 и элемент И 6 блокируется нулевым сигналом выхода элемента ИЛИ 14при а 2 =а 1 или нулевым сигналом инверсного выхода знакового (п+1)-го разряда вычитателя 4 при а 2 а 1. Блокировкаэлементов И 13(1) - 13 рп) нулевым сигналомвыхода элемента И 6 обеспечивает формирование нулевых сигналов на выходах мультиплексоров 12(1) - 12 рп+1) в случае нулевогосигнала на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 7, В этом случае на выходе сумматора 2 формируется двоичный кодВЕЛИЧИНЫ а 1 +а 2,Таким образом, имеется три случая формирования различных кодов на выходе сумматора 2;1) Р 1 Р 2+(а 1 +а 2), если а 1 - четное,а 2- нечетное, или а 1 - нечетное,а 2 - четное;2) 2 Р 1 Р 2+(а 1 + а 2), если а 1 и а 2- обачетные или нечетные; а 2 а 1;40 3)( а 1+а 2) ЕСли а 1 иа 2 - Оба чЕтныЕили нЕчЕтныЕ; а 2 а 1.В зависимости от управляющих сигналов на выходах элементов И 6 и ИСКЛЮЧАЮЩЕЕ ИЛИ 7 на входы уменьшаемого45 вычитателя 5 поступает с выхода сумматора2 двоичный код одной из трех величинР 1 Р 2+(а 1+а 2) 2 Р 1 Р 2+(а 2+а 1) или(а 1 + аг).Одновременно с формированием дво 50 ичного кода на выходе сумматора 2 на выходе (и+3)-разрядного сумматора 3формируется двоичный код величины 3( а 2 - а 1), так как на его входы первогослагаемого поступает с выхода вычитателя55 4 двоичный код величины (а 2 - а 1),а на входы второго слагаемого - сдвинутый на одинразряд в сторону старших разрядов двоичный код величины 2 (02 - а 1), Так как навыходе вычитателя 4 отрицательная разность (аг - а 1) формируется в дополнительном коде, то выход знакового (и+1)-го разряда вычитателя 4 соединен с входами обоихслагаемых в (п+2)-м и (и+3)-м разрядах сумматора 3, чтобы обеспечить сложение дополнительных кодов величин (аг - а 1) и 2(аг - а 1). Сдвигатель 11 выполняет сдвиг нав разрядов в сторону старших разрядов(и+3)-разрядного двоичного кода величины 3( аг - а 1), действующего на выходах 10сумматора 3.Параметр гп = О, 1, 2, 3(п - 3) определяетоснования Р 1 = 6 2 - 1 и Р 2 = 6 2 +1системы остаточных классов и задается ввиде двоичного кода на входах 17(1) - 17(п)задания основания преобразователя, соединенных с входами задания величинысдвига сдвигателя 11, На выходах сдвигателя 11 формируется 2 п-разрядный двоичныйкод величины 3 2 (а 2 - а 1), который поступает на входы вычитаемого 2 п-разрядноговычитателя 5. Входы уменьшаемого вычитателя 5 с первого по 2 п-й соединены соответственно с второго по (2 п+1)-й выходамисумматора 2, что равносильно сдвигу двоичного кода сумматора 2 на один разряд всторону младших разрядов или уменьшению его на 1/2. На выходе вычитателя 5формируется 2 п-разрядный позиционныйкод преобразованного числа А согласно алгоритму:1)А= - Р 1 Рг+(а 1 +аг) - 3 2 (аг - а 1),если а 1 - четное, аг - нечетное;или а 1- нечетное, аг -четное;2)А= - 2 Р 1 Рг+(а 1+аг)1-3 2" (аг -а 1),1если а 1 и аг - оба четные или нечетные;а 2 )а 11, п 1403)А= - (а 1+а 2) - 3 2" (аг - а 1),если а 1 и аг - оба четные или нечетные;а 2 а 1Сигнал м 1", сформированный на выходе 4элемента задержки 8, спустя время, равноевремени выполнения операции суммирования сумматором 3, сдвига сдвигателем 11 ивыполнения операции вычитания вычитателем 5, начинает действовать на выходе элемента задержки 9. По этому сигналу502 п-разрядный позиционный код преобразованного числа А, действующий на выходахвычитателя 5 записывается в 2 п-разрядныйвыходной регистр 10.Рассмотрим процесс преобразованияна примерах при основанияхР 1=11; Рг=13; и =4 и в=1.П р и м е р 1. а 1 = 9; аг =7; Р 1 Р 2 = 143,Так как а 1 иаг - оба нечетные и а 2 ( а 1,то имеем третий случай преобразования: аг 0111 аг 0111а 1 1001 а 1 1001 Выч, 4111 0 См. ГПГОООЧУ 1111110 См.2 0000100001111100 См.З 1111010 Сдв.11 11110100 00001000 11110100 Выч. 5 0 0 0 1 0 1 0.0 А = 20 П р и м е р 2. а 1 =2; а 2 = 12; 2 Р 1 Р 2 =286. Так как а 1 иаг - оба четные или а 2 ) а 1, то имеем второй случай преобразования; аг 1100а 1 0010 Выч,4. 01 01 0 аг 11 00 а 1001 0 См, ОТ 110 0001010 0010100 См,З 0011110 Сдв. 11 0 0 1 1 1 1 0 0 а 1+аг 000001110 2 Р 1 Р 2 100011110 См,2 100101100 1001011000111100 Выч.5 01011010А=90 Пример 3. а 1=10; а 2=7; Р 1 Р 2==143. Так как а 1 - четное, а 2 - нечетное, то имеем первый случай преобразования: аг 0111 а 1 1010 Выч,4 111 01 аг 0111а 1 1010 См,1 10001 аг 0111 а 1 1010 Выч,4 11101111 11 011111010 См.З 1110111 Сдв.11 11101110 аг+0111 01 1010 См.1 10001а 1+аг 000010001 Р 1 Р 2 010001111 См.2 010100000 01010000 11101110А=985 10 15 20 25 30 3.5 40 45 50 55 Технико-экономический эффект от использования изобретения по сравнению с прототипом заключается в повышении быстродействия преобразования в и раз. Так как каждый из элементов 8 и 9 задержки вносит задержку в один такт, то предложенное устройство выполняет преобразование за два такта, в то время как прототип выполняет преобразование за 2 п тактов, Например, при представлении остатков на п = 16 разрядах быстродействие предложенного преобразователя в 16 раз выше, чем быстродействие устройства-прототипа.Формула изобретения Преобразователь кода системы остаточных классов в позиционный код,содержащий с первого по третий сумматоры, первый и второй вычитатели, элемент И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй элементы задержки, причем входы разрядов вычитаемого и уменьшаемого первого вычитателя соединены соответственно с входами разрядов первого и второго информационных входов преобразователя, входы разрядов первого и второго слагаемых первого сумматора соединены соответственно с входами разрядов первого и второго информационных входов преобразователя, первый и второй входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с входами младших разрядов первого и второго информационных входов преобразователя, о т л и ч а ю щ и й с я тем, что, с целью повышения быстродействия, он содержит выходной регистр, сдвигатель, группу мультиплексоров, группу элементов И и элемент ИЛИ, причем выходы с первого по п-й (и - разрядность информации) разрядов выхода первого вычитателя соединены с соответствующими входами элемента ИЛИ и входами соответствующих разрядов входа первого слагаемого третьего сумматора, вход первого разряда входа второго слагаемого которого соединен с входом "0" преобразователя, входы с второго по (и+1)-й разрядов входа второго слагаемого третьего сумматора соединены соответственно с выходами с первого по и-й разрядов выхода первого вычитателя, прямой выход (и+1)го разряда выхода которого соединен с входом (и+1)-го разряда, входами первого слагаемого и входами (и+2)гои (п+3)-го разрядов входов первого и второго слагаемых третьего сумматора, выход которого соединен с информационным входом сдвигателя, входы разрядов входа задания величины сдвига которого соединены с входами соответствующих разрядов входа задания основания преобразователя, выходы разрядов выхода первого сумматора соединены с входами соответствующих разрядов входа первого слагаемого второго сумматора, инверсный выход(п+1)го разряда выхода первого вычитателя и выход элемента ИЛИ соединены соответственно с первым и вторым входами элемента И, входы с первого по 2 п-й разрядов входа задания диапазона преобразователя соединены с первыми информационными входами соответствующих мультиплексоров группы и первыми входами соответствующих элементов И группы, вторые входы которых соединены с выходом элемента И, первый информационный вход (2 п+1)-го мультиплексора и второй.информационный вход первого мультиплексора группы соединены с входом "О" преобразователя, вторые информационные входы с второго по (2 п+1)-й мультиплексоров группы соединены соответственно с первого по 2 п-й выходами элементов И группы, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с управляющими входами мультиплексоров группы, выходы которых соединены с входами соответствующих разрядов входа второго слагаемого второго сумматора, выход сдвигателя соединен с входом вычитаемого второго вычитателя, выход которого соединен с информационным входом выходного регистра, вход установки в "0" которого соединне с входом начальной установки преобразователя, вход запуска преобразователя через первый элемент задержки соединен с третьим входом элемента И, выход первого элемента задержки через второй элемент задержки соединен с входом разрешения записи выходного регистра, выходы с второго по (2 п+1)й разрядов выхода второго сумматора соединены соответственно с входами с первого по 2 п-й разрядов входа уменьшаемого второго вычитателя, входы с (и+2)-го по (2 п+1)-й разрядов входа первого слагаемого второго сумматора, входы (и+1)х разрядов входов первого и второго слагаемых первого сумматора, входы (и+1)-х разрядов входов уменьшаемого и вычитаемого первого вычитателя соединены с входом "0" преобразователя,