Делительное устройство Советский патент 1985 года по МПК G06F7/52 

соединены с информационными входами соответствующих умножителей блока умножителей и с третьей группой информационных входов сумматора-вычитателя, отличающееся тем, что, с целью повышения быстродействия, в него введены вычитатель и коммутатор, а блок управления дополнительно содержит два элемента И-ИЛИ и элемент НЕ, причем вход кода основания системы счисления устройства соединен с первым входом вычитателя, второй вход которого соединен с вторым выходом вычитающего счетчика и первым информационным входом коммутатора, второй информационный вход которого соединен с выходом вычитателя, управляющие входы умножителей блока умножителей соединены с выходом коммутатора, первый управляющий вход которого сое динен с выходом седьмого D-триггера блока управления, выход второго D-триггера которого соединен с вторым управляющим входом коммутатора и с первым входом четвертого элемента ИЛИ блока управления, выход которого соединен с входом записи вычитающего счетчика, вход записи регистра остатка соединен с выходом элемента И блока управления, выход щестого D-триггера

которого через третий элемент задержки соединен с информационным входом седьмого D-триггера блока управления и .с вторым управляющим входом сумматора-вычитателя, а в блоке управления информационный вход четвертого D-триггера соединен с выходом третьего элемента И-ИЛИ, первый вход которого соединен с выходом третьего D-триггера, с вторым входом элемента И, с первым входом третьего элемента И-ИЛИ с первым, вторым, третьим входами четвертого элемента И-ИЛИ и выходом второго элемента НЕ, вход которого соединен с вторым и третьим входами третьего элемента И-ИЛИ, четвертые входы третьего и четвертого элементов И-ИЛИ соединены с выходом седьмого D -триггера, информационный вход пятого D -TpHrrepa соединен с выходом четвертого элемента И-ИЛИ, второй вход четвертого элемента ИЛИ соединен с первым входом элемента И, вход пуска устройства соединен с входом третьего элемента НЕ, выход которого соединен с четвертым входом второго элемента И-ИЛИ, пятый и щестой входы которого соединены соответственно с выходами первого и пятого D-триггеров.

