Операционное устройство для сложения целых двоичных чисел

При построении такого устройства существенным является способ кодирования чисел. Целые двоичные числа со знаком могут быть представлены в прямом, обратном и дополнительном коде. Знак положительного числа кодируется – «0», а отрицательного числа - «1».

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

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

Например, отрицательное десятичное число «- 5» в восьмиразрядном двоичном представлении, где самый левый разряд – знак числа имеет вид:1 000 0101 – прямой код; 1 111 1010 – обратный код;
1 111 1011 – дополнительный код.

При выполнении операции сложения двоичных чисел в обратном или в дополнительном коде можно со знаковыми разрядами слагаемых оперировать также как с цифровыми разрядами. Знаковыми разряды можно складывать, производить перенос из старшего цифрового разряда в знаковый и перенос из знакового разряд в младший цифровой (при сложении в обратном коде). Это позволяет использовать сумматор с однородной структурой, приведенный на рис. 1.14.

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

В модифицированном коде под знак числа выделяется два разряда: знак положительного числа кодируется – «00», а отрицательного числа - «11». Обычно в памяти ЭВМ числа хранятся в прямом немодифицированном коде. Преобразование в модифицированный код производится при пересылке слагаемых в сумматор. Появление в знаковых разрядах сумматора кода «01» или «10» в результате суммирования является признаком переполнения его разрядной сетки.

Сложение целых чисел в обратном модифицированном коде.

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

модифицированный прямой код: модифицированный обратный код:

+

– 5 11 000 0101 11 111 1010

+ 2 00 000 0010 00 000 0010

11 111 1100 → –3 в обратном коде

11 000 0011 → –3 в прямом коде.

+

– 5 11 000 0101 11 111 1010

– 2 11 000 0010 11 111 1101

+

11 111 0111

11 111 1000→ –7 в обратном коде

11 000 0111→ –7 в прямом коде.

 

+

+127 00 111 1111 00 111 1111

+2 00 000 0010 00 000 0010

01 000 0001→ переполнение.

 

 

+

–127 11 111 1111 11 000 0000

–2 11 000 0010 11 111 1101

+

10 111 1101

10 111 1110→ переполнение.

 

 

Сложение целых чисел в дополнительном модифицированном коде.

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

модифицированный модифицированный

прямой код: дополнительный код

 

+

– 5 11 000 0101 11 111 1011

+ 2 00 000 0010 00 000 0010

11 111 1101 → –3 в доп. коде;

11 111 1100 → –3 в обратном коде

11 000 0011 → –3 в прямом коде.

 

+

– 5 11 000 0101 11 111 1011

– 2 11 000 0010 11 111 1110

11 111 1001→ –7 в доп. коде;

11 111 1000→ –7 в обратном коде

11 000 0111→ –7 в прямом коде.

 

+

+127 00 111 1111 00 111 1111

+2 00 000 0010 00 000 0010

01 000 0001→ переполнение.

 

 

+

–127 11 111 1111 11 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 используются следующие логические условия:

x₁ – дополнительный знаковый разряд сумматора SM;

x₂ – первый (знаковый) разряд сумматора SM;

x₃ – первый (знаковый) разряд регистра RG.

В микропрограмме используются следующие микрооперации, инициализирующие в операционном автомате следующие действия:

y₁ – по этой микрооперации происходит инвертирование цифровых (со второго по k-тый) разрядов сумматора, то есть: SM(2:k):= SM(2:k);

y₂ - по этой микрооперации ко всему содержимому сумматора, включая разряд d, прибавляется содержимое цифровых разрядов регистра RG, то есть: d.SM(1:k):=d.SM(1:k) + RG(2:k);

y₃ - по этой микрооперации ко всему содержимому сумматора, включая разряд d, прибавляется обратный код второго слагаемого, прямой код которого содержится в регистре RG, то есть: d.SM(1:k):=d.SM(1:k) + 11.RG(2:k);

y₄ - по этой микрооперации происходит установка в состояние «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 видно, что в процессе взаимодействие операционного и управляющего автоматов каждая микрооперация, в результате ее выполнения, может менять или не менять значения логических условий.

В общем случае влияние микрооперации y_j на значение логического условия x_i может происходить одним из следующих способов:

x_i:= 0 - присвоение значения 0;

x_i:= 1 - присвоение значения 1;

x_i:= z - присвоение неопределенного значения (0 или 1);

x_i:= x_i - присвоение инверсного значения;

x_i:= x_i - отсутствие влияния y_j на x_i.

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

 

	x1	x2	Микрооперации y1, y4 не влияют на значение логических условий, а y2, y3 влияют на x1, x2 неопределенным образом. x3
y1
y2	z	z
y3	z	z
y4

 

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

КОНЕЧНЫЕ АВТОМАТЫ

Введение

Все цифровые устройства можно разделить на два класса:

1. логические схемы;

2. схемы с памятью.

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

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

Для описания таких схем используется теория конечных автоматов.

 

Теория конечных автоматов

Основные определения:

1. конечная совокупность различных символов называется алфавитом;

2. каждый отдельный символ алфавита - буквой;

3. последовательность букв, имеющая конечную длину - словом;

4. число букв в слове - длиной;

5. два алфавита называются равнозначными, если между буквами этих алфавитов можно установить взаимно-однозначное соответствие.

Пример конечного автомата:

Пусть: P = {p₁, p₂, p₃} – входной алфавит, W = {w₁, w₂} – выходной алфавит.

Будем рассматривать абстрактный конечный автомат в виде «черного ящика» с одним входом и одним выходом (рис. 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

Работа автомата рассматривается в дискретные моменты времени t_i называемые автоматными тактами (i меняется от 0 до n, где n – длина входного слова). В примере на рис.2.1 в начальный момент времени t₀ автомат входную букву р₃ перерабатывает в выходную букву w₂. В результате работы автомат входное слово p₃p₁p₃p₂ перерабатывает в выходное слово w₂w₁w₂w₂.

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

Различают два класса абстрактных автоматов:

1. автомат без выходного преобразователя;

2. автомат с выходным преобразователем.