Практические занятия Прикладная теория цифровых автоматов
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Занятие 5. Метод допустимых конфигураций синтеза многоуровневых И-НЕ схем по матричной форме

Цель занятия – изучение операции вычитания и ее применение при проектировании комбинационных схем.

Теоретические положения и примеры проектирования схем.

Вспомним дискретную математику - операцию вычитания на множествах.

А\В = А∩В.

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

Например, А =х1х2\х3х4, На матричной форме представлен в следующем виде.

Простейший пример применения операции вычитания.

Рисунок 27. Простейший пример применения операции вычитания.

Рассмотрим другой пример. Например, С =х2\(х4\(х1\х3)) представлен на матрице.

Рисунок 28. Более сложный пример применения операции вычитания.

Конфигурацию вида А назовем простой конфигурацией, т. е. простой конфигурацией называется разность, когда из конъюнкции простых переменных вычитается конъюнкция простых переменных. Выражение вида С называется допустимой конфигурацией, т. е. разность простой конфигурации и допустимой конфигурации. В свою очередь можно из допустимой конфигурации вычитать допустимую конфигурацию. Например, допустимая конфигурация D= х2\х3\(х1\х4) представлена на следующей матрице.

Рисунок 29. Реализация допустимой конфигурации D.

Наконец, булева функция может быть представлена дизъюнкцией допустимых конфигураций. Например, F = х2\х3Vх1х3\х4.

Рисунок 30. Дизъюнкция допустимых конфигураций.

Это, в свою очередь, является структурной формулой следующей многоярусной схемы.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Рисунок 31. Схема, построенная методом допустимых конфигураций.

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

1.  Задана булева функция в матричной форме. Считаем все элементы множества М1еще не реализованными.

2.  Находим минимальный в векторном смысле не реализованный элемент и формируем интервал простых переменных, если этот интервал покрывает элементы множества М0, то вычитаем из него дополнительные конфигурации. Считаем элементы множества М1, покрытые этим интервалом, реализованными. Если есть еще не реализованные элементы множества М1, то выполняем пункт 2, иначе пункт 3.

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

Например, пусть задана следующая булева функция F.

Рисунок 32. Функция для метода допустимых конфигураций.

Первый минимальный в векторном смысле элемент 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.

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

Многоярусная схема на элементах И-НЕ

Рисунок 33. Многоярусная схема на элементах И-НЕ

Домашнее задание. Выполнить проектирование методом допустимых конфигураций многоярусной схемы на элементах И-НЕ для булевых функций (2, стр. 69).

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство