Особенности сложения чисел, представленных в форме с плавающей запятой

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

 

1. Берутся модули от сомножителей.

2. Исходное значение суммы частичных произведений принимается равным нулю.

3. Если анализируемая цифра множителя равна 1, то к сумме частичных произведений прибавляется множимое; если эта цифра равна 0, прибавление не производится.

4. Производится сдвиг суммы частичных произведений вправо на 1 разряд.

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

6. Произведению присваивается знак плюс, если знаки сомножителей одинаковы; в противном случае – знак минус.

 

Ускорение операции умножения

 

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

При использовании аппаратурных методов дополнительные затраты оборудования прямо пропорциональны числу разрядов операндов. Эти методы вызывают усложнение схемы АЛУ (ОА).

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

В ЭВМ для ускорения умножения используется комбинация этих методов.

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

 

Логические методы ускорения операции умножения

 

Наиболее простой способ ускорения – пропуск тактов суммирования в случаях, когда очередная цифра множителя равна 0.

Другим способом является способ, позволяющий за один шаг умножения обработать несколько разрядов множителя.

Например, при умножении на два разряда множителя, в каждом цикле анализируются два разряда множителя, начиная с младших разрядов. Множитель разбивается на группы по два разряда. В зависимости от их значения возможны 4 комбинации: 00, 01, 10, 11.

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

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

При комбинации 10 производится добавление к сумме частичных произведений удвоенного множимого (сдвинутого на один разряд влево) и сумма частичных произведений и множитель сдвигаются на два разряда вправо.

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

В первых трех случаях результат получается верным, а в последнем – неправильный и требует корректировки на следующем шаге. Если следующая пара 00, то она обрабатывается как пара 01; если 01, то она обрабатывается как пара 10; если - 10, то как 11; если 11, то как 00 и фиксируется необходимость коррекции при обработке следующей пары. Признак необходимости коррекции может запоминаться в специальном триггере. Если старшая пара разрядов множителя 11 или 10 и состояние триггера коррекции 1, то к полученному произведению должно быть добавлено множимое.

 

Матричные методы умножения

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

Вариант устройств деления

В настоящее время практически применяется деление по способу без восстановления остатков. В этом способе есть два варианта. При выполнении деления можно:

1)  сдвигать остаток влево, делитель неподвижен

2)  сдвигать делитель вправо, остаток неподвижен

 

Способ со сдвигом остатка влево

 

УОЦ - устр-во обращения цифр

УСЗ - устр-во схемо знака

УУД - устр-во управления делением

 

Способ со сдвигом остатка вправо

 

Основа устройств деления - сумматор и два регистра. Делимое в нулевом такте заносится в сумматор. В первом способе сумматор производит сдвиг текущего остатка влево и алгебраическое сложение его с делителем. Передача в сумматор модуля делителя (сложение) или дополнение модуля до единицы (вычитание) обеспечивается устройством управления делением, которое анализирует выталкиваемые при сдвиге из сумматора знаковые цифры остатков. Эти цифры, проходя через устройство обращения цифр (УОЦ), инвертируются (заменяются на взаимообратные) и подаются на младший разряд сдвигающего регистра частного уже как цифра частного.

 

Во втором способе одновременно с передачей цифры делителя в сумматор, осуществляется и сдвиг ее вправо. Здесь введено устройство съема знаков (УСЗ) остатков, т.к. нет выталкивания знаковых разрядов из сумматора.

 

Во втором случае сумматор и регистр делителя имеют удвоенную длину, но 2-й способ более быстродействующий.

 

Контроль по модулю.

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

 

1. A₁=B₁(mod p) A₂=B₂(mod p)

(A₁+A₂)mod p=B₁(mod p)+B₁(mod p)

2. A=B(mod p) C=B(mod p) A=C(mod p)

3. A₁=B₁(mod p) C=B₂(mod p) (AC)mod p=B₁B₂(mod p)

4. A=B(mod p) Am=Bm(mod mp)

5. A=B(mod p) Aⁿ=Bⁿ(mod p)

6. (mod p)

 

Существуют два метода получения контрольного кода: числовой и цифровой

 

Числовой метод контроля

 

Код числа определяется в ССОК с mod P              

 r_A=A-[ ]

Если p=q (основанию СС), то контролируется только младший разряд (плохо).

Аналогично для m<n p=q^m контролируется m младших разрядов

Контроль на основании выполнения операций в ССОК

Неудобство: получение r_A

 

Цифровой метод контроля

При цифровом методе:

 

или  , где a_i-цифра числа

 

Контрольный код получают:

1)  непосредственным делением  на mod p

2)  суммированием цифр по mod p

(Второй способ легче)

 

Однако при цифровом методе свойства сравнений не всегда справедливы из-за наличия переносов (заемов) при арифметических действиях. Поэтому контрольный код результата операции находят с коррекцией.

Но можно выбрать такой модуль, что коррекция не нужна. Очевидно, это будет если:

 

r_A=A mod p

 

т.е. , но A=

т.е

Это возможно, если a_iqⁱ=a_i(mod p)

т.е. qⁱ=1(mod p) q=1(mod p)

т.е. q=mp+1, где m-целое число

 

Но тогда

 

Анализ показывает, что для двоичной СС (q=2) целого p нет. Это значит, что контролируемую информацию надо представлять в некоторой промежуточной СС.

 

К модулю p представляют требования:

1)  величина mod p должна быть такой, чтобы возникновение ошибки нарушало сравнимость кодов.

2)  образование контрольного кода должно осуществляться простыми средствами

3)  величена mod p должна быть по возможности небольшой, чтобы не возрастал объем вспомогательного оборудования.

 

Т.к. в ЭВМ информация представляется символами двоичного алфавита, то для контроля целесообразно перейти к системам с основанием q=2^S (S 2): 4,8,16

Переход от двоичного представления исходной информации к новому представлению с основанием q=2^S осуществляется разбиением информации на группы по S разрезов с последующим суммированием этих групп по модулю p=(2^S-1)/m или при m=1 p=2^S-1

Модули для контроля p=3 (m=2, s=2, p=3)

                        p=7 (m=1, s=3, p=7)

 

Пример: контроль по mod 3

Контролируемая информация представляется символами 4-й системы с последующим суммированием по mod 3 диад (свертывание). Требуется двухразрядный двоичный сумматор с цепью циклического переноса из старшего разряда в младший.

A=46=101110₂ B=29=011101₂

 

 

Особенности сложения чисел, представленных в форме с плавающей запятой

 

Операция сложения чисел, представленных в форме с плавающей запятой распадается на 4 этапа:

 

1. Выравниваются порядки слагаемых (меньший порядок увеличивается до большего, а мантисса преобразуемого числа сдвигается вправо (число денормализуется)). В машине определяется Р₁-Р₂, а потом ясно, что и куда сдвигать.

2. Производится преобразование мантисс слагаемых в один из модифицированных кодов.

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

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

Преобразовывать всегда нужно меньшее слагаемое, т.е. то у которого порядок меньше, чтобы не произошло переполнения разрядной сетки мантиссы преобразуемого числа. При сложении мантисс может произойти «временное, кажущееся» переполнение разрядной сетки, которое можно устранить путем сдвига мантиссы результата вправо и увеличением порядка результата.

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

– переполнение порядка (выход величины порядка за пределы разрядной сетки в положительную сторону);

– исчезновение порядка (выход величины порядка за пределы разрядной сетки в отрицательную сторону);

– потеря значимости (получение нулевой мантиссы при ненулевом порядке).

 

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

Пусть необходимо построить операционное устройство для выполнения сложения чисел, представленных в форме с фиксированной запятой. Исходные операнды поступают на вход устройства последовательно за два такта по шине DI(0:7) в следующем формате:

 

Результат должен быть выдан на шину DO(0:7) в таком же формате. В случае переполнения необходимо сформировать сигнал признака переполнения OV.

Тогда структурная схема ОУ будет иметь вид.

 

Напишем микропрограмму и построим операционный автомат сложения чисел с фиксированной запятой.

Операционное устройство (ОУ) может быть представлено в виде композиции двух автоматов: операционного (ОА) и управляющего (УА) (рис.1).

Для построения ОУ, выполняющего операцию сложения чисел, представленных в форме с фиксированной запятой, необходимо выбрать алгоритм выполнения заданной операции. Как известно, для выполнения арифметических операций над числами в ЭВМ используются прямой, обратный и дополнительные коды чисел. При этом основную операцию сложения в ОА выполняет сумматор. Наибольшее распространение получили сумматоры обратного и дополнительного кодов. Будем считать, что для выполнения операции сложения будет использоваться комбинационный сумматор чисел, представленных в дополнительном коде. Суммирование будем выполнять в модифицированном дополнительном коде (два разряда для представления знака числа). Для этого в сумматор вводится дополнительный разряд.

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

0. Принять операнды по входной шине на регистры А и В.

1. Перевести операнды в дополнительный модифицированный код.

2. Выполнить сложение полученных кодов операндов на сумматоре дополнительного кода.

3. Проверить на отсутствие переполнения разрядной сетки. Если есть переполнение – установить признак переполнения в 1. Переход на п.6.

4. Перевести результат в прямой код.

5. Выдать результат на выходную шину.

6. Конец.

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

Для построения управляющего автомата строится кодированная ГСА и синтез УА проводится одним из ранее рассмотренных методов.

Для построения ОА используются следующие списки:

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

– РгА(0:7) – внутреннее слово с памятью;

– РгВ(0:7) – внутреннее слово с памятью;

– РгС(0:8) – внутреннее слово с памятью;

– OV – внутреннее и выходное слово с памятью;

– DI(0:7) – входное слово без памяти;

– DO(0:7) – выходное слово без памяти.

2. Список микроопераций.

– y₁: РгА:= DI;

– y₂: РгB:= DI;

– y₃: РгА:= РгА(1:7)+1;

– y₄: РгB:= РгB(1:7)+1;

– y₅: РгС:= РгА(0).РгА + РгВ(0).РгВ;

– y₆: OV:= 1;

– y₇: РгC:= РгC(2:8)+1;

– y₈: DO:= РгC(1:8).

3. Список логических условий.

– x₁ = РгА(0);

– x₂ = РгB(0);

– x₃ = С(0) Å С(1);

– x₄ = РгС(0).

 

Структурная схема ОА будет иметь следующий вид.

 

 

Если разметить ГСА как автомат Мили, то можно сделать вывод, что в зависимости от знаков операндов микропрограмма выполняется от 4 – 7 тактов. Написав другую микропрограмму, можно получить ОУ, выполняющую операцию, сложения за 2 такта (один из которых занимает прием первого слагаемого в ОА).

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

 

Умножение чисел с фиксированной точкой.

 

Существуют 2 основных способа умножения:

1. Умножение, начиная с младших разрядов множителя

2. Умножение, начиная со старших разрядов множителя

 

Рассмотрим умножение на примере двоичных чисел.

Особенности умножения двоичных чисел в 2-й системе счисления:

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

2. Т.о. умножение в 2-й системе счисления естественным образом сводится к двум операциям: сложению и сдвигу, т.е. для выполнения операции умножения нужен сумматор и сдвигатель (сдвиговый регистр).

3. Количество значащих цифр в произведении равно сумме значащих цифр в обоих сомножителях.

4. Знак произведения определяется как сумма по mod 2 знаковых размеров сомножителей.

Операция умножения состоит из ряда последовательных операций сложения частичных произведений. Операциями сложения управляют разряды множителя: если в очередном разряде множителя есть «1», то к сумме частных произведений добавляется множимое с соответствующим сдвигом; если в разряде множителя «0», то множимое не прибавляется.

В зависимости от того, что сдвигается (множимое или сумма частичных произведений) различают 4 метода реализации умножения.

1. Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведений вправо и при неподвижном множимом.

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

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

При данном методе все три регистра имеют одинаковую длину, равную разрядности сомножителей. Этот метод нашел наибольшее применение в ЭВМ.

2. Умножение, начиная с младших разрядов множителя, при сдвиге множимого влево и неподвижной сумме частичных произведений.

Регистр множителя должен иметь цепи сдвига вправо, регистр множимого – цепи сдвига влево.

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

3. Умножение, начиная со старших разрядов множителя, при сдвиге суммы частичных произведений влево и неподвижном множимом.

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

При этом методе сумматор частичных произведений должен иметь двойную длину. Метод требует дополнительного по сравнению с первым методом оборудования. Несмотря на это он применяется в некоторых АЛУ, так как позволяет без дополнительных цепей сдвига выполнять и деление. Для выполнения операции деления на оборудовании метода 1 необходимы дополнительные цепи сдвига влево в регистре множимого (частного) и в сумматоре частичных произведений (разностей).

4. Умножение, начиная со старших разрядов множителя, при сдвиге множимого вправо и неподвижной сумме частичных произведений.

 

Регистр множителя должен иметь цепи сдвига влево, регистр множимого – цепи сдвига вправо.

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

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

 

При любом методе умножения операция обычно начинается с анализа на «0» сомножителей. При равенстве нулю хотя бы одного сомножителя умножение не производится, а произведению присваивается нулевое значение.

 

Рассмотрим более подробно наиболее распространенный метод умножения чисел, начиная, с младших разрядов со сдвигом суммы частичных произведений вправо.