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

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

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

t₀ t₁ t₂ t₃ w₂ w₁ w₂ w₂  

t₀ t₁ t₂ t₃ p₂ p₁ p₃ p₃  

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

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	последовательность состояний

Автоматы (с выходным преобразователем)

Они представляют собой совокупность следующих шести объектов

A = <P, S, s₀, φ, W, ψ>

W – выходной алфавит

ψ – функция выходов

Существует две математические модели автомата(автомат Мура и Миля) обе мобели можно представить виде двух частей – формулирователь предыстории и выходного преобразователя.

Автомат Мура:

В автомате Мура осуществляется отображение S -> W, т.е. каждой букве состояния ставится буква выходного алфавита.

W_i = ψ(s_i)

W_i (t+1)= ψ(s(t+1)) – новый выходной символ определяется новым состоянием.

Автомат Миля:

осуществляется отображение P * S -> W. т.е.

W_k = ψ(P_i, S_j)

W(t+1) = ψ(P(t)_, S(t))

Новое выходное слово в автомате Миля определяется состоянием, в котором был автомат и выходным словом, который поступил на автомат.

Был в состоянии -> поступил в состояние.

Способы задания автоматов

Задание автомата Мура:

A: <P, W, S, s₀, φ, ψ>

В автомате Мура ψ зависит только от состояний.

Автомат как Мура, так и Миля задается шестью параметрами.

P, W, S – задаются в виде множеств

s₀ – начальное состояние указывается как буква алфавита S

Функция φ – задается тремя способами (рассмотренными ранее): перечисление, табличный, графический.

Функция ψ – также может быть представлена теми же тремя способами.

Автомат Мура:

a) перечисление

φ: S_{1 =} φ(S_0, S₁) ψ: W₁ = ψ (S₁)

φ: S_{2 =} φ(S_1, S₁) ψ: W₂ = ψ (S₂)

….. …..

φ: S_{k =} φ(S_k, S_k-1) ψ: W₀ = ψ (S₀)

b) табличный способ

φ, ψ

Wi	Pi	Pi	P0	P1	P2	…	Pn-1
Si
W0	S0	Si	Sj	…	…	…	…
W1	S1	…	…	…	…	…	…
Wl-1	Sm-1	S0	Sk	..	…	…	…

Данная таблица одна определяет две функции, так как W_i зависит только от S_i

Таблица называется «отмеченной» таблицей.

Количество W и S может быть разное, т.к. разным состояниям может быть поставлено в соответствие одна и та же выходная буква.

c) графический способ

Пример (автомат Мура)

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

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

S = {s_0, s_1, s_2, s₃ } – алфавит состояний

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

Функция переходов:

S₀ = φ (S_0, P₁)

S₀ = φ (S_3, P₂)

S₁ = φ (S_0, P₂)

S₂ = φ (S_1, P₁)

S₂ = φ (S_2, P₁)

S₃ = φ (S_1, P₂)

S₃ = φ (S_2, P₂)

S₃ = φ (S_3, P₁)

Функция выходов:

W₀ = ψ (S₀)

W₁ = ψ (S₁)

W₀ = ψ (S₂)

W₀ = ψ (S₃)

Табличный способ:

Wi	Pi	P1	P2
Si
W0	S0	S0	S1
W1	S1	S2	S3
W0	S2	S2	S3
W0	S3	S3	S0

Графический способ:

ti	t0	t1	t2	t3	t4
si	s0	s0	s1	s3	s3	s0
Pi	P1	P2	P2	P1	P2
Ni	*	W0	W1	W0	W0	W0

* - эта ячейка пуста, т.к. W(t+1) = ψ(s(t+1)) – это не реакция на входной сигнал

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

На выходе автомата тем не менее будет значение W₀, т.к. выход однозначно определяется состоянием автомата Мура, а состояние = S₀.

Для полной проверки автомата необходимо послать такую последовательность P, чтобы автомат прошел по всем переходам при всех входных сигналах, желательно чтобы автомат оказался в начальном состоянии S₀, что позволит подавать новые входные последовательности без предварительной начальной установки.

Способы задания автомата Миля

P, W, S, s₀ – задается аналогично автомату Мура.

Функции выхода задаются тремя способами:

a) перечисление

φ:

S_{1 =} φ(S₀, P₁) – предыдущее воздействие – новое состояние

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

…

S_{m-1 =} φ(S_m-2, P₀)

ψ:

W₁ = ψ (S₀, P₁)

W₂ = ψ (S₁, P₂)

…

W_l-1 = ψ (S_m-1, P₀)

b) Табличный способ

Pj	P0	P1	…	Pn-1
Si
S0	S1	S2	…	S3
S1	S2	S3	…	…
…	…	…	…	…
Sm-1	S0	…	…	…

Таблица выходов для ψ

Pj	P0	P1	…	Pn-1
Si
S0	W0	W1	…	Wl-1
S1	W1	W2	…	…
…	…	…	…	…
Sm-1	W0	…	…	…

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

Pj	P0	P1	…	Pn-1
Si
S0	S1/W0	S2/W1	…	S3/Wl-1
S1	S3/W1	S2/W2	…	…
…	…	…	…	…
Sm-1	S0/W0	…	…	…

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

Так как выходной сигнал зависит и от состояния и от входного сигнала, то выходной сигнал приводят на ребре графа.

Пример (автомат)

P = {P₁, P₂}

W = {W₀, W₁}

S = {S_0, S₁, S₂}

s₀

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

φ:

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

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

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

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

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

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

ψ:

W₀ = ψ (S₀, P₁)

W₁ = ψ (S₀, P₂)

W₀ = ψ (S₁, P₁)

W₀ = ψ (S₀, P₂)

W₀ = ψ (S₂, P₁)

W₀ = ψ (S₂, P₂)

2) Таблица (совмещение переходов и выходов)

Pj	P1	P2
Si
S0	S0/W0	S1/W1
S1	S1/W0	S2/W0
S2	S2/W0	S0/W0

3)

P₁/W₀

Графический способ

Тест:

ti	t0	t1	t2	t3	t4
si	s0	s0	s1	s2	s2	s0
Pi	P1	P2	P2	P1	P2
Wi		W0	W1	W0	W0	W0

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

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

Преобразование автоматов из Миля в Мура и обратно

Дата добавления: 2014-01-06