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

ТЕОРИЯ АВТОМАТОВ.

Уровни представления ЭВМ.

Различные уровни представления ЭВМ обусловлены особенностями свойств цифровых машин.

Свойства цифровых машин:

 

1. Многочисленность и многофункциональность.

2. Сложность функционирования.

3. Иерархический характер организации машины.

 

Существует 4 уровня представления ЭВМ; в каждом уровне по- своему описывается как аппаратная, так и производственная часть:

 

 1. Уровень электрических схем и таблиц истинности.

2. Уровень логических схем и таблиц истинности.

3. Уровень операционных схем и микропрограмм.

4. Уровень структурных схем и программ.

 

1. Уровень элементов на плате 0 и 1, занесенных в микросхемы. Уровень отражает только физические свойства программы. Используется при производстве и ремонте.

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

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

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

Описание ЭВМ на уровне операционных схем и микропрограмм.

 

F= {f₁, f₂, …, f_n}- набор функций.

{A,(B),C,F,Q}

Операционное устройство

 

ОА имеет дело с обрабатываемыми словами, над которыми выполняется микрооперация Y_i. Управляющий автомат работает по микропрограмме, которая состоит из микрокоманд.

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

Микрооперация – это элементное машинное действие, которое не может быть разбито на более мелкие.

Микропрограмма – это алгоритм выполнения машинной операции, описанной в терминах микроопераций и логических условий. ОА состоит из набора операционных элементов.

Операционные элементы. (ОЭ)

ОЭ описывается:

 

1. входными и выходными словами
2. множеством реализованных микроопераций
3. множеством сформированных логических условий.

 

Типы операционных элементов:

1. Управляемая шина

1. Регистры для передачи и хранения информации.

Регистр – набор триггеров, каждый из которых хранит 1 бит информации (0-1)

a) регистр для хранения информации с одним выходом.

Одна микрооперация – запись.

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

b) Регистр с двумя выходами.

с) многофункциональный регистр

Например Y₁ – сброс, Y₂ – прием числа, Y₃ – сдвиг содержимого на 1 разряд влево, Y_k - сдвиг содержимого на 1 разряд вправо и др.

 

1. Счетчик

 

 

Y₁ – обнуление                     СT: = 0

Y₂ – прием кода                    CT:= A

Y₂ – прямой счет                              CT:= CT + 1

Y₂ – обратный счет              CT:= CT - 1

 

 

1. Различные комбинационные узлы

 

a) Дешифраторы

 

 

b) Сумматоры

 

 

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

 

 

2. Одноразрядный сумматор

 

C:

 

--------------p
-----------------b
a 0	1	0	1
1	0	1	0

 

q:

 

 

--------------p
-----------------b
a 0	0	1	0
0	1	1	1

 

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

 

 

0	00 01 10 11 ab 0 0 1 0 1 1 1 0 1 0 p   Ось отраж. 0
0	1
1	Ось отраж. 1
1	0

 

1	1	0
1	1	1
1	0	1
1	0	0
	1	0	0
	1	0
	1	1	1

A

 

0	1	0	1
1	0	1	0

 

                                                                      

 

В карте Карно вместо 1- черточка, вместо 0- пусто.

 

 

После того, как склеили:

 

 

	I       II         III

                                                                             

110 1

Q= a b p v a b p v a b p = bp v ap v ab

 

 

                    

c= a b p  v  a b p  v  a b p  v  a b p

bp

a b  p

&

 

 

2. Накапливающий сумматор.

 

 

 

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

 

 

Для описания микропрограмм используют три различных языка:

1. язык графической схемы алгоритма ГСА

2. язык логической схемы алгоритма ЛСА

3. язык метрической схемы алгоритма МСА

 

ГСА- граф, в котором используются следующие вершины:

У0

                                       - начально - операторская вершина, которая помечается                       

                                             начальной операцией У0.

		Ук

 

                                      - конечно – операционная вершина, получаемая Ук.

 

 

Уi

                                 - операционная вершина, получаемая Уi.

 

 

Xj

                                      - логическое условие.

 

               

 

Алгоритмы бывают:

 

- линейные,

- разветвляющиеся,

- циклические.

 

Процессор ГСА:

а) линейный алгоритм.       б) разветвляющийся алгоритм.

 

                                                                     

1

1

0

X2

Y3

Y2

0

X1

X1

Y1

Y0

 

 

 

в) циклический алгоритм.

 

Условия корректности ГСА:

1. достижимость.

2. отсутствие тупиковых ситуаций.

а) наличие пути из начала вершины в каждую из операционных вершин.

б) из каждой операционной вершины должен быть путь в конечную.

 

Достоинства и недостатки.

Достоинства ГСА – наглядность.

Недостатки ГСА – громоздкость,

                         - сложность представления в машинных кодах.

Линейный алгоритм.

 

	Y1	Y2	....	Yk
Y0	1
Y1		1
. . .			. . .
Yk-1				1

   Начальная вершина – микрон Y0.

   Переход из Yi Yj - 1

5 cтрок, 5 столбцов.

 

	Y1	Y2	Y3	Y4	Yk
Y0	1
Y1		X1	X1 X2	X1 X2
Y2					1
Y3					1
Y4					1

 

               X1 v X1 X2 v X1 X2
                   

 

Условия корректности:

 

1. Отсутствие пустых строк и столбцов.

2. В каждой строке объединение по «или» всех логических условий должно приводить к 1.

3. Эти два условия одновременно проверяют достижимость оперативных вершин и наличие пути из них в конечную.

Достоинства: удобно хранить в памяти компьютера.

Недостатки: очень громоздок, при большом количестве операторов.

 

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

 

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

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

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

 

+23     0010111

+18     0010010

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

 

-23     1101000

           1100101

      1 1010101

 

 

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

 

 

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

 Пусть 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)

 

 

Способы задания функций переходов.

 

Существует три способа:

1. перечисление

2. табличный

3. графический

a) При перечислении приводятся все значения функции переходов

S_{1 =} φ(S₀, P₁)

S_{2 =} φ(S₁, P₂)

......

S_{m =} φ(Sm-₁, P_i)

b) При табличном способе столбцы помечаются входными буквами, строки – буквы состояний из которых осуществляется переход.

 

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

Pi	P1	P2	…..	Pn
Sj
S0	S1	S2	…..	S1
S1	S0	S2	…..	Sm
…..	…..	…..	…..	……
Sm			…..

c) Графический

Каждому состоянию автомата ставится в соответствие вершина графа, которая помечается символом состояния.

Между состояниями присутствует дуга – если между ними есть переход.

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

 

 

 

Пример:

S_{0 =} φ(S₀, P₁)

S_{1 =} φ(S₀, P₂)

S_{1 =} φ(S₁, P₁)

S_{2 =} φ(S₁, P₂)

S_{2 =} φ(S₂, P₁)

S_{0 =} φ(S₂, P₂)

Pj	P1	P1
Sj
S0	S0	S1
S1	S1	P1 S2
S2	S2	S0

 

t0	t1	t2	t3	t4	t5	t6	t7	машинные такты
P1	P2	P1	P1	P2	P1	P2		входное слово
S0	S0	S1	S1	S1	S2	S2	S0	последовательность состояний

 

 

Обратный переход.

Синтез конечных автоматов.

 

Синтез состоит из двух этапов.

1) Абстрактный синтез

2) Структурный синтез

 

Типы памяти.

 

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

Элемент памяти как правило имеет два выхода: прямой и инверсный.

Значение на прямом выходе соответствует коду состояния триггера и как правило выходному сигналу триггера.

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

Автомат обладает полной системой переходов, если любых пар S_i и S_j можно указать сигнал вызвавший переход из S_i в S_j.

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

 

Основные типы триггеров.

 

Существует 4 основных логических типа триггера:

          два одновходовых: «D», «T»

          два двухвходовых: «RS», «JK»

 

1. «D» триггер или триггер задержки (delay)

 

    Графическое обозначение:

 

 

                это автомат Мура (дуги – значения D)

 

Выходные значения во всех значениях будут совпадать с кодом состояния и будут обозначаться буквой q.

 

W(q)	P(D)	0	1
	S(q)
0	0	0	1
1	1	0	1

 

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

 

q^t à q^t+1	D
0 à 0	0
0 à 1	1
1 à 0	0
1 à 1	1

 

Эта таблица упрощается и приводится к виду:

 

0

0 à 0 т.е. значение D пишется над стрелкой.

1

0 à 1

0

1 à 0

1

1 à 1

 

1. «T» триггер (Toggle - кувыркаться)

 

 

Триггер меняет свое состояние (Т = 1)

 

 

q / T	0	1
0	0	1
1	1	0

 

q^t à q^t+1	T
0 à 0	0
0 à 1	1
1 à 0	1
1 à 1	0

 

0

0 à 0

1

0 à 1

1

1 à 0

0

1 à 1

1. «RS» триггер

 

R – reset – сбрасывает в 0 (00 – хранение предыдущего состояния)

S – set – установка в 1 (11 - запрещена)

R = 1 – сброс

S = 1 – установка

R = S = 0 – хранение

R = S = 1 – запрещена.

 

* - безразлично чему равен сигнал

 

q / RS	00	01	10	11
0	0	1	0	--
1	1	1	0	--

«--» - запрещенные комбинации

 

q^t à q^t+1	RS
0 à 0	*0
0 à 1	01
1 à 0	10
1 à 1	0*

*0

0 à 0

01

0 à 1

10

1 à 0

0*

1 à 1

 

1. «JK» триггер (jump – установка 1, kill - сброс)

 

 

J = 1         K = 0 – установка

J = 0         K = 1 – сброс

J = K = 0 - хранение

J = K = 1 – инверсия

1)

0*

00 – хранение

01 - сброс

2) 0 à 1

1*

10 – установка

11 - инверсия

3) 1 à 1

*0

4) 1 à 0

  *1

 

q / JK	00	01	10	11
0	0	0	1	1
1	1	0	1	0

 

q^t à q^t+1	JK
0 à 0	0*
0 à 1	1*
1 à 0	*1
1 à 1	*0

 

0*

0 à 0

1*

0 à 1

*1

1 à 0

*0

1 à 1

 

Пример структурного синтеза синхронного автомата.

 

Автомат называется синхронным, если его состояние меняется в строго определенные моменты времени.

Эти моменты времени определяется с помощью специальных синхронизаций сигналов.

 

тип логического элемента:

                      «И»                                                                «НЕ»

 

тип памяти RS

Нужно получить минимум затрат, т.е. минимум логических элементов.

Этапы:

P = {0,1}

W = {0,1}

Кодирование производить не надо. т.к. они уже кодированы.

Триггер – 1 разряд

log₂3 = 2, т.е. для кодирования нужно минимум два разряда

Закодируем произвольно

    q₀ q₁

S₀ = 0 1

S₁ = 1 1

S₂ = 1 0

 

 Представим исходный автомат виде таблицы переходов и выходов.

Si / Pi	0	1
S0	S1 /0	S1 /0
S1	S2 /0	S2 /0
S2	S0 /1	S0 /0

Вместо состояний приводим в таблице их коды и получаем кодированную таблицу переходов и выходов

Xi / q0q1	0	1
0 1	11 /0	11 /0
1 1	10 /0	10 /0
1 0	01 /1	01 /0

RS

*0

0 à 0

01

0 à 1

10

1 à 0

0*

1 à 1

 

Xi / q0q1	0	1
0 1	01,0* /0	01,0* /0
1 0	0*,10 /0	0*,10 /0
1 1	10,01 /1	10,01 /0

Данная таблица называется таблица функций возбуждения и выходов.

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

В данной таблице представлены 5 булевых функций: R₀, S₀, R₁, S₁,Z₀

 

R0			------------q1
		------------q0
	---	1	0	0
X0 -	---	1	0	0

 

S0			------------q1
		------------q0
	---	0	*	1
X0 -	---	0	*	1

 

R1			------------q1
		------------q0
	---	0	1	0
X0 -	---	0	1	0

 

S1			------------q1
		------------q0
	---	1	0	*
X0 -	---	1	0	*

 

Z0			------------q1
		------------q0
	---	1	0	0
X0 -	---	0	0	0

 

 

В результате:

 

R₀ = ^q₁ (^ - отрицание)

S₀ = q₁

R₁ = q₀q₁

S₁ = ^q₁

Z₀ = ^q₁^X₁

 

 

В результате получается окончательная схема:

C – синхронизация

 

В начальном состоянии триггеры должны быть закодированы (установлены в начальное состояние S₀) т.е. q₀ – сброс

                 S₁ – установка

При с = 0 функции возбуждения непосредственно на входах триггеров равны 0

Это соответствует режиму хранения двух триггеров, следовательно автомат находится (остается) в том же состоянии и не осуществляет переход.

При с = 1 получаем

                       R₀¹ = R₀

                                S₀¹ = S₀

                                R₁¹ = R₁

                                S₁¹ = S₁

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

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

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

С другой стороны в это время меняется значение q_i и они по обратной связи поступают на вход триггера, т.е. могут привести к изменению значений R_i, S_i

Следовательно длительность сигнала с должна быть ограничена сверху так, чтобы новые значения q_i не успели поступить на входы R_i, S_i (т.е. с – достаточно короткое).

Корректное значение z можно получить лишь тогда, когда q и x неизменные, т.е. после окончания их переключения и завершения всех переходных процессов в схеме, а это происходит при с = 0.

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