Автоматная полнота и теорема В.М.Глушкова

В структурном автомате входные и выходные переменные представляются не в абстрактном виде через символы алфавита, а в виде наборов значений сигналов на входных и выходных полюсах автомата. Как правило, эти сигналы принимают двоичные значения, обозначаемые как 0 и 1. Автомат имеет вид, показанный на рис.2.1.

Состоянию автомата сопоставляется совокупное состояние автоматов, называемых элементами памяти. Каждый из таких автоматов может находиться в одном из двух состояний, обозначаемые  как 1 и 0. Тогда каждому состоянию автомата будет сопоставлен двоичный вектор состояний элементов памяти, и это сопоставление называют кодированием состояний.

Таким образом, структурный автомат представляется в виде композиции комбинационной (логической) схемы и элементов памяти, связанных со схемой, как показано на рис. 2.2. Входными переменными схемы являются входные переменные автомата - сигналы x1,x2, …,xn, и переменные t1, n2,…,tk, определяющие текущее состояние автомата, выходные переменные реализуются на выходах y1, y2,…, ym. Выходы схемы v1, v2,…,vk определяют переход автомата в следующее состояние.

Все переменные, приведенные на рис. 2.2, – двоичные, то есть принимают значение из множества {0,1}.

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

 

Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …,xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор. Чтобы это можно было сделать, число n должно быть таким, чтобы выполнялось условие N£2ⁿ, где N  – число символов входного алфавита.

Точно также, кодировка M символов выходного алфавита требует, чтобы число m обеспечивало равенство M£2^m, а кодировка K символов алфавита состояний была связана с числом k равенством K£2^k.

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

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

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

2) иметь возможность перевести элемент памяти из любого состояния в любое другое с помощью одного входного сигнала. Это значит, что в его таблице переходов в каждом столбце должны присутствовать все состояния. Говорят, что такие автоматы имеют полноту переходов.

Сформулируем всё сказанное в виде теоремы, определяющей, какие свойства должны быть у множества элементов, чтобы из них можно было построить любой автомат. В теореме нетривиальным назван автомат, имеющий более одного состояния. Функциональная полнота необходима для того, чтобы можно было построить схему, реализующую любые заданные функции (см. рис.2.2).

Теорема об автоматной полноте В.М.Глушкова.

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

Простейшими автоматами Мура, обладающими полнотой выходов и переходов, являются автоматы, представленные в табл.1 и табл.2. Они имеют два состояния,  обозначенные как 0 и 1, два входных сигнала – z1 и z2.  Выходные сигналы совпадают с состояниями и обозначаются так же, как 0 и 1.

 

Таблица 2.1				Таблица 2.2
	0	1			0	1
z1	0	0		z1	0	1
z2	1	1		z2	1	0

 

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

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

В счётном триггере при поступлении входного сигнала, равного нулю, элемент остаётся в том же состоянии, что и был. При единичном сигнале состояние элемента меняется с 0 на 1 и с 1 на 0.

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

 

Гонки в автомате

 

Кодирование состояний

Задача кодирования состояний является одной из первых задач канонического метода структурного синтеза автоматов. Напомним, что кодирование заключается в установлении взаимно однозначного соответствия между множеством А = {а₁,…,а_N} состояний автомата и множеством r-компонентных векторов {К₁,…, К_m), К_m= (е_m1,…,e_mr}, где е_mr - состояние r-го элемента памяти,  r = 1,…,m.

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния а_r с кодом 0101 в состояние а_S  с кодом 1001, то это означает, что триггер Т₁  переходит из состояния 0 в состояние 1, триггер Т₂ - из состояния 1 в состояние 0, а состояние триггеров Т₃, и Т₄ не изменяется.

 

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

Поделиться: