Устройство для формирования остатков по модулю
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Номер патента: 1449986
Автор: Черкасский
Текст
союз советских ОЦИАЛИСТИЧЕСКИ СПУБЛИН 9) (1) 9)4 СО ГОСУДАРСТВЕННЫЙ НОМИПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТПРИ ГКНТ СССР ЯМ ОПИСАНИЕ ИЗОБРЕТЕН инст ельство СССР Феаауаеаоаау 4 в лз Л -Лдаюфю фО ам аде Йц а Ф а фщю,4 ааавав ааа 4 Луае азв а,Ж АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свицетФ 1397918; 1397919,кл. С 06 Р 11/О, 1985.Авторское свидетельствоЯф 13056841 1305685 экл. О 06 Г 11/1 О, 1985,(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ(5) Изобретение относится к вычислительной технике и может быть использовано при построении контроли-,руемых арифметических устройств.Цель изобретения - повьппение коэффициента использования оборудованияэа счет формирования остатков по модулю одиннадцать. Контролируемое слово разбивается на группы по пять разрядов в каждой. Зти грцппы.разрядовсоединяются с входами одноразрядных-10 9 7 3 6 1 2 4 8 5 10 9 7 3 сумматоров 1, объединенных в (1-1)игруппу 2 (1= - , где п - разрядность контролируемого слова). Первые две группы разрядов контролируемого слова соединяются соо гветственно с инверсными входами первого слагаемого и прямыми входами второго слагаемого соответствующих одноразрядных сумматоров 1 первой группы 2.1, Выход переноса каждого предыдущего одноразрядного сумматора 1 каждой группы 2 соединен с входом переноса последующего одноразрядного сумматора 1. Выходы результата одноразрядных сумма-. Изобретение относится к вычислительной технике и может быть использовано при построении контролируемых арифметических устройств.Цель изобретения - повышение коэффициента использования оборудования за счет формирования остатков по модулю одиннадцать.На Фиг.приведена функциональная схема устройства; на Фиг. 2 - функциональная схема блока свертки.Устройство для формирования остатка по модулю (фиг.1) Рассчитано на контроль 32-разрядного числа и содержит одноразрядные сумматоры 1.1-1,5, объединенные в шесть групп 2.1-2.6, одноразрядные сумматоры 3,1-3.8 блок 4 свертки, входы 5 блока 4 свертки и группу выходов 6 устройства.20 Блок 4 свертки, (Фиг, 2) содержит одноразрядные сумматоры 7,1-7.4, элемент И-НЕ 8, элемент НЕ 9, группу 10 элементов И-ИЛИ, элементы И 11.1-11.4.Устройство работает следующим образом. торов 1 каждой предыдущей группы 2соединены с инверсными входами первого слагаемогоодноразрядных сумматоров 1 последующей группы 2. Прямыевходы одноразрядных сумматоров 1 каждой группы 2, кроме первой, соединены с соответствующими группами разрядов контролируемого слова. Затемс помощью восьми одноразрядных сумматоров 3.1-3.8 из пятиразрядногокода образуется четырехразрядный,который с помощью блока 4 сверткипреобразуется в код остатка, поступающий на выходы группы 6 устройства.2 ил табл,Пусть А(п) исходное число, заданное в следующей двоичной системе счисленияА А +А, 2+А 2 +,е(1) где А,АА - группы последовательных двоичных цифр содинаковым количеством разрядов.Остаток от деления числа А(п) на модуль ш равен г=А(п)= А.+Б А+БРА+)2) где Б =(2 ) , Б=1 26;КоэФФициенты Б определяют сложность вычисления остатков по выражению ,2). Наименьшее число вычислений при Б =Б ==1, что имеет место длягмодулей чисел Черсенна и Ферма. В обоих этих случаях количество разрядов в группах 1 равно степени р или Ч.Для отыскания минимальных значений Б; таблица положительных и отрицательных остатков от длеения последовательного разряда степени двойки на модуль 11 имеет следующий вид.14499Как видно из таблицы, значениявычетов периодичны, Для Б;=+1 этотпериод равен и 5. Отсюда вь 1 ражениедля отыскания вычета можно записать5как г =(Ао А +Ах Аз+ 1/- (3)Выражение (3) позволяет свернуть многоразрядное число до 5-разрядного, 1 О вычета по модулю 11.Для отыскания остатка г (наименьшего вычета) необходима дополнительная свертка, так как вычет г имеет 5 разрядов, а вычет гразряда для 15 модуля 11, =101 . Переход от г к г производится на сумматорах 3. Вычет гможно разбить на две группы, каждая из которых содержит определенное число разрядов, например 2 и 3 или 1 и 4. Наиболее экономичным с точки зрения аппаратной реализации является второй вариант. Присоединение старшего разряда к младшим должно производиться с определенным коэффи циентом, который определяется по таб 4лице, Так, при 2 коэффициент равен ;+5, поэтому=11010, А 4=00110, -А=ООО 0, А=11. г=(г"), Е 1 =(В+5 В,)п,где В,Ь - четыре младших и один старший разряд г.При использовании. выражения ,4) возможно получение отрицательного остатка, Переход от отрицательного к 35 положительному остатку несложен, Так как где г- дополнение г до модуля а,то где г - обратный кодтатка г,а( " ), .,Для модуля 113 =4, =000.Согласно (3) исходное число разбивается на 1 п/ц=32:5=6,4=7 групп по 5 разрядов, причем все нечетные числа отрицательные. При вычислении суммы единица переполнения и-разрядной . сетки слагаемых А; одинакового знака эквивалентна единице младшего разряда 55 тех же слагаемых, но с противоположным знаком, Это обстоятельство позволяет применить схему в виде прямоугольной матрицы одноразрядных трех 864входовых сумматоров с горизонтальной цепью распространения сигнала переноса, содержащей ряд ступеней. В этой матрице не происходит увеличения разрядной сетки сумматоров по мере накопления результата. В целях исключения операции вычитания использовано сочетание прямых кодов частей исходного числа и инвертирование отрицательных слагаемых и всех промежуточных результатов путем дополнения их по модулю. Выбранный способ инвертирования суммируемых чисел позволяет взаимно компенсировать все отрицательные и положительные значения оо .В сумматорах 3 производится переход от 5-разрядного вычета к 4-разрядному. Для этого содержимое сумматоров последней группы 2.6 и сумматора 1.4 группы 2.5 складывается со значением сумматора 1.5 группы 2.5, умноженным на 5,О =101 . На входах 5 образуется вычет г согласно ,4). В блоке 4 свертки получают наименьший положительный вычет. Для получения1положительного г прибавляем к г дополнение о=4 в сумматорах 7. Если возникает при этом перенос (что соответствует случаю, когда выполняется неравенство асг 15), то наименьший остаток снимается с выходов сумматоров 7 через элемент И-ИЛИ 1 О. Если сигнала переноса на сумматоре 7.4 не возникает, тогда остаток подается на выход схемы, минуя сумматоры 7, с выходов сумматоров 3.5-3.8 из-эа наличия сигнала "1" на выходе инвертора 9. Исключение составляет случай, когда г =а=11, =101 . Для получения г 0 служат элементы И-НЕ 8 и И 1. При г =011 на входе элемента И-НЕ 8 установятся все "1", а на выходе образуется "0. Этот сигнал закрывает все элементы И 11 и на выходах 6 образуетсякод 0000 независимо от состояния сумматоров 7. Во всех остальных случаях элементы И-НЕ 8 и И 11 не препятствуют прохождению данных на выходы 6 устройства. Кроме того, такое подключение элемента И-НЕ 8 и элементов И 11.1-11.4 запрещает возникновение возбуждения в сумматорах 7 при г =а.+ 0111 А 60110 ++1101 1001-+101 1000Проверка. Целение А на 1011 дает остаток 000. На выходе сумматоров 3.5-3,8 образуется код 1000. При этом на выходе элемента И-НЕ 8 устанавливается 1", которая разрешает прохождение кода через элементы И 11. При сложении в сумматорах 1 чисел 1000+0100 переполнения не образуется, в связи с чем через элемент И-ИЛИ 10 проходит код 1000 с выходов суммато- ров 3.5-3.8. формула и зоб ре те ния Устройство для формирования остатков по модулю, содержащее (1-1) группу одноразрядных сумматоров ( 1игде и - разрядность числа,число одноразрядных сумматоров в группе) и блок свертки, содержащийгруппу одноразрядных сумматоров, причем инверсные вхоцы первого слагаемого и прямые входы второго слагаемогоодноразрядных сумматоров первой группы соединены с соответствующими цразрядами первой и второй групп информационных входов устройства, в 1 О каждой группе одноразрядных сумматоров выход переноса 1-го одноразрядного сумматора соединен с входом переноса ,+1)-го одноразрядного сумматора (1 Ыц), выход переноса послед него сумматора каждой группы соединенс входом переноса первого одноразрядного сумматора последующей группы,выходы суммы одноразрядных сумматоровкаждой предыдущей группы соединеныс инверсными входами первого слагаемого, соответствующих одноразрядныхсумматоров последующей группы, прямыевходы второго слагаемого сумматоровкаждой К-й группы (2 К 61-1) соединены 25 с (К+1)-й группой изразрядов группы информационных входов .устройства,о т л и ч а ю щ е е с я тем, что,с целью повышения коэффициента ис;пользования оборудования за счет Фор мирования остатков по модулю одиннадцать, оно содержит восемь одноразрядных сумматоров, число одноразрядныхсумматоров в каждой группе, кроме последней, о=5-, блок свертки содержит 35 элемент И-НЕФ элемент НЕ группу элементов И-ИЛИ и четыре элемента И,причем выходы сумматоров последнейгруппы соединены с прямыми входами3первого слагаемого первого, второго и 40 третьего одноразрядныхсумматоров, юверсный вход первого слагаемого четвертого одноразрядного сумматора соединен с выходом суммы четвертого одноразрядного сумматора пред последней группы, выход суммыпятого одноразрядного сумматора последней группы соединен с инверснымивходами вторых слагаемых первого итретьего одноразрядных сумматороввыход переноса последнего сумматорапоследней группы соединен с прямымвходом второго слагаемого четвертогоодноразрядного сумматора, выходысуммы первого, второго, третьего ичетвертого одноразрядных сумматоровсоединены с прямыми входами первогослагаемого пятого, шестого, седьмогои восьмого одноразрядных сумматоровсоответственно, выход переноса каждо -1449986 г. Гречнев СоставительВ, Байко Техрец М,Дид Редак Корректор Г,Решетник Заказ 69674 ВНИИПИ Госуд Тираж 704твенного комитет 113035, Москва,по -3 оизводственно-полиг Фическое предприятие, г. Ужгород, ул . Проектная, 4 го -го одноразрядного сумматора113) соединен с входом переносаЯ +1)-го одноразрядного сумматора,выход переноса четвертого одноразрядного сумматора соединен с прямымивходами второго слагаемого пятого иседьмого одноразрядных сумматоров,выход переноса каждого ш-го одноразрядного сумматора ,5 пй 7) соединенс входом переноса (ш+1)-го одноразрядного сумматора, прямые входы втОрого слагаемого второго, шестого ивосьмого одноразрядных сумматоровсоединены с шиной нулевого потенциала устройства, выходы суммы пятого,шестого, седьмого и восьмого одноразрядных сумматоров соединены с входами первого слагаемого соответствующих одноразрядных сумматоров группыблока свертки, в блоке сверткивход первого слагаемого каждого одноразрядного сумматора группы объецинен с первым входом соответствующегоэлемента И-ИЛИ группы и соответствующим входом элемента И-НЕ, выход которого соединен с первыми входами первого, второго, третьего и четвертого1 элементов И, входы второго слагаемого первого, второго и четвертогоодноразрядных сумматоров группы соединены с шиной нулевого потенциала 5устройства, вхоц второго слагаемоготретьего одноразрядного сумматорагруппы соединен с шиной единичногопотенциала устройства, выходы переноса первого, второго и третьегоодноразрядных сумматоров группы соединены с входами переноса второго,третьего и четвертого одноразрядныхсумматоров группы соответственно, 15 выход переноса четвертого одноразрядного сумматора группы соединенс вторыми входами всех элементовИ-ИЛИ группы и входом элемента НЕ,выход которого соединен с третьимивходами всех элементов И-ИЛИ группы,выход суммы каждого одноразрядногосумматора группы соединен с четвертым входом соответствующего элемента И в И группы, выходы которых сое динены с вторыми входами .соответственно первого, второго, третьего и четвертого элементов И,выходы которыхявляются группой выходов устройства . Подписноезобретениям и открытиям при ГКНТ СССР Раушская наб., д. 4/5
СмотретьЗаявка
4118342, 12.09.1986
ЛЬВОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ ИМ. ЛЕНИНСКОГО КОМСОМОЛА
ЧЕРКАССКИЙ НИКОЛАЙ ВЯЧЕСЛАВОВИЧ
МПК / Метки
МПК: G06F 11/10
Метки: модулю, остатков, формирования
Опубликовано: 07.01.1989
Код ссылки
<a href="https://patents.su/5-1449986-ustrojjstvo-dlya-formirovaniya-ostatkov-po-modulyu.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для формирования остатков по модулю</a>
Предыдущий патент: Устройство для вычисления полярных координат
Следующий патент: Коррелометр
Случайный патент: Способ монтажа опорных колонн плавучей буровой установки