WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 13 |

Z= 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 байт байт байт байт Если перевести операнд из формата КВ в двоичную систему счисления, а затем – в восьмеричную, то получим:

Z= – 1,00001010*21001= – 10000100100(2)=2044(8).

Результат верен.

4.6. Алгоритмы деления в цифровых процессорах В цифровом процессоре операция деления сводится к последовательности выполнения операций вычитания и сдвига. Количество получаемых битов частного определяется разрядностью процессора.

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

1) с восстановлением остатка;

2) без восстановления остатка.

Алгоритм деления с восстановлением остатка. Цикл алгоритма деления с восстановлением остатка состоит в следующем. Из старших разрядов делимого (а затем из остатка) вычитается делитель.

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

Рассмотрим алгоритм деления с восстановлением остатка «столбиком» в двоичной системе счисления на примере деления целых чисел.

Пример. X/Y=Z(R), где Z – частное, а R – остаток.

X=251(8)=10101001(2);

Y=5(8)=101(2).

ОпераДелимое/Остаток Частное Комментарий ция 1 0 1 0 1 0 0 – 1 0 1 вычитание 0 0 0 0 1 0 0 1 1 остаток положительный – 1 0 1 вычитание – 1 0 1 1 0 остаток отрицательный + 1 0 1 восстановление остатка 0 0 0 0 1 0 0 1 остаток восстановлен – 1 0 1 вычитание – 1 0 0 1 0 0 остаток отрицательный + 1 0 1 восстановление остатка 1 0 0 1 остаток восстановлен – 1 0 1 вычитание – 1 1 1 0 0 0 остаток отрицательный + 1 0 1 восстановление остатка 1 0 0 1 остаток восстановлен – 1 0 1 вычитание – 1 1 0 0 0 0 остаток отрицательный + 1 0 1 восстановление остатка ОпераДелимое/Остаток Частное Комментарий ция 1 0 0 1 остаток восстановлен – 1 0 1 вычитание 1 0 0 1 0 0 0 0 1 остаток положительный Так как последнее вычитание делителя было с учетом младшего разряда делимого, то деление завершено Результатом деления будут частное, равное 41(8), остаток, равный 4(8). Таким образом, алгоритм деления с восстановлением остатка включает следующие основные действия:

1. Биты частного получаются в цикле деления, начиная со старшего разряда.

2. Каждый цикл деления включает операцию вычитания делителя из остатка делимого (на первом шаге из старших разрядов делимого).

3. Если при вычитании получен отрицательный остаток, то очередная цифра частного равна 0, а если положительный или равный 0, то очередная цифра частного равна 1.

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

5. Остаток увеличивается присоединением очередной цифры делимого.

6. Число тактов деления определяется разрядностью процессора.

Алгоритм деления без восстановления остатка. Цикл алгоритма деления без восстановления остатка состоит в следующем. Из старших разрядов делимого (а затем из остатка) вычитается делитель. Если разность положительная или равна 0, то очередная цифра частного равна 1. Если же отрицательная, то цифра частного равна и предыдущий остаток не восстанавливается. Затем остаток увеличивается присоединением очередной цифры делимого. В следующем цикле к увеличенному остатку прибавляется делитель (на самом деле, поскольку знаки слагаемых разные, происходит вычитание).

Рассмотрим алгоритм деления без восстановления остатка «столбиком» в двоичной системе счисления на примере деления целых чисел.

Пример. X/Y=Z(R), где Z – частное, а R – остаток.

X=251(8)=10101001(2);

Y=5(8)=101(2).

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

Операция Делимое/Остаток Частное Комментарий 1 0 1 0 1 0 0 – 1 0 0 вычитание 0 0 0 0 1 0 0 1 1 остаток положительный – 1 0 1 вычитание – 1 0 1 1 0 остаток отрицательный 1 0 0 1 добавляется – следующий разряд делимого (– 1010+ +1=1001) + 1 0 1 прибавление делителя – 1 0 0 1 0 0 остаток отрицательный – 1 0 0 0 добавляется следующий разряд делимого (– 1000+ +0=1000) + 1 0 1 прибавление делителя – 1 1 1 0 0 0 остаток отрицательный – 1 1 0 добавляется следующий разряд делимого (–110+ +0=110) Операция Делимое/Остаток Частное Комментарий + 1 0 1 прибавление делителя – 1 1 0 0 0 0 остаток отрицательный – 1 добавляется следующий разряд делимого (–10+ +1= – 1) + 1 0 1 прибавление делителя 1 0 0 1 0 0 0 0 1 остаток положительный Так как при делении использованы все разряды делимого, то деление завершено.

Результатом деления будут частное, равное 41(8), остаток, равный 4(8). Алгоритм деления без восстановления остатка включает следующие основные действия:

1. Биты частного получаются в цикле деления, начиная со старшего разряда.

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

3. Если на предыдущем шаге получен отрицательный остаток, то очередная цифра частного равна 0, а если положительный или равный 0, то очередная цифра частного равна 1.

4. Остаток увеличивается присоединением очередной цифры делимого.

5. Число тактов деления определяется разрядностью процессора.

6. Если знак последнего остатка не совпадает со знаком делимого, то остаток не истин и производится его восстановление добавлением к нему делителя.

Алгоритм деления без восстановления остатка при получении n цифр частного содержит только n операций сложения/вычитания, а в алгоритме с восстановлением остатка (в наихудшем случае) таких операций может быть 2*n. Поэтому, несмотря на то что алгоритм деления с восстановлением остатка более простой, в большинстве современных цифровых процессоров используется алгоритм деления без восстановления остатка. Поэтому в дальнейшем, если не оговорено специально, рассматриваем алгоритмы деления без восстановления остатка.

4.6.1. Алгоритмы деления целых чисел в формате с ФТ При делении операндов в формате целых чисел с ФТ делимое имеет удвоенную длину по отношению к делителю, так в n-разрядном процессоре делимое содержит 2*n битов, а делитель – n битов.

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

Р1 – регистр, в который записывается делитель;

РСМ – регистр сумматора, в который перед началом деления записываются старшие n разрядов делимого, а затем (в цикле деления) в нем находится остаток от делимого;

Р2 – регистр, в который перед началом деления записываются младшие разряды делимого, а затем (в цикле деления) при сдвигах влево в него последовательно заносятся цифры частного;

СМ – n-разрядный сумматор;

МS – n-разрядный мультиплексор, который используется или для прибавления делителя (МS:=Р1), или для вычитания делителя (МS:=¬Р1 и СМ:=СМ +1);

СЧТ используется для подсчета количества циклов деления (работает на вычитание);

ШФ – шинный формирователь, который подключает ШД на передачу или прием к ОП;

дизъюнктор 1 определяет равенство 0 делителя;

дизъюнктор 2 определяет равенство 0 СЧТ;

СФФ – схема формирования флагов;

РФ – регистр флагов.

Рис. 4.9. Функциональная схема операционного автомата для операции деления Рассмотрим общие положения по делению беззнаковых чисел в формате с ФТ. Перед началом операции деления делимое записывается в регистры РСМ и Р2 так, чтобы младший бит делимого был записан в младший разряд Р2. Делитель записывается в Р1. В счетчик тактов заносится значение n. По окончании операции деления в Рбудет частное, а в РСМ – остаток от деления.

Сумматор работает в дополнительном коде. При выполнении сдвига влево выдвигаемый из Р2 бит делимого передается в младший разряд регистра РСМ, а на место освободившегося младшего бита Рзаносится очередная цифра частного. Значение цифры частного зависит от знака остатка. Для определения знака остатка при делении беззнаковых чисел используется флаг СF. Если после сложения СF=0, то остаток отрицательный, а если СF=1 – остаток положительный.

При делении чисел возможно переполнение разрядной сетки процессора. Это происходит в том случае, если частное не помещается в регистр частного. Определение возможности переполнения при делении производится при первом вычитании. Если при первом («пробном») вычитании знак остатка положительный, то частное не поместится в регистр частного и фиксируется переполнение, в противном случае переполнения не будет и деление состоится. Это вытекает из следующего. Для того чтобы частное поместилось в регистр частного, должно выполниться условие:

X/Y<2n, где n – разрядность процессора.

Откуда получаем:

X

X – Y*2n<0.

Y*2n – это и есть то, что вычитается на первом шаге деления из старших разрядов делимого.

Деление X/Y на данном ОА, из-за того что шина обмена с ОП имеет n разрядов, распадается на три операции: «посылка старших разрядов Х», «посылка младших разрядов Х», «деление на Y».

На рис. 4.10, 4.11, 4.12 приведены граф-схемы этих алгоритмов.

Рис. 4.10. Алгоритм операции Рис. 4.11. Алгоритм операции «посылка старших разрядов Х» «посылка младших разрядов Х» Восстановление остатка, если он отрицательный Рис. 4.12. Алгоритм операции «деление на Y» Алгоритм деления целых беззнаковых чисел в формате с ФТ (без восстановления остатка) состоит из следующих шагов.

Ша г 1. Запись делимого в регистры РСМ и Р2. Младшая половина битов делителя записывается в регистр Р2, а старшая – в регистр РСМ. Запись делителя в регистр Р1. Сброс флагов CF и OF.

Ш а г 2. Проверка Р1 на равенство нулю. Если Р1 равен 0, установка OF в 1 и завершение деления (так как деление на 0 не определено).

Ш а г 3. Пробное вычитание – из старших разрядов делимого (т.е. регистра РСМ) вычитается делитель (Р1), при этом:

а) если остаток 0 (CF=1), то будет переполнение при делении, флаг OF устанавливается в единицу, деление завершается.

б) если остаток < 0 (СF=0), то деление состоится, переход к шагу 4.

Ш а г 4. Циклический сдвиг влево Р2 и флага СF на 1 бит.

Ша г 5. Циклический сдвиг влево РСМ и флага СF на 1 бит.

Ша г 6. Если CF=1 (полученный остаток отрицательный), то к содержимому РСМ прибавляется содержимое Р1, иначе из РСМ вычитается Р1 (прибавляется –Р1+1).

Ша г 7. Содержимое СЧТ уменьшается на 1. Если СЧТ 0, переход к шагу 4, иначе к шагу 8.

Ша г 8. Выполняется циклический сдвиг влево регистра Р2 и флага CF на 1 бит.

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

Если CF=0, то производится восстановление остатка путем добавления Р1 к РСМ.

Рассмотрим пример деления X/Y по этому алгоритму в восьмиразрядном процессоре (табл. 4.7).

X=251(8); Y=5(8).

X=10101001(2); Y=101(2).

Для восьмиразрядного процессора получаем:

X=10101001(2); Y=00000101(2); [–Y]2=11111011.

Проверим результат. Частное находится в регистре Р2=00100001(2)= =41(8), а остаток в РСМ=00000100(2)=4(8). Результат верен.

Таблица 4.Деление беззнаковых операндов в прямом коде X/Y, где X = 251(8), Y= 5(8) CF PCM P2 CЧТ Комментарий * * * * * * * * * * * * * * * * * * * * * Исходное состояние 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 (РСМ,Р2):=Х; СЧТ:=8, CF:=0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 +(–Р1+1) Результат пробного вычита0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 ния 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 +Р0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 Результат сложения 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 СЧТ:=СЧТ – 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 1 +Р0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 1 Результат сложения 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 СЧТ:=СЧТ – 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 +Р1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 Результат сложения 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 СЧТ:=СЧТ - 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 (CF,P2):=LC((CF,P2),1) 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 (CF,PСМ):=LC((CF,PСМ),1) 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 +(–Р1+1) 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 Результат сложения Окончание табл. 4.0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 СЧТ:=СЧТ – 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 +Р0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 Результат сложения 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 СЧТ:=СЧТ – 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 +Р0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 Результат сложения 0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 СЧТ:=СЧТ – 0 1 1 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 +Р0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 Результат сложения 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 СЧТ:=СЧТ – 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 (CF,P2):=LC((CF,P2),1) 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 (CF,PСМ):=LC((CF,PСМ),1) 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 +Р1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 Результат сложения 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 СЧТ:=СЧТ – 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 (CF,P2):=LC((CF,P2),1) Так как после последнего сложения CF=1 (остаток положительный), то восстановления остатка не требуется.

4.6.2. Деление целых двоичных чисел в формате с ФТ в прямом коде Операция деления в прямом коде выполняется над модулями операндов, а знак частного получается сложением по «модулю 2» знаковых разрядов делимого и делителя. Деление модуля делимого на модуль делителя выполняется по алгоритму деления беззнаковых чисел. Знак остатка должен совпадать со знаком делимого, так как остаток остается от делимого. Поэтому при СЧТ=0 сравнивается знак остатка со знаком делимого, и если они не совпадают, то к РСМ прибавляется делитель со знаком, противоположным знаку РСМ (называется «восстановление остатка»).

Рассмотрим пример деления X/Y по этому алгоритму в восьмиразрядном процессоре (табл. 4.8).

X=251(8); Y= – 5(8).

X=10101001(2); Y= – 101(2).

В формате байта получаем:

X=10101001(2); Y= – 00000101(2); [|Y|]2=00000101; [– |Y|]2=11111011.

[|Х|]2=0000000010101001.

Проверим результат. Модуль частного находится в регистре Р2=00100001(2)=41(8), а остаток – в РСМ=00000100(2)=4(8). Определяем знак частного:

знак Z= (знак Х)^(знак У)=0^1=1.

[Z]1=10100001; Z= –0100001(2) = – 41(8).

Результат верен.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 13 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.