устройство для параллельного деления чисел

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

1. УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОГО ДЕЛЕНИЯ ЧИСЕЛ , содеpжащее (L + 1) опеpационных блоков и блок упpавления, пpичем вход l-го делимого устpойства (l = 1, L) соединены с инфоpмационным входом l-го опеpационного блока, вход делителя устpойства соединен с инфоpмационным входом (L + 1)-го опеpационного блока, вход запуска устpойства соединен с входом запуска блока упpавления, пеpвый выход котоpого соединен с входом пpизнака сигнала занесения всех опеpационных блоков, входы пpизнака конца опеpации котоpых соединены с одноименным выходом устpойства и втоpым выходом блока упpавления, тpетий выход котоpого соединен с выходом пpизнака деления на нуль устpойства, четвеpтый выход блока упpавления соединен с входами унитаpного кода всех опеpационных блоков, пеpвый выход l-го опеpационного блока соединен с l выходом пpизнака сигнала пеpеполнения устpойства, выход l-го частного котоpого соединен с выходом l-го опеpационного блока, выход (L + 1)-го опеpационного блока соединен с пеpвым входом пpизнака делителя блока упpавления, тактовый вход котоpого соединен с тактовым входом устpойства, отличающееся тем, что, с целью увеличения быстpодействия, вход числовых pазpядов делителя устpойства соединен с втоpым входом пpизнака делителя устpойства, пятый выход блока упpавления соединен с входом пpизнака опеpации всех опеpационных блоков, вход знака делителя устpойства соединен с одноименным входом l-го опеpационного блока, вход запуска котоpого соединен с входом запуска устpойства, тpетий выход l-го опеpационного блока соединен с выходом знакового pазpяда l-го частного устpойства.

2. Устpойство по п. 1, отличающееся тем, что опеpационный блок содеpжит мультиплексоp, pегистp, сдвигатель, сумматоp, гpуппу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, тpиггеp знака pезультата, тpиггеp пеpеполнения, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, тpи элемента И, два элемента ИЛИ, пpичем пеpвый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с инфоpмационным входом знакового pазpяда блока, вход знака делителя котоpого соединен с втоpым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход котоpого соединен с инфоpмационным входом тpиггеpа знака pезультата, вход pазpешения записи котоpого соединен с входом запуска блока, инфоpмационный вход котоpого соединен с пеpвым инфоpмационным входом мультиплексоpа, выход котоpого соединен с инфоpмационным входом pегистpа, выход котоpого соединен с инфоpмационным входом сдвигателя и пеpвым инфоpмационным входом сумматоpа, выход котоpого соединен с втоpым инфоpмационным входом мультиплексоpа, упpавляющий вход котоpого соединен с входом пpизнака конца опеpации блока, входом установки в "0" тpиггеpа пеpеполнения, пеpвым входом пеpвого элемента И и пpямым входом пеpвого элемента ИЛИ, вход сигнала занесения блока соединен с пеpвым входом втоpого элемента И, выход котоpого соединен с входом pазpешения записи pегистpа, выход стаpшего pазpяда котоpого соединен с пpямым входом тpетьего элемента И и втоpым входом пеpвого элемента И, выход котоpого соединен с пеpвым входом втоpого элемента ИЛИ, выход котоpого является пеpвым выходом блока, вход унитаpного кода котоpого соединен с входом упpавления сдвигом сдвигателя, выходы котоpого соединены с пеpвыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ гpуппы, выходы котоpых соединены с втоpым инфоpмационным входом сумматоpа, вход пpизнака опеpации блока соединен с втоpыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ гpуппы и инвеpсным входом тpетьего элемента И, выход котоpого соединен с инфоpмационным входом тpиггеpа пеpеполнения, выход котоpого соединен с втоpым входом втоpого элемента ИЛИ и инвеpсным входом пеpвого элемента ИЛИ, выход котоpого соединен с втоpым входом втоpого элемента И, выходы pегистpа и тpиггеpа знака pезультата являются втоpым и тpетьим выходами блока соответственно.

Описание изобретения к патенту

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

Известно устройство для деления чисел, содержащее регистры делимого и делителя, два накапливающих сумматора, генератор импульсов, блок формирования сигналов управления, элементы И и ИЛИ [1] .

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

Наиболее близким к предлагаемому по технической сущности является устройство для параллельного деления чисел, содержащее L+1 операционных блоков (L - число делимых), блок управления и триггер [2] .

Недостатком данного устройства является низкое быстродействие.

Цель изобретения - увеличение быстродействия устройства.

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

Устройство осуществляет одновременное деление L n-разрядных двоичных делимых x₁ = 2^-j на отличный от нуля двоичный делитель y = 2^-j, где _1j, _j { 0,1} . Все числа х₁, у ( х , у < 1) представлены в прямом двоичном коде в форме с фиксированной точкой.

Работа устройства основана на использовании итерационного алгоритма деления, реализующего мультипликативный метод вычислений. Операция параллельного деления, реализующая вычисления по формуле z₁ = x₁/y, l = , выполняется с использованием рекуррентных соотношений

где k = - номер выполняемой итерации,

t { 1,2, . . . , n} - количество итераций, необходимое для получения результатов операции.

Начальные значения переменных определяются соотношениями

a₁₀ = x₁, l = ; b_o = y. (2)

Значение _k определяет вид выполняемой операции на k-й итерации и может быть рассчитано по формуле

_k = 1 - 2 ^. b_k-1(0), (3) где b_k-1(0) - разряд целой части кода b_k-1.

Значение j_k определяет число сдвигов операндов на k-й итерации и вычисляется по формуле

j_k = j_k* + b_k-1(j_k*) - b_k-1(j_k*+1) -1, (4) где j_k* = min{ j b_k-1(j) = b_k-1(0)} , (5)

т. е. j_k* является номером разряда, содержащего старший ноль в мантиссе кода b_k-1 при условии, что его целая часть b_k-1(0) равна нулю, или номером разряда, содержащего старшую единицу в коде b_k-1 при b_k-1(0) = 1;

b_k-1(j_k*) и b_k-1(j_k*+1) - значение двоичных разрядов мантиссы кода b_k-1, имеющих подряд идущие номера j_k* и j_k*+1 соответственно, определенные выражением (5).

Таким образом, построенный на основании выражений (1)-(5) мультипликативный алгоритм параллельного деления использует операцию сложения на k-й итерации, если целая часть b_k-1(0) кода b_k-1 равна нулю, или операцию вычитания, если b_k-1(0) = 1. Когда целая часть b_k-1(0) кода b_k-1 равна нулю, величина сдвига j_k на k-й итерации совпадает с номером разряда старшего нуля мантиссы кода b_k-1 при условии, что разряд, следующий за разрядом старшего нуля, содержит единицу, или на единицу меньше номера разряда старшего нуля, если следующий разряд также содержит ноль. Когда b_k-1(0) = 1, величина сдвига j_k равна номеру разряда старшей единицы в мантиссе кода b_k-1, если разряд, следующий за разрядом старшей единицы содержит ноль, или на единицу меньше номера разряда старшей единицы, если следующий разряд тоже содержит единицу.

Вычисления продолжаются до тех пор, пока в результате выполнения очередной t-й итерации не будет выполнено условие

l 1-b_t l 2^-m; l 1-b_t-1 l > 2^-m, где m - мультипликативная разрядность вычислений, обеспечивающая получение результата с заданной точностью (m > n).

Полученные в результате вычислений значения a_lt (l = ) используются в качестве частных z₁.

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

Устройство содержит L+1 операционных блоков 1 и блок 2 управления, имеет L+1 информационных входов 3, вход 4 запуска, тактовый вход 5, L выходов 6 признаков переполнения, L информационных выходов 7, L выходов 8 знаков результатов, выход 9 признака деления на ноль и выход 10 признака конца операции.

Операционный блок содержит регистр 11, сумматор 12, сдвигатель 13, мультиплексор 14, группу 15 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, триггер 16 знака результата, триггер 17 переполнения, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 18, первый 19, второй 20 и третий 21 элементы И, первый 22 и второй 23 элементы ИЛИ, имеет первый информационный вход 3, второй вход 24 признака конец операции, третий вход 25 сигнала занесения, четвертый управляющий вход 26, пятый вход 27 признака операции, шестой вход 28 знака делителя, седьмой вход 4 сигнала запуска, первый выход 6 сигнала переполнения, второй информационный выход 7, третий выход 8 знака результата.

