Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Ответы на экзаменационные билеты по теории автоматов - файл 1.doc


Ответы на экзаменационные билеты по теории автоматов
скачать (353 kb.)

Доступные файлы (1):

1.doc353kb.29.11.2011 18:47скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
1. Классификация автоматов. Одноблочные и многоблочные автоматы.

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

Все цифровые автоматы классифицируются по ряду признаков:

1) По закону функционирования цифрового автомата. (Автомат подразделяется на 2 класса – 1рода и 2 рода (Мили и Мура) отличительной особенностью которых является зависимость от входных сигналов.)

2) По конечности множеств входных и выходных сигналов, а так же множеств состояний. Они подразделены на конечные автоматы и бесконечные автоматы.

3) По объёму памяти (с памятью – последовательные и без памяти – лог. схемы)

4) По степени раскрытия структуры (Абстрактные и структурные)

5) По отношению между автоматами (Подавтомат и надавтомат)

6) По полноте используемых переходов из одного состояния в другое (Полностью и частично определённые).

7) По стабильности следования выходных сигналов (Синхронные асинхронные).

^ Одноблочные автоматы

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

Многоблочные автоматы

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

Так как микропроцессорный автомат имеют стандартную архитектуру, применяя которую с небольшими изменениями для различных проектов, можно существенно облегчить проектирование специализированных ИС и в несколько раз уменьшить время от начала разработки до выхода конечного продукта. Весь процесс разработки в таком случае включает в себя следующие этапы:

  • описание (на уровне блоков) алгоритма;

  • создание необходимой системы команд;

  • подключение к микропрограммному автомату необходимых библиотек;

  • написание микропрограммы;

  • отладка микропрограммы.


^ 3. Структурные автоматы. Представление структурных автоматов.

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

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

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

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

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

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

Крупные вычислительные системы строятся по многоблочной распределённой схеме.
^ 4. Структуры построения многоблочных автоматов.

Многоблочные автоматы это автоматы, в которых управляющий автомат управляет блоками объектов управления, грубо говоря, объект управления не один.

Существует несколько распространённых структур построения таких автоматов:

  • Структура управления многоблочного объекта управления



  • Структурная схема с Функциональными блоками



  • Многоблочная структурная схема с концентрированными управляющими связями



  • Многоблочные иерархические цифровые автоматы


^ 5. Определение абстрактного автомата. Алфавиты входа, выхода,

состояний. Функции выходов и переходов.

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

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

Под алфавитом в теории автоматов понимают непустое множество различных символов.

Элементом алфавита являются буквы, а упорядоченные буквы называются словом.

Абстрактный автомат представляется в виде чёрного ящика со входными и выходными алфавитами. Математическая модель цифрового автомата определяется 6ти компонентной функцией. А={x,y,S,б,-\,So} где х – входной алфавит, у- алфавит выходных сигналов, S- множество состояний автомата. б – функция перехода и -\ - функция выхода.

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


6. Способы задания автоматов. Таблицы и матрицы переходов и выходов. Объединенная таблица. Графы автоматов.

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

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

Автоматные языки позволяют установить однозначную взаимосвязь между состояниями автомата, входными и выходными сигналами.

Способы описания цифровых автоматов подразделяются на:

  1. Начальные языки

  • ЛСА – Логическая Схема Алгоритма

  • ГСА – Графическая Схема Алгоритма

  • МСА – Матричная Схема Алгоритма

  • ФМП – Функциональная МикроПрограмма

  • СФП – Система Формул Перехода

  1. Автоматные языки

  • ТП – Таблица Переходов

  • ТВ – Таблица Выходов

  • СТПиВ – Совместная Таблица Переходов и Выходов

  • МП – Матрица Переходов

  • МВ – Матрица Выходов

  • СМПиВ – Совместная Матрица Переходов и Выходов

ЛСА устанавливает логическую последовательность между событием и условием, ГСА делает тоже самое, только блок-схемой. МСА устанавливает взаимосвязь между событиями и условиями в виде матрицы. ФМП описывает последовательность действий в виде команд. СФП делает тоже самое, только сразу описывает действия.

Автоматные языки имеют три формы записи:

  • Табличная – форма представлена в виде таблицы, где столбцы обозначаются состояниями автомата, а строки – входными сигналами. На пересечении строк и столбцов устанавливаются состояния автоматов или выходные сигналы.

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

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


