Сделай Сам Свою Работу на 5

Структурный синтез автомата





Выберем в качестве структурной схемы распознающего автомата следующую схему:

Рис. 5. Структурная схема распознающего автомата

 

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

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

derr - сигнал функции ошибки; dok - сигнал функции принадлежности цепочки входных символов языку с грамматикой G’, (p1, p2, p3 - код входного символа); z(t-1) - код предыдущего состояния; z(t) - код нового состояния

С помощью сигнала НУ осуществляется начальная установка триггеров автомата.



Дешифратор преобразует двоичный код символов (p1,p2,p3) в унитарный код, в котором только одна из выходных переменных принимает значение 1, в то время как все другие равны 0.

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

Построить функцию переходов, значит найти переключательную функцию кодирующих (внутренних) переменных. Каждая внутренняя переменная кода (z1,z2,z3,z4 ) представляет собой состояние соответствующего элемента памяти, то есть триггера. По переключательным функциям внутренних переменных находятся функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата.

Рассмотрим часть общей комбинационной схемы автомата, реализующую функцию переходов по x0, x1, ..., x7.

Рис. 6. Общая комбинационная схема автомата

 

Рассмотрим построение логической схемы на примере для f(x0):

z(t)

xo f(xo) z(t+1)

Рис. 7. Общий вид схемы обработки сигнала х0



Пусть входной сигналxo обрабатывается автоматом в соответствии с функцией переходов следующим образом: r1 ® r2; r2 ® r11. Приведем таблицу кодировки (см. табл.8), чтобы на ее основе построить таблицу переходов автомата по символу xo.

Таблица 8

r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11

 

Cоставим таблицу переходов автомата по символу x0:

Таблица 9

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r1
r2

 

Запишем в соответствии с табл.9 функции z(t+1). Будем иметь:

 

z1(t+1) = z1(t); z2(t+1) = z3(t);

z3 (t+1) = z4(t+1) = z1(t);

 

Построим схему на элементах И-НЕ:

Рис. 8. Схема обработки входного сигнала х0

 

Аналогично составляются логические функции остальных zi (t+1)

и строятся соответствующие им комбинационные схемы fxi , а в итоге и вся схема : xi & z (t) ® z (t+1) , то есть схема таблицы переходов автомата. В случае, когда по таблице переходов сложно записать функцию zi(t+1), применяют построение карт Карно и минимизацию слабо определенных функций.

Cоставим таблицу переходов автомата по символу x1:

Таблица 10

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r3
r9

 

 

Запишем в соответствии с табл.10 функции z(t+1). Будем иметь:

z1 (t+1) = z3(t+1) = z1(t);

z2(t+1) = z2(t); z4 (t+1) =

Построим схему на элементах И-НЕ:

Рис. 9. Схема обработки входного сигнала х1



Cоставим таблицу переходов автомата по символу x2:

Таблица 11

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r6
r7

 

Запишем в соответствии с табл.11 функции z(t+1). Будем иметь:

z1 (t+1) = z2(t); z3(t+1) =

z2(t+1) = z2(t); z4 (t+1) = z4 (t);

Построим схему на элементах И-НЕ:

 

Рис. 10. Схема обработки входного сигнала х2

 

Cоставим таблицу переходов автомата по символу x3:

Таблица 12

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r11

Запишем в соответствии с табл.12 функции z(t+1). Будем иметь:

z1 (t+1) = z1(t); z3(t+1) = z1 (t);

z2(t+1) = z1(t); z4 (t+1) = z1 (t);

Построим схему на элементах И-НЕ:

Рис. 11. Схема обработки входного сигнала х3

Cоставим таблицу переходов автомата по символу x4:

Таблица 13

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r0
r1
r2
r3
r4
r5

 

Запишем в соответствии с табл.13 функции z(t+1). Будем иметь:

z1 (t+1) = ; z3(t+1) =

z2(t+1) = z4 (t+1) =

Построим схему на элементах И-НЕ:

 

Рис. 12. Схема обработки входного сигнала х4

 

Cоставим таблицу переходов автомата по символу x5:

Таблица 14

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r0
r8

 

Запишем в соответствии с табл.14 функции z(t+1). Будем иметь:

z1 (t+1) = z1(t); z3(t+1) =

z2(t+1) = z3(t); z4 (t+1) = z3 (t);

Построим схему на элементах И-НЕ:

Рис. 13. Схема обработки входного сигнала х5

 

Cоставим таблицу переходов автомата по символу x6:

Таблица 15

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r0
r3
r4

 

Запишем в соответствии с табл.15 функции z(t+1). Будем иметь:

z1 (t+1) = z3(t+1) = z1(t);

z2(t+1) = z4(t); z4 (t+1) = z4 (t);

Построим схему на элементах И-НЕ:

 

 

Рис. 14. Схема обработки входного сигнала х6

 

Cоставим таблицу переходов автомата по символу x7:

Таблица 16

ri t t+1
  z1 z2 z3 z4 z1 z2 z3 z4
r0
r10

 

Запишем в соответствии с табл.16 функции z(t+1). Будем иметь:

z1 (t+1) = z1(t); z3(t+1) = z2(t);

z2(t+1) = z2(t); z4 (t+1) =

Построим схему на элементах И-НЕ:

 

Рис. 15. Схема обработки входного сигнала х7

Функция возбуждения сигнала ошибки может быть представлена в виде:

derr = x0 & derrx0 Ú x1 & derr x1 Ú ... Ú x7 & derr x7.

 

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


Таблица 17

  r derr x0 derr x1 derr x2 derr x3 derr x4 derr x5 derr x6 derr x7

 

Анализ табл. 17 показывает, что в ней больше нулей, чем едениц. Поэтому удобно строить логическую функцию для . Для каждой функции проводим минимизацию слабо определенной функции. Затем берется отрицание полученной в ходе минимизации функции. Запишем функции ошибок при обработке x0, x1 и т.д.:

Для x0:

(z1 z2 z3 z4) v (z1 z2 z3 z4) = (z4 z1 z3) & (z2 v z2) = z4 z1 z3

 

Для x1:

(z1 z2 z3 z4) v (z1 z2 z3 z4) = (z1 z2 z4) & (z3 v z3) = z1 z2 z4

Для x2:

(z1 z2 z3 z4) v (z1 z2 z3 z4)

Для x3:

Для x4 проведём минимизацию при помощи карты Карно:

(z1 z4) v (z1 z4) v (z4 z2 z3 z1) = z4 (z1 v z1) v (z4 z1 z2z3) = z4 v (z1 z2 z3 z4)

 

Для x5:

(z1 z2 z3 z4) v (z1 z2 z3 z4)

Для x6 проведём минимизацию при помощи карты Карно:

(z3 z2) v (z3 z4 z1) = z3 (z2 v z4 z1)

Для x7:

(z1 z2 z3 z4) v (z1 z2 z3 z4)

 

Функцию ошибки можно представить формулой вида

=

 

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

Сигнал dok=1 вырабатывается только тогда, когда на вход автомата пришел сигнал «конец цепочки», в рассматриваемой задаче x3, а автомат находился в заключительном состоянии, то есть

Очевидно, при этом derr = 1.

Комбинационная схема функции dok строится аналогично рассмотренным выше построениям.

 

 

Литература

1. Льюис Ф., Розенкранц Д., Стинз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979. -654 с.

2. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. - М. : Наука, 1980. - 400 с.

3. Герасимов И. В. Построение цифровых устройств в автома-

тике и вычислительной технике на современной элементной базе: Учеб. пособие / ЛЭТИ. - Л., 1984. - 49 с.

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

5.Синтез распознающего автомата: Методические указания к курсовой

работе .-Новочеркасск: Изд-во НПИ, 1987. - 32 с.

6. Прохорова О.В. Синтез конечных автоматов. Йошкар-Ола: МарГТУ, 2000. – 24с.

 

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.