Блок управления содержит пять элементов И 29, два элемента ИЛИ 30, m элементов И-ИЛИ 31, имеет первый вход 4 запуска, второй вход 5 тактовых сигналов, третий 32 и четвертый 33 информационные входы, первый выход 34 сигнала занесения, второй выход 10 признака конца операции, третий выход 9 признака деления на ноль, четвертый информационный выход 35 и пятый выход 36 признака операции.

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

В исходном состоянии на вход 3. l (l = ) устройства и далее на первый вход операционного блока 1. l поступает значение l-го делимого х₁. На вход 3. L+1 и далее на первый вход операционного блока 1. L+1, а также на четвертый вход блока 2 управления поступает значение делителя y. Знаковый разряд делителя y поступает на шестые входы операционных блоков 1. l (l = 1, L). На вход 5 устройства непрерывно поступают тактовые импульсы (ТИ). Признак КОНЕЦ ОПЕРАЦИИ, поступающий с второго выхода блока 2 управления на вторые входы операционных блоков 1 и на выход 10 устройства, имеет единичное значение.

Информационные коды, поступающие на первые входы операционных блоков 1, преобразуются из (n+1)-разрядного в (v+1)-разрядный формат (v > n) путем добавления v-n младших разрядов, которым присваивается нулевое значение. Знаковые разряды кодов также заменяются нулевыми значениями. Изменение формата операндов проводится для обеспечения допустимой погрешности вычислений, возникающей за счет усечения чисел, сдвигаемых при вычислениях за пределы разрядной сетки. Кроме того, использование дополнительных разрядов позволяет реализовать изменение знака числа путем инвертирования числа без подсуммирования единицы в младший разряд.

Для начала вычислений синхронно с одним из ТИ на вход 4 устройства подается сигнал ПУСК. По сигналу ПУСК на первом выходе блока 2 управления формируется сигнал ЗАНЕСЕНИЕ, который поступает на третьи входы операционных блоков 1, обеспечивая занесение в операционные блоки 1 операндов, поступающих на их первые входы. Одновременно сигнал ПУСК поступает на седьмые входы операционных блоков 1, обеспечивая формирование на выходах 8 устройства знаков результатов.

Если все разряды 1,2, . . . , n кода делителя у, поступившего на четвертый вход блока 2 управления с входа 3. L+1 устройства, равны нулю или единице, признак КОНЕЦ ОПЕРАЦИИ сохраняет единичное значение и вычислений не производится. На вторых выходах операционных блоков 1 формируются в качестве результатов прямые значения модулей делимых. На третьих выходах операционных блоков 1 формируются знаковые разряды результатов. При нулевых значениях всех разрядов кода, поступившего на четвертый вход блока 2 управления, на его третьем выходе формируется единичное значение признака ДЕЛЕНИЕ НА НОЛЬ.

При наличии хотя бы одной единицы и хотя бы одного нуля в коде, поступившем на четвертый вход блока 2 управления, признак КОНЕЦ ОПЕРАЦИИ, формируемый на втором выходе блока управления, принимает нулевое значение и в устройстве выполняется итерационный процесс вычислений в соответствии с выражением (1).

Очередная k-я итерация (k = 1, t) реализуется в устройстве следующим образом. На четвертом выходе блока 2 управления формируется m-разрядный унитарный код j_k, содержащий единичное значение в j_k-м разряде и нулевые значения в остальных разрядах, который поступает на четвертые входы операционных блоков 1. На пятом выходе блока 2 управления формируется сигнал _k, который поступает на пятые входы операционных блоков 1. Операционные блоки формируют в соответствии с выражениями (1) значения a_lk (l = ), а также значение b_k. С приходом очередного ТИ на первом выходе блока 2 управления формируется сигнал ЗАНЕСЕНИЕ, по которому сформированные значения a_lk и b_k заносятся на регистры операционных блоков, после чего они появляются на вторых выходах операционных блоков 1. На этом выполнение очередной итерации заканчивается.