^ 7. Автомат Мура. Закон функционирования автомата Мура.

Автомат Мура отличается от автомата Мили законом функционирования цифровых автоматов. Выходной сигнал автомата Мура зависит от состояния в которое перейдёт автомат, и непосредственно не зависит от входного сигнала.

Автомат Мура, как и любой другой цифровой автомат, задаётся своими таблицами перехода и выхода.

Закон функционирования автомата Мура S(t)=б(S(t-1);x(t)) Y(t)= -\(S(t))

По закону функционирования автомат Мура определяется как автомат второго рода.

В исходном состоянии триггер находится в состоянии 0 на единичном входе и сигналом 0 на инверсном выходе.

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

Нетрудно видеть, что выходной сигнал автомата Мура не зависит от входного сигнала.

^ 8. Автомат Мили. Закон функционирования автомата Мили.

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

Автомат Мили, как и любой другой цифровой автомат, задаётся своими таблицами перехода и выхода.

Закон функционирования автомата Мили: S(t)=б(S(t-1);x(t)) Y(t)= -\(S(t-1);x(t))

По закону функционирования автомат Мура определяется как автомат первого рода.

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

На первый вход схемы подаётся 0 с прямого выхода. На второй вход – 1 с инверсного.

При поступлении сигнала 1 на &2 появляется импульс, который и будет выходным сигналом на y2. На выходе схемы &1, а соответственно и на у2 сигнал будет отсутствовать. Импульс через линию задержки D поступает на первый вход и переводит его в состояние 1. На второй вход подаётся 0. Теперь на &1 поступает 1 и так же появляется импульс, являющийся выходным на у1, а на &2 поступает 0 и = > ничего там нет. После этого импульс с у1 переводит входной сигнал на втором входе и ситуация повторяется.
^ 9. Теорема эквивалентности. Эквивалентность автоматов Мили и Мура.

Два автомата Sa и Sb с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.

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

Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура.

Пусть дан конечный автомат Мили S(t)1={x1,y1,S1,б1,-\1} имеющий множество состояний S, множество входных и выходных сигналов x1 и y1, а так же функции переходов и выходов б1 и -\1. Требуется построить эквивалентный ему автомат Мура S(t)2={x2,y2,S2,б2,-\2} у которого x2=x1, y2=y1. Т.к множества входных и выходных сигналов у эквивалентных автоматов должны совпадать.

Для определения множества состояний S2 автомата Мура образуем всевозможные пары вида (Sn,yn). Если такие пары возможно образовать для всех вершин, то получим множество пар, которое является множеством состояний автомата Мура. S2={(S0,y1),(S0,y2),… (Sn,yk)}.

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

Y=-\2[(Si,yj)]=-\2[bi]. Таким же образом определяется функция переходов.

В итоге автомат Мили будет иметь два состояния, а автомат Мура – три. ( (Si,yf) (Si,yr) (Si,yp) )

Если автомат Мили был в некотором состоянии Si и пришёл входной сигнал xj, то должен выработаться выходной сигнал yp. Поэтому в автомате Мура из состояний (Si,yf) (Si,yr) при поступлении входного сигнала xj будет переход в состояние (Si,yp). В качестве начального состояния можно взять любое состояние из множества состояний.
^ 10. Частично-определенные автоматы. Таблицы перехода и выхода частично-определенного автомата.

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

При неполном определении различают допустимые и недопустимые входные слова.

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

Недопустимые состояния исключают на этапе задания цифрового автомата.

Не полностью определённый автомат задаётся таблицами перехода и выхода и совмещенной таблицей.
^ 11. Минимизация автоматов. Минимизация полностью определенного автомата.

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

По степени совместимости состояния подразделяются на:

1) Абсолютно несовместимые – состояния, которые на выходе автомата имеют разные выходные сигналы.

2) Абсолютно совместимые – состояния, имеющие одинаковые выходные сигналы и равные функции перехода.

3) Условно совместимые – состояния, совместимые при условии равенства функция выхода и эквивалентности функций перехода.

Треугольная матрица заполняется в 3 этапа:

1 этап: На первом этапе мы определяем абсолютно несовместимые состояния, попарно сравнивая столбцы в таблице выходов. Если значение не равно значению , то ставим «X» в соответствующей ячейке.

2 этап: На втором этапе мы определяем абсолютно-совместимые состояния, попарно сравнивая столбцы в таблице переходов, пропуская те пары, что мы определили как абсолютно несовместимые. Если состояния одинаковы при одинаковых сигналах, то ставим «V» в соответствующей ячейке.

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

