Материал: 4183
Полученная таблица переходов и выходов еще представлена на так называемом абстрактном уровне. Чтобы перейти к комбинационным схемам необходимо заменить абстрактные символы состояний комбинациями наборов двоичных переменных, т. Е. произвести кодирование состояний автомата. Необходимое условие правильного кодирования состояний – каждому состоянию нужно поставить свой, отличный от других состояний код. Отсюда число к внутренних переменных z1z2…zk, кодирующих состояния, вычисляется по следующей формуле k=]log2(L +1)[.Состояния переменных zi представляются состояниями памяти автомата, отсюда схема последовательностного автомата выглядит следующим образом.
Первоначально проведем так называемое тривиальное кодирование состояний, состояние Si закодируем k-разрядным двоичным кодом числа i.
K=]log2(5+1)[=3.
3 2 1
0
1
2
3
4
5
Рисунок 27. Кодированная таблица переходов и выходов.
Прежде всего обратим внимание на расстановку состояний по столбцам кодированной таблицы переходов и выходов. Они расставлены согласно их кодированию. Состояния Sx обозначают не использованные коды 110 и 111.
Итак, мы перешли от абстрактного представления автомата к системе булевых функций: первый столбец кодированной таблицы переходов и
31
выходов представляет булеву функцию z1(t+1), второй столбец – булеву функцию z2(t+1), третий столбец – булеву функцию z3(t+1).
Чтобы построить выходные функции автомата, поступим следующим образом. Разместим состояния автомата на матрице трех переменных – z1z2z3:
Рисунок 28. Размещение состояний автомата “Секретный замок” на матричной форме переменных z1, z2, z3.
Функция у1 принимает единичное значение на единственном наборе, соответствующему состоянию S3 – это набор 011. И кроме того она не определена на наборах, соответствующих состояниям Sx. Функция у2 Принимает единичное значение на наборах, соответствующих состояниям S4, S5 и не определена на наборах для состояний Sx.
Рисунок 29. Выходные функции автомата “Секретного замка”.
Практическое задание. Построить граф автомата “Секретный замок”. Построить таблицу переходов и выходов автомата, провести кодирование состояний и построить кодированную таблицу переходов и выходов. Построить функции z1,z2,z3,у1 и y2.
Лабораторная работа 6 Метод допустимых конфигураций синтеза многоуровневых И-НЕ схем по матричной форме
Цель занятия – изучение операции вычитания и ее применение при проектировании комбинационных схем.
Теоретические положения и примеры проектирования схем.
32
Вспомним дискретную математику – операцию вычитания на множествах.
А\В = А∩В.
Интервал рассматривается нами как множество точек булева пространства, организованное по некоторым правилам. Множество А можно представить конъюнкцией простых переменных без инверсии. Операцию пересечения заменим на конъюнкцию. Интервал В представим конъюнкцией простых переменных.
Например, А =х1х2\х3х4, На матричной форме представлен в следующем виде.
Рисунок 30 Простейший пример применения операции вычитания. Рассмотрим другой пример. Например, С =х2\(х4\(х1\х3)) представлен
на матрице.
Рисунок 31 Более сложный пример применения операции вычитания.
Конфигурацию вида А назовем простой конфигурацией, т. Е. простой конфигурацией называется разность, когда из конъюнкции простых переменных вычитается конъюнкция простых переменных. Выражение вида С называется допустимой конфигурацией, т. Е. разность простой конфигурации и допустимой конфигурации. В свою очередь можно из допустимой конфигурации вычитать допустимую конфигурацию. Например, допустимая конфигурация D= х2\х3\(х1\х4) представлена на следующей матрице.
33
Рисунок 32 Реализация допустимой конфигурации D.
Наконец, булева функция может быть представлена дизъюнкцией допустимых конфигураций. Например, F = х2\х3Vх1х3\х4.
Рисунок 33 Дизъюнкция допустимых конфигураций.
Это, в свою очередь, является структурной формулой следующей многоярусной схемы.
Рисунок 34. Схема, построенная методом допустимых конфигураций.
34
Алгоритм проектирования многоуровневой схемы методом допустимых конфигураций состоит в следующем.
1.Задана булева функция в матричной форме. Считаем все элементы множества М1еще не реализованными.
2.Находим минимальный в векторном смысле не реализованный элемент и формируем интервал простых переменных, если этот интервал покрывает элементы множества М0, то вычитаем из него дополнительные конфигурации. Считаем элементы множества М1, покрытые этим интервалом, реализованными. Если есть еще не реализованные элементы множества М1, то выполняем пункт 2, иначе пункт 3.
3.Это мы получили первоначальное покрытие множествами допустимых конфигураций булевой функции. Теперь построения интуитивные. Строим дополнительные допустимые конфигурации, стараясь уменьшить число различных допустимых конфигураций.
Например, пусть задана следующая булева функция F.
Рисунок 35 Функция для метода допустимых конфигураций.
Первый минимальный в векторном смысле элемент 0100. Ему соответствует интервал х2. Считаем точки 0100, 1100, 1110 и 1101 реализованными. Следующий минимальный элемент 0010 с покрывающим интервалом х3. Точки 0010, 1010 и 1110 реализованы. Осталась одна точка 1001с покрывающим ее интервалом х1х4. Точки все реализованы, приступаем к построению допустимых конфигураций.
Чтобы вычесть области множества М0, формируем две дополнительные конфигурации.
Φд1 = х2х3\х1 φд2 = х4\(х1\х3)
Тогда
φ1 = х2\ φд1\ φд2 φ2 = х3\ φд1\ φд2 φ3 = х4\ φд2
F = φ1V φ2V φ3.
Приведенная совокупность допустимых конфигураций соответствует следующей схеме.
35