Делительное устройство

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5l)4 G 06 F 7/52

ОПИСАНИЕ ИЗОБРЕТЕН

H ABTOPCKOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3723675/24-24 (22) 28.! 2.83 (46) 23.07.85. Бюл. № 27 (72) И. А. Баранов, Ж. Б. Ерема-Еременко и И. A. Лезин (53) 68!.325 (088.8) (56) Карцев М. A. Арифметика цифровых машин, М., «Наука», 1969, с. 515 — 519.

Авторское свидетельство СССР № 1104508, кл. G 06 F 7/52, 1982. (54) (57) ДЕЛИТЕЛЬНОЕ УСТРОЙСТВО, содержащее регистр делителя, регистр остатка, сумматор, сумматор-вычитатель, блок умножителей из и умножителей (и-разрядность операндов), вычитающий счетчик, блок памяти, счетчик и блок управления, который содержит семь D-триггеров, два элемента И вЂ” ИЛИ, четыре элемента ИЛИ, элемент И, два элеме,та НЕ, три элемента задержки, причем вход начальной установки устройства соединен с установочным входом первого D-триггера и входами сброса с второго по седьмой D-триггеров блока управления, вход пуска устройства соединен с первым входом первого элемента И вЂ И блока управления, тактовый вход устройства соединен с тактовыми входами всех

D-триггеров блока управления, выход первого D-триггера блока управления соединен с вторым входом первого элемента И вЂ” ИЛИ, выход которого соединен с информационным входом второго D-триггера, выход которого соединен с первым входом первого элемента ИЛИ и через первый элемент задержки— с информационным входом третьего D-триггера, выход которого соединен с первым входом второго элемента ИЛИ, выход четвертого D-триггера соединен с первым входом третьего элемента ИЛИ, с третьим входом первого элемента И вЂ” ИЛИ и с первым входом второго элемента И вЂ” ИЛИ, выход которого соединен с информационным входом первого D-триггера, выход пятого D-триггера соединен через второй элемент задерж„„Я0„„1168929 д ки с информационным входом шестого Dтриггера, выход которого соединен с вторым входом третьего элемента ИЛИ и первым входом первого элемента И, выход седь мого D-триггера соединен с вторыми входами первого и второго элементов ИЛИ, второй и третий входы второго элемента И-ИЛИ соединены с входом первого элемента

НЕ, выход которого соединен с четвертым входом первого элемента И вЂ” -ИЛИ, Bblxo j первого D-триггера соединен с входом сброса счетчика, выход которого соединен c Входом первого элемента НЕ блока управления, а информационный вход — с выходом второго элемента ИЛИ блока управления, выход третьего D-триггера которого соединен с первым управляющим входом сумматоравычитателя, выходы которого соединены с информационными входами регистра остатка, выходы которого соединены с информационными входами первой группы сумматора-вычитателя, информационные входы второй группы которого соединены с выходами сумматора, первая группа информационных входов которого соединена с выходами нечетных умножителей блока умножителей, выходы четных умножителей которого соединены с второй группой информационных входов сумматора, выход знакового разряда регистра остатка соединен с входом второго элемента НЕ блока управления, выход первого элемента ИЛИ которого соединен с входом сдвига регистра частного, вход записи которого соединен с выходом третьего элемента ИЛИ блока управления, выход пятого D-триггера которого соединен с входом вычитания вычитающего счетчика.; с рвый выход которого соединен с информационным входом регистра частного, а информационный вход — с выходом блока памяти, первая группа входов которого соединена с выходами и/2 старших разрядов регистра делителя, а вторая группа входов— с выходами Il/4 старших разрядов реги Tра делителя, выходы и разрядов которого

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

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

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

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

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

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

l3 управления, вход 14 кода основания системы счисления устройства. Блок 13 управления построен в виде автомата на регистре с перемещаемой единицей. Граф переходов состояний автомата приведен на фиг. 2, где А;, (1 = 0 (1) 6) — состояния автомата. а на дугах указаны условия переходов.

25 которого через третий элемент задержки соединен с информационным входом седьмого

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

D-триггера, с вторым входом элемента И, с первым входом третьего элемента И вЂ” -ИЛИ с первым, вторым, третьим входами четвертого элемента И вЂ” ИЛИ и выходом второго элемента НЕ, вход которого соединен с вторым и третьим входами третьего элемента

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

Блок 13 управления (фиг. 3) содержит

D-триггеры 15 — 21, элементы И вЂ” ИЛИ 22—

25, элементы ИЛИ 26 — 29, элемент И 30, элементы 31 — 33 задержки, элементы НЕ 3436, входы 37 и 38 блока 13 управления, выход 39 тактовых импульсов устройства, вход

40 пуска устройства, вход 41 начальной установки устройства, выходы 42 — 52 блока управления.

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

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

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

Сумматор-вычитатель 4 предназначен для вычитания из очередного остатка (содержимого регистра 1) частичного произведения делителя на очередную цифру частного Сл или К, формируемого в сумматоре

