Устройство для деления чисел в системе остаточных классов

(54) УСТРОЙСТВО ДЛЯСИСТЕИЕ ОСТАТОЧНЬ 1 Х ЛЕНИЯ ЧИСЕЛССОВ Ю ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ВТОРСНОМУ СВИДЕТЕЛЬС(57) Изобретение относится к вычислительной технике и предназначенодля быстрого деления целых чисел всистеме остаточных классов. Цельизобретения - повышение быстродействия устройства за счет примененияконвейерного принципа обработки кодов делимого и делителя, Основнымэлементом устройства является высокоскоростной блок масштабированиячисел конвейерного типа. Поставлен-.ная цель достигается введением четырех дополнительных регистров, двухпреобразователей прямого кода в дополнительный, счетчика, узла задержки и двух коммутаторов, 3 ил, 1287Изобретение относится к вычислительной технике и предназначено дляиспользования в быстродействующихарифметических устройствах для выполнения операции делейия чисел, 5представленных в остаточной системесчисления.Цель изобретения - повышение быстродействия устройства.На фиг, 1 представлена структур- Юная схема предлагаемого устройствадля деления в системе остаточныхклассов, на Фиг. 2 - схема блока управления; на фиг, 3 - схема дешифратора, 15Устройство содержит вход 1 запуска устройства, вход делимого 2 и делителя 3 устройства, блок 4 управления, регистр 5 делимого, регистр6 делителя, третий регистр 7, узел 208 задержки, счетчик 9, первый преобразователь 10 прямого кода в дополнительный, блок 11 вычитания, блок12 умножения, блок 13 масштабирования, блок 14 сложения, второй преобразователь 15 прямого кода в дополнительный, первый коммутатор 16,первый и второй регистры 17 и 18, четвертый регистр 19, регистр 20 частоты, второй коммутатор 21, выход 22 30окончания деления устройства, выходыостатка 23 и частного 24 устройства,В состав блока 4 управления входятэлемент 25 задержки, счетчик 26,первыи элемент ИЛИ 27, первый триггер 28, дешифратор 29, элемент НЕ30, второй элемент ИЛИ 31, третийэлемент ИЛИ 32, элемент И 33, второй триггер 34,Дешифратор 29 (фиг. 3) может быть 40реализован с помощью логических элементов типа И 35.1, 35,2, ,35.2ш; (2 ш) - входового элемента ИЛИ36 и (ш) - входового элемента ИЛИ37, . где ш - модуль основания системы счисления.Блок 13 масштабирования представляет собой устройство, осуществляющее деление входного числа Х, принадлежащего диапазону Р, на некоторый положительный масштаб Р 6 Р,число которых ограничено и равно Ь.Модульный код числа, Х и номер1610, 1 Ьмасштаба Бе подаютсясоответственно"на первый и второйвходы блока 13. Результатом операции масштабирования является оценкаУближайшее целое число дроби. Векировки выдачи ненулевой информациипутем подключения к выходам сумматоров коррекции, входящих в его состав, группь элементов И,управляемыхпосредством входа управления выдачейкода блока 13.Набор используемых масштабов иправило их упорядочения определяютсясоотношениемЬ,(Е 01)Б, дгд ье,Х, 2, если Е 1О,где 2 е 10, 1 2"-2), 1 = 20, 1, 2" - 1),Ь= (2" -1 ) 2 ь,.Узел 8 задержки представляет собой цепь из Т+2 регистров, где Тнаименьшее целое число не меньп 1 е1 о 8 К; Е - число оснований системысчисления, выходы Т-го и (Т+2)-гопервый и второй его выходы.По сигналу Г ( Г=1 ),подаваемомучерез вход 1 устройства на первыйвход блока 4 управления, вход приема кода регистра делителя б, установочный вход элемента 8 задержки ивход обнуления счетчика 9, кольцевойсчетчик 26 (фиг. 2), (Т+2)-й региструзла 8 задержки и счетчик 9 обнуляются, триггер 28 блока управленияустанавливается в единичное состояние, элемент НЕ 30 Формирует сигналГ =Г=О, который поступая с первоговыхода блока 4 управления на входысинхронизации блока 13 масштабирования и первого регистра 17, блокирует поступление с их выходов, а, следовательно, и с выходов преобразователя 10 в дополнительный код по модулю М и коммутатора 16 ненулевойкинформации, на выходах элементов ИЛИ31 и 27 вырабатываются соответственно сигналы-го разряда счетчика 26 (1=0,1,Т+5). Так как в данный момент Г=1,то Г =Г =1, благодаря чему в регистр5 через информационный вход 2 устройства записывается модулярный код(0 С"ск) делимого А, а в ре -гистры 6, 7 и 19 через информационный вход 3 устройства поступает модулярный код (р р . делителя В (А, ВеР, 310;сЕ 1=А 1 Р ==В 1=1,21 с. После этого на(3) 52 2блоке 13 масштабирования стандартным образом реализована функция бло 3 128 чинается выполнение операции деления числа А на В.На первом такте операции код ( ,( Р ,) делителя В с выхода регистра 7 поступает на вход блока 35 масп 1 табирования, а номер масштаба, записанный в счетчике 9, на данном такте он равен нулю, подается на вход узла 8 задержки и второй вход блока 13 масштабирования, который по истечении (Т+3)-го такте опредеВ Ьо лит оценку В, дроби , где Р, =2 (формула (1) ), при этом на (Т+1)-ом такте номер масштаба подается также и на третий вход блока 13 с первого выхода узла 8 задержки. Параллельно с этим на каждом такте работы устройства в блоке 4 управления дешифратор 29, анализируя модулярный код некоторого числа Е Е В, по ступающий с выхода регистра 19, вырабатывает сигнаПн л, Ь Ь11 дЗфеф Величинас второго выхода дег 11 ифратора передается в регистр 34,а сигнал с первого выхода дешифратора 29 подается на вход сброса триггера 28 и вторые входы элементов ИЛИ 32 и И 33, на первые входы которнх с инверсного и прямого выходов триггера 28 подаются соответственно величины 30 б и б . В результате элемент ИЛИ 32 формирует сигналл:бЧ А поступающий на счетный вход счетчи ка 26, а на выходе элемента И 33 сфор.мируется сигнал(4)который через шестой выход блока 4 40 управления подается на входы обнуления регистров 18 и 20 и управляющий вход приема кода счетчика 9. Предварительно на счетный вход счетчика 9 с пятого выхода блока 4 подается содержимое ь триггера 28. Так как вначале работы устройства триггер 28 был установлен в единичное состояние то, содержимое счетчика 9 от такта к такту будет увеличиваться на 1 до тех пор, пока.на первом выходе дешифратора 29 не сформируется сигнал д =1, который приведет к сбросу1триггера 28. С этого же момента величина 1 от такта к такту начнет 55 принимать единичное значение. Содержимое счетчика 26 станет ненулевым лип 1 ь в конт 1 е (Т+2)-го такта, когда В е 1 О 1,Т+3,-й раЗряд С ВЫХОда ЭЛЕ 52 4мента 25 задержки поступит величина Г=1. Гоэтому начиная с (Т+3)-го такта (с момента получения оценки В )о и до первого появления на первом выходе дешифратора 29 единичной величины ( А =1) с третьего выхода блокауправления на управляющий вход приема кода регистра 19 будет поступать единичный сигнал (бг =1),вследствие чего выходная инФормация блока 13 масштабирования на каждом из тактов в указанном промежутке времени будет запись 1 ваться в регистр 19.Благодаря конвейерной структуре блока 13 на (1+1)-ом такте (1О) начинается выполнение операции масп 1 табирования делителя на масп 1 таб 8 =2 (формула (1) ), результат которой В будет получен в регистре 19 по истечении (Т+1+3)-го такта. Так как последовательность оценок В Вг ЯвлЯетсЯ абсолютно Убл 1 ваю - щей, то для любого В из диапазона Р системы исчисления существует такойл минимальный номер .гЕ 0,1. 2-1, для которого оценка В 1-ш+1, -ш+2, ,ш. Тогда согласно изложенному на (Т+Ч+4) - ом такте в рассматриваемой при 2=В , на первом выходе дегифуратора 29, а, следовательно, и на выходе элемента И 33 вырабатываются единичные сигналы, а триггер 28 обнуляется, в связи с чем наращивание содержимого счетчика 29 в дальнейшем производиться не будет. Го сигналу Г =1, поступающему с шестого выхода блока 4 управления, регистры 18 и 20 обнуляются, а в группы из младп 1 их 1 и старших Ь разрядов счетчика 9 поступают соответственно номер Ъл с второго выхода элемента 8 задержки и выходная величина з коммутатора 21, где=(В зпрпВь=В згрпВ,Формирование величины 8 осуществляетсяя путем подачи содержимогоВ 26 группы г 1 младптих разрядов К-й гифры модулярного кода числа В , записанного в регистре 19, на первый информационный вход коммутатора 21 и вход преобразователя 15, определяющего вычет -ВЬ, который поступает на второй информационный вход коммутатора 21, при этом на его вход управления с восьмого выхода блока 4 управления подается знак Л числа В, а следовательно, и делителя В, вырабатываемый на втором выходе дешифратора 29 при 7,=В . Если А=О, то(,1=23,) на выходе блока 12лучится произведение й. В, код3.торого передается в регистр 18,на выходе блока 14 сформируется5суммы Е й который по сигналус+7+4)-ом такте содержимое счетчика9 в дальнейшем не изменяется а соответствующий ему масштабл р 0(формула (1 используется в качестве приближения абсолютной величиныделителя В на следующем этапе алгоритма,Второй этап реализуемой процедуры делителя носит итеративный характер. Все итерации имеют одинаковуюдлительность Т+6 тактов, причем первый такт первой итерации во временисовмещен с заключительным (Т+11+4)-ымтактом первого этапа алгоритма,На втором такте первой итерациимодулярный код делимого А с выходарегистра 5 и содержимое второго регистра 18 код нуля подаются соответственно на первый и второй входы блока 11 вычитания, в результате чегона его выходе формируется разностьА,=А-О=А, которая передается в первый регистр 17.На третьем такте первой итерациикод числа А с выхода регистра 17пересылается в регистр 5, а такжеподается на первый информационныйвход коммутатора 16 и вход преобразователя 10 в дополнительный кодпо модулю 1; . Полученный преобразовактелем 10 код числа ) -А ) О к поступает на второй информационный входкоммутатора 16, на вход управлениякоторого с седьмого выхода блока 4управления подается сигнал Ь (знак,числа В). В результате на выходекоммутатора 16 сформируется модулярный код числа Р,=А,з:1 р,пВ которыйпередается в регистр 7. Заметим,чтов текущем такте содержимое б нулеового разряда счетчика 26 принимаетединичное значение, поэтому на входы разрешения записи регистров 5 и7 будет подан единичный сигналГ =1, В течение (Т+3) последних тактов первой итерации блок 13 масштабирования находит модулярный код оценНоки Й дроби -а и он записывается вВрегистр 19, так как на последнем(Т+6)-ом такте каждой итерации 6т+3=1 и, следовательно, на вход разрешения записи регистра 19 с четвертого выхода блока 4 поступит сигнал1=1 .=б =1, поступающему с третьего выт+4хода блока 4 управления, записыва ется в регистр 20 частного, Аналогично первой итерации на втором итретьем тактах ,1-й итерации с помо.щью блока 11 вычитания, регистра 17,преобразователь 10 в дополнительныйкод по модулю Р и коммутатора 16 вКрегистрах 5 и 7 сформируются соответственно модулярные коды чиселА =А. 1-Р,В и Р. =Л вп(В)а по истечении (Т+б)"го такта итераии врегистре 19 будет получена опенкаГ17дробиВОписанйая последовательность действий повторяется до тех пор, пока 25 по окончании некоторой г-й итерации(г ) 1) в выходном регистре 19 блокамасштабирования не будет получен коднуля (й =О). В том случае на третьемвыходе дешифратора 29, а, следовательно, и на выходе 22 устройствапоявится единичный сигнал, Искомоер.частное Ц=Й, и остаток В=В сии=0 маются с выходов 24 и 23 устройства, на этом процесс деления числа А и В Формула и з о б р е т е н и я Устройство для деления чисел в системе остаточных классов, содержащее регистры делимого, делителя и частного, блок вычитания, блок сложения, причем первые информационные входы регистров делимого и делителя являются входами делимого и делителя устройства соответственно, выход регистра частного является выходом частного устройства и соединен с первым информационным входом блока сложения, выход которого соединен с информационным входом регистра частного, о тл и ч а ю щ е е с я тем, что, с целью повьшения быстродействия, в него введены четыре регистра, два преобразователя прямого кода в дополнительныйсчетчикузел задержки, блок масштабирования, два коммутатор и блок управ ения, ьос газ с р.т, 3 287152входят счетчик, два триггера, дешифратор,три элемента ИЛИ,элемент задержки, элемент НЕ и элемент И, причем вход запуска устройства является входом элемента задержки блокауправления и соединен с входом элемента НЕ, с первыми входами первогои второго элементов ИЛИ, с входомразрешения сброса счетчика и с входом установки в единипу триггера 10блока управления, с входом разрешения записи регистра делителя, с тактовым входом узла задержки и входомсброса счетчика устройства, выходрегистра делимого соединен с входом15уменьшаемого блока вычитания, выходкоторого соединен с информационнымвходом первого регистра, выход которого соединен с входом первого преобразователя прямого кода в дополни Отельный, с первой группой информационных входов первого коммутатора и свторым информационным входом регистраделимого, выход регистра делителясоединен с первым информационным вхо дом блока умножения, выход которогосоединен с информационным входом второго регистра, выход которого соединен с .входом вычитаемого блока вычитания, вход делителя устройства 1 Осоединен с первыми информационнымивходами третьего и четвертого регистров, выход третьего регистра является выходом остатка устройства исоединен с входом остаточного кодаблока масштабирования, первый и второй входы номера масштаба которогосоединены с первым выходом узла задержки и информационным выходом счетчика, второй выход узла задержки соеОдинен с входом младших информационных разрядов счетчика, выход которого соединен с входом узла задержки,выход первого преобразователя прямого кода в дополнительный соединен с 45вторым информационным входом первогокоммутатора, выход которого соединенс вторым информационным входом второго регистра, выход блока масштабиро-вания соединен с вторым информационным входом четвертого регистра,выход которого соединен с вторыми информационными входами блоков умножения и сложения, с первой группой информационных входов второго коммутатора, входом второго преобразователяпрямого кода в дополнительный и входом дешифратора блока управления,выход второго преобразователя прямого кода в дополнительный соединен с вторым информационным входом второго коммутатора, выход которого соединен с входом старших информационных разрядов счетчика, выход элемента .НЕ блока управления соединен с входом разрешения записи первого регистра и с входом синхронизации блока масштабирования, выход второго элемента ИЛИ блока управления соединен с входом разрешения записи регистра делимого и третьего регистра, выход (Т+4)-го разряда счетчика блока управления, где- целая часть, Т=1 од Е , К - число основания системы счисления, соединен с входом разрешения записи регистра частного, выход первого элемента ИЛИ блока управления соединен с входом разрешения записи четвертого регистра, прямой выход первого триггера блока управления соединен с первым входом элемента И блока управления и счетным входом счетчика устройства, входразрешения записи которого соединенс входами сброса второго и четвертого регистров и выходом элемента Иблока управления, выход второго триггера которого соединен с входом управления первого коммутатора, выходэлемента задержки блока управлениясоединен с информационным входомсчетчика блока управления, счетныйвход которого соединен с выходом третьего элемента ИЛИ блока управления,первый и второй входы которого соединены соответственно с первым выходомдешифратора и инверсным выходом первого триггера блока управления,выходы нулевого и (Т+3) разрядов счетчика блока управления соединены свторыми входами соответственно второго и первого элемента ИЛИ блокауправления, первый выход дешифратораблока управления соединен с входомразрешения сброса первого триггера .и вторым входом элемента И блока управления, второй выход деппИратораблока управления соединенс информационным входом второго триггераблока управления и входом управления второго коммутатора, третий выход дешифратора блока управления является выходом окончания деления устройства,