ДЕЛИТЕЛЬНОЕ УСТРОЙСТВО, содержащее регистр делителя, регистр остатка, сумматор, су.мматор-вычитатель, блок умножителей из п умножителей (п-разрядность операндов), вычитающий счетчик, блок иамяти, счетчик и блок управления, который содержит семь D-триггеров, два элемента И-ИЛИ, четыре элемента ИЛИ, элемент И, два элеме,та НЕ, три элемента задержки, приче.м вход начальной установки устройства соединен с установочным входом цервого D-триггера и входами сброса с второго по седьмой D-триггеров блока уцравления, вход пуска устройства соединен с первым входом первого элемента И-ИЛИ блока управления, тактовый вход устройства соединен с тактовыми входами всех D-триггеров блока управления, выход первого D-триггера блока управления соединен с вторым входом первого элемента И-ИЛИ, выход которого соединен с информационным входом второго D-триггера, выход которого соединен с первым входом первого элемента ИЛИ и через первый элемент задержки - с информационным входом третьего D-триггера, выход которого соединен с первым входом второго элемента ИЛИ, выход четвертого D-триггера соединен с первым входом третьего элемента ИЛИ, с третьим входом первого элемента И - ИЛИ и с первым входом второго элемента И-ИЛИ, выход которого соединен с информационным входом первого D-триггера, выход пятого D-тркггера соединен через второй элемент задержки с информационным входом шестого Dтриггера, выход которого соединен с вторым входом третьего элемента ИЛИ и первым входом первого элемента И, выход седьмого D-триггера соединен с вторыми входами первого и второго элементов ИЛИ, второй и третий входы второго элемента И ИЛИ соединены с входом первого элемента НЕ, выход которого соединен с четвертым входо.м первого элемента И-ИЛИ, выход первого D-триггера соединен с входом сброса счетчика, выход которого соединен о входом первого элемента НЕ блока управления, а информационный вход - с выходом второго элемента ИЛИ блока управления, выход третьего D-триггера которого соединен с первым управляющим входом сумматораiS вычитателя, выходы которого соединены с (Л информационными входами регистра остатка, выходы которого соединены с информационными входами первой группы сумматора-вычитателя, информационные входы второй группы которого соединены с выходами сумматора, первая группа информационных входов которого соединена с выходами нечетных умножителей блока умножителей, выходы четных умножителей которого соединены с второй группой информационных О5 входов сумматора, выход знакового разря00 да регистра остатка соединен с входом втосо ю рого элемента НЕ блока управления, выход первого элемента ИЛИ которого соединен с входом сдвига регистра частного, вход засо писи которого соединен с выходом третьего элемента ИЛИ блока управления, выход пятого D-триггера которого соединен с входом вычитания вычитающего счетчика, iiepвый выход которого соединен с информационным входом регистра частного, а информационный вход - с выходом блока памяти, первая группа входов которого соединена с выходами п/2 старщих разрядов регистра делителя, а вторая группа входов - с выходами п/4 старших разрядов регистра делителя, выходы п разрядов KOTopttrci

Изобретение относится к цифровой вычис-лительной технике и может быть использовано при построении арифметических устройств быстродействующих ЦВМ с жесткими ограничениями на массогабаритные характеристики и энергопотребление.

Целью изобретения является повыщение быстродействия устройства путем выполнения операции деления без восстановления остатка.

На фиг. 1 приведена структурная схема делительного устройства; на фиг. 2 - граф переходов состояний автомата; на фиг. 3 - схема блока управления.

Делительное устройство (фиг. 1) содержит регистр 1 остатка, регистр 2 делителя, регистр 3 частного сумматор-вычитатель 4, счетчик 5, блок 6 умножителей, вычитающий счетчик 7, блок 8 памяти, сумматор 9, умножители 10 многоразрядного блока 6 умножителей, вычитатель 11, коммутатор 12, блок 13 управления, вход 14 кода основания системы счисления устройства. Блок 13 управления построен в виде автомата на регистре с перемещаемой единицей. Граф переходов состояний автомата приведен на фиг. 2, где Aj, ((1)6) - состояния автомата, а на дугах указаны условия переходов.

Блок 13 управления (фиг. 3) содержит D-триггеры 15-21, элементы И-ИЛИ 22- 25, элементы ИЛИ 26-29, элемент И 30, элементы 31-33 задержки, элементы НЕ 3436, входы 37 и 38 блока 13 управления, выход 39 тактовых импульсов устройства, вход 40 пуска устройства, вход 41 начальной установки устройства, выходы 42-52 блока управления.

Основу автомата составляют семь D-триггеров с асинхронными S- и R-входами.

Внешними сигналами устройства являются сигналы «Пуск, «Начальная установка, тактовый и вход кода q основания системы счисления.

Для определенности будем полагать, что умножители 10 четырехразрядные. В этом случае в регистре 2 делитель в исходном состоянии нормализован по двоичному основанию, и на адресный вход блока 8 памяти подключены 1-4 разряды регистра 2, а прошивка блока 8 сделана с учетом того, что содержимое старщего нулевого разряда равно единице. При этом достигается точность определения цифры частного при реализации алгоритма ускоренного деления. Адресные

входы старших разрядов блока 8 соединены с пятью (в случае использования 4-разрядных умножителей) старшими разрядами регистра 1 остатка, который используется для хранения первоначально делимого, а в последующем - очередного остатка. Сумматор-вычитатель 4 предназначен для вычитания из очередного остатка (содержимого регистра 1) частичного произведения делителя на очередную цифру частного Сп или Кп,..формируемого в сумматоре 9, а также для инвертирования результата, если предыдущий остаток отрицательный, Регистр 1 и регистр 3 частного сдвиговые, причем сдвиги в них осуществляются на число разрядов, равное разрядности основания g. Счетчик 5 предназначен для подсчета числа умножений, которое равно разрядности числа (делимого), деленной на разрядность умножителей. Так, например, для 40разрядных мантисс и 4-разрядных умножителей число умножений равно 10. Разрядность счетчика 5 или код дополнения выбираются таким образом, что появление единицы в старщем разряде означает заверщение выполнения операции деления. Вычитатель 11 предназначен для получения величины Кд по формуле . Он представляет собой сумматор, выполняющии операцию вычитания из одного и того же числа g аппроксимируемой очередной цифры частного. Коммутатор 12 предназначен для подключения первых входов умножителей 10 либо к вычитающему счетчику 7, либо к вычитателю 11. Назначение остальных функциональных элементов совпадает с их названием. В основе работы делительного устройства лежит алгоритм деление Евклида. Получение очередного остатка осуществляется либо по формуле W«M Wng-.DCh(l), причем /Wn+i/ 4D, с аппроксимацией очередной цифры частного Сп при , либо по формуле Wn+i -(Wrtg-DKn),(2) где g - основание счисления; JD - делитель; Сп - очередная цифра частного; Кп g-Сн. Устройство работает следующим образом. Исходное -состояние устройства следующее. В регистре 1 находится делимое, нормализованное по основанию g, в регистре 2 делитель, нормализованный по двоичному основанию. Регистр частного обнулен. В счетчике 5 сигналом «Сб.Сч. подтверждается исходное число: либо нуль, либо код, дополняющий его до переполнения. При поступлении сигнала «Пуск устройство переходит из состояния АО в состояние А. В этом состоянии формируются сигналы «Зп 1 и «П 1. По сигналу «Зп 1 по значениям старших цифр делимого и делителя цифра Сп из блока 8 считывается на вычитающий счетчик 7, а по сигналу «П 1 первые входы умножителей 10 подключаются через коммутатор 12 к вычитающему счетчику 7. Далее автомат по очередному хактовому импульсу переходит в состояние Aj. Формируются сигналы «Зп 2 и « + 1 Сч Т. По сигналу «Зп 2 в сумматоре 4 выполняется операция вычитания по формуле (1), и очередной остаток заносится в регистр 1, а по сигналу « + 1 Сг Т в счетчик 5 добавляется единица. Затем осуществляется анализ знака очередного остатка, поступающего на вход 37 блока 13. Если очередной остаток не отрицательный, то обеспечивается переход автомата в состояние Aj, иначе автомат переходит в состояние А. Рассмотрим первоначально работу устройства для случая, когда очередной остаток неотрицательный. В состоянии АЗ формируется сигнал «ЗП 3, по которому цифра С принимается в качестве Си и заносится в регистр 3 частного. Заметим, что запись цифры каждый раз осуществляется в старщие разряды регистра, число которых определяется величиной g, а подготовка записи-сдвигом содержимого регистра 3 в сторону младщих разрядов по сигналу «Cg 1 в состоянии автомата А или Ag. Осуществляется анализ условия СгТ п. Если условие не выполняется, то автомат переходит в состояние А;,.и устройство работает аналогично рассмотренному, иначе автомат переходит в состояние АО, и на этом выполнение операции заверщается. В том случае, если очередной остаток отрицательный, автомат, перейдя в состояние AJ, формирует сигналы «-I и «Зп 3. По сигналу «-1 содержимое счетчика 7 уменьщается на единицу, а модифицированная таким образом цифра частного по сигналу «Зп 3 заносится в регистр 3. Осуществляется анализ условия СгТ п. Если условие не выполняется, то автомат переходит в состояние AS, иначе - в состояние Ар,..и на этом выполнение операции заверщается. В состоянии Ag формируются сигналы «Зп I и «П 2. По сигналу «Зп 1 по значениям старших цифр очередного остатка и делителя из блока 8 в счетчик 7 считывается цифра Сд. По сигналу «П2 первые входы умножителей 10 подсоединяются через коммутатор 12 к выходам вычитателя 11, на выходе которого формируется величина Kji g-С. Затем автомат переходит в состояние Ag, в котором формируются сигналы «-f 1СчТ, «Зп4 и «Cgl. По сигналу «Зп4 в сумматоре 4 выполняется операция вычитания по формуле (2), и очередной остаток заносится

в регистр 1, а по сигналу «+1СчТ в счетчик 5 добавляется единица. Аналогично осуществляется анализ знака очередного остатка. Если очередной остаток неотрицательный, то автомат переходит в состояние АЗ, иначе - в состояние А. Далее устройство

работает аналогично рассмотренному до появления сигнала «СчТ, по которому автомат либо с состояния АЗ, либо с состояния А4 переходит в состояние АО, завершая, таким образом, выполнение операции деления без восстановления остатка.

.г

f

Ni