устройство для деления
Классы МПК: | G06F7/52 для умножения; для деления |
Автор(ы): | Сафонова Э.М., Шостак А.А. |
Патентообладатель(и): | Научно-исследовательский институт электронных вычислительных машин |
Приоритеты: |
подача заявки:
1991-07-03 публикация патента:
30.08.1994 |
Изобретение относится к вычислительной технике и может быть использовано в быстродействующих арифметических устройствах для выполнения операции деления чисел. По сравнению с устройством - прототипом предложенное устройство позволяет сократить длительность такта работы при большой разрядности операндов и малом количестве цифр частного, формируемых в течение такта. Устройство содержит первый 1 и второй 2 регистры остатка, регистр 3 делителя, регистр 4 частного, сумматор 5 принудительного округления делителя, узел 6 вычисления обратной величины, два сумматора 7,8, два блока 9,10 умножения, вычитатель 11, первый коммутатор 12, селектор 16, элемент НЕ 15, блок 17 микропрограммного управления и введенные второй 13 и третий 14 коммутаторы. 1 табл., 5 ил.
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6
Формула изобретения
УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ, содержащее два регистра остатка, регистр делителя, регистр частного, сумматор принудительного округления, узел вычисления обратной величины, два сумматора, два блока умножения, первый коммутатор, селектор, вычитатель, элемент НЕ и блок микропрограммного управления, причем вход данных устройства соединен с информационным входом регистра делителя и с первым информационным входом первого коммутатора, выход которого соединен с информационным входом первого регистра остатка, выход первого сумматора является выходом результата устройства и соединен с входом уменьшаемого вычитателя, входы вычитаемого и заема которого соединены с выходами первой и второй групп первого блока умножения соответственно, выходы разности и заема вычитателя соединены с вторым информационным входом первого коммутатора и информационным входом второго регистра остатка соответственно, выходы старших разрядов первого и второго регистров остатка соединены с первым и вторым информационными входами второго сумматора соответственно, выход младших разрядов которого соединен с первым информационным входом второго блока умножения, второй информационный вход которого соединен с выходом узла вычисления обратной величины, вход которого соединен с выходом сумматора принудительного округления, информационный вход которого соединен с выходом старших разрядов регистра делителя, выход которого соединен с первым информационным входом первого блока умножения, второй информационный вход которого соединен с информационным входом младших разрядов регистра частного и выходом селектора, информационный вход которого соединен с выходом второго блока умножения, вход переноса сумматора принудительного округления является входом логической единицы устройства, выход старшего разряда второго сумматора соединен с входом элемента НЕ, выход которого соединен с управляющим входом селектора, вход синхронизации устройства соединен с синхровходами первого и второго регистров остатка, регистра делителя, регистра частного и блока микропрограммного управления, первый выход которого соединен с первым управляющим входом первого коммутатора и входом установки в "0" второго регистра остатка, второй выход блока микропрограммного управления соединен с вторым управляющим входом первого коммутатора и входами разрешения записи второго регистра остатка и регистра частного, третий и четвертый выходы блока микропрограммного управления соединены с входами разрешения записи первого регистра остатка и регистра делителя соответственно, пятый выход блока микропрограммного управления является выходом признака окончания деления устройства, отличающееся тем, что в устройство введены второй и третий коммутаторы, причем выход первого регистра остатка соединен с первым информационным входом второго коммутатора, второй информационный вход которого соединен с первым выходом регистра частного, выход второго регистра остатка соединен с первым информационным входом третьего коммутатора, второй информационный вход которого соединен с вторым выходом регистра частного, выход второго коммутатора соединен с первым информационным входом первого сумматора, второй информационный вход которого соединен с выходом третьего коммутатора, первые управляющие входы второго и третьего коммутаторов соединены с вторым выходом блока микропрограммного управления, шестой выход которого соединен с вторыми управляющими входами второго и третьего коммутаторов.Описание изобретения к патенту
Изобретение относится к вычислительной технике и может быть применено в быстродействующих арифметических устройствах для выполнения операции деления чисел. Известно устройство для деления, формирующее в каждом такте k цифр частного (2![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-2t.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-3t.gif)
величины, два блока умножения, три вычитателя, коммутатор, селектор, элемент НЕ и блок микропрограммного управления [2]. Данное устройство имеет низкое быстродействие вследствие большой длительности такта работы. Наиболее близким по технической сущности к изобретению является устройство для деления, формирующее в каждом такте k цифр частного (2
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-4t.gif)
микропрограммного управления, причем вход данных устройства соединен с информационным входом регистра делителя и с первым информационным входом коммутатора, выход которого соединен с информационным входом первого регистра остатка, выходы первого и второго регистров остатка соединены соответственно с первым и вторым информационными входами первого сумматора, выход которого является выходом остатка устройства
и соединен с входом уменьшаемого вычитателя, входы вычитаемого и заема которого соединены с выходами первой и второй групп первого блока умножения соответственно, выходы разности и заема вычитателя соединены с вторым информационным входом коммутатора и информационным входом второго регистра остатка соответственно, выходы старших разрядов первого и второго регистров остатка соединены с первым и вторым информационными
входами второго сумматора соответственно, выход младших разрядов которого соединен с первым информационным входом второго блока умножения, второй информационный вход которого соединен с выходом узла вычисления обратной величины, вход которого соединен с выходом сумматора принудительного округления делителя, информационный вход которого соединен с выходом старших разрядов регистра делителя, выход которого соединен с первым информационным
входом первого блока умножения, второй информационный вход которого соединен с информационным входом младших разрядов сумматора частного и выходом селектора, информационный вход которого соединен с выходом второго блока умножения, вход переноса сумматора принудительного округления является входом
логической "1" устройства, выход старшего разряда второго сумматора соединен с входом элемента НЕ, выход которого соединен с управляющим входом селектора, вход синхронизации устройства соединен с синхровходами первого и второго регистров остатка, регистра делителя, сумматора частного и блока микропрограммного управления, первый выход которого соединен с первым управляющим входом коммутатора и входами установки в ноль второго регистра остатка и сумматора частого, выход которого является выходом
частного устройства, второй выход блока микропрограммного управления соединен с вторым управляющим входом коммутатора и входами разрешения записи второго регистра остатка и сумматора частного, третий и четвертый выходы блока микропрограммного управления соединены с входами разрешения записи первого регистра остатка и регистра делителя соответственно, пятый выход блока микропрограммного управления является выходом признака окончания деления устройства [3]. Недостаток известного устройства - относительно низкое быстродействие, так как при большом значении n и малом значении k время срабатывания сумматора частного становится больше времени срабатывания первого блока умножения и вычитателя вместе взятых. Повышение быстродействия достигается тем, что в устройство для деления, содержащее два регистра остатка, регистр делителя, регистр частного, сумматор принудительного округления, узел вычисления обратной величины, два сумматора, два блока умножения, первый коммутатор, селектор, вычитатель, элемент НЕ и блок микропрограммного управления, причем вход данных устройства соединен с информационным входом регистра делителя и с первым информационным входом первого коммутатора, выход которого соединен с информационным входом первого регистра остатка, выход первого сумматора является выходом результата устройства и соединен с входом уменьшаемого вычитателя, входы вычитаемого и заема которого соединены с выходами первой и второй групп первого блока умножения соответственно, выходы разности и заема вычитателя соединены с вторым информационным входом первого коммутатора и информационным входом второго регистра остатка соответственно, выходы старших разрядов первого и второго регистров остатка соединены с первым и вторым информационными входами второго сумматора соответственно, выход младших разрядов которого соединен с первым информационным входом второго блока умножения, второй информационный вход которого соединен с выходом узла вычисления обратной величины, вход которого соединен с выходом сумматора принудительного округления, информационный вход которого соединен с выходом старших разрядов регистра делителя, выход которого соединен с первым информационным входом первого блока умножения, второй информационный вход которого соединен с информационным входом младших разрядов регистра частного и выходом селектора, информационный вход которого соединен с выходом
второго блока умножения, вход переноса сумматора принудительного округления является входом логической "1" устройства, выход старшего разряда второго сумматора соединен с входом элемента НЕ, выход которого соединен с управляющим входом селектора, вход синхронизации устройства соединен с синхровходами первого и второго регистров остатка, регистра делителя, регистра частного и блока микропрограммного управления, первый выход которого соединен с
первым управляющим входом первого коммутатора и входом установки в ноль второго регистра остатка, второй выход блока микропрограммного управления соединен с вторым управляющим входом первого коммутатора и входами разрешения записи второго регистра остатка и регистра частного, третий и четвертый выходы блока
микропрограммного управления соединены с входами разрешения записи первого регистра остатка и регистра делителя соответственно, пятый выход блока микропрограммного управления является выходом признака окончания деления устройства, введены второй и третий коммутаторы, причем выход первого регистра остатка соединен с первым информационным входом второго коммутатора, второй информационный вход которого соединен с
первым выходом регистра частного, выход второго регистра остатка соединен с первым информационным входом третьего коммутатора, второй информационный вход которого соединен с вторым выходом регистра частного, выход второго коммутатора соединен с первым информационным входом первого сумматора, второй информационный вход которого соединен с выходом третьего коммутатора, первые управляющие входы второго и третьего коммутаторов соединены с вторым выходом блока микропрограммного управления, шестой выход которого соединен с вторыми управляющими входами второго и третьего коммутаторов. Заявляемое устройство для
деления содержит отличительные признаки, не обнаруженные ни в одном из известных устройств - наличие второго и третьего коммутаторов с соответствующими связями. Эти признаки позволяют повысить быстродействие устройства за счет сокращения длительности такта работы при большом значении n и малом значении k. Таким образом, так как в заявляемом техническом решении имеются отличительные признаки, обеспечивающие достижение цели и не обнаруженные ни в одном другом известном аналогичном техническом решении, то оно соответствует критерию "существенные отличия". На фиг. 1 приведена структурная схема предлагаемого устройства для деления; на фиг. 2 показано расположение k-разрядных групп цифр Zi частного в регистре частного для случая n = 16, k = 4, M = 5 (M - число тактов собственно деления, определяемое по формуле
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-5t.gif)
1 и 2 соответственно, выходы 24 и 25 старших разрядов регистров 1 и 2 соответственно, выход 26 регистра 3, выход 27 старших разрядов регистра 3 делителя, выход 28 сумматора 5, выход 29 узла 6 вычисления обратной величины, выходы 30 и 31 младших разрядов и старшего разряда второго сумматора 8 соответственно, выход 32 второго блока
10 умножения, выход 33 селектора 16, выходы 34, 35 первой и второй групп первого блока 9 умножения соответственно, первый 36 и второй 37 выходы регистра 4 частного, выходы 38 и 39 второго 13 и третьего 14 коммутаторов соответственно, выход 40 первого сумматора 7, выходы 41 и 42 разности и заема вычитателя 11 соответственно, выход 43 коммутатора 12, выходы 44-49 блока 17 микропрограммного управления соответственно. Вход 18 данных устройства соединен с информационным входом регистра 3 делителя и с первым информационным входом коммутатора 12, выход 43 которого соединен с информационным входом первого регистра 1 остатка. Выходы 22 и 23 первого 1 и второго 2 регистров остатка соединены с первыми информационными входами соответственно второго
13 и третьего 14 коммутаторов, вторые информационные входы которых соединены с первым 36 и вторым 37 выходами регистра 4 частного соответственно. Выходы 38 и 39 второго 13 и третьего 14 коммутаторов соединены соответственно с первым и вторым информационными входами первого сумматора 7, выход 40 которого является выходом 21 результата устройства и соединен с входом уменьшаемого вычитателя 11, входы вычитаемого и заема которого соединены с
выходами 34 и 35 первой и второй групп первого блока 9 умножения соответственно. Первый информационный вход первого блока 9 умножения соединен с выходом 26 регистра 3 делителя, выходы 41 и 42 разности и заема вычитателя 11 соединены с вторым информационным входом коммутатора 12 и информационным входом второго регистра 2 остатка соответственно. Выходы 24 и 25 старших разрядов первого 1 и второго 2 регистров остатка соединены с первым и вторым информационными входами второго сумматора 8 соответственно, выход 30 младших разрядов которого соединен с первым информационным входом второго блока 10 умножения. Выход 31 старшего разряда второго
сумматора 8 соединен с входом элемента НЕ 15, выход которого соединен с управляющим входом селектора 16, информационный вход которого соединен с выходом 32 второго блока 10 умножения. Выход 33 селектора 16 соединен с информационным входом младших разрядов регистра 4 частного и с вторым информационным входом первого блока 9 умножения, выход 27 старших разрядов регистра 3 делителя соединен с информационным входом сумматора 5 принудительного округления. Вход 20 логической "1" устройства соединен с входом переноса сумматора 5 принудительного округления, выход 28
которого соединен с информационным входом узла 6 вычисления обратной величины, выход 29 которого соединен с вторым информационным входом второго блока 10 умножения. Вход 19 синхронизации устройства соединен с синхровходами первого 1 и второго 2 регистров остатка, регистра 3 делителя, регистра 4 частного и блока 17 микропрограммного управления, первый выход 44 которого соединен с первым управляющим входом коммутатора 12 и входом установки в ноль второго регистра 2 остатка. Второй выход 45 блока 17 микропрограммного управления соединен с вторым управляющим входом коммутатора 12, с входами разрешения
записи регистров 2, 4 и с первыми управляющими входами второго 13 и третьего 14 коммутаторов, третий 46 и четвертый 47 выходы блока 17 микропрограммного управления соединены с входами разрешения записи первого регистра 1 остатка и регистра 3 делителя соответственно, пятый выход 48 блока 17 микропрограммного управления является выходом признака окончания деления устройства, шестой выход 49 блока 17 микропрограммного управления соединен с вторыми управляющими входами
второго 13 и третьего 14 коммутаторов. Первый регистр остатка (n+2)-разрядный, из которых два разряда расположены слева от запятой, а остальные - справа от запятой. В исходном состоянии в разрядах справа от запятой этого регистра хранится n-разрядный двоичный код делимого без знака, а в процессе деления в него записываются значения разности очередных остатков. Второй регистр 2 остатка содержит n+1 разрядов, из которых два расположены слева от запятой, а остальные - справа. В исходном состоянии этот регистр обнулен, а в процессе деления в него записывается значение заемов очередных остатков. Регистр 3 делителя n-разрядный, причем все разряды расположены справа от запятой. В регистре 3 делителя в исходном состоянии хранится n-разрядный двоичный код делителя без знака. Регистр 4 частного предназначен для хранения частного k-разрядных групп цифр Zi частного. В тактах собственно деления работы устройства в регистр 4 частного записываются k-разрядные группы цифр Zi частного. Для этого в младшие разряды регистра 4 частного, содержимое которого сформировано на предыдущих тактах работы устройства и сдвинуто на k разрядов в сторону старших разрядов, заносятся k цифр частного, полученных на выходе 33 селектора 16 в текущем такте работы устройства. Запись информации в регистр 4 частного осуществляется по синхроимпульсу при наличии разрешающего потенциала на его входе разрешения записи, который подключен к второму выходу 45 блока 17 микропрограммного управления. Предполагается, что все регистры устройства реализованы на двухтактных синхронных DV-триггерах. Запись информации в регистры производится по синхроимпульсу при наличии разрешающего потенциала на их V-входах. Формирование k цифр частного в каждом такте работы устройства деления производится путем умножения однорядного кода усеченного остатка, сформированного на выходе 30 младших разрядов второго сумматора 8, на значение старших разрядов обратной величины усеченного делителя, подаваемое с выходов 29 узла 6 вычисления обратной величины. Чтобы устранить возможность получения в устройстве k цифр частного с избытком, значение старших разрядов делителя, поступающее с выхода 27 старших разрядов регистра 3 делителя, увеличивается на единицу младшего разряда в сумматоре 5 принудительного округления. Пусть делимое X и делитель Y есть нормализованные двоичные дроби, т.е. 1/2
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018045/8773.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-6t.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018085/729.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018085/729.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018085/729.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018085/729.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018101/964.gif)
V1 = (M+3)
![устройство для деления, патент № 2018933](/images/patents/455/2018085/729.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-7t.gif)
Tпрот - длительность одного такта работы устройства-прототипа. Время работы предлагаемого устройства при делении на нем n-разрядных чисел определяется по формуле
V2 = (M+4)
![устройство для деления, патент № 2018933](/images/patents/455/2018085/729.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018933/2018933-8t.gif)
Tпредл. - длительность одного такта работы предлагаемого устройства. При n= 64 и k=4 время работы устройства-прототипа V1=1200
![устройство для деления, патент № 2018933](/images/patents/455/2018101/964.gif)
![устройство для деления, патент № 2018933](/images/patents/455/2018101/964.gif)
Класс G06F7/52 для умножения; для деления