Построение комбинационных схем по минимальным

Нормальным формам в различных базисах

Булев базис (И, ИЛИ, НЕ)

Пример 3.3. Построить схему, реализующую функцию:

Построим схему с парафазными входами на элементах булева базиса, реализующую заданную функцию (рис. 3.6).

 

 

       Цена схемы:

       S_Q=3+3+2+4=12,    

        S^a=9,       

        S^b=9+4=13,

        S^a< S_Q< S^b.

 

      Рис. 3.6. Схема с парафазными входами в булевом базисе

В общем случае, задержка схемы с парафазными входами: Т=2t (схема двухуровневая),  в частном случае Т=1t.

При построении схемы по МКНФ элементами 1-го уровня будут ИЛИ, а 2-го - И.

В общем случае, задержка схемы с однофазными входами составляет Т=3t, а в частных случаях, Т=2t или Т=1t.

Построим схему с однофазными входами на элементах булева базиса, реализующую заданную функцию (рис. 3.7).

Цена схемы:

       S_Q=16, S^a=9, S^b=9+4=13,   

       S^a< S_Q< S^b+    4 (четыре входных инвертора).

         

          

 

 

Рис. 3.7. Схема с однофазными входами

 

При построении схемы с однофазными входами целесообразно выбирать такую минимальную форму (если она не единственная), которая содержит наименьшее число инверсий над разными входными переменными.

При наличии единственной минимальной нормальной формы, можно осуществить ее преобразование с использованием законов двойного отрицания и двойственности (Де Моргана).

Для реализации этой схемы понадобятся три инвертора.

    По сравнению со схемой рис. 3.7. цена уменьшается на единицу (S_Q=15). Однако наличие выходного инвертора приведет к увеличению задержки, T=4t.

Сокращенный булев базис (И, НЕ)

    При использовании этого базиса необходимо из используемого выражения удалить все операции дизъюнкции, заменив их на конъюнкции и отрицания.

    Используя предыдущие преобразования, можно построить схему как с парафазными, так и с однофазными входами.

.

Построим схему с парафазными входами в данном базисе (рис. 3.8).

При построении схемы на элементах базиса (И, НЕ) по МДНФ задержка схемы, в общем случае, составляет Т=4t. А при использовании однофазных входов - Т=5t.

 

Сокращенный булев базис (ИЛИ, НЕ)

При использовании этого базиса необходимо из выражения удалить все операции конъюнкции, заменив их на дизъюнкции и отрицания.

.

Схема в базисе (ИЛИ, НЕ) приведена на рис. 3.9.

 

Универсальный базис (И-НЕ)

Для получения выражения в базисе (И-НЕ) воспользуемся выражением, полученном для базиса (И, НЕ).

Заметим, что цена по Квайну и задержка схемы (рис. 3.10), построенной в базисе (И-НЕ), такие же, как и у схемы, построенной в булевом базисе.

 

Универсальный базис (ИЛИ-НЕ)

 

 

 

 

Цена по Квайну и задержка схемы, построенной в базисе (ИЛИ-НЕ) (рис. 3.11), из-за наличия выходного инвертора больше, чем у схем, построенных в булевом базисе (рис. 3.6) и базисе (И-НЕ) (рис. 3.10).

 

Задача факторизации булевых функций

Факторизация (факторное преобразование) булевой функции сводится к определению общих частей термов и вынесению их за скобки для ДНФ и из скобок для КНФ, что, как правило, приводит к уменьшению цены синтезируемой схемы.

Рассмотрим факторное преобразование булевой функции из примера 3.3.

вынесем из первых двух термов переменные  получим

                                      (1)

можно из исходного выражения сначала из трех термов вынести переменную  

 а затем из первых двух термов переменную

                     (2)

Решение задачи факторизации, приводя к уменьшению цены схемы, увеличивает ее задержку. Для рассмотренного примера S_Q=10, а Т₁=3t и Т₂=5t.

В тех случаях, когда схема синтезируется при ограничении на число входов в элементы, например, равное двум, предпочтение следует отдавать скобочной форме (2).

Построим схему по выражению (1) без ограничений на число входов в элементы (рис. 3.12).

                           

 

 

S_Q=10, T=3t.

 

                                                                          

                                                                                        

                            

 

Построим схему по выражению (1) с ограничением на число входов в элементы, равное двум (рис. 3.13).

 

 

 

S_Q=12, T=3t, К_вх=2.

 

 

Построим схему по выражению (2) с ограничением на число входов в элементы, равное двум (рис. 3.14).

 

 

Схема, построенная по выражению (2) (рис. 3.14), по критерию цены схемы является более предпочтительной по сравнению со схемой (рис. 3.13), а по критерию минимальной задержки - лучше схема (рис. 3.13).

Пример 3.4. Для функции, заданной в МКНФ 

выполним факторное преобразование. Вынесем из первых двух термов дизъюнкцию  можно вынести из всех термов переменную

а затем – переменную  из двух

Оценка эффекта факторизации

Этот эффект характеризуется разностью цен схемы до и после факторизации.

Можно показать, что для однократной факторизации ее эффект определяется выражением:

DS_Q= S_Q^до - S_Q^после=m (k-1) + q - D,

где m - количество букв, выносимых за скобки;

k - количество термов, из которых происходит вынесение;       

q - количество термов, в которых после вынесения осталась одна буква (q£ k);

D=1, если вынесение осуществляется из всех термов;

D=2, если не из всех.

Замечание. Для эффективного решения задачи факторизации необходимо учитывать следующие моменты:

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

2. При минимизации не полностью определенной булевой функции может оказаться, что максимальный эффект за счет факторизации дает нормальная форма, не являющаяся минимальной.

Пример 3.5. Рассмотрим минимизацию функции y = f ⁴(x), которая принимает значение, равное единице на наборах (9, 10, 11) и безразличное значение – на наборах (2, 6, 14) и выполним факторизацию.

Второе покрытие не минимальное, но эффект от факторизации больше.

3. В некоторых случаях максимального эффекта за счет факторизации можно достичь путем расширения термов МНФ с применением законов тавтологии.

Пример 3.6. Выполним факторизацию булевой функции, заданной в МДНФ

    y = x₁x₂x₃Ú x₁x₂x₄Ú x₁x₃x₅x₆Ú x₂x₄x₅x₆=  (S_Q=18), вынесем из первых двух термов конъюнкцию переменных x₁x₂, аз остальных - x₅x₆:

     = x₁x₂(x₃Ú x₄) Ú x₅x₆(x₁x₃Ú x₂x₄)= (S_Q=16), расширим дизъюнктивный терм (x₃Ú x₄) переменными x₁ и x₂:

     = x₁x₂(x₁x₃Ú x₂x₄)Ú x₅x₆(x₁x₃Ú x₂x₄)= (S_Q=20), вынесем общую дизъюнкцию за скобки:

     = (x₁x₃Ú x₂x₄)( x₁x₂Ú x₅x₆)     (S_Q=14).

⇐ Предыдущая891011121314151617Следующая ⇒

Поделиться: