Теория автоматов

 

Учитывая, что 10=8+2, и приведенный  выше пример, сформулируем алгоритм перевода следующим образом:  В процессе перевода выполняется k циклов, где k число требуемых разрядов десятичного числа. В каждом цикле сумматор обнуляется. Затем производится подсуммирование  дробной части числа, полученного в предыдущем цикле, сдвинутого на один двоичный разряд влево (умножение на 2). В следующем такте производится подсуммирование первого слагаемого, сдвинутого еще на два разряда влево (умножение на 8). Четыре бита слева от старшего разряда исходного числа дают очередную цифру десятичной дроби в коде Д1.

Перевод целого числа из кода Д1 в  двоичную систему счисления

Основанием для алгоритма перевода является схема Горнера. Число, представленное в системе счисления с основанием q необходимо перевести в систему счисления с основанием p. Целое число A_q в системе счисления с основанием p можно представить следующим образом:

A_q=a_npⁿ+a_n-1p^n-1+…+a₁p+a₀=a₀+p(a₁+p(a₂+…+p(a_n+0))…)

(2)

Из (2) следует, что для получения  цифр кода в системе счисления  с основанием p необходимо делить число А, записанное в исходной системе счисления с основанием q на основание новой системы счисления p, записанное в исходной системе счисления. Остатки от последовательных делений будут давать цифры числа А в системе счисления с основанием p, начиная с младшего разряда.  Если q>p, то результат перевода будет автоматически иметь правильный вид. Если же q<p, то цифры числа в новой системе счисления будут получаться как q-ичные коды p-ичных цифр.

В рассматриваемом случае q=10, p=2. следовательно остатки от деления десятичного числа на 2 дадут цифры кода двоичного числа, начиная с младшего разряда.

Пример. А=137₁₀. Алгоритм перевода очевиден из таблицы 3.

Определим необходимое число разрядов двоичного кода.

10³=2ⁿ. Отсюда n=]3/lg2[=10. Таким образом, для выполнения перевода нам потребуются следующие структурные элементы операционного автомата.

РгА[0-11] – регистр трехразрядного десятичного числа, записанного в коде Д1.

РгВ[0-9] – регистр двоичного числа.

СТ – счетчик, для контроля числа  определенных двоичных цифр.

КС -= комбинационные схемы, одинаковые для всех трех тетрад кода Д1, выполняющие коррекции тетрад кода Д1 после сдвига РгА на один разряд вправо (деления А на 2). Комбинационные схемы разрабатываются перед выполнением численного примера перевода, чтобы одновременно с выполнением перевода контролировать правильности комбинационной схемы.

Таблица 15 Пример перевода целого числа из кода Д1 в двоичную систему счисления

Десятичное Число	РгА	РгВ	СТ	Комментарии
137	0001 0011 0111	----------	10	РгА:=[A], CT:=10,
68	0000 1001 1011	1--------	9	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1, Во вторую и третью тетраду произошел перенос единицы  из старшей тетрады, который принес лишние 3 единицы. Поэтому в этих тетрадах должна быть выполнена коррекция «-3».
	000 0110 1000	-1--------		РгА:=КС(РгА)Б(коррекция), СТ=0? НЕТ РгВ:=R(1)РгВ,
34	0000 0011 0100	01--------	8	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
		-01-------		Коррекция тетрад не выполняется, так как ни в одной тетраде  нет переносов 1 из старшей тетрады. СТ=0? НЕТ РгВ:=R(1)РгВ,
17	0000 0001 1010	001-------	7	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
	0000 0001 0111	-001-------		РгА:=КС(РгА)Б(коррекция), СТ=0? НЕТ РгВ:=R(1)РгВ,
8	0000 0000 1011	1001------	6	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
	0000 0000 1000	-1001-----		РгА:=КС(РгА)Б(коррекция), СТ=0? НЕТ РгВ:=R(1)РгВ,
4	0000 0000 0100	01001-----	5	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
		-01001----		Коррекция тетрад не выполняется, так как ни в одной тетраде  нет переносов 1 из старшей тетрады. СТ=0? НЕТ РгВ:=R(1)РгВ,
2	0000 0000 0010	001001----	4	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
		-001001---		Коррекция тетрад не выполняется, так как ни в одной тетраде  нет переносов 1 из старшей тетрады. СТ=0? НЕТ РгВ:=R(1)РгВ,
1	0000 0000 0001	0001001---	3	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
		-0001001--		Коррекция тетрад не выполняется, так как ни в одной тетраде нет переносов 1 из старшей тетрады. СТ=0? НЕТ РгВ:=R(1)РгВ,
0	0000 0000 0000	10001001--	2	РгВ[0]:=РгA[11], РгА:=R(1)РгА, CT:=CT-1,
		010001001-		Коррекция тетрад не выполняется, так как ни в одной тетраде  нет переносов 1 из старшей тетрады. СТ=0? НЕТ РгВ:=R(1)РгВ, РгА=0? ДА Прекращаем операции над РгА и продолжаем выполнять сдвиги РгВ и декремент счетчика СТ, пока СТ>0.
		-010001001	1	СТ=0? НЕТ РгВ:=R(1)РгВ,
		0010001001	0	СТ=0? ДА Выход из цикла. Результат перевода находится в РгВ.

 

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

Перевод целого двоичного числа  в код Д1

Как было отмечено в предыдущем разделе, результат перевода в этом случае будет представлять каждую десятичную цифру в виде четырехразрядного двоичного кода. Поскольку код Д1 имеет естественные веса разрядов, то получаемые при переводе тетрады будут кодами соответствующих десятичных цифр в коде Д1. Если требуется выполнить перевод двоичного целого числа в код Д2 или Д4, необходимо уточнить механизм коррекций в тетрадах в соответствии с допустимыми в  рассматриваемом коде тетрадами. В качестве примера выполним обратных перевод полученного в предыдущем разделе двоичного числа в код Д1.  Так же, как и в предыдущем случае, требуется оценить число необходимых десятичных разрядов. Число значимых двоичных разрядов равно 8, следовательно, требуемое число десятичных разрядов равно n=]log₂8[ =3.

Схема операционного автомата должна содержать следующие структурные элементы:

• РгА[0-11] для записи тетрад кода Д1,
• РгВ[0-7] для записи исходного двоичного числа,
• КС1 – три комбинационные схемы для выполнения коррекций в тетрадах,
• СТ служит для контроля числа подсуммированных разрядов двоичного числа.

КС1 выполняет коррекцию тетрад следующим образом: для кода Д1 коррекция  «+3» выполняется в тетраде, если ее значение превышает 4. Это позволяет  избежать при сдвигах РгА влево появления недопустимых тетрад.

В каждом такте производится подсуммирование старшего бита двоичного числа к коду десятичного числа. Цикл управляется значением счетчика СТ. Выход из цикла при СТ=0.

Пример перевода целого двоичного  числа в код Д1 в таблице 3.

Таблица 16 Перевод целого двоичного числа в код Д1

РгА	РгВ	СТ	Комментарии
0000 0000 0000	10001001	8	РгА:=0, РгВ:= [B],
0000 0000 0001	0001001-	7	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 0000 001-			СТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?НЕТ Коррекции в тетрадах не требуются. РгА:=L(1)РгА,
0000 0000 0010	001001--	6	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 0000 010-			СТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?НЕТ Коррекции в тетрадах не требуются. РгА:=L(1)РгА,
0000 0000 0100	01001---	5	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 0000 100-			СТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?НЕТ Коррекции в тетрадах не требуются. РгА:=L(1)РгА,
0000 0000 1000	1001----	4	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 0000 1011			СТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?ДА Требуется коррекция  в третьей тетраде. Выполняем коррекцию +3.
0000 0001 011-			РгА:=L(1)РгА,
0000 0001 0111	001-----	3	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 0001 1010			СТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?ДА Требуется коррекция  в третьей тетраде. Выполняем коррекцию +3.
0000 0011 010-			РгА:=L(1)РгА,
0000 0011 0100	01------	2	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 0110 100-			РгВСТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?НЕТ Коррекции в тетрадах не требуются. РгА:=L(1)РгА,
0000 0110 1000	1-------	1	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
0000 1001 1011			СТ=0? НЕТ РгА[0-3]>4?НЕТ РгА[4-7]>4? НЕТ РгА[7-11]>4?НЕТ Коррекции во второй и  третьей тетрадах +3
0001 0011 011-			РгА:=L(1)РгА,
0001 0011 0111	--------	0	РгА[11]:= РгВ[0], РгВ:=L(1)РгВ,
			СТ=0? ДА Выход из цикла. Коррекция  тетрад не выполняется. Ответ: данное двоичное число  равно 13710.

 

Таким образом, алгоритм перевода целого двоичного числа в код Д1 работает до тех пор, пока не будут подсуммированы все разряды двоичного числа, начиная со старшего к десятичному числу.  Так как подсуммирование всегда производится после сдвига, то подсуммирование означает просто замещение нуля, стоящего в младшем разряде РгА, на значение старшего разряда РгВ. Признак СТ=0 означает выход из цикла. При этом сдвиг  РгА не производится и коррекция в тетрадах не выполняется.

 

Основные сведения о конечных цифровых автоматах

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

По степени детализации описания ЦА различают  абстрактные и структурные  ЦА. В соответствии с этим рассматривают абстрактную и структурную теорию ЦА.

В абстрактной теории  ЦА автомат рассматривается как "черный ящик", имеющий один вход и один выход. При рассмотрении таких автоматов отвлекаются от структуры как самого ЦА, так и его входных и выходных сигналов.

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

Абстрактная теория цифровых автоматов

Простейшим типом дискретных автоматов  являются комбинационные схемы, выход  которых в каждый момент времени определяется исключительно состояниями  входов и не зависит от предыстории.  В реальных системах поведение систем часто зависит не только от текущего состояния входов, но и от некоторой предыстории, т.е. от значений сигналов, поступавших на вход системы ранее. Такие системы называют "системами с памятью". Математической моделью систем с памятью является абстрактный автомат, определяемый как кортеж S=(A,Z,W,d,l, a₀), у которого

• A={a₀,a₁, …, a_m, …, a_M} - множество состояний (алфавит состояний), содержащее не менее двух элементов;
• Z={z₁,z₂, …, z_F} - множество входных сигналов (входной алфавит);
• W={w₁,w₂, …, w_G} - множество выходных сигналов (выходной алфавит);
• d : A´Z ®A - функция переходов, реализующая отображение пары "состояние - входной сигнал" в некоторое состояние автомата, т.е. d(a_m,z_f) = a_s, a_m,a_s Î A;
• l : A´Z ® W - функция выходов для автомата Мили, она ставит в соответствие паре "состояние автомата - входной сигнал" некоторый выходной сигнал, т.е. l(a_m,z_f) = w_g;
• l : A®W  функция выходов для автомата Мура, т.е. l(a_m)=w_f, w_f Î W;
• а₀ - начальное состояние автомата.

Рисунок 2 Абстрактный автомат

Абстрактный автомат, рис. 1, имеет  один вход и один выход. Автомат работает в дискретном времени, принимающем  целые неотрицательные значения t=0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата А, причем в начальный момент он всегда находится в состоянии а₀.  В момент времени t автомат воспринимает на входе букву входного алфавита z(t)ÎZ, находясь в состоянии a(t). В соответствии с функцией переходов автомат переходит в момент времени (t+1)  в состояние a(t+1)= d(a(t), z(t)) и вырабатывает выходной сигнал z(t)  в соответствии с функцией выходов: z(t)=l(a(t), z(t)) в случае автомата Мили, и z(t)=l(a(t)) в случае автомата Мура. Таким образом, автомат S отображает множество слов входного алфавита Z в множество слов выходного алфавита W. 

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

Автомат называется конечным, если конечны множества A,Z,W. Далее мы будем рассматривать только конечные автоматы. Автомат называется полностью определенным, если он определен всюду на множестве A´Z. В противном случае автомат называется частичным.

Чтобы задать автомат, необходимо  описать все компоненты вектора  S=(A,Z,W,d,l, a₀), т.е. входной и выходной алфавиты, алфавит состояний, функции переходов и выходов.  Для описания автомата наиболее часто используются табличный и графический способы задания. Наиболее удобны отмеченные таблицы переходов-выходов, Таблицы 17, 18.

 

 

Таблица 18 Отмеченная таблица переходов-выходов для автомата Мили

 

A Z	a0	a1	a2
z1	a1/w1	a0/w3	a2/w2
z2	a2/w2	a1/w1	a0/w1

Таблица 17 Таблица переходов-выходов для автомата Мура

A Z	a0	a1	a2
z1	a2	a0	a1
z2	a1	a2	a0
W	w1	w2	w3