Особенности арифметико-логических устройств (АЛУ) с двоично-десятичными кодами (ДДК) при вычислении операций умножения и деления и поиск путей их ускорения

Особенности АРИФМЕТИКО-ЛОГИЧЕСКИХ УСТРОЙСТВ (АЛУ) с двоично-десятичными кодами (ДДК) при вычислении операций умножения и деления и поиск путей их ускорения

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

Пример:

37=

АЛУ, построенное для обработки ДДК базируется на традиционном двоичном сумматоре с выполнением дополнительных корректирующих действий. Основная идея корректирующих механизмов заключается в том, что при обработке десятичных разрядов переносы в смежные разряды возникают при значениях, превышающих число 10, а при сложении ДДК перенос в смежный разряд возникает при превышении в разряде 16. Единицей данных при обработке ДДК является т. наз. тетрада, представляющая собой 4 последовательных бита. Для компенсации искажений, возникающих при сложении ДДК, формируют операнд, каждая цифра которого имеет избыток, равный 6. В таком случае:

z[i]=x[i]+y[i]+P[i]

Если при обработке i-того разряда десятичного кода при сложении i-того разряда первого операнда, i-того разряда второго операнда и входного переноса в i-тый разряд, значение превышает 10, то в i-том разряде остается

z[i]=x[i]+y[i]+P[i]-10

P[i+1]=1

Формируется сигнал переноса в следующий разряд. Поэтому при сложении операндов с избытком в (х6) получаем:

z=x6+Y

В таком случае в i-том разряде z будет такое значение:

тогда z16. В таком случае в i-том разряде z будет:

z[i]=6+x[i]+y[i]+P[i]-16=x[i]+y[i]+P[i]-10=z[i]

P[i+1]=1 –перенос в следующий разряд

При получении псевдосуммы z обнаруживается ситуация, когда разряды (тетрады), из которых был перенос в старший разряд, содержат правильное значение цифры этого разряда. Разряды, из которых не было переносов в старший разряд, содержат цифру с избытком, равным 6. Поэтому полученное значение требует корректировки. Она может быть проведена путем вычитания из разрядов, из которых не было переносов, значения 6. На практике, вместо вычитания к этим разрядам добавляют значение равное 10 и блокируют межтетрадные переносы:

Упрощенная схема АЛУ

Алгоритм сложения ДДК

РгВ принимает первый операнд, затем в РгА формируют числосо значением 6 в каждой тетраде.

В РгСм формируется код первого операнда с избытком 6, который принимается в РгВ.

В РгА принимается второй операнд. Сумматор формирует значение z=x6+y. При этом тетрады, из которых не возникли сигналы переноса, фиксируются.

В ргА формируется операнд, в тетрадах которого размещено число 10, если в соответствующих тетрадах z не возникал сигнал переноса. z из РгСм передается в РгВ.

Корректировка z путем добавления операнда с 10 в РгА с блокировкой межтетрадных переносов. Полученный результат передается на выходную шину данных.

Для вычитания ДДК производятся такие действия:

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

Выполняется суммирование . Если из старшей тетрады z при формировании был перенос, то получено положительное значение результата. Если переноса не было из старшей тетрады, то результат является отрицательным в дополнительном коде. При этом дополнительный код инвертируется и добавляется 1 к младшему разряду. Полученное значение требует корректировки. Если при получении z из тетрады был перенос, то в последствии к этой тетраде надо добавить 10 с блокировкой межтетрадных переносов.

Опции с ДДК со знаками сводятся к определению реальных опций, которые затем выполняются по приведенным схемам.

Умножение ДДК. Анализируется значение очередной тетрады, начиная с младшей и к сумме частичных произведений добавляется множимиое столько раз, какому значению равно число в тетраде. Значение суммы частичных произведений сдвигается вправо на тетраду, чтобы уменьшить количество сложений. Отдельно формируется 8, 4 и 2 кратное множимое (8х, 4х, 2х, 1х). Данная процедура повторяется, пока все тетрады множителя не будут проанализированы.

Деление ДДК. Производится путем многократного вычитания делителя из текущего значения частичных разностей, которые первоначально равны значению делимого, последовательным сдвигом частичных разностей влево по разрядной сетке. Многократное вычитание выполняет до получения отрицательного результата. Количество вычитаний до получения отрицательного результата соответствует очередной цифре частного. В целом, опция похожа на традиционное деление «уголком».

Методы ускорения операции умножения. Аппаратурные методы ускорения требуют дополнительных затрат , пропорциональных количеству обратных разрядов . Как пример к аппартным методам операции (*) – включение дополнительных цепей сдвига возможно за 1 такт алгоритма синхронизировать выполнение сдвига на нескольких разрядах .Другим методом является работы сумматоров , а также совмещение во времени сдвиговых операций и операций суммирования

Логические методы ускорения операции умножения требуют изменения центрального управления . Основным источником повышения эффективности является уменьшение кол-ва сложений выполняемых в процессе получения  частных произведений . К логическим так же можно отнести методы позволяющие анализировать несколько разрядов множителей одновременно и выполнить соответствующие изменения суммы частных произведений.

Пример лог. метода

0151413121100=26 –21 ;

k+1 k k-1 0

| | | |

0 1 1 1 0 1 1 1 …….

Вместо 2-Х вычитаний выполняется одно .Если … 0 1к 0 в (к) выполняется только одно сложение

Формализация этого подхода может быть сделана так :

di=(bi + bi-1)*di-1

Si = di *bi+1

bi –логическая переменная определяющая необходимость выполнения арифметической операции для i-того разряда множителя

Si –определяет знак выполнимой операции . Если Si =0 ,то выполняется сложение текущей суммы частного произведения и множимого . Если Si =1 то выполняется “-“ вычитание множимого из суммы частн. Произведений

Данное правило – правило Лемана. Оно при самых неблагоприятных комбинациях разрядов множителей вдвое сокращает кол-во операций суммирования . Среднее значение ускорения *3.

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

При анализе 2-х разрядов множителя можно предложить след последовательность действий :

Если два разряда 00 . то выполняется только сдвиг  частного произведения (далее  ч.п.)вправо на 2 разряда

Если 01 то к  ч.п. добавляется множимое , а далее выполняется сдвиг на два разряда

Если 10 то к  ч.п добовляется удвоеное множимое и  ч.п сдвигается вправо на два разряда, если 11 то вычитаем множимое и на специальном триггере запоминается ситуация о необходимости коррекции при анализ след 2-х разрядов. Далее  ч.п сдвигается вправо на два разряда , след пара разряда множителя уже рассматривается как увел на 1.

Значение разрядов	Операция при знаке предыдущего разрядов <1000	Операция при знаке предыдущего разрядов >=1000
0000	П(4)z	П(4)(z+x)
0001	П(4)(z+x)	П(4)(z+2x)
0010	П(4)(z+2x)	П(4)(z+3x)
0011	П(4)(z+3x)	П(4)(z+2x+2x)
0100	П(4)(z+2x+2x)	П(4)(z+2x+3x)
0101	П(4)(z+2x+3x)	П(4)(z+6x)
0110	П(4)(z+6x)	П(4)(z+x+6x)
0111	П(4)(z+x+6x)	П(4)(z+2x+6x)
1000	П(4)(z+2x+6x)	П(4)(z-x-6x)
1001	П(4)(z-x-6x)	П(4)(z-6x)
1010	П(4)(z-6x)	П(4)(z-2x-3x)
1011	П(4)(z-2x-3x)	П(4)(z-2x-2x)
1100	П(4)(z-2x-2x)	П(4)(z-x-2x)
1101	П(4)(z-x-2x)	П(4)(z-2x)
1110	П(4)(z-2x)	П(4)(z-x)
1111	П(4)(z-x)	П(4)z

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

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

АЛУ для реализации операции деления.Операция / является обратной по отн к операции *, поэтому общая структура операции заключается в последовательности вычитания значения делителя из делимого и сдвигах.

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

Рассм. осн. требования: Частное Z как рез-т деления делимого X на делитель Y, Z=X/Y. Х представляется в формате двойного слова, т.е. занимает (2n-1) разрядов, Z и Y представлены в формате одинарного слова, т.е. занимают (n-1)разрядов. Поэтому |Z|<2n-1. Для того, чтобы частное размещалось в формате двойного слова необходимо |X’|-|Y|<0, где |X’|=|X|-2-(n+1). В противном случае частное не может быть размещено в формате одного слова. Поэтому операция деления невыполнима. Для поверки этого условия выполним пробное вычитание. Для этого выравнивают делимое и делитель так, чтобы младший разряд делителя был под (n-1)-м разрядом делимого.если вычитание даст отрицательный результат, то операция продолжается. По сути дела мы реализовали традиционное деление «в столбик».Т.о. для выполнения операции деления необходимо либо сдвигать вправо делитель по разрядной сетке, начиная со старших разрядов в процессе получения частичных разностей. При этом делимое остается неподвижным. Либо можно сдвигать влево значение делимого при неподвижном делителе. В процессе получения частичных разностей очередная цифра частного определяется знаком текущего значения частичных разностей. Исходя из этого может быть построено 2 варианта АЛУ.(СХЕМА)

Данная схема предполагает использование двойной разрядности всех элементов. При этом делимое и послед. значение частичных разностей неподвижны, а сдвигаются вправо компоненты делителя. Начальное положение делителя старшие разряды регистра РгУ, а затем делитель  из результате каждой итерации. Частичные разности получаются с помощью сумматора, на один вход которого подается делимое, а на другой-обратный код делителя. Доп. код получается подсуммированием 1 к младшему разряду сумматора. Цифры частного формируют по знаку полученных частичных разностей, т.е. по нулевому разряду сумматора. Цифры заносятся в младший разряд регистра РгZ, которые передаются со сдвигом влево в регистр Z’, а далее прямо в регистр Z. Основным недостатком этой схемы является использование двойной разрядности всех компонентов. На практике получила распространение схема с неподвижным делителем и сдвигаемым влево значением частичных разностей.(СХЕМА).

В Рг1 размещается делитель, а в РгВ и Рг2-делимое. В триггерах знака сохраняются знаки операндов. Регистр 3 используется для размещения цифр частного. Общая схема алгоритма:

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

2.Делимое  на 1 разряд, для этого регистр А обнуляется и содержимое передается в регистр сумматора со сдвигом  на один разряд.В освободившийся младший разряд сумматора записывается младший разряд из регистра 2. После этого содержимое регистра сумматора записывается в регистр В. одновременно разряды регистра 2, кроме старшего, передаются в Рг2’ со сдвигом  на 1 разряд и затем в регистр 2.

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

4.Если 0-й разряд регистра сумматора>0, то цифра Zi, заносимая в младший разряд регистра 3’=1. Содержимое регистра 3’ передается в регистр 3. При очередном получении частичных (текущих?)разностей содержимое регистра 3 передается в 3’ со сдвигом  на 1 разряд.

Счетчик циклов содержит количество цифровых разрядов частного. После получения очередной цифры частного значение счетчика уменьшается на 1. При достижении 0 операция заканчивается. Если в процессе получения частичных разностей текущее значение в регистре сумматора <0, то в качестве цифры Zi заносится 0, а предыдущее значение частичных разностей восстанавливается(оно хранилось в регистре В) и сдвигается  на 1 разряд; с занесением из регистра 2 очередной цифры делимого в младший разряд регистра сумматора при обнулении регистра А. Затем производится передача полученного значения текущей разности в регистр В.

В регистре В производится сдвиг  оставшейся части делимого для последующих операций.

Рассмотренный алгоритм предполагает при получении значения <0 частичного остатка его восстановление до предыдущего значения. Это требует дополнительного промежутка времени. Поэтому на практике используется алгоритм деления без восстановления остатка со сдвигаемым значением частичной разности и неподвижным делителем. Алгоритм:

1.Берутся модули от делимого и делителя.

2.Значение частичного остатка полагается равным старшим разрядам делимого

3.Значение частичного остатка удваивается путем сдвига  на 1 разряд.

4.Из значения частичных остатков вычитается делитель; если частичный остаток >0 !!!! то прибавляется делитель если <0!!!!

5.Цифра частного полагается =1, если после выполнения предыдущего шага частичные остатки >=0 и 0 в противном случае.

6.Пункты 3,4,5 выполняются до получения всех цифр частного.

7.Если в конце цикла частичный остаток <0 то он восстанавливается путем добавления делителя.

Знак частного =0, если знаки делимого и делителя совпадают, и 1 если они различны.

Содержание деления без восстановления остатков заключается в том, что при сдвиге  значение частичного остатка а удваивается 2а ,поэтому вычитание делителя эквивалентно 2а-в=2(а-в)+в его добавлению на следующем шаге.

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

Частичные остатки	Делитель	Операция	Цифра частного
+	+	Вычитание Y	1
+	-	Добавление Y	0
-	+	Добавление Y	0
-	-	Вычитание Y	1

Если x>0,a y<0 то частное следует увеличить на 1

Если x<0,a y>0 то частное следует увеличить на 1 в случае если остаток =0

Если x<0,a y<0 то частное следует увеличить на 1если остаток=0.

Построение АЛУ для выполнения операции умножения чисел с плавающей точкой

Правила умножения:

X=qx*SPx

Y=qy*SPy

Z=X*Y=  qx* qy* SPx+Py =  qz *SPz

T.o. qz= qx* qy ; Pz= Px+ Py ;

В соответствии с данными выражениями мантисса произведения равна произведению мантисс сомножителей.

Результат нормализуется. Знаку результата соответствует:

+ если мантиссы сомножителей имеют одинаковые знаки;

- если мантиссы сомножителей имеют разные знаки.

Учитывая то, что порядки сомножителей имеют смещение, то при прямом копировании приведенных действий порядок результата должен быть уменьшен на 1 смещения. Поэтому, если при сложении смещённых порядков старшие разряды суммы имеют нулевые значения, то это означает, что мы не можем извлечь смещение, т.к. значение 00 меньше чем извлекаемое смещение. Поэтому в качестве результата операции принимается 0 т.к. мантисса не может быть размещена в разрядной сетке при таком значении порядка.

Р[0]=0; P[1]=0 в качестве результата операции принимается 0

Р[0]=0; P[1]=1

Тогда производится коррекция, путём инвертирования этого разряда, т.о. получаем требуемый смещённый порядок.

Р[0]=1; P[1]=0

Мы получили отрицательное значение суммы смещённых порядков и смещённый порядок суммы получается путём инвертирования.

Р[0]=1; P[1]=1

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

Общая схема АЛУ для операции умножения

В Рг1 размещается множимое, в Рг2-множитель. В начале для сложения смещённых порядков в РгА и РгВ передаются только биты смещённых порядков. Биты мантисс в РгА и РгВ обнуляются. Соответственно обнуляются и регистры знаков. Сами знаки пишутся в ТрЗн. После размещения порядков в РгА и РгВ сумматор формирует код суммы смещённых порядков. Он размещается в соответствующем поле РгСм.

Производится анализ двух старших разрядов в этом поле в соответствии с приведенными выше рассуждениями. В результате формируется смещённый порядок произведения с необходимыми корректировками кода, который помещается в Сч1.

После этого идёт произведение мантисс. Для этого:

В РгА идёт код мантиссы Х(8-31 разр.). РгВ используется для хранения текущего значения суммы частичных произведений. Идёт анализ младших разрядов мантиссы Y в Рг2 и добавление или не добавление к текущему значению суммы частичных произведений мантиссы Х.

Результат в виде суммы частичных произведений передаётся в РгСм со сдвигом вправо и последующей передачей в РгВ.

Процесс идёт до получения требуемого количества разрядов произведения мантисс.

Отличие данного умножения мантисс от умножения мантисс целых чисел в том, что мантисса произведения имеет тот же размер, что и мантиссы сомножителей. После окончания умножения мантисс результат нормализуется (возможно изменяется значение Сч1). Результат Сч1 идёт в поле для смещённого порядка.