Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-12-12 | 938 |
5.00
из
|
Заказать работу |
Рассмотрим алгоритм построения КС с помощью скобочных преобразований.
1. Преобразуем исходную ДНФ многократно вынося за скобки переменные.
Пример.
2. Выделяем одинаковые подфункции в скобочной форме F и получаем совокупность функций для F.
Пример.
F = XY(Ф Ú W) Ú WФ
Ф = Z Ú PQ
3. Выделяем конъюнкции или их части общие для нескольких мест (одинаковые) и расширяем совокупность функций.
Пример.
F = XY(F Ú W) Ú WF Ú MN K
F = Z Ú MN P
F = XY(F Ú W) Ú WF Ú YK
F = Z Ú YP
Y = MN
При поиске и выделении общих частей конъюнкций учитывается, что выделение k букв из L конъюнкций дает выигрыш W = k(L - 1).
Выделяя общие части с максимумом W при W > 0, мы обеспечиваем упрощение схемы.
Далее по совокупности БФ строится КС, например, моделированием полученных выражений.
Действия по п.2 и 3 ясны. Действия по п.1 рассмотрим подробнее, полагая, что исходное выражение для F - ДНФ.
Исходную ДНФ, рассматриваемой БФ F, обозначим как D 0.
Делая вынесение за скобки переменных, получим
D 0 = K 0 &(D 01) Ú D 02
КонъюнкцияДНФ
Поиск выносимых за скобки переменных (конъюнкции) рассмотрим далее.
«Убираем» на время из рассмотрения внутри - скобочное выражение для D 01 и получаем ДНФ D 1 .
D 1 = K 0 &(F 01) Ú D 02 .
Переменная, заменяющая ДНФ D 01.
D 1 обрабатываем как исходную ДНФ D 0, если возможно вынесение за скобки K 1 и представление ее в виде
D 1 = K 1 &(D 11) Ú D 12 .
Затем аналогично получаем D 2 , D 3 и т.д.
Если в D j уже нельзя выделить К j, то берем
D j = K j-1 &(F j-11) Ú D j-12
и подставляем туда последовательно (D j-11) вместо F j-11, (D j-21) вместо F j-21 и т.д. до (D 01) вместо F 01.
При этом мы получаем выражение, в котором в скобки заключены ДНФ D 01, D 11, …D j-11.
Каждую из этих ДНФ будем обрабатывать как исходную, продолжая до тех пор, пока это возможно.
В результате получим искомую форму.
Рассмотрим пример.
К 0 D 01 D 02
К 1 D 11 D 12
Дальнейшее вынесение за скобки невозможно.
Подставляя всюду D q1 вместо F q1, получаем
Преобразуя каждую ДНФ из скобок, получим
Полученные здесь в скобках ДНФ уже не допускают дальнейших скобочных преобразований.
Заменив преобразованные ДНФ на скобочные выражения, получим
На этом скобочные преобразования завершены.
Выделив одинаковые подфункции, мы получим
В результате, получаем схему.
Замечание о многовыходных схемах.
Для системы БФ, каждая функция приводится к скобочной форме отдельно. Затем во всех функциях находятся одинаковые части формул и конъюнкций и формируется общая совокупность функций.
Следует отметить, что при большом числе «похожих» конъюнкций в разных БФ, лучшие результаты может дать другой подход.
1) В совокупности всех БФ выделяются общие части и заменяются новыми переменными;
2) БФ (с новыми переменными, если они введены) раздельно обрабатываются описанным ранее способом;
3) Введенные в 1) переменные реализуются схемами.
При синтезе многовыходных схем удобно строить схемы, используя поочередно оба подхода, и выбирать лучшую.
Выясним теперь, как в днф D j найти конъюнкцию K j, чтобы, вынеся ее за скобки, получить D j = K j &(D j 1) Ú D j2
Обозначим (K i) J совокупность первых j букв в K i.
Весом W(K i) J для (K i) J назовем
W[(K i) J ] = j . (L k- 1),
где L k - число конъюнкций в D i, содержащих (K i) J.
K i строим, последовательно находя (K i) 1, (K i) 2, …так, чтобы вес W для (K i) J всякий раз был наибольшим и больше нуля.
Переходя к (K i) J нужно подобрать к (K i) J-1 такую переменную, чтобы вес (K i) J был наибольшим.
Отбор переменных к (K i) идет до тех пор, пока вес (K i) J не начнет убывать.
Рассмотрим пример.
D i = X1X2X3ÚX1X2X4ÚX1X5ÚX2X5
X1 | W=2 - max | (Ki)1 = x1 | |
X2 | W=2 | ||
(Ki)1 = | X3 | W=0 | |
X4 | W=0 | ||
X5 | W=1 | ||
X1X2 | W=2 - max | (Ki)2 = X1X2 | |
(Ki)2 = | X1X3 | W=0 | |
X1X4 | W=0 | ||
X1X5 | W=0 | ||
X1X2X3 | W=0 | ||
(Ki)3 = | X1X2X4 | W=0 | |
X1X2X5 | W=0 |
В итоге получаем
D i = X1X2(X3ÚX4)ÚX1X5ÚX2X5
К i D i1 D i2
Схема, построенная по этому выражению, будет содержать 4 двухвходовых конъюнктора.
Схема для исходной ДНФ содержит 6 двухвходовых конъюнкторов.
Вес W для K i равен числу конъюнкторов, которые могут быть удалены из КС для ДНФ D i после перехода к КС для D i в виде
D i = K i &(D i1) Ú D i2
СИНТЕЗ КС ИЗ ЭЛЕМЕНТОВ
И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.
КС часто используемых БФ.
Наиболее часто используемыми БФ являются конъюнкция, дизъюнкция, сумма «по модулю 2» и инверсия.
F = X1&X2& … &Xn
F = X1ÚX2Ú… ÚXn
F = X1 X2 … Xn
F = X1oX2o…oXn
где o - либо &, либо Ú, либо .
Существует набор стандартных решений для построения БФ.
Для этого используются следующие правила:
Для &, и имеется свойство ассоциативности:
возможность произвольной расстановки скобок в формуле
F = X1oX2o…oXn
Например:
F = X1oX2o…oXn = X1o(X2(o…oXn))= (X1oX2)o(…oXn)
В зависимости от того, как расставляются скобки, можно получить выражение, задающее КС последовательной, пирамидальной или смешанной структуры.
Последовательная структура.
;
N - число переменных; К - число входов ЛЭ;
Г - глубина КС; S - число ЛЭ в КС.
Пирамидальная структура.
,
Смешанная структура.
Мы увидели, как построить КС с n входами из ЛЭ (либо «блоков») с К входами, реализующими такие же функции, что и вся КС. Обратимся теперь к построению «блоков».
Рассмотрим типы используемых ЛЭ и их обозначения.
ЛЭ И - ИЛИ - НЕ таков, что из него путем подстановки констант или отождествления входов можно получать ЛЭ типа И - НЕ либо ИЛИ - НЕ.
Покажем это.
Рассмотрим способы получения инверторов из элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.
Рассмотрим способы получения конъюнкции из элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.
Получение конъюнкции из элементов И-НЕ.
Получение конъюнкции из элементов ИЛИ-НЕ.
Получение конъюнкции из элементов И-НЕ и ИЛИ-НЕ.
Получение конъюнкции из элементов И-ИЛИ-НЕ.
Рассмотрим примеры получения конъюнкций.
Получение дизъюнкции из элементов ИЛИ-НЕ.
Получение дизъюнкции из элементов И-НЕ и ИЛИ-НЕ.
Получение дизъюнкции из элементов И-ИЛИ-НЕ.
Рассмотрим примеры получения дизъюнкций.
Теперь рассмотрим схемы для получения суммы по модулю два.
X | Y | ||
В соответствии с таблицей истинности можно получить несколько способов реализации этой функции.
Первый способ – на элементах И-НЕ.
Второй способ – на элементах ИЛИ-НЕ.
Третий способ – на элементе И-ИЛИ-НЕ.
Рассмотрим использование выражений вида И - ИЛИ.
F=(X1&…&XP) (Y1&…&YP) … (W1&…&WP)
Рассмотрим примеры реализации выражений И-ИЛИ.
КС ДЛЯ ПРОИЗВОЛЬНЫХ БФ.
Процедура построения КС состоит из трех этапов:
1. Строится схема из элементов И, ИЛИ, НЕ.
2. Отдельные части схемы вида И - ИЛИ, либо И, либо ИЛИ переводятся в схемы из заданных ЛЭ (см. раздел 2.3.1).
3. Полученная КС корректируется с целью устранения возможной избыточности, например, вида
или нахождения общих частей.
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!