9, а также для инвертирования результата, если предыдущий остаток отрицательный.

Регистр 1 и регистр 3 частного сдвиговые, причем сдвиги в них осуществляются на число разрядов, равное разрядности основания g.

Счетчик 5 предназначен для подсчета числа умножений, которое равно разрядности числа (делимого), деленной на разрядность умножителей. Так, например, для 40разрядных мантисс и 4-разрядных умножителей число умножений равно 10. Разрядность счетчика 5 или код дополнения выбираются таким образом, что появление единицы в старшем разряде означает завершение выполнения операции деления.

Вычитатель 11 предназначен для полу-, чения величины Кд по формуле К„=g — Сл.

Он представляет собой сумматор, выполняющий операцию вычитания из одного и того же числа g аппроксимируемой очередной цифры частного.

Коммутатор 12 предназначен для подключения первых входов умножителей 10 либо к вычитающему счетчику 7, либо к вычитателю 1 1.

Назначение остальных функциональных элементов совпадает с их названием.

В основе работы делительного устройства лежит алгоритм деление Евклида.

Получение очередного остатка осуществляется либо по формуле

Юл+1 = Wg g — „ВСл(1), причем /W„+ /а0, с аппроксимацией очередной цифры частного С л при

/С„Ф/ Clt (1, 40 либо по формуле / л+1 = — (%д g — Кл), где g — основание счисления;

D — делитель;

Сл — очередная цифра частного;

Кл= g — Cn

Устройство работает следующим образом.

Исходное состояние устройства следующее. В регистре 1 находится делимое, нормализованное по основанию g, в регистре 2 - 50 делитель, нормализованный по двоичному основанию. Регистр частного обнулен. В счетчике 5 сигналом «Сб.Сч.» подтверждается исходное число: либо нуль, либо код, дополняющий его до переполнения.

При поступлении сигнала «Пуск» устройство переходит из состояния А0 в состояние А>. В этом состоянии формируются сиг29

4 налы «Зп 1» и «П 1». По сигналу «Зп 1» по значениям старших цифр делимого и делителя цифра Сп из блока 8 считывается на вычитающий счетчик 7, а по сигналу «П 1» первые входы умножителей 10 подключаются через коммутатор 12 к вычитающему счетчику 7.

Далее автомат по очередному тактовому импульсу переходит в состояние А . Формируются сигналы «Зп 2» и «+1 Сч Т». По сигналу «3п 2» в сумматоре 4 выполняется операция вычитания по формуле (1), и очередной остаток заносится в регистр 1, а по сигналу «+1 Cr Т» в счетчик 5 добавляется единица.

Затем осуществляется анализ знака очередного остатка, поступающего на вход 37 блока 13. Если очередной остаток не отрицательный, то обеспечивается переход автомата в состояние Аэ, иначе автомат переходит в состояние А .

Рассмотрим первоначально работу устройства для случая, когда очередной остаток неотрицательный.

В состоянии Аз формируется сигнал «ЗП

3», по которому цифра С» принимается в качестве Сл и заносится в регистр 3 частного.

Заметим, что запись цифры каждый раз осуществляется в старшие разряды регистра, число которых определяется величиной

g, а подготовка записи-сдвигом содержимого регистра 3 в сторону младших разрядов по сигналу «Cg 1» в состоянии автомата А или Aq. Осуществляется анализ условия (CrT=n). Если условие не выполняется, то автомат переходит в состояние А, и устройство работает аналогично рассмотренному, иначе автомат переходит в состояние А„и на этом выполнение операции завершается.

В том случае, если очередной остаток отрицательный, автомат, перейдя в состояние А+ формирует сигналы «-!» и «Зп 3».

По сигналу «-1» содержимое счетчика 7 уменьшается на единицу, а модифицированная таким образом цифра частного по сигналу «Зп 3» заносится в регистр 3.

Осуществляется анализ условия (CrT=

= п). Если условие не выполняется, то автомат переходит в состояние А«, иначе— в состояние А, и на этом выполнение операции завершается. В состоянии А формируются сигналы «Зп 1» и «П 2». По сигналу «Зп 1» по значениям старших цифр очередного остатка и делителя из блока 8 в счетчик 7 считывается цифра C„". По сигналу

«П2» первые входы умножителей 10 подсоединяются через коммутатор 2 к выходам вычитателя 11, на выходе которого форми» руется величина K„= g — Сл.

Затем автомат переходит в состояние А, в котором формируются сигналы «+ IC«T», «Зп4» и «Cgl». По сигналу «Зп4» в сумматоре 4 выполняется операция вычитания по формуле (2), и очередной остаток заносится

11б8929

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

А переходит в состояние А, завершая, таким образом, выполнение операции деления без восстановления остатка.

1168929

Фиг. Z

Составитель Е. Захарченко

Редактор В. Данко Техред И. Верес Корректор Л. Тяско

Заказ 4614/42 Тираж 710 Г1одписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4