Способы задания булевых функций

Способы задания булевых функций Содержание • • • 1 Аналитический метод o 1.1 ДНФ o 1.2 КНФ 2 Карты Карно o 2.1 Способ построения последовательностей o 2.2 Карта Карно от 5ти переменных 3 АНФ (Полином Жегалкина) Аналитический метод К аналитическому методу относится построение ДНФ, КНФ и АНФ. ДНФ Какую схему можно построить по ДНФ? Пример Функция от 3х переменных: Схема в общем виде для ДНФ: В худшем случае: tzd=tnot+tand+tor В лучшем случае: tzd=tor tand+tor (если не нужен инвертор) При реализации б.ф. от 3х переменных: 7 - "1", 1 - "0" ⇒ 3 инвертора, 7 конъюнкторов, 1 дизъюнктор. КНФ Если используется КНФ ⇒ 1 И, множество дизъюнкций. По быстродействию: В худшем случае 7 "0", 1 "1" ⇒ 7 ИЛИ, 1 И В лучшем случае tand≈tor Схемы идентичны с точки зрения быстродействия. При построении ДНФ - основной элемент "1", КНФ - "0" ⇒ получим полиномиальную схему. Карты Карно Существуют для любого количества переменных. Последовательности должны отличаться на одну единицу. Способ построения последовательностей 000 001 011 010 110 111 101 100 Отличие ровно на 1 бит (отличие в старшем бите; склеили ???) Карта Карно от 5ти переменных x1x2\ x3x4 00 01 11 10 000 001 x x 011 x x 010 x x 110 x x 111 x x 101 x x 100 x: отличия в значении x_0 (011, 111) - т.е. отличия в 1м разряде ⇒ покрытие. Правила проверки симметричности покрытий (в многомерных Картах Карно): фигура симметрична относительно всех осей симметрии (необходимое условие) АНФ (Полином Жегалкина) f(x0,x1,x2)=a0⊕a1x0⊕a2x1⊕a3x2⊕a4x0x1⊕a5x1x2⊕a6x0x2⊕a7x0x1x2⊕ В худшем случае: txor+tand=tzd В лучшем случае: txor=tzd XOR: 1 элемент (8ми входовый) AND: 4 элемента - 3 элемента AND (2х входовый), 1 элемент 3AND (3х входовый) ⇒ количество элементов в худшем случае (в случае ДНФ) - 11 штук. Минусы ⊝: 1. В предыдущей схеме использовались однотипные элементы, а здесь - 2х входовые, 3х входовые и т.д. (особенности реализации) 2. tzdxor>tand, tor Самый простой вариант - синтез с помощью этих схем (2 базиса: И, ИЛИ, НЕ; ⊕, И). Если надо синтезировать Штрих Шеффера и Стрелку Пирса: …⇒ схема модифицируется в базисе И-НЕ (т.е.присутствует только эти однотипные элементы; их количество не изменяется). ИЛИ-НЕ - не ее основе раскрываем КНФ. И-НЕ ⇒ присутствует в худшем случае в базисе И-НЕ: tzd=3tor Для минимизации схем необходимо рассматривать все эти случаи. Если функциональный базис не полный, то б.ф., возможно, можно реализовать. Либо можно перебирать различные схемные решения для того, чтобы найти оптимальное решение.