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

Способы кодирования чисел со знаком:

 

	Прямой	Обратный	Дополнит.
+23	010111	010111	010111
-23	110111	101000	101001
+18	010010	010010	010010
-18	110010	110010

- «1»

+ «0»

модуль 23= 10111

модуль 18= 10010

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

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

В дополнительном коде: положительные – совпадают с прямым, в отрицательном числе – инвертируются прям +1

Знак числа кодирования «+» - «0»,«-» - «1» во всех способах кодирования.

Если при выполнении операции выбирается способ кодирования (прямой, обратный или дополнительный), то как отрицательное, та и положительное число представляет собой только в выбранном способе кодирования.

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

 

Суммирование при использовании прямого кодирования.

Алгоритм выполнения суммирования сложения:

Он подразумевает предварительный анализ знаков и анализ модулей.

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

 

+23	010111
-18	110010
	000101
-23	110111
+18	010010
	100101

23>18

 

→ +5

23>18

 

→ -5

Суммирование чисел при использовании обратного кода.

 

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

Сумма получается в обратном виде:

 

+23 1 010111

-18        101101

             000100

             000101 → +5  в обратном коде.

-23   0 101000

+18        000010

              111010 → -5 в обратном коде.

 

 

Осуществляется безусловное суммирование всех разрядов, а результат в дополнительном коде.

Дополнительный код.

+23   1 010111

-18         101110

              000101 → +5 в дополнительном коде.

 

 

-23        101001

+18       101110   

             111011 → -5 в дополнительном коде.

 

Суммирование в дополнительном коде наиболее быстрое, в прямом коде самые медленные. Использование обратного кодирования позволяет производить преобразования из прямого в обратное и наоборот.

 

	А

Xi

Yi

YA

OA

В

 

 

 

23       010111

18       010010    переполнение разряда сети

           101001

 

Используются модифицированные разряды.

00 +

11 -

переполнение

01                                  +

10                                  -

 

 

Модифицированный код.

 

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

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

В случае переполнения, получается 01, 10, причем старший бит соответствует правильному значению знака, а младший показывает о наличии переполнения, 10 – отрицательное переполнение.

 

+23     0010111

+18     0010010

           0101001   положительное переполнение.

 

-23     1101000

           1100101

      1 1010101

 

 

           1010110 переполнение

 

 

Операционный автомат (неоптимальный), сумматор накапливающий.

 

 

X4

X3

X1

X2

Y9

Y8

X1

Y1

 

 

 

Предполагаем, что А, В, С представлены в прямом коде, суммировать будем представленные в обратном коде.

 А, В, С представлены в модифицированном коде.

 

 

У 0 – на входе регистра – сигнал записи (микрооперация записи).

 

У 0  - У 2 – на входах сумматора – микрооперация сброса и суммирования накапливающего сумматора.

 

У 8, У 9 – положительное и отрицательное переполнение.

 

Остальные микрооперации управляются шиной.

 

Х 1, Х 2 – логические условия, показывающие значения операндов А, В соответственно.

По начальной микрооперации У0 осуществляется прием А, В – обновление сумматора.

 

У0:              RGA: = A

    RGB: = B

    SM: = 0

 

Y1, Y2:       SM: = RGA

 

Y3, Y2:       SM [0,1]: = RGA [0,1]

                  SM [2:k]: = RGA [2:k]

 

Y4, Y2:       SM: = SM + RGB

 

Y5, Y2:       SM: = SM + RGB [0,1], RGB [2:k]

 

Y6:             C: = SM

 

Y7:             C: = SM [0,1], SM  [2:k]

 

Y8:             Y8: = 1 (положительное переполнение)                             

 

Y9:             Y9: = 1 (отрицательное переполнение)

 

Положительные и отрицательные переполнения по У0 сбрасываются. Уn можно записать новое значение в регистре А, В вместо У0.

 

Пример суммирования.

 Пусть A = -5, B = 2, K = 5

RGA	RGB	SM	X1 X2 X3 X4	Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9
* * * * * * 1 1 0 1 0 1	* * * * * * 0 0 0 0 1 0	* * * * * * 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0   C: = 110011	* * * * 1 0 0 0 1 0 1 1   1 0 1 1	1 1 1                      1

YG YK влияет Xi => Xi  = 0 

                               Xi = 1

                              Xi = Z

                               Xi = Xi

                                                 Xi  = Xi ()

                               Xi =

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

Это влияние осуществляется одним из следующих образов:

 

Xi  = 0                   - обнуление логического условия.

Xi = 1              - установка в 1.

Xi = Z              - перевод в неопределенное состояние (0 или 1).

Xi = Xi               - инвертированное значение.

Xi = Xi ()    - перезапись Х.

Xi =                  - У не влияет на Х.

 

1. Y_i => X_i = X_i (X_i  =)

Y_n => X_i =

Y_i Y_k => X_i = X_i

                                                           

Примеры влияния микрокоманд.

Y_i => X_i = X_i ()

Y_k => X_i = X_i

Y_i Y_k => X_i = Z

Таблица влияний У^ов в нашем примере.

	X1 X2 X3 X4
Y0 ·Y1  Y2 ·Y3 ·Y4 ·Y5 ·Y6 ·Y7  Y8  Y9	z z 0 0   z z

Конечные автоматы.

Все цифровые устройства делятся на два класса:

 

1. Комбинационные устройства.

2. Последовательные устройства (автоматы).

 

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

Эти устройства описываются с помощью переключательных функций. (форменные представления которых являются таблицы истинности, карты Карно.)

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

Эти устройства перерабатывают последовательность входных сигналов в последовательность выходных.

Описанием этих устройств занимается теория конечных автоматов.

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

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

Каждый отдельный элемент множества или символ алфавита называется буквой.

Последовательность букв, имеющая конечную длину называется словом.

Число букв в слове называется длиной.

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

Пример автомата:

P = {P₁ , P₂, P₃} – входной алфавит

W = {W₁ , W₂ } – выходной алфавит

 

 

A

t0   t1   t2   t3 w2 w1 w2 w2

t0  t1  t2  t3 p2 p1 p3 p3

 

абстрактный автомат

t_i – машинные такты

В момент t₀ автомат перерабатывает входную букву P₂ в выходную букву W₂

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

Абстрактный автомат можно рассматривать виде совокупности двух блоков:

1. формирователь предыстории
2. выходной преобразователь

Формирователь предыстории – это совокупность четырех объектов.

F = A^l = <p,s,s₀,φ>

P = {P₁,P₂…P_n} – входной алфавит

S = {s₀, s₁,s₂,…s_m} – выходной алфавит

s₀ – начальное состояние

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

       P * S -> S

т.е. каждой паре букв p_js_j ->s_k ставится в соответствие новое значение s_k

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

P_i – входная буква

S_j – текущее состояние

S_k – новое состояние автомата

 

S_k = φ(P_i, P_j)

 

Если все алфавиты автомата конечны, то автомат – конечный, если хотя бы один бесконечен – бесконечный.

Если алфавит состояний бесконечен – автомат бесконечен.

S_k (t+1) = φ(P_i(t), S_j(t))

Работу автомата рассматривают в дискретные моменты времени.

Пример:

 

t0	t1
P(t0)	P(t1)	P(t2)
S0(t0)	S(t1)	S(t2)

 

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: