Курсовая работа: Синтез цифрового аппарата

Введение

электрический схема логический триггер

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

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

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

1. Синтез абстрактного автомата

электрический схема логический триггер

1.1 Исходные данные

Таблица переходов и выходов

Разобьем исходную таблицу на таблицу переходов и таблицу выходов.

Таблица переходов

Таблица выходов

1.2 Минимизация по алгоритму Ангера - Пола

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

По степени совместимости состояния бывают:

· Абсолютно несовместимые - состояния имеющие разные выходные сигналы.

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

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

Составление треугольной матрицы

Для нахождения минимального частично-определенного автомата необходимо составить треугольную матрицу Ангера-Полла.

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

1 этап:

На первом этапе мы определяем абсолютно несовместимые состояния, попарно сравнивая столбцы в таблице выходов.

Если значение не равно значению , то ставим «X» в соответствующей ячейке.

2 этап:

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

3 этап:

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

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

Определение совместимых состояний

Для нахождения несовместимых (а так же совместимых) пар состояний треугольная таблица просматривается по столбцам, начиная с нижнего правого (т.е. 9-10). С правого нижнего столбца мы ищем первую ячейку, отмеченную крестом. В нашем случае это (8,10).Тогда во всех клетках, где есть пара (8,10), ставится крест. Эту процедуру мы проводим для всех клеток, отмеченных крестом (в том числе и свежеотмеченные), и заканчиваем, когда таких клеток не остаётся. В этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами - несовместимым.

В итоге получаем окончательный вариант матрицы Ангера-Пола:

После выполнения этих действий мы получаем совместимые пары состояний - 1-2, 1-6, 2-6, 3-7, 3-9, 7-9.

Минимизированный цифровой автомат

Для получения минимизированного автомата мы рассматриваем совокупность максимальных множеств. Составление максимальных классов совместимости осуществляется по матрице Ангера-Пола. Все состояния, на пересечениях которых присутствует «V», считаются совместимыми. Рассмотрение максимальных классов совместимости осуществляются с крайнего правого столбца, имеющего, по крайней мере, одну клетку без «Х».

1. (S₇; S₉) Ф=(7,9)

2. (S₃; S₉)&(S₃; S₇)&(S₇; S₉) Ф=(3,7,9)

3. (S₂; S₆) Ф=(2,6)

4. (S₁; S₆)&(S₁; S₇)&(S₆; S₂) Ф=(1,6,2)

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

b₁={1,2,6}, b₂={4}, b₃={5}, b₄={3,7,9}, b₅={8}, b₆={10}.

Из этого получаем, что в минимизированном автомате будет 6 состояний, 5 входных сигналов и 2 выходных сигнала.

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

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

Например: в b1 входят состояния {1,2,6}. При входном сигнале x1 они все перейдут в состояние {5}, входящее в b3. Значит на пересечении {b1, x1} таблицы переходов минимизированного автомата мы запишем b3. Таким способом заполняем все ячейки.

Таблица переходов минимизированного автомата

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

Таблица выходов минимизированного автомата

1.3 Декомпозиция автоматов

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

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

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

Определение СП разбиений

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

Ищем СП-разбиения, попарно рассматривая все состояния:

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

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

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

X4 {61} Аналогично рассматриваем все пары состояний

X5 {54}

{13} X1 {34} {1345} X1 {134}

X2 {4} X2 {14}

X3 {4} => {1345} {62}; X3 {134} => {123456}; X

X4 {62} X4 {126}

X5 {54} X5 {125}

{14} X1 {13} {1245} X1 {134}

X2 {14} X2 {14}

X3 {34} => {1345} {26}; X3 {134} => {123456}; X

X4 {26} X4 {126}

X5 {15} X5 {125}

{15} X1 {3} {12456} X1 {1346}

X2 {4} X2145}

X3 {14} => {12456} {3}; X3 {134} => {123456}; X

X4 {16} X4 {126}

X5 {25} X5 {1245}

{16} X1 {34} {13456} X1 {134}

X2 {45} X2 {145}

X3 {14} => {13456} {3}; X3 {134} => {123456}; X