После выполнения описанных действий мы получим матрицу Ангера-Пола.


^ 12. Минимизация частично-определенного автомата. Получение совместимых пар с помощью составление треугольной таблицы Пола и Ангера.

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

По степени совместимости состояния подразделяются на:

1) Абсолютно несовместимые – состояния, которые на выходе автомата имеют разные выходные сигналы.

2) Абсолютно совместимые – состояния, имеющие одинаковые выходные сигналы и равные функции перехода.

3) Условно совместимые – состояния, совместимые при условии равенства функция выхода и эквивалентности функций перехода.

Треугольная матрица заполняется в 3 этапа:

1 этап: На первом этапе мы определяем абсолютно несовместимые состояния, попарно сравнивая столбцы в таблице выходов. Если значение не равно значению , то ставим «X» в соответствующей ячейке.

2 этап: На втором этапе мы определяем абсолютно-совместимые состояния, попарно сравнивая столбцы в таблице переходов, пропуская те пары, что мы определили как абсолютно несовместимые. Если состояния одинаковы при одинаковых сигналах, то ставим «V» в соответствующей ячейке.

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

После выполнения описанных действий мы получим матрицу Ангера-Пола.

Составления максимальных классов совместимости осуществляется по таблице Ангера-Пола. Все состояния на пересечении которых отсутствуют кресты считаются совместимыми (т.е. абсолютно и условно совместимые). Рассмотрение максимальных классов совместимости осуществляется с крайнего правого столбца имеющего по крайней мере одну клетку без крестов.

^ 13. Композиция автоматов. Последовательное соединение автоматов.

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

Задача композиции – нахождение функций перехода и выхода.

^ Алгоритм определения функций перехода и выхода объединённого автомата:

    1. Определение состояния объединённого автомата путём перемножения всех состояний включённых в него автоматов.

    2. По входному сигналу определить новое состояние автомата и выходной сигнал первого автомата.

    3. Найти функцию перехода второго автомата.

По результатам выполнения алгоритма строится таблица переходов и выходов объединённого автомата.


^ 14. Композиция автоматов. Параллельное соединение автоматов.

Из схемы параллельного соединения видно, что сигналы для всех автоматов одинаковы, т.е. х1=х2=х. Выходной сигнал будет определяться какоё то логической функцией F и выходными сигналами автоматов А1 и А2.

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

Внутренний алфавит состояний объединённого автомата будет равен произведению алфавитов автоматов А1 и А2.

^ Алгоритм определения функций переходов и выходов параллельно соединённого автомата:

1) По состоянию автомата A3 определить предыдущие состояния автоматов A1 & A2

2) По входному сигналу и предыдущему состоянию предыдущего автомата определить последующие состояния и выходные сигналы.

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

По результатам выполнения алгоритма строится таблица переходов и выходов объединённого автомата.
^ 15. Композиция автоматов. Соединение автоматов в сеть.

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

^ 16. Декомпозиция автоматов. Задача декомпозиции.

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

Декомпозиция автоматов основана на разбиении множеств состояний автоматов.

Декомпозиция заключается в составлении П и СП-разбиений.

П-разбиением множества S является множеством его подмножеств, которые не пересекаются между собой и при объединении дают множество S.

Декомпозиция автоматов при наличии СП-автоматов разбиения от П до С называется СП-разбиением.

Суть Декомпозиции автоматов состоит в том, что любому количеству П-разбиений можно сопоставить сеть автоматов, реализующую заданный, если эти П-разбиения ортогональны.
^ 17. Общие понятия о π-разбиениях. Виды π-разбиений.

П-разбиением множества S является множеством его подмножеств, которые не пересекаются между собой и при объединении дают множество S. Эти подмножества называются блоками П-разбиений.

^ Несколько фактов о П-разбиениях:

  • Одноэлементным П-разбиением называется разбиение, при котором в каждом блоке содержится только один элемент множества S. Пример - П={1,2,3,4,5,6}.

  • П-разбиения можно сравнивать между собой.

  • П-разбиение считается меньшим, если каждый его блок входит в другой блок большего П-разбиения.

  • П-разбиения можно перемножать. Произведением П-разбиений называется такое П-разбиение при котором выполняется условие Пis=Пкs где первое – перемножаемые множества, а второе произведения П-разбиений.

  • Ортогональными П–разбиениями называются такое П-разбиение которое при перемножении даёт одноэлементное П-разбиение.



^ 18. π — разбиения со свойствами подстановки (СП-разбиения).

Декомпозиция автоматов при наличии СП-автоматов разбиения от П до С называется СП-разбиением. При условии, что если состояния находятся в одном блоке, то при одинаковом входной воздействии состояния, в которые перейдёт автомат будут так же находиться в одном блоке.

Определение СП-разбиений основано на предположении, что рассматриваемые состояния находятся в одном блоке. Если в разных блоках совпадает хотя бы одно состояние, то эти блоки объединяются.

Ищем СП-разбиения, попарно рассматривая все состояния в таблице выходов минимизированного автомата:


δ

b1

b2

b3

b4

b5

b6

x1

b3

b6

b4

b1

b3

b4

x2

b4

b4

b1

b1

b4

b5

x3

b4

b1

b1

b3

b1

B1

x4

b6

b1

b2

b2

b1

b1

x5

b5

b4

b1

b1

b2

b4

На примере я рассматриваю состояния b1 и b2, но в действительности мы должны рассматривать ВСЕ комбинации состояний.

{1 2} X1{36} объединяем блоки, имеющие хотя бы одно одинаковое состояние

X2 {4} и получаем один блок {123456}. Это значит, что в данном случае

X3{41} => СП-разбиения нет. В таком случае ставил «Х»

X4{61} Аналогично рассматриваем все пары состояний
^ 19. Метод декомпозиции. Определение π- разбиений.

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


^ 20. Метод декомпозиции. Определение таблиц переходов для π- разбиений.

После того, как вы определили ортогональные π-разбиения из множества состояний минимизированного автомата ( π1={1234; 56}, π2={1256; 34}, π3={135; 246} ) мы составляем таблицы переходов для них.

Каждое π-разбиение соответствует новому автомату, т.е обозначим блоки π-разбиений через состояния автоматов:

π1->E{e1=1234; e2=56} π2->C{c1=1256; c2=34} π3->D{d1=135; d2=246}.

Для каждого разбиения построим функцию перехода компонентных автоматов на основе функции перехода исходного автомата. Функции переходов компонентных автоматов определяют реакцию автоматов E, C, D на внешнее входное воздействие и что исходный автомат находится в состояние К соответствующему произведению алфавитов компонентных автоматов.

e1*c1*d1=1 e2*c1*d1=5

e1*c1*d2=2 e2*c1*d2=6

e1*c2*d1=3 e2*c2*d1= *

e1*c2*d2=4 e2*c2*d2= *


δ

b1

b2

b3

b4

b5

b6

x1

b3

b6

b4

b1

b3

b4

x2

b4

b4

b1

b1

b4

b5

x3

b4

b1

b1

b3

b1

B1

x4

b6

b1

b2

b2

b1

b1

x5

b5

b4

b1

b1

b2

b4
^ Таблица переходов Автомат E

минимизированного автомата



δ

1

2

3

4

5

6

x1

e1

e2

e1

e1

e1

e1

x2

e1

e1

e1

e1

e1

e2

x3

e1

e1

e2

e1

e1

e1

x4

e2

e1

e1

e1

e1

e1

x5

e2

e1

e1

e1

e1

e1



^ 21. Синтез структурных автоматов. Задачи и этапы синтеза.

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

Синтез структурных автоматов проходит в два этапа:

  1. ^ Кодирование автомата – на данном этапе мы кодируем цифровой автомат в 2ую систему счисления. Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …,xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор. При синтезе цифровых автоматов применяются триггеры счета или триггеры типа «линия задержки». В моей курсовой работе я кодировал структурный автомат по триггеру счёта.

  2. ^ Определение функций логики – на данном этапе мы получаем функции возбуждения триггеров, которое проводим в два этапа:

    • Определение функций возбуждения триггеров - функция определяется из кодированной таблицы по следующей методике: если обозначить кодирующие переменные входа как а1, а2 и а3, состояний – как t1 , t2, t3, выхода – как g.

    • ^ Упрощение логических функций – на данном этапе мы упрощаем полученные на предыдущем этапе функции возбуждения триггеров. Для упрощения мы пользуемся картами Карно или методом Квайна. Но о них подробнее в другом билете.


^ 22. Кодирование структурных автоматов. Условия кодирования.

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

Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …,xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор.

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

Закодируем для примера таблицу выходов, используемую мной в разработке курсового проекта:

примем следующие обозначения:

x1= 000 b1= 000 y1= 1 y2=0

x2= 001 b2= 001 Закодированная таблица:


g

000

001

010

100

011

111




1

2

3

4

5

6

000

0

0

0

0

1

1

001

1

0

1

1

1

0

010

0

0

0

0

1

0

100

0

0

1

0

0

0

011

0

0

0

0

0

0
x3= 010 b3= 010

x4= 011 b4= 100

x5= 111 b5= 011

b6= 111


λ

b1

b2

b3

b4

b5

b6

x1

y2

y1

y1

y2

y1

y1

x2

y1

y1

y1

y1

y1

y2

x3

y2

y2

y2

y2

y1

y2

x4

y2

y2

y1

y2

y2

y1

x5

y2

y2

y2

y2

y1

y2
Исходная таблица выходов:

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

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

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

Автомат мура обладает полной системой переходов, если для любой пары состояний (ai,aj) найдётся входной сигнал, переводящий один элемент пары в другой, включая случай, когда i=j.

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


^ 24. Триггеры. Принципы работы. Типы триггеров. Триггеры типа «линия задержки» и «счетный триггер».

  • Элементарные асинхронные RS-триггеры строятся на основе логических схем ИЛИ-НЕ или И-НЕ, выход каждой из которых соединен с одним из входов другой.

  • JK-триггеры отличаются от RS-триггеров тем, что при значениях входной информации, запрещенной для ^ RS-триггеров, они инвертируют хранимую в них информацию. JK-триггеры могут быть асинхронными и синхронными.

  • D-триггер (триггер задержки) – запоминающий элемент с двумя устойчивыми состояниями и одним информационным входом. Функция перехода D-триггера задается таблицей истинности. В отличие от RS-триггера D-триггер имеет только режимы установки 1 и 0. Асинхронный D-триггер практически не применяется, так как его выход будет просто повторять входной сигнал. Синхронный D-триггер задерживает распространение входного сигнала на время паузы между синхросигналами.

  • Т-триггер (счетный триггер, триггер со счетным входом, двоичный счётчик) – запоминающий элемент, имеющий два устойчивых состояния и изменяющий своё состояние после прихода каждого счётного импульса на вход Т. Т-триггер осуществляет операцию суммирования по модулю 2 сигнала состояния триггера Q и входного сигнала, поступающего на вход Т. Единичный входной сигнал меняет состояние триггера на противоположное, а нулевой – оставляет без изменения.


^ 25. Проектирование автомата. Определение функций возбуждения элементов памяти.

Функции возбуждения элементов памяти определяются из закодированных таблиц автоматов.

Рассмотрим на примере:

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


δ

c1

c2

0000

1

0

01000

0

1

10000

1

*

11000

1

*

00001

1

1

01001

1

1

10001

1

*

11001

0

*

00010

1

1

01010

0

0

10010

0

*

11010

0

*

00011

0

1

01011

0

1

10011

0

*

11011

0

*

00111

0

1

01111

1

1

10111

0

*

11111

1

*


Всем понятно, что в первом столбце – перебор всех возможных состояний, для минимизации мы используем второй.
Обозначим кодирующие переменные входа некоторыми символами алфавита. Заменив в матрице выходов состояния на их коды, получим описание функции.
Если в столбце «0», то мы его пропускаем, грубо говоря строчки с нулями нам не нужны, мы используем только те строки, во втором столбце которых «1».
Рассмотрим подробно одну из них:


01 0 0 1

eda1a2a3

1

Используем уже принятые нами обозначения.

d=0 d=1 a1=0 a2=0 a3=1

Теперь запишем это формулой, заменив «0» на «НЕ»

Функцией возбуждения данной таблицы будет

^ 26. Проектирование автомата. Определение функций выхода.

Данная функция определяется из закодированной таблицы выходов:

g

000

001

010

100

011

111




1

2

3

4

5

6

000

0

0

0

0

1

1

001

1

0

1

1

1

0

010

0

0

0

0

1

0

100

0

0

1

0

0

0

011

0

0

0

0

0

0


Функция выхода определяется из кодированной таблицы выходов по следующей методике: если обозначить кодирующие переменные входа как а1, а2 и а3,
состояний – как t1 , t2, t3, выхода – как g, то функция выхода будет иметь вид:



^ 27. Минимизация логических функций методом Квайна и картами Карно.

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

В своей курсовой я пользовался двумя методами минимизации – методом Квайна и картами Карно.

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

К примеру функцию



Удобно минимизировать с помощью карт Карно, т.к. функция не большая и много внимания её не требуется.

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










0

0

0

0



0

0

0

0





1

0

0

1




1

0

1

0













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

Объединив мы получим такую упрощённую функцию:



А теперь рассмотрим функцию



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

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



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

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


^ 28. Синтез логических схем. Понятие базиса.

Любая логическая схема без памяти полностью описывается таблицей истинности. Эта таблица является исходной информацией для синтеза схемы на основе логических элементов «И», «ИЛИ», «НЕ». Для разработки требуемого цифрового устройства сначала на основе таблицы истинности записывают его логическое выражение. Затем с целью упрощения цифрового устройства минимизируют его логическое выражение и далее разрабатывают схему, реализующую полученное логическое выражение. Логические выражения можно получить двумя способами:

  • на основе совершенной дизъюнктивной нормальной формы (СДНФ)

  • на основе совершенной конъюнктивной нормальной формы (СКНФ)

^ Совершенная дизъюнктивная нормальная форма (СДНФ)

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

f(х)=xxx3 + xxx3 + xxx3

Совершенная конъюнктивная нормальная форма (СКНФ)

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

f(х)=(x1+x2+x3) · (x1+x2+x3) · (x1+x2+x3)

Если схема имеет несколько выходов, то каждый выход описывается своей функцией. Такая система функций называется системой собственных функций. СДНФ составляется на основе таблицы истинности по следующему правилу: для каждого набора переменных, при котором функция равна 1, записывается произведение, в котором с отрицанием берутся переменные, имеющие значение «0».
^ 29. Автоматы Тьюринга. Основные элементы автоматов Тьюринга. Принцип работы автоматов Тьюринга

Вычислитель подобен человеку, производящему большое кол-во операций и обладающий большим объёмом памяти. Вычислитель работает в дикр. времени (в каждый момент времени известно известно только, что будет производиться в следующий момент времени).

МТ нах. в одном из множества состояний Q={q1,q2,q3,…,qn},это мн-во обозначает кол-во операций, которых может выполнять МТ.

Один из блоков МТ- Устройство Управления (УУ)- выполняя одну операцию оно нах. в одном состоянии, другую- в другом.

Q={q1,q2,q3,…,qn}-УУ

q1- начальное состояние;

qz- конечное состояние (Пассивное);

Состояния, отличные от qz- активные.

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

В МТ имеется устройство обращения к ленте, которое с помощью записывающей или считывающей головки обрабатывает ленту. В зависимости от того, в каком состоянии нах-ся МТ, и какой символ нах-ся в поле зрения головки, записывается в ячейку новый символ. Также имеется ф-ия dk={L,R,E}, показывающая направление( знак) сдвига.

С помощью МТ можно произвести любое выч-е .

Формулировка тезиса: всякая конструктивно заданная процедура (алгоритм) может быть описана с помощью тьюринговой функц. схемы и реализована на соотвующей МТ.Если для задачи нельзя построить алгоритм, то машину Тьюрингп нельзя построить для выч-я.

^ 30. Микропрограммные автоматы. Структурная схема микропрограммных автоматов и функции ее элементов.

Микропрограммные автоматы отличаются от цифровых автоматов с жёсткой логикой тем, что они работают в соответствии с программой.

Программа прошивается в постоянное запоминающее устройство (ПЗУ).

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

Процессор ЦВМ или другое операционное устройство, выполняющее операции над словами информации, можно разделить на две части – операционный (ОА) и управляющий (УА) автоматы .

Процессор ЦВМ выполняет заданное множество операций ^ F над входными словами D с целью вычисления результатов R. Каждая операция из множества операций F возбуждается соответствующей командой из множества команд K.

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

  • Любая операция из множества F, реализуемая устройством, рассматривается как сложное действие и разделяется на последовательность элементарных действий над словами информации, называемых микрооперациями.

  • Каждая микрооперация инициализируется соответствующей микрокомандой из множества микрокоманд Y, вырабатываемых УА

  • Для управления порядком следования микроопераций (порядком выдачи управляющим автоматом микрокоманд Y) используются логические условия Х, принимающие значения 1 или 0.

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



Скачать файл (353 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru