Устройство для деления

 

Изобретение относится к вычислительной технике и может быть использовано в быстродействующих арифметических устройствах для выполнения операции деления чисел. По сравнению с устройством - прототипом предложенное устройство позволяет сократить длительность такта работы при большой разрядности операндов и малом количестве цифр частного, формируемых в течение такта. Устройство содержит первый 1 и второй 2 регистры остатка, регистр 3 делителя, регистр 4 частного, сумматор 5 принудительного округления делителя, узел 6 вычисления обратной величины, два сумматора 7,8, два блока 9,10 умножения, вычитатель 11, первый коммутатор 12, селектор 16, элемент НЕ 15, блок 17 микропрограммного управления и введенные второй 13 и третий 14 коммутаторы. 1 табл., 5 ил.

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

Известно устройство для деления, формирующее в каждом такте k цифр частного (2≅ k≅ ][ где n - разрядность делимого и делителя) и содержащее два регистра остатка, регистр делителя, сумматор частного, сумматор принудительного округления делителя, узел вычисления обратной величины, два сумматора, два блока умножения, селектор, коммутатор, вычитатель, элемент И-НЕ и блок микропрограммного управления [1].

Основным недостатком этого устройства является низкое быстродействие из-за большой длительности такта работы.

Известно устройство для деления, формирующее в каждом такте k цифр частного (2≅ k≅ ][ , где n - разрядность делимого и делителя) и содержащее два регистра остатка, регистр делителя, сумматор частного, сумматор принудительного округления делителя, узел вычисления обратной величины, два блока умножения, три вычитателя, коммутатор, селектор, элемент НЕ и блок микропрограммного управления [2].

Данное устройство имеет низкое быстродействие вследствие большой длительности такта работы.

Наиболее близким по технической сущности к изобретению является устройство для деления, формирующее в каждом такте k цифр частного (2≅ k≅ ][ , где n - разрядность делимого и делителя) и содержащее два регистра остатка, регистр делителя, сумматор частного (он является композицией комбинационного сумматора и регистра частного), сумматор принудительного округления, узел вычисления обратной величины, два сумматора, два блока умножения, коммутатор, селектор, вычитатель, элемент НЕ и блок микропрограммного управления, причем вход данных устройства соединен с информационным входом регистра делителя и с первым информационным входом коммутатора, выход которого соединен с информационным входом первого регистра остатка, выходы первого и второго регистров остатка соединены соответственно с первым и вторым информационными входами первого сумматора, выход которого является выходом остатка устройства и соединен с входом уменьшаемого вычитателя, входы вычитаемого и заема которого соединены с выходами первой и второй групп первого блока умножения соответственно, выходы разности и заема вычитателя соединены с вторым информационным входом коммутатора и информационным входом второго регистра остатка соответственно, выходы старших разрядов первого и второго регистров остатка соединены с первым и вторым информационными входами второго сумматора соответственно, выход младших разрядов которого соединен с первым информационным входом второго блока умножения, второй информационный вход которого соединен с выходом узла вычисления обратной величины, вход которого соединен с выходом сумматора принудительного округления делителя, информационный вход которого соединен с выходом старших разрядов регистра делителя, выход которого соединен с первым информационным входом первого блока умножения, второй информационный вход которого соединен с информационным входом младших разрядов сумматора частного и выходом селектора, информационный вход которого соединен с выходом второго блока умножения, вход переноса сумматора принудительного округления является входом логической "1" устройства, выход старшего разряда второго сумматора соединен с входом элемента НЕ, выход которого соединен с управляющим входом селектора, вход синхронизации устройства соединен с синхровходами первого и второго регистров остатка, регистра делителя, сумматора частного и блока микропрограммного управления, первый выход которого соединен с первым управляющим входом коммутатора и входами установки в ноль второго регистра остатка и сумматора частого, выход которого является выходом частного устройства, второй выход блока микропрограммного управления соединен с вторым управляющим входом коммутатора и входами разрешения записи второго регистра остатка и сумматора частного, третий и четвертый выходы блока микропрограммного управления соединены с входами разрешения записи первого регистра остатка и регистра делителя соответственно, пятый выход блока микропрограммного управления является выходом признака окончания деления устройства [3].

Недостаток известного устройства - относительно низкое быстродействие, так как при большом значении n и малом значении k время срабатывания сумматора частного становится больше времени срабатывания первого блока умножения и вычитателя вместе взятых.

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

Заявляемое устройство для
деления содержит отличительные признаки, не обнаруженные ни в одном из известных устройств - наличие второго и третьего коммутаторов с соответствующими связями. Эти признаки позволяют повысить быстродействие устройства за счет сокращения длительности такта работы при большом значении n и малом значении k.

Таким образом, так как в заявляемом техническом решении имеются отличительные признаки, обеспечивающие достижение цели и не обнаруженные ни в одном другом известном аналогичном техническом решении, то оно соответствует критерию "существенные отличия".

На фиг. 1 приведена структурная схема предлагаемого устройства для деления; на фиг. 2 показано расположение k-разрядных групп цифр Zi частного в регистре частного для случая n = 16, k = 4, M = 5 (M - число тактов собственно деления, определяемое по формуле ); на фиг. 3 - представление содержимого регистра частного в виде двух слагаемых, сумма которых равна искомому значению частного; на фиг. 4 показана функциональная схема блока микропрограммного управления; на фиг. 5 - микропрограмма работы устройства.

Устройство для деления содержит (фиг. 1) первый 1 и второй 2 регистры остатка, регистр 3 делителя, регистр 4 частного, сумматор 5 принудительного округления делителя, узел 6 вычисления обратной величины, первый 7 и второй 8 сумматоры, первый 9 и второй 10 блоки умножения, вычитатель 11, коммутаторы 12, 13 и 14, элемент НЕ 15, селектор 16, блок 17 микропрограммного управления, вход 18 данных устройства, вход 19 синхронизации устройства, вход 20 логической "1" устройства, выход 21 результата устройства, выходы 22 и 23 регистров
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 ≅ X < 1 и 1/2 ≅ Y < 1. Это справедливо только в первом такте деления. В дальнейшем, когда в роли делимого выступают промежуточные остатки, возможно нарушение нормализации делимого как влево, так и вправо. В общем случае делимое X в предлагаемом устройстве может изменяться в пределах 0 ≅ X < 2Y. Можно показать, что для получения на выходе 33 селектора 16 k двоичных цифр частного с точностью до единицы их младшего разряда достаточно обрабатывать k+4 старших разрядов делимого (один разряд - слева от запятой, а остальные - справа от запятой), k+3 старших разрядов делителя Y (все разряды расположены справа от запятой) и k+2 старших разрядов обратной величины принудительно округленного усеченного делителя (один разряд - слева от запятой, а остальные - справа от запятой).

Сумматор 5 (k+3)-разрядный комбинационного типа. В сумматоре 5 осуществляется принудительное округление делителя путем прибавления к значению k+3 старших разрядов делителя, поступающих на информационный вход сумматора 5 с выхода 27 старших разрядов регистра 3 делителя, единицы в младший разряд, поступающей на вход переноса сумматора 5 принудительного округления через вход 20 логической "1" устройства. На выходе 28 сумматора 5 принудительного округления образуется (k+4)-разрядный результат (один разряд - слева от запятой, а остальные - справа от запятой), который далее поступает на вход узла 6 вычисления обратной величины.

Узел 6 вычисления обратной величины производит вычисление значения k+2 старших разрядов обратной величины от принудительно округленного значения k+3 старших разрядов делителя, поступающего на вход узла 6 вычисления обратной величины с выхода 28 сумматора 5 принудительного округления. На выходе 29 узла 6 вычисления обратной величины формируется значение k+2 старших разрядов обратной величины принудительно округленного усеченного делителя. Узел 6 может быть выполнен в виде комбинационной схемы, реализующей метод деления Стефанелли, или же совместно с сумматором 5 на ПЗУ по соответствующей таблице истинности.

С помощью первого сумматора 7 комбинационного типа двухрядный код остатка, хранимый в первом 1 и втором 2 регистрах остатка, преобразуется в однорядный код. Второй сумматор 8 комбинационного типа. Он осуществляет преобразование k+5 старших разрядов двухрядного кода остатка, хранимого в регистрах 1 и 2 остатка, в однорядный код (два разряда - слева от запятой и k+3 разрядов - справа от запятой). На выходе 30 младших разрядов второго сумматора 8 образуется однорядный код k+4 старших разрядов остатка (один разряд - слева от запятой, k+3 разрядов - справа от запятой), а на выходе 31 старшего разряда второго сумматора 8 образуется старший дополнительный разряд остатка.

В первом блоке 9 умножения осуществляется перемножение k-разрядного частного, сформированного на выходе 33 селектора 16 и поступающего на второй информационный вход первого блока 9 умножения, и значения n-разрядного делителя, хранимого в регистре 3 делителя и поступающего на первый информационный вход блока 9 умножения с выхода 26 регистра 3 делителя. На первом 34 и втором 35 выходах первого блока 9 умножения образуется произведение в двухрядном коде (в виде двух чисел). Первый блок 9 умножения комбинационного типа и может быть разработан, например, в виде многослойной структуры без распространения переносов внутри слоев. Он также может быть реализован в виде совокупности из n/k k-разрядных двоичных умножителей.

Во втором блоке 10 умножения производится умножение значения однорядного кода k+4 старших разрядов остатка, поступающего на его первый информационный вход с выхода 30 младших разрядов второго сумматора 8, на значение k+2 старших разрядов обратной величины принудительно округленного усеченного делителя, поступающее на его второй информационный вход с выхода 29 узла 6 вычисления обратной величины. На выходе 32 блока 10 умножения формируется значение k цифр частного. Значение k-разрядного частного, полученного на выходе 33 селектора 16, может быть либо равно значению старших k разрядов частного, получаемого при делении n-разрядных чисел, либо меньше его на единицу младшего разряда с весом 2^-(k-1). Блок 10 умножения комбинационного типа может быть разработан, например, в виде многослойной структуры с распространением переноса только в последнем слое.

В вычитателе 11 осуществляется вычитание из текущего остатка, сформированного в однорядном коде на выходе 40 первого сумматора 7, произведения делителя на k цифр частного, образованного в двухрядном коде на первом 34 и втором 35 выходах первого блока 9 умножения. Результат этого вычитания является очередным остатком и получается на выходах 41 и 42 разности и заема вычитателя 11 в двухрядном коде. Как и в устройстве-прототипе, вычитатель 11 комбинационного типа без распространения заема. Вычитатель 11 может быть реализован как на одноразрядных двоичных вычитателях, так и на одноразрядных двоичных сумматорах. В предлагаемом устройстве предполагается, что вычитатель 11 реализован на одноразрядных двоичных вычитателях.

С помощью коммутатора 12 осуществляется передача на информационный вход первого регистра 1 остатка либо делимого с входа 18 данных устройства, когда на первом выходе 44 блока 17 микропрограммного управления формируется сигнал логической "1", либо результата, образованного на выходе 41 разности вычитателя 11, когда на втором выходе 45 блока 17 микропрограммного управления формируется сигнал логической "1". Коммутатор 12 может быть реализован на элементах 2И - 2ИЛИ.

С помощью второго коммутатора 13 и третьего коммутатора 14 осуществляется передача на первый и второй информационные входы первого сумматора 7 значения очередного остатка в двухрядном коде с выходов 22 и 23 первого 1 и второго 2 регистров остатка соответственно, когда на втором выходе 45 блока 17 микропрограммного управления формируется сигнал логической "1", либо содержимого регистра 4 частного, представленного в виде двух слагаемых на первом 36 и втором 37 выходах регистра 4 частного соответственно, когда на шестом выходе 49 блока 17 микропрограммного управления формируется сигнал логической "1". Второй 13 и третий 14 коммутаторы могут быть реализованы на элементах 2И - 2ИЛИ (каждый разряд коммутатора строится на одном элементе 2И - 2ИЛИ).

Так как в предлагаемом устройстве при формировании k цифр частного используются старшие разряды остатка, полученные при приведении на втором сумматоре 8 к однорядному коду старших разрядов двухрядного кода остатка, то становится возможным образование неправильного значения k цифр частного. Так, если значение старших разрядов приведенного остатка, полученного на выходе 40 первого сумматора 7, равно нулю, то при формировании однорядного кода старших разрядов остатка путем сложения на втором сумматоре 8 старших разрядов двухрядного кода остатка возможно получение значения суммы на выходе 30 младших разрядов сумматора 8 меньшего, чем ноль на единицу младшего разряда, т. е. значения . Но в этом случае на выходе 31 старшего разряда второго сумматора 8 формируется логическая "1", а в случае, если значение старших разрядов приведенного остатка, полученного на выходе 40 первого сумматора 7, не равно нулю, на выходе 31 старшего разряда второго сумматора 8 формируется логический "0". Для исключения возможности получения в первом случае неверного значения k цифр частного в устройстве предусмотрена блокировка (формирование значения k цифр частного, равного нулю) k цифр частного, полученных на выходе 32 второго блока 10 умножения, путем подачи на управляющий вход селектора 16 уровня логического "0" с выхода элемента НЕ 15. Уровень логического "0" на его выходе устанавливается в том случае, если на выходе 31 старшего разряда второго сумматора 8 устанавливается уровень логической "1". Во всех других случаях на выход 33 селектора 16 пропускается значение k цифр частного с выхода 32 второго блока 10 умножения.

Селектор 16 производит формирование на выходе 33 значения k цифр частного, равного нулю, если на его управляющем входе присутствует сигнал логического "0", или же пропускает на выход 33 значение k цифр частного с выхода 32 второго блока 10 умножения, если на его управляющем входе присутствует сигнал логической "1". Предполагается, что селектор 16 реализован так же, как и в устройстве-прототипе, т.е. содержит k двухвходовых элементов И, имеющих один общий вход, служащий в качестве управляющего входа.

Блок 17 микропрограммного управления координирует работу узлов и блоков устройства при выполнении в нем операции деления. Как и в устройстве-прототипе он может быть реализован различными методами, например на счетчике 50 и памяти 51 микрокоманд (фиг. 4). Счетчик 50 накапливающего типа и предназначен для естественной адресации микрокоманд. Вход счета счетчика 50 соединен с входом 19 синхронизации устройства. В качестве памяти 51 микрокоманд может быть применена быстродействующая постоянная память емкостью (M+5)6, где M - число тактов собственно деления, в течение которых в устройстве формируется [M ˙ (k-1)+1] цифр частного; ] X [- ближайшее целое, большее или равное X. В самом начале работы устройства счетчик 50 устанавливается в некоторое исходное состояние, например в ноль (на фиг. 4 цепь установки счетчика 50 в исходное состояние не показана). Микропрограмма работы устройства представлена на фиг. 4.

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

Пусть на входе 18 данных устройства присутствуют без знаков n-разрядные двоичные коды делителя Y и делимого X (т.е. коды дробных частей делителя и делимого), а счетчик 50 блока 17 микропрограммного управления установлен в начальное нулевое состояние. Тогда на четвертом 47 выходе блока 17 микропрограммного управления формируется единичный сигнал, под действием которого регистр 3 делителя подготовлен к приему информации. С приходом первого импульса синхронизации на вход 19 синхронизации устройства осуществляется запись двоичного кода делителя Y в регистр 3 делителя. Счетчик 50 блока 17 микропрограммного управления устанавливается в состояние "1".

Во втором такте работы устройства на первом 44 и третьем 46 выходах блока 17 микропрограммного формируются сигналы логической "1", под действием которых коммутатор 12 пропускает на информационный вход первого регистра 1 остатка делимое X с входа 18 данных устройства, на информационные входы сумматора 5 принудительного округления делителя поступает значение старших разрядов делителя с выхода 27 старших разрядов регистра 3 делителя, принудительно округленное значение усеченного делителя с выхода 28 сумматора 5 поступает на вход узла 6 вычисления обратной величины, на выходе 29 которого формируется значение k+2 старших разрядов обратной величины принудительно округленного усеченного делителя, регистр 1 подготовлен к приему информации, а второй регистр 2 остатка - к обнулению. С приходом второго синхроимпульса на вход 19 синхронизации устройства осуществляется запись двоичного кода делимого X в регистры 1, а также обнуление второго регистра 2 остатка. Счетчик 50 блока 17 микропрограммного управления устанавливается в состояние "2". После завершения действия второго импульса на входе 19 синхронизации устройства заканчивается подготовительный этап и начинается собственно деление, в процессе которого в течение M тактов формируется [M˙ (k-1)+1] двоичных цифр частного.

В третьем такте (в первом из M тактов собственно деления) работы устройства на втором 45 и третьем 46 выходах блока 17 микропрограммного управления образуются сигналы логической "1". Под действием этих управляющих сигналов в устройстве выполняются следующие действия. Второй коммутатор 13 и третий коммутатор 14 пропускают на первый и второй информационные входы первого сумматора 7 значение очередного остатка в двухрядном коде с выходов 22 и 23 первого 1 и второго 2 регистров остатка соответственно. По значению старших разрядов делимого (на следующих тактах в роли делимого выступает остаток, хранящийся в регистрах 1 и 2 остатка в двухрядном коде) и обратной величины принудительно округленного усеченного делителя на выходе 32 блока 10 умножения формируется значение k двоичных цифр частного. Параллельно с работой второго сумматора 8 и второго блока 10 умножения работает первый сумматор 7, который преобразует двухрядный код текущего остатка в однорядный. По значению старшего разряда второго сумматора 8 осуществляется окончательное формирование k цифр частного на выходе 33 селектора 16. Если сигнал на выходе 31 второго сумматора 8 соответствует уровню логической "1", то на выходе элемента НЕ 15 формируется сигнал логического "0", который устанавливает значение k цифр частного на выходе 33 селектора 16 равным нулю. В противном случае в качестве k-разрядного частного в устройстве используется значение k цифр частного, сформированное на выходе 32 второго блока 10 умножения, Сформированное на выходе 33 селектора 16 k-разрядное частное Z1 (в следующих тактах - Zi, где i - номер такта собственно деления) поступает на информационные входы младших разрядов регистра 4 частного и на второй информационный вход первого блока 9 умножения, на выходах 34, 35 которого образуется произведение Y ˙ Z1 в двухрядном коде. С помощью вычитателя 11 формируется разность X-Y ˙ Z1 в двухрядном коде, которая в дальнейшем служит очередным остатком и подается на второй информационный вход коммутатора 12 и на информационный вход второго регистра 2 остатка со сдвигом на k-1 разрядов влево (в сторону младших разрядов). Регистры 1, 2 и регистр 4 частного подготовлены к приему информации. С приходом третьего синхроимпульса на вход 19 синхронизации устройства в регистры 1 и 2 записывается сформированный на выходах 41, 42 вычитателя 11 двухрядный код остатка, в младшие разряды регистра 4 частного заносятся k старших цифр частного с выхода 33 селектора 16, а счетчик 50 блока 17 микропрограммного управления устанавливается в состояние "3". На этом третий такт работы устройства заканчивается и далее выполняется еще M-1 аналогичных тактов. В каждом из этих тактов k очередных цифр частного, образованных на выходе 33 селектора 16, поступают на информационные входы младших разрядов регистра 4 частного, содержимое которого сдвинуто на k-1 разрядов в сторону его старших разрядов.

После выполнения последнего (M-го) такта собственно деления в регистре 4 частного хранятся все M k-разрядных групп цифр Zi частного. На фиг. 2 показано расположение k-разрядных групп цифр Zi частного в регистре 4 частного для случая n = 16, k = 4, M = 5.

В (M+3)-м такте работы устройства на шестом выходе 49 блока 17 микропрограммного управления образуется сигнал логической "1", под действием которого второй коммутатор 13 и третий коммутатор 14 пропускают на первый 38 и второй 39 информационные входы первого сумматора 7 содержимое регистра 4 частного, представленное в виде двух слагаемых, с первого 36 и второго 37 выходов регистра 4 частного соответственно. На фиг. 3 показано представление содержимого сумматора 4 частного в виде двух слагаемых, сумма которых равна искомому значению частного. После выполнения (M+3)-го такта работы устройства на выходе 21 результата устройства образуется n-разрядное частное.

В (M+4)-м такте работы устройства на втором выходе 45 блока 17 микропрограммного управления образуется сигнал логической "1", под действием которого второй коммутатор 13 и третий коммутатор 14 пропускают на первый 38 и второй 39 информационные входы первого сумматора 7 значение остатка в двухрядном коде с выходов 22 и 23 первого 1 и второго 2 регистров остатка соответственно. Этот такт может не выполняться, если не требуется получения конечного остатка. После выполнения (M+4)-го такта работы устройства на выходе 21 результата устройства образуется n-разрядный остаток от деления. Одновременно с этим из памяти 51 микрокоманд блока 17 микропрограммного управления считывается микрокоманда M+5, которой соответствует управляющий сигнал Y 48, и соответственно на пятом выходе 48 блока 17 микропрограммного управления устанавливается уровень логической "1", сигнализирующий об окончании операции деления.

Сравнение предлагаемого устройства и устройства-прототипа по быстродействию. Так как в предлагаемом устройстве и устройстве-прототипе деление выполняется за разное число тактов, то для сравнения их быстродействия необходимо сравнить их по скорости деления в них двух n-разрядных чисел.

Сравнение предлагаемого устройства для деления и устройства-прототипа по скорости деления в них двух n-разрядных чисел при следующих допущениях: n = 64, k = 4, в качестве элементной базы используются двух=, трех= и четырехвходовые элементы И, ИЛИ, а также элемент НЕ, τ - задержка на одном логическом элементе.

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

Время работы устройства-прототипа при делении на нем n-разрядных чисел определяется по формуле
V1 = (M+3) ˙ T_прот, где M - число тактов собственно деления, определяемое по формуле ;
T_прот - длительность одного такта работы устройства-прототипа.

Время работы предлагаемого устройства при делении на нем n-разрядных чисел определяется по формуле
V2 = (M+4) ˙T_предл, где M - число тактов собственно деления, определяемое по формуле ;
T_предл. - длительность одного такта работы предлагаемого устройства.

При n= 64 и k=4 время работы устройства-прототипа V1=1200 τ , а время работы предлагаемого устройства V2=1125 τ .

Следовательно, быстродействие предлагаемого устройства примерно на 6% выше, чем быстродействие устройства-прототипа. Кроме того, предлагаемое устройство является более экономичным, так как два введенных коммутатора проще исключенного из устройства комбинационного сумматора частного.

Формула изобретения

УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ, содержащее два регистра остатка, регистр делителя, регистр частного, сумматор принудительного округления, узел вычисления обратной величины, два сумматора, два блока умножения, первый коммутатор, селектор, вычитатель, элемент НЕ и блок микропрограммного управления, причем вход данных устройства соединен с информационным входом регистра делителя и с первым информационным входом первого коммутатора, выход которого соединен с информационным входом первого регистра остатка, выход первого сумматора является выходом результата устройства и соединен с входом уменьшаемого вычитателя, входы вычитаемого и заема которого соединены с выходами первой и второй групп первого блока умножения соответственно, выходы разности и заема вычитателя соединены с вторым информационным входом первого коммутатора и информационным входом второго регистра остатка соответственно, выходы старших разрядов первого и второго регистров остатка соединены с первым и вторым информационными входами второго сумматора соответственно, выход младших разрядов которого соединен с первым информационным входом второго блока умножения, второй информационный вход которого соединен с выходом узла вычисления обратной величины, вход которого соединен с выходом сумматора принудительного округления, информационный вход которого соединен с выходом старших разрядов регистра делителя, выход которого соединен с первым информационным входом первого блока умножения, второй информационный вход которого соединен с информационным входом младших разрядов регистра частного и выходом селектора, информационный вход которого соединен с выходом второго блока умножения, вход переноса сумматора принудительного округления является входом логической единицы устройства, выход старшего разряда второго сумматора соединен с входом элемента НЕ, выход которого соединен с управляющим входом селектора, вход синхронизации устройства соединен с синхровходами первого и второго регистров остатка, регистра делителя, регистра частного и блока микропрограммного управления, первый выход которого соединен с первым управляющим входом первого коммутатора и входом установки в "0" второго регистра остатка, второй выход блока микропрограммного управления соединен с вторым управляющим входом первого коммутатора и входами разрешения записи второго регистра остатка и регистра частного, третий и четвертый выходы блока микропрограммного управления соединены с входами разрешения записи первого регистра остатка и регистра делителя соответственно, пятый выход блока микропрограммного управления является выходом признака окончания деления устройства, отличающееся тем, что в устройство введены второй и третий коммутаторы, причем выход первого регистра остатка соединен с первым информационным входом второго коммутатора, второй информационный вход которого соединен с первым выходом регистра частного, выход второго регистра остатка соединен с первым информационным входом третьего коммутатора, второй информационный вход которого соединен с вторым выходом регистра частного, выход второго коммутатора соединен с первым информационным входом первого сумматора, второй информационный вход которого соединен с выходом третьего коммутатора, первые управляющие входы второго и третьего коммутаторов соединены с вторым выходом блока микропрограммного управления, шестой выход которого соединен с вторыми управляющими входами второго и третьего коммутаторов.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6