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

Пусть 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	* * * * * * 00 0 0 1 0	* * * * * * 0 0 0 0 0 0 11 1 0 1 0 00 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

YGYK влияет 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_iY_k=>X_i =X_i

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

Y_i=>X_i =X_i(¬ ¬)

Y_k => X_i = ¬ X_i

Y_i Y_k => X_i = Z

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

	X1X2 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₂} – выходной алфавит

t₀ t₁ t₂ t₃

p₂ p₁ p₃ p₃

t₀ t₁ t₂ t₃

w₂ w₁ w₂ w₂

A

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

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)