Если в процессе вычислений в некотором l-м операционном блоке 1 (l { 1,2, . . . , L} в результате выполнения очередной итерации происходит переполнение разрядной сетки, на первом выходе указанного операционного блока 1 по окончании итерации сформировано единичное значение признака ПЕРЕПОЛНЕНИЕ, которое сохраняется до начала выполнения следующей операции параллельного деления. На втором и третьем выходах указанного операционного блока 1 формируется и сохраняется до начала выполнения следующей операции параллельного деления результат выполнения итерации, в результате выполнения которой произошло переполнение.

Итерационный процесс продолжается до тех пор, пока в результате реализации очередной t-й итерации разряды 1,2, . . . , m кода b_t, поступающего на третий вход блока 2 управления, не станут одновременно равными единице при нулевом значении разряда целой части bt(0) кода bt, или пока они не станут одновременно равными нулю при b_t(0) = 1. При этом блок 2 управления прекращает формирование сигналов ЗАНЕСЕНИЕ на своем первом выходе и формирует единичное значение признака КОНЕЦ ОПЕРАЦИИ на своем втором выходе.

Операционный блок работает следующим образом. В исходном состоянии на первый 3, второй 24, третий 25, четвертый 26, пятый 27, шестой 28 и седьмой 4 входы блока поступают значения _o { x₁, l = ; y} , признак КОНЕЦ ОПЕРАЦИИ, сигнал ЗАНЕСЕНИЕ, унитарный код j_k, признак операции, знак делителя и сигнал ПУСК соответственно.

Единичное значение признака КОНЕЦ ОПЕРАЦИИ, поступающее с входа 24 на управляющий вход мультиплексора 14, обеспечивает прохождение кода _o с информационного входа мультиплексора на его выход и далее на информационный вход регистра 11. Сигнал ЗАНЕСЕНИЕ, поступающий с входа 25 блока через элемент И 21, обеспечивает занесение значения _o в регистр 11.

Знаковый разряд кода _o поступает на элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 18. На информационный вход мультиплексора 14 вместо знакового разряда кода _o поступает нулевое значение, поскольку числа представлены в прямом коде. На второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 18 с шестого входа 28 блока поступает знак делителя y. На выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 18 образуется знак результата, который поступает на информационный вход D-триггера 16 и при появлении на седьмом входе 4 блока и далее на управляющем входе триггера 16 сигнала ПУСК, знак результата формируется на выходе триггера 16 и далее на третьем выходе 8 блока.

При выполнении k-й итерации (k = 1, t) значение _k-1 { a_l(k-1), l = ; b_k-1} с выхода регистра 11 поступает на первый вход сумматора 12, а также на первый вход двигателя 13. На второй вход сдвигателя с четвертого входа 26 блока поступает унитарный код J_k. Сдвигатель 13 обеспечивает сдвиг информации, поступившей на первый вход, вправо (в сторону младших разрядов) на число разрядов, равное номеру единичного разряда в унитарном коде, поступившем на четвертый вход блока. При сдвиге освобождающиеся разряды обнуляются. В результате на выходе сдвигателя 13 формируется код _k-1 ^. 2^-jk, поступающий на первые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15. На вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 с пятого входа 27 блока подается признак операции, которая должна быть выполнена на данной итерации - сложение или вычитание. В зависимости от значения признака операции элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 15 поразрядно инвертируют либо повторяют код, поступающий на первые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15. Таким образом, на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 формируется код _k-1^. 2^-jk _k , поступающий на второй вход сумматора 12. На выходе сумматора формируется значение _k { a_lk, l = ; b_k} и этот код поступает на первый вход мультиплексора 14. Нулевое значение признака КОНЕЦ ОПЕРАЦИИ обеспечивает прохождение кода _k на выход мультиплексора 14 и далее на информационный вход регистра 11.

Разряд целой части кода _k-1 с выхода регистра 11 поступает на первый вход элемента И 19, на второй вход которого поступает инвертированное значение признака операции. Если значение признака операции равно нулю (операция сложения), а значение разряда целой части кода _k-1 равно единице, то на выходе элемента И 19 формируется единичное значение, которое будучи поданным на первый вход триггера 17 переполнения, вызывает его установку в единичное состояние. С выхода триггера 17 сигнал поступает на вход элемента ИЛИ 22, формируя на его выходе и далее на выходе 6 блока единичное значение признака ПЕРЕПОЛНЕНИЕ. С инверсного выхода триггера 17 сигнал поступает на первый вход элемента ИЛИ 23. На второй вход элемента ИЛИ 23 поступает признак КОНЕЦ ОПЕРАЦИИ. При единичном значении сигнала на прямом выходе триггера 17 переполнения (а значит, нулевом значении сигнала на его инверсном выходе) и нулевом значении признака КОНЕЦ ОПЕРАЦИИ на выходе элемента ИЛИ 23 формируется нулевое значение сигнала, которое будучи поданным на второй вход элемента И 21, на первый вход которого с третьего входа 25 блока поступают сигналы ЗАНЕСЕНИЕ, прекращает прохождение сигналов ЗАНЕСЕНИЕ через элемент И 21 на управляющий вход регистра 11. Таким образом, до окончания операции параллельного деления операционный блок, в котором произошло переполнение, оказывается неработающим. На второй вход триггера 17 подается признак КОНЕЦ ОПЕРАЦИИ, по положительному перепаду которого триггер 17 сбрасывается в нулевое состояние.

Разряд целой части кода _k-1 с выхода регистра 11 также подается на первый вход элемента И 20, на второй вход которого поступает признак КОНЕЦ ОПЕРАЦИИ с второго входа 24 блока. При единичном значении разряда целой части кода _k-1 и при единичном значении признака КОНЕЦ ОПЕРАЦИИ на выходе элемента И 20 формируется единичное значение, которое, будучи поданным на вход элемента ИЛИ 22, формируется на его выходе и далее на первом выходе 6 блока (сигнал ПЕРЕПОЛНЕНИЕ).

При отсутствии переполнения в результате выполнения итерации очередной сигнал ЗАНЕСЕНИЕ, поступающий на третий вход 25 блока проходит через элемент И 21 (так как на втором входе элемента И 21 также единичное значение) на управляющий вход регистра 11, осуществляя занесение в регистр 11 значение _k. При наличии переполнения и нулевом значении признака КОНЕЦ ОПЕРАЦИИ сигнал ЗАНЕСЕНИЕ не поступает на управляющий вход регистра 11 и в регистре 11 хранится зафиксированный результат реализации итерации, при выполнении которой произошло переполнение разрядной сетки.

Блок 2 управления работает следующим образом. На первый 4, второй 5, третий 23 и четвертый 33 входы блока поступают сигнал ПУСК, ТИ, (m+2) разрядов кода b_k-1 и n числовых разрядов кода делителя у. С первого по m-й элементы И-ИЛИ 31 формируют унитарный код J_k, поступающий на четвертый выход 35 блока. На пятый выход 36 блока в качестве признака операции поступает разряд целой части кода b_k-1 с входа 32 блока.

При равенстве нулю (единице) всех n разрядов кода на четвертом входе 33 блока или при равенстве нулю (единице) всех разрядов 1,2, . . . , m кода на третьем входе 32 блока и равенстве единице (нулю) разряда целой части этого кода, на выходе второго (третьего) или на выходе четвертого (пятого) элемента И 9 соответственно формируется единичный уровень сигнала, который поступает через второй элемент ИЛИ 30 на второй выход 10 блока в качестве признака КОНЕЦ ОПЕРАЦИИ, а также на инверсный вход первого элемента И 29, запрещая прохождение ТИ с второго входа 5 блока на выход первого элемента И 29. На выходе первого элемента ИЛИ 30, являющегося одновременно первым выходом 34 блока, при поступлении сигнала ПУСК на первый вход 4 блока или при поступлении ТИ на второй вход 5 блока и нулевом значении признака КОНЕЦ ОПЕРАЦИИ на выходе второго элемента ИЛИ 30 формируется сигнал ЗАНЕСЕНИЕ. Сформированное на выходе второго элемента И 29 значение сигнала поступает на третий выход 9 блока в качестве признака ДЕЛЕНИЕ НА НОЛЬ. (56) 1. Авторское свидетельство СССР N 1013948, кл. G 06 F 7/52, 1983.

2. Авторское свидетельство СССР N 1618165, кл. G 06 F 7/52, 1989.