Синтез конечного распознающего автомата

Таблица 9

В графе «Код состояния» таблицы представлены все возможные наборы значений внутренних переменных z₁,z₂,z₃,z₄ в порядке возрастания их двоичных эквивалентов. В графе «Символ состояния» эти наборы помечаются условными обозначениями (r₀?r₁₁) в соответствии с выбранным вариантом размещения состояний автомата (рис.12). Четыре набора, которые не соответствуют никаким состояниям автомата, помечены звездочками.

Принцип составления функций возбуждения заключается в следующем. Рассмотрим заполнение, например, строки r₀ (табл.9). Из состояния r₀ (код 0111) возможны три перехода: в состоянии r₁ (код 0101) при поступлении на вход символа x₅, в состоянии r₄ (код 0000) при воздействии x₇ и в состояние r₆ (код 1111) при воздействии x₃. В первом переходе (0111 - 0101) изменяет свое значение внутренняя переменная z₂ из 1 в 0, поэтому в столбце D₂ должен быть записан символx₅. Во втором переходе (0111 - 0000) изменяют свои значения сразу три переменных z₁, z₂, z₃, причем из 1 в 0, значит, в столбцах D₁, D₂, и D₃ должны быть записаны символыx₇. Но так как в столбце D₂ уже записан символx₅, а изменение z₂ в обоих случаях происходит из 1 в 0, то в столбце D₂ должно быть записано выражение . Последнее означает, что переход из 1 в 0 переменной z₂ происходит при поступлении на вход схемы символа x₂ или символа x₃. Наконец в третьем переходе (0111-1111) при поступлении символа x₃ изменяется только переменная z₄ из 0 в 1, поэтому в столбце D₄ записывается символ x₃.

Аналогично заполняются остальные строки в таблице, причем при отсутствии изменений любой из переменных z₁,z₂,z₃,z₄, в каком либо состоянии в соответствующий столбец D_i записывается значение переменой z_i, определяемое данным состоянием. Значение D_i в четырех строках, отмеченных звездочками, могут быть заданы произвольно.

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

Для нахождения минимальной ДНФ функции возбуждения удобно воспользоваться ее геометрическим представлением на вершинах 4-мерного куба, которое для функции Д₁ представлено на рис.15. На этом рисунке вершины, в которых значение функции равно 1, помечены зачерненными кружками, вершины, на которых значение функции равно 0, не имеют отметки, вершины, на которых функция не определена, помечены звездочками. Вершины, помеченные входными переменными или логическими выражениями из них, обозначаются полузачеркнутыми кружками. Этим отражается тот факт, что в этой вершине значение функции равно 1, если соответствующая переменная (или выражение) равна 1 и 0 в противном случае. Причем инверсные и неинверсные значения переменных помечаются противоположным полузачеркиванием кружка (рис.15). При выполнении минимизации сначала выписываются импликанты (коньюкции), покрывающие зачерненные вершины (и, возможно, некоторые вершины, помеченные звездочками).

Рис.15. Геометрическое представление функции D₁

После этого можно считать, что остальная часть функций задана на этих вершинах произвольно.

На рис.15 для функции D₁ мы имеем одну зачерненную вершину с координатой 1001 (иначе, доопределив функцию D₁) запишем импликанту, покрывающую эту вершину. Она будет иметь вид z₂, z₄, так как эти переменные однозначно определяют данные вершины, (переменные z₂ и z₄ не меняют своих значений на этих вершинах, соответственно z₁ и z₃ меняют значения).

После этого выписываются импликанты, каждая из которых накрывает одинаково отмеченные полузачеркнутые вершины и возможно большое число вершин с произвольным заданием функции или зачерненных (значение функции равно 1). Это позволяет покрыть функцию наименьшим числом импликант минимального ранга (т.е. содержащих минимальное число переменных). Начинается такая импликанта с входной переменной или логического выражения из входных переменных, соответствующих данной вершине.

Например, для вершиныx₅ (координата 1011) наилучшим будет покрытие: вершинаx₅ (1011), зачерненная вершина (1001). Тогда импликанта будет иметь вид: x₅ z₁z₃ z₄. В то же время, для вершинx₁ (0101 и 0001) наилучшим будет покрытие с вершинами, x₁ (0101 и 0001), вершиной помеченной звездочкой (1101), и зачерненной вершиной (1001), а импликанта будет иметь вид:x₁ z₁z₂. Проделав аналогичные операции для остальных вершин, получим минимальную ДНФ функции D₁:

Упрощая выражение, окончательно получим минимальную ДНФ:

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

Рис.16. Геометрическое представление функции D₂

Рис.17. Геометрическое представление функции D₃

Рис.18. Геометрическое представление функции D₄

По геометрическим представлениям функций (рис.16;рис.17;рис.18), получим минимальную ДНФ функции D₂ D₃ D₄

Упрощая выражение, окончательно получим минимальную ДНФ:

Теперь рассмотрим переключательные функции z₅ и z₆, представляющие выходные сигналы автомата. Сигнал z₆, свидетельствующий о принадлежности цепочки входных символов языку с грамматикой G“, принимает значение 1, если автомат находится в заключительном состоянии (в нашем случае r₁₁) и на его вход поступает сигнал признака конца цепочки символов x₈=1, в противном случае z₆=0. Следовательно,

z₆= x₈z₁ z₂z₃z₄.

Функция сигнала ошибки z₅ может быть построена точно так же, как функции D₁?D₄, но для уменьшения сложности ее реализации можно воспользоваться следующим условием.

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

, где

С целью исключения возможного влияния функциональных состязаний и фиксации ошибки до момента принятия решения сигнал z₅ удобно представить состоянием триггера, стробируемого синхросигналом t₂. В качестве триггера, реализующего сигнал z₅, может быть выбран любой тип триггера, в том числе и RS-триггер. Сигнал z₆ тоже необходимо стробировать, но синхросигналом t₁. При этом необязательно представлять этот сигнал состоянием триггера.

Примечание. При условии, если минимальная ДНФ функции возбуждения для прямого значения имеет высокую сложность, можно найти минимальную ДНФ для инверсии функции возбуждения и оценить ее сложность.

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

Так, рассмотрим прямую и инверсную функции возбуждения для информационного входа D₁. Геометрическое представление для D₁. дано на рис.15. Функция возбуждения D₁. будет иметь вид

Сложность функции - 23.

Для получения функции возбуждения D₁ проинвертируем значения на помеченных вершинах, а непомеченные вершины будем рассматривать как единицы функции.

Сложность функции - 24. Необходимо реализовать функцию D₁.

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

Сложность функции D₂ - 12, D₂ - 15. Необходимо реализовать функцию D₂.

Сложность функции D₃ - 16, D₃ - 18. Необходимо реализовать функцию D₃.

Сложность функции D₄-7, D₄-8.Необходимо реализовать функцию D₄.

РЕАЛИЗАЦИЯ АВТОМАТА

Реализация автомата выполнена на интегральных микросхемах малой степени интеграции. Каждая серия микросхем имеет определенный набор микросхем различного функционального назначения. Совокупность этих микросхем называется функциональным рядом.

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

Наибольшее распространение получили микросхемы серий КР555 и КР1533, выполненные по технологии ТТЛШ (транзистор-транзисторная логика с диодами Шоттки), а также серий К561 или КР1561, выполненных по технологии КМДМ (на основе комплементарных полевых транзисторов типа металл-диэлектрик-полупроводник).

Несмотря на различие параметров, схема автомата будет мало завесить от типа микросхем, поэтому выберем для применения в реализации автомата интегральные микросхемы серии КР555. Рекомендуемый набор микросхем приведен на рис.19.

Другие элементы, реализующие более сложные функции, приведены на рис.20. и рис.21. Здесь же приводятся таблицы состояний. Так, микросхема КР555ЛП5 реализует функцию «исключающее ИЛИ», а выходной сигнал соответствует логическому уравнению Q=AB=AB +BA, где - символ суммирования по модулю 2.

Микросхема КР555ИД4 - два дешифратора-демультиплексора. Она может выполнять функции двойного дешифратора с 2 на 4; двойного демультиплексора на 4; дешифратора с 3 на 8; демультиплексора 1 на 8. В частности, дешифратор (рис.14) может быть реализован на этой микросхеме.

Микросхема имеет два адресных входа A₀ и A₁, они служат для одновременного управления выходными состояниями DC_A и DC_B. В каждом дешифраторе имеется отдельный стробирующий входE_A иE_B, а также по одному информационномуE_A иE_B (инверсный).

Для дешифрации трехразрядного кода следует соединитьE_A иE_B,E_A и E_B.

Логические элементы

Рис.19

Рис.20

Рис.21

Таблица 10

В качестве элементов памяти выбраны триггеры D-типа. Поэтому рекомендуется использовать микросхему КР555ТМ8, содержащую четыре триггера D-типа. Структура микросхемы ТМ8 представлена на рис.22.

Рис.22

Таблица 11

Используя приведенные микросхемы, реализуем часть комбинационной схемы рассматриваемого примера для полученной в предыдущем разделе функции возбуждения D₁.

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

Реализация дешифратора входных сигналов, помимо приведенной на рис.21, может быть выполнена на микросхеме КР555ИД4. Реализация функции возбужденияS₅ RS-триггера сигнала «Ошибка» (z₅ ) может быть выполнена с использованием микросхемы КР555ЛП5.

Сигнал начальной установки НУ реализуется путем подачи на входы D триггеров вспомогательного регистра сигналов, соответствующих выбранному начальному состоянию (в рассматриваемом примере это r₀=0111, что соответствует D₁=1, D₂=1, D₃=1, D₄=0). Эти сигналы объединяются логическим «ИЛИ» с функциями возбуждения D₁,D₂,D₃,D₄. Сигналом НУ триггеры основного регистра устанавливаются в состояние 0000. Синхросигналами t₁ и t₂, подаваемыми на вход С, оба регистра устанавливаются в начальное состояние. Если начальное состояние имеет код 0000, установка может производиться путем подачи сигнала начальной установки на входR триггеров вспомогательного и основного регистров.

Реализация формирования сигнала начальной установки для триггера 1 регистра 1 рассматриваемого примера приводится на рис.15.

Рис.23

Начальная установка автомата осуществляется сигналом НУ=1 каждый раз перед подачей на вход автомата первого символа очередной распознаваемой цепочки. При этом длительность сигнала начальной установки должна быть такой, чтобы синхросигнал t₁ поступал во время действия сигнала НУ. Так как триггеры основного регистра установлены в состоянии 0, и следовательно для установки 4-го триггера вспомогательного регистра в состояние 0 нет необходимости использования объединения D₄ и НУ по «ИЛИ».

В заключение дипломной работы выполнен чертеж принципиальной схемы. При составлении принципиальной схемы руководство осуществлялось по следующим правилам:

§ элементы не могут иметь незадействованные входы, они либо соединяются с задействованными, либо на них подаются константы;

§ подача на вход элемента константы 0 осуществляется соединением этого входа с общим проводом, подача константы 1 - соединением этого входа с выходом инвертора, вход которого соединен с общим проводом;

§ объединение входов одного элемента не увеличивает нагрузку на выход элемента, соединенного с этими входами;

§ максимальная нагрузочная способность выхода элемента для микросхем серии КР555 и КР1533 равна 20, для серий КР561 и КР1561 равна 100, что означает невозможность соединения его более чем с 20 (или 100) входами различных элементов.

ЗАКЛЮЧЕНИЕ

распознающий автомат интегральная микросхема

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

Была синтезирована комбинационная схема распознающего конечного автомата и начерчена его принципиальная схема с использованием библиотеки интегральных микросхем.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / Под. ред. В. И. Варшавского. - М.: Наука, 2006. - 400 с.

2. Крючкова Е.Н. Теория формальных языков и автоматов. - Барнаул; 2008

3. Рейуорд - Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Мир, 2008

4. Саломаа А. Жемчужины теории формальных языков. - М.: Мир, 1987.

5. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах под.ред. В.И.Варшавского. - М.Науки, 2006 - 400с.

6. Донован, Дж. Системное программирование/Дж. Донован. - М.Мир, 1975 - 540с.

7. Поспелов, Д.А. Логические методы анализа и синтеза схем/Д.А. Поспелов. - М.: Энергия, 1974. - 368с.

8. Шило, В.Л. Популярные мировые микросхемы: //Справочник/ В.Л. Шило. - М.: Радио и связь 2009. - 352с.

9. Цифровые интегральные микросхемы: //Справочник/ М.И. Богданович, И.Н. Грель, В.А.Прохоренко, В.В. Шалимо. - Минск: Беларусь, 1991. - 493с.

10. Горбунов, А.Н. Синтез конечного распознающего автомата:// Методические указания к выполнению дипломной работы/А.Н. Горбунов. - Брянск, 2004г.-20с.

Размещено на Allbest.ru