Операционное устройство для сложения целых двоичных чисел
При построении такого устройства существенным является способ кодирования чисел. Целые двоичные числа со знаком могут быть представлены в прямом, обратном и дополнительном коде. Знак положительного числа кодируется – «0», а отрицательного числа - «1».
Для положительных чисел прямой, обратный и дополнительный коды совпадают.
Обратный код отрицательного числа образуется инвертированием цифровых разрядов прямого кода двоичного числа. Дополнительный код отрицательного числа образуется прибавлением единицы к младшему разряду обратного кода этого числа.
Например, отрицательное десятичное число « - 5» в восьмиразрядном двоичном представлении, где самый левый разряд – знак числа имеет вид:1 000 0101 – прямой код; 1 111 1010 – обратный код;
1 111 1011 – дополнительный код.
При выполнении операции сложения двоичных чисел в обратном или в дополнительном коде можно со знаковыми разрядами слагаемых оперировать также как с цифровыми разрядами. Знаковыми разряды можно складывать, производить перенос из старшего цифрового разряда в знаковый и перенос из знакового разряд в младший цифровой (при сложении в обратном коде). Это позволяет использовать сумматор с однородной структурой, приведенный на рис. 1.14.
При сложении чисел с одним знаком может возникнуть аварийная ситуация, когда результат не помещается в сумматор. Для выявления переполнения разрядной сетки сумматора необходимо использовать модифицированные коды слагаемых.
В модифицированном коде под знак числа выделяется два разряда: знак положительного числа кодируется – «00», а отрицательного числа - «11». Обычно в памяти ЭВМ числа хранятся в прямом немодифицированном коде. Преобразование в модифицированный код производится при пересылке слагаемых в сумматор. Появление в знаковых разрядах сумматора кода «01» или «10» в результате суммирования является признаком переполнения его разрядной сетки.
Сложение целых чисел в обратном модифицированном коде.
В данном способе сложения производится суммирование всех разрядов числа и перенос из старшего знакового разряда в младший цифровой разряд. Примеры сложения целых чисел, записанных в одном байте памяти в прямом двоичном коде со знаком :
модифицированный прямой код: модифицированный обратный код:
| + |
+ 2 00 000 0010 00 000 0010
11 111 1100 →–3 в обратном коде
11 000 0011 → –3 в прямом коде.
| + |
– 2 11 000 0010 11 111 1101
| + |
11 111 1000→ –7 в обратном коде
11 000 0111→ –7 в прямом коде.
| + |
+2 00 000 0010 00 000 0010
01 000 0001→ переполнение.
| + |
–2 11 000 0010 11 111 1101
| + |
10 111 1110→ переполнение.
Сложение целых чисел в дополнительном модифицированном коде.
В данном способе сложения производится суммирование всех разрядов числа без переноса из старшего знакового разряда. Результат получается в дополнительном коде. Суммирование в дополнительном коде происходит быстрее, чем в обратном коде.
модифицированный модифицированный
прямой код: дополнительный код
| + |
+ 2 00 000 0010 00 000 0010
11 111 1101→–3 в доп. коде;
11 111 1100→–3 в обратном коде
11 000 0011 → –3 в прямом коде.
| + |
– 2 11 000 0010 11 111 1110
11 111 1001→ –7 в доп. коде;
11 111 1000→ –7 в обратном коде
11 000 0111→ –7 в прямом коде.
| + |
+2 00 000 0010 00 000 0010
01 000 0001→ переполнение.
| + |
–2 11 000 0010 11 111 1110
10 111 1111→ переполнение.
Операционное устройство для выполнения операции сложения целых двоичных чисел можно представить в виде композиции операционного и управляющего автомата, приведенной на рис.1.18.
.
| A |
| B |
| OA |
| УA |
| Y |
| X |
| C |
Рис.1.18
На рис. 1.19 представлена схема операционного автомата (OA), приведенного на рис. 1.18.
| B |
| A |
| SM |
| k |
| x1 |
| x2 |
| C |
| q |
| p |
| RG |
| y1 |
| y2 |
| k |
| y3 |
| d |
| x3 |
Рис.1.19
Слагаемые А и В поступают в операционное устройство в прямом коде, причем слагаемое А записывается в сумматор накапливающего типа SM с 1 по k–тый разряд. Знаковый (первый) разряд слагаемого А дублируется в дополнительном знаковом разряде d, таким образом число А в сумматоре будет представлено в модифицированном коде. Слагаемое B записывается в регистр операнда RG. Суммирование производится в сумматоре SM в обратном модифицированном коде, так как в сумматоре имеется перенос из дополнительного знакового разряда d в младший разряд сумматора k. После выполнения операции сложения результат С преобразуется в прямой код
На рис.1.20 представлен управляющий автомат (УА) с его входами и выходами из рис. 1.18 в виде «черного ящика», вместе с реализуемой им микропрограммой.
| Начало |
| x1 |
| x3 |
| y2 |
| y1 |
| y3 |
| x1 |
| x2 |
| x2 |
| y4 |
| y1 |
| Конец |
| УА |
| y2 |
| y1 |
| x1 |
| y4 |
| y3 |
| x3 |
| x2 |
Рис.1.20
В микропрограмме, приведенной на рис. 1.20 используются следующие логические условия:
x1 – дополнительный знаковый разряд сумматора SM;
x2 – первый (знаковый) разряд сумматора SM;
x3 – первый (знаковый) разряд регистра RG.
В микропрограмме используются следующие микрооперации, инициализирующие в операционном автомате следующие действия:
y1 – по этой микрооперации происходит инвертирование цифровых (со второго по k-тый) разрядов сумматора, то есть: SM(2:k):= SM(2:k);
y2 - по этой микрооперации ко всему содержимому сумматора, включая разряд d, прибавляется содержимое цифровых разрядов регистра RG, то есть: d.SM(1:k):=d.SM(1:k) + RG(2:k);
y3 - по этой микрооперации ко всему содержимому сумматора, включая разряд d, прибавляется обратный код второго слагаемого, прямой код которого содержится в регистре RG, то есть: d.SM(1:k):=d.SM(1:k) + 11.RG(2:k);
y4 - по этой микрооперации происходит установка в состояние «1» триггера признака переполнения, то есть ПП:= 1.
В табл. 1.4 приведена «прокрутка» микропрограммы, показывающая работу операционного устройства с числом разрядов k = 5, при сложении чисел: A = -5, B = 2.
Таблица 1.4
| SM | RG | x1 x2 x3 | y1 y2 y3 y4 |
| 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 | 0 0 1 0 | 1 1 0 | 1 0 0 0 0 1 0 0 1 0 0 0 |
В табл. 1.5 приведена аналогичная «прокрутка» микропрограммы, при сложении чисел: A = -5, B = -3, выявляющая ситуацию переполнения разрядной сетки сумматора.
Таблица 1.5
| SM | RG | x1 x2 x3 | y1 y2 y3 y4 |
| 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 | 1 0 1 1 | 1 1 1 1 0 1 | 1 0 0 0 0 0 1 0 0 0 0 1 |
Из рассмотрения примеров моделирования работы операционного устройства рассмотренных в табл.1.4 и в табл. 1.5 видно, что в процессе взаимодействие операционного и управляющего автоматов каждая микрооперация, в результате ее выполнения, может менять или не менять значения логических условий.
В общем случае влияние микрооперации yj на значение логического условия xi может происходить одним из следующих способов:
xi := 0 - присвоение значения 0;
xi := 1 - присвоение значения 1;
xi := z - присвоение неопределенного значения (0 или 1);
xi := xi - присвоение инверсного значения;
xi := xi - отсутствие влияния yj на xi.
Влияние микроопераций на значения логических условия в приведенном примере удобно представить в виде табл. 1.6.
| x1 | x2 |
| ||
| y1 | ||||
| y2 | z | z | ||
| y3 | z | z | ||
| y4 |
Таблица, определяющая влияние микроопераций на значение логических условий, строится исходя из уже построенной схемы операционного автомата и выбранного набора микроопераций и логических условий. Схема операционного автомата строится на основе интуиции и опыта разработчика. Для построения управляющего автомата можно использовать методы синтеза теории конечных автоматов. Учет взаимодействия операционного и управляющего автомата в этих методах позволяет получить более экономичную схему управляющего автомата.
КОНЕЧНЫЕ АВТОМАТЫ
Введение
Все цифровые устройства можно разделить на два класса:
1. логические схемы;
2. схемы с памятью.
Логические и комбинационные схемы формируют значения выходных сигналов в зависимости от значений входных сигналов, подаваемых в данный момент независимо от значений входных сигналов, подаваемых на входы ранее. Для описания этих схем используются переключательные (булевы) функции.
В другом классе схем значение выходных сигналов зависят не только от значений входных сигналов, поступающих в данный момент, но еще и от значений сигналов, подаваемых на эти входы ранее, т.е. эти схемы учитывают предысторию входных сигналов. Эти схемы называются схемами с памятью или последовательностными схемами, так как они последовательность входных сигналов перерабатывают в последовательность выходных сигналов.
Для описания таких схем используется теория конечных автоматов.
Теория конечных автоматов
Основные определения:
1. конечная совокупность различных символов называется алфавитом;
2. каждый отдельный символ алфавита - буквой;
3. последовательность букв, имеющая конечную длину - словом;
4. число букв в слове - длиной;
5. два алфавита называются равнозначными, если между буквами этих алфавитов можно установить взаимно-однозначное соответствие.
Пример конечного автомата:
Пусть: P = {p1, p2, p3} – входной алфавит, W = {w1, w2} – выходной алфавит.
Будем рассматривать абстрактный конечный автомат в виде «черного ящика» с одним входом и одним выходом (рис. 2.1), т.е. анализируемое устройство описывается на уровне задания зависимости значений на его выходе от значений на его входе.
| t3 t2 t1 t0 p2 p3 p1 p3 p2 p1 p3 p3 |
| t3 t2 t1 t0 w2 w2 w1 w2 |
| A |
Рис. 2.1
Работа автомата рассматривается в дискретные моменты времени ti называемые автоматными тактами (i меняется от 0 до n, где n – длина входного слова). В примере на рис.2.1 в начальный момент времени t0 автомат входную букву р3 перерабатывает в выходную букву w2. В результате работы автомат входное слово p3p1p3p2 перерабатывает в выходное слово w2w1w2w2.
В общем случае конечный автомат определяет устройство, которое реализует отображение множества слов входного алфавита во множество слов выходного алфавита.
Различают два класса абстрактных автоматов:
1. автомат без выходного преобразователя;
2. автомат с выходным преобразователем.