При преобразовании ЛСА в ГСА каждому оператору в ЛСА ставится в соответствие операторная вершина и каждому логическому условию (кроме тождественно ложного оператора) условная вершина ГСА.

Рисунок 1.1 - Начальная вершина ГСА Рисунок 1.3 - Операторная вершина ГСА

Рисунок 1.2 - Конечная вершина ГСА Рисунок 1.4 - Условная вершина ГСА

На первом этапе осуществляется построение отдельных фрагментов ГСА, число которых зависит от количества символов в ГСА и равно +1. Начальный фрагмент ГСА содержит операторные и условные вершины, соответствующие всем операторам и логическим условиям, которые записаны в ЛСА перед первым символом . При этом все вершины соединены последовательно в том порядке, в каком записаны в ЛСА соответствующие им символы. Выход любой условной вершины хi соединенный со следующей вершиной, отмечается символом “1”, второй выход этой вершины отмечается символом «0» и помечается номером, соответствующим номеру верхней стрелки, которая расположена в ЛСА непосредственно за логическим условием хi. Если между парой символов ЛСА имеется нижняя стрелка с номером i, то на фрагменте ГСА к линии, соединяющей две вершины, которые соответствуют этой паре символов, подводится входящая стрелка с этим же номером. Из последней вершины фрагмента выводится стрелка с номером, соответствующим номеру верхней стрелки, которая стоит непосредственно за символом .

Каждый последующий фрагмент ГСА содержит операторные и условные вершины, соответствующие всем операторам и логическим условиям в ЛСА, которые записаны между двумя последовательными символами или за последним символом для конечного фрагмента. Данные фрагменты строятся в основном по тем же правилам, что и начальный фрагмент. Дополнительные требования заключаются в следующем: к начальной вершине каждого фрагмента подводится входящая стрелка с номером, соответствующим номеру нижней стрелки, стоящей в ЛСА непосредственно перед символом этой вершины; из последней вершины конечного фрагмента стрелка не выводится.

На втором этапе построения ГСА все одноименные входящие и исходящие стрелки фрагментов соединяются, в результате чего получается искомая ГСА. В результате изучения описанной выше (рис. 1.1 - 1.4) методики преобразования ЛСА в ГСА, в данной работе была получена искомая ГСА (приложение А).

2. Разработка УА с жёсткой логикой

По ЛСА строим таблицу переходов автомата Мура. Для этого нужно выполнить следующее:

1) Пронумеровать все операторы ЛСА (см. формулу 1).

2) Каждому оператору ЛСА поставить в соответствие определённое состояние автомата. Одинаковым операторам, стоящим в разных местах ЛСА, должны соответствовать разные состояния. Начальной вершине будет соответствовать исходное состояние автомата. Если в ЛСА имеются циклы из логических условий, то в цепь обратной связи вводится пустая операторная вершина, отмеченная пустым выходным сигналом ye .

3) Осуществляется просмотр всех путей перехода, ведущих от одного оператора к другому. Каждый такой путь должен соответствовать шагу алгоритма и состоять только из логических условий.

4) Каждому пути из логических условий от одного оператора к другому сопоставить конъюнкцию входных сигналов.

5) Построить таблицу переходов автомата Мили, анализируя все полученные пути между операторными вершинами и учитывая, что каждая операторная вершина отмечена совокупностью выходных сигналов.

Строим таблицу переходов автомата Мура, в которой каждая строка таблицы соответствует одному пути перехода из состояния ai(t) в состояние ai(t+1).

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

2.1.1 Абстрактный синтез автомата Мили

Полученную ранее таблицу переходов автомата Мура (см. таблицу 2.1) можно рассматривать и для синтеза эквивалентного ему автомата Мили. При этом в таблице 2.1 необходимо исключить третий столбец (Уi(t)) и скорректировать последний (Yij(t)), учитывая способ получения выходного сигнала автомата Мили. Получаем таблицу переходов автомата Мили (таблица 2.3).

Найдем эквивалентное разбиение состояний автомата Мили. Для автомата Мили отыскиваются 1-эквивалентные состояния, то есть состояния, при переходе из которых под действием одного и того же входного сигнала формируются одинаковые выходные сигналы.

Для нашего примера имеются четыре класса 1-эквивалентных состояний:

Теперь выполним минимизацию таблицы переходов на основе эквивалентного разбиения состояний.

Эквивалентным разбиением состояний называется k-эквивалентное разбиение их, когда в каждом из классов этого разбиения смежные состояния эквивалентны. Такое разбиение может быть получено, если последовательно получать k-эквивалентное разбиение состояний, начиная с k = 1, для автомата Мили.

K-эквивалентное состояние получают до тех пор, пока первый раз не получится разбиение, которое полностью совпадает с предыдущим. Это разбиение состояний и будет эквивалентным разбиением. Полученное эквивалентное разбиение состояний автомата Мура удобно рассматривать на примере ПТП, в которой все состояния, как исходные, так и состояния перехода, отмечены выходными сигналами.

Такое представление ПТП позволит рассмотреть её как для минимизации автомата Мура, так и для минимизации автомата Мили.

На основании вышеизложенного получаем таблицу пар автомата Мили (Таблица 2.2)

Для определения минимальной таблицы переходов автомата Мили каждый класс эквивалентного разбиения состояний обозначим произвольно своим символом:

(S0,S1) = a1 ; (S4S8) = a4 ; (S7) = a7 ; (S10) = a9 ; (S2) = a2 ; (S5) = a5 ; (S11) = a10 ; (S14) = a12 ;

(S3) = a3 ; (S6 S13) = a6 ; (S9) = a8 ; (S12) = a11 ;

После подстановки введённых обозначений в исходную таблицу переходов и вычёркивания повторяющихся строк получаем минимальную таблицу переходов автомата Мили (таблица 2.3).

Таблица 2.3 - Минимальная таблица переходов автомата Мили

На этапе структурного синтеза строится логическая схема полученного ранее автомата Мили. Для этого используется канонический метод структурного синтеза автоматов, предложенный академиком Глушковым В.М. Этот метод позволяет свести задачу синтеза схемы автомата к задаче синтеза комбинационной схемы (КС). При этом предлагается представление схемы автомата в виде памяти и КС в соответствии с рисунком 2.1.

Рисунок 2.1 - Структура УА с жёсткой логикой

Память автомата состоит из I элементарных автоматов памяти - триггеров, которые служат для отображения состояния автомата. Каждое состояние am (m=1,2,…,M) кодируется двоичным набором Q1,Q2…QI , компонентами которого являются состояния триггеров T1,T2 … TI . Двоичный набор Q1,Q2…QI называется кодом состояния автомата.

При использовании различных методов кодирования состояний автомата количество триггеров, необходимых для представления M состояний автомата, равно:

] log2 M [ ? I ? M.

Если I = ] log2 M [ , то состояния автомата кодируются кодом минимальной длины. При I = M состояния автомата представляются в унитарном коде, имеющем максимальную длину. Каждому состоянию автомата ставиться в соответствие код, отличный от кодов всех других состояний.

Дешифратор состояний используется для выделения состояний автомата путём дешифрирования его кода Q1,Q2 …QI , то есть для преобразования кода элементов памяти в унитарный код состояний. Дешифратор состояний позволяет уменьшить трудоёмкость синтеза схем автомата, так как при его использовании не требуется минимизация схем.

КС1 - комбинационная схема формирования сигналов возбуждения памяти, реализует функцию переходов автомата вида

ai(t+1) = fn(x1,x2,…,xL,a1,aI,…, aM), i = 1,M.

КС2 - комбинационная схема формирования выходных сигналов, реализует функцию выходов автомата.

Для модели Мили

yn = fn(x1,x2,…,xL,a1,aI,…, aM), n = 1,N.

При включении устройства триггеры УА устанавливаются в произвольное состояние. Для приведения автомата в исходное состояние используется сигнал “Начальная установка”.

Канонический метод структурного синтеза условно можно разбить на следующие этапы:

1. Выбор типа логических элементов и элементов памяти.

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

3. Построение булевых функций возбуждения памяти и функций выходов.

4. Построение функциональной схемы автомата.

Этап 1. Тип элементов памяти (D - триггер) выбран согласно заданию. Для реализации КС используем элементы серии К555.

Этап 2. Определяем число элементов памяти при условии кодирования состояний автомата кодами минимальной длины.

I = ] log2 M [ = ] log2 12 [ = 4 ;

Q1Q2Q3Q4 - код состояний автомата;

При построении памяти на D-триггерах можно минимизировать число переключений элементов памяти и тем самым уменьшить сложность комбинационной схемы функций возбуждения КС1. Для этого состояния, в которые автомат переключается чаще, чем в другие, необходимо закодировать кодами с минимальным числом единиц. Результаты кодирования состояний автомата поместим в карту Карно:

Q3Q4

Q1Q2 00 01 11 10

00

01

11

10

Используя результаты кодирования состояний автомата, строим структурную таблицу переходов автомата Мили. Для этого дополняем таблицу переходов (таблица 2.2) кодами состояний автомата (3-й и 6-й столбцы) и, используя таблицу переходов D - триггера, заполняем 7 - й столбец таблицы 2.3

Таблица 2.4 - Структурная таблица переходов автомата Мили

Этап 3. По таблице 2.4 строится СКУ функций возбуждения памяти. СВФ была получена на этапе абстрактного синтеза.

D1 = a2x2x3 v a3x3x7 v a4 v a5 v a8x5 v a8x7 v a10x7;

D2 = a1x1 v a2 x2 x3x6 v a3x3x7 v a4 v a5 v a6 v a7 x4 v a8 x5 v a8 x7 v a10 x7;

D3 = a1x1 v a2 x2 v a2x3 v a3x3 v a5 v a6 v a7x4 ;

D4 = a1x1 v a2 x2 v a2x3 v a7x4 v a8x5 v a9 v a11;

Так как в нашей курсовой работе СКУ и СВФ будут реализованы в базисе И-НЕ на элементах серии К-555, их необходимо преобразовать и упростить. В данном случае будут использованы законы алгебры - логики (законы де - Моргана, законы поглощения и т.д.).

Этап 4. Электрическая функциональная схема УА Мили строится в соответствии с рисунком 2.1 с использованием СКУ функций возбуждения памяти и СВФ.(Приложение Б)

Также стоит отметить, что в нашем УА возникают гонки, так как при переходе из одного состояния в другое сразу несколько элементов памяти изменяют своё состояние. Чтобы устранить нежелательные последствия гонок (переход автомата в состояние, не предусмотренное законом функционирования) воспользуемся способом импульсной синхронизации. Он заключается в том, что гонки устраняются путём ограничения длительности сигнала C, поступающего в цепь синхронизации.

3. УА с программируемой логикой