Синтез цифрового аппарата

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

1 этап:

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

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

2 этап:

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

3 этап:

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

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

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

После выполнения этих действий мы получаем совместимые пары состояний - 9-10, 5-10, 5-8, 4-10, 4-8, 4-5, 2-8,2-5, 2-4, 1-2.

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

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

Ф1=(9,10)

Ф2=(5,10), (5,8)

Ф=(9,10), (5,10), (5,8)

Ф3=(4,10), (4,8), (4,5)

Ф=(9,10), (4,10), (5,10), (4,5,8)

Ф4=(2,8), (2,5), (2,4)

Ф=(9,10), (5,10), (4,10), (2,4,5,8)

Ф= (1,2), (9,10), (5,10), (4,10), (2,4,5,8), (3), (7), (6)

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

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

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

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

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

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

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

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

алгоритм логический аппарат цифровой

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

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

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

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

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

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

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

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

объединяем блоки, имеющие хотя бы одно одинаковое состояние и

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

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

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

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

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

Определим ортогональные р-разбиения из множества состояний минимизированного автомата.

р1={1234; 5678}, р2={1357; 2468}, р3={1256; 3478}.

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

р1->В {b1=1234; b2=5678}

р2->C {c1=1357; c2=2468}

р3->D {d1=1256; d2=3478}.

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

b₁*c₁*d₁=1 b₂*c₁*d₁=5

b₁*c₁*d₂=3 b₂*c₁*d₂=7

b₁*c₂*d₁=2 b₂*c₂*d₁= 6

b₁*c₂*d₂=4 b₂*c₂*d₂=8

Автомат B

Автомат C

Автомат D

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

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

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

Определим ф-разбиения для компонентных автоматов, путем сравнения столбцов таблиц переходов:

фb= {17}; {2345}; {6}, {8}

ф_c ={1}; {2}; {345}; {6}; {7}; {8}.

ф_d= {1}; {2345}; {6}; {7}; {8}.

Определим з-разбиения для компонентных автоматов, путем сравнения строк таблиц их переходов:

?b = {1}; {2}; {3}, {4}, {5}

?c = {1}; {2}; {3}; {4}: {5}.

?d = {1}; {24}; {3}; {5}

7. Определение входных сигналов компонентных автоматов и составление таблиц

Влияние автоматов друг на друга определяется по следующему правилу: если произведение р-разбиений i-го автомата меньше или равно ф-разбиению i-го автомата, то составляющая определяется как произведение р-разбиений исключая р-разбиение i-го автомата.

р₁*р₂={13,24,57,68}

р₁*р₃={12,34,56,78}

р₂*р₃={15,37,26,48}

р₁*р₂*р₃={1,2,3,4,5,6,7,8}

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

Для составления таблиц переходов автоматов C, D и B примем следующие обозначения:

В {b1=1234; b2=5678}

C {c1=1357; c2=2468}

D {d1=1256; d2=3478}

U={u₁=x₁, u₂₌x₂; u₃=x₃; u₄=x₄; u₅=x₅}

V={v₁=x₁; v₂=x₂, v₃₌x₃; v₄=x₄; v₅=x₅}

W={w₁=x₁; w₂=x₂, x₄; w₃=x₃; w₄=x₅}.

Таблицы заполняем по следующему алгоритму на примере первой ячейки: c1*d1*b1=1. По сигналу u1 (x1, x2) автомат B перейдет в состояния b₁, что мы и запишем в первую ячейку таблицы переходов автомата B.

Таким образом, заполняются все ячейки всех трёх автоматов:

Определение выходных сигналов осуществляется по произведению состояний компонентных автоматов B, C и D и входным сигналам в соответствии с таблицей выходов автомата B.

8. Структурный синтез цифрового автомата

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

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

Кодировать таблицы переходов и выходов будем в соответствии с условиями:

c₁d₁= b₁c₁= b₁d₁= 11 u₁₌w₁=000 v₁=000

c₁d₂= b₁c₂= b₁d₂= 10 u₂₌w₂= 001 v₂= 001

c₂d₁= b₂c₁= b₂d₁= 01 u₃₌w₃=010 v₃= 010

c₂d₂= b₂c₂= b₂d₂= 00 u₄₌w₄=011 v₄= 011

u₅₌w₅ =100

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

x₁= 000 b₁= c₁= d₁ =1 t1=b1 y₁= 1 y₂=0

x₂= 001 b₂= c₂= d₂ =0 t2=c1

x₃= 010 t3=d 1

x₄= 011

x₅= 100

g=?a1?a2?a3t1t2t3+ ?a1?a2?a3t1t2?t3+ ?a1?a2?a3t1t?2t3+ ?a1?a2?a3t1?t2?t3+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2t3+ ?a1a2?a3?t1?t2?t3+ ?a1a2a3t1t2t3+ ?a1a2a3t1t2?t3+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1t2t3+ ?a1a2a3?t1?t2t3+ ?a1a2a3?t1t2?t3+ ?a1a2a3?t1?t2?t3+ a1?a2?a3t1t2t3+ a1?a2?a3?t1t2t3+ a1?a2?a3?t1t2?t3+ a1?a2?a3?t1?t2?t3

9. Определение функций логики

Определение функции выхода

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

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

g=?a1?a2?a3t1t2t3+ ?a1?a2?a3t1t2?t3+ ?a1?a2?a3t1t?2t3+ ?a1?a2?a3t1?t2?t3+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2t3+ ?a1a2?a3?t1?t2?t3+ ?a1a2a3t1t2t3+ ?a1a2a3t1t2?t3+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1t2t3+ ?a1a2a3?t1?t2t3+ ?a1a2a3?t1t2?t3+ ?a1a2a3?t1?t2?t3+ a1?a2?a3t1t2t3+ a1?a2?a3?t1t2t3+ a1?a2?a3?t1t2?t3+ a1?a2?a3?t1?t2?t3

Определение функции возбуждения триггеров.

Опять обозначим кодирующие переменные входа как a1, a2 и a3, состояний - как t, заменив в матрице выходов состояния на их коды, получим описание функций u(t1), u(t2), u(t3)

U(t1)=?a1?a2?a3t2t3+ ?a1?a2?a3t2?t3+ ?a1?a2?a3?t2t3+?a1?a2?a3?t2?t3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3? t3t2+ a1?a2?a3? t2?t3

U(t2) =?a1?a2?a3?t1?t3+ ?a1?a2a3t1t3+ ?a1?a2a3?t1t3+ ?a1a2?a3t1t3+ ?a1a2?a3t1?t3+ ?a1a2?a3?t1t3+ ?a1a2?a3?t1?t3+ ?a1a2a3t1t3+ ?a1a2at1?t3+?a1a2a3?t1t3+ ?a1a2a3?t1?t3+ a1?a2?a3t1t3+ a1?a2?a3?t1t3+ a1?a2?a3?t1?t3

U(t3)=?a1?a2?a3?t1?t2+ ?a1?a2a3t1t2+ ?a1?a2a3t1?t2+ ?a1?a2a3?t1t2+ ?a1a2?a3?t1t2+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3?t1?t2

10. Упрощение логических функций

Для упрощения функций u(t1) используем карты Карно:

U(t1)=?a1?a2?a3t2t3+ ?a1?a2?a3t2?t3+ ?a1?a2?a3?t2t3+?a1?a2?a3?t2?t3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3? t3t2+ a1?a2?a3? t2?t3

Получим упрощённую функцию u(t1):

U(t1)=?a1?a2?a3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3?t3

Дл...