Синтез схем на элементах типа «НЕ-ИЛИ».

1. Функция задана в ДНФ:

f(x1 x2… xn)=K1+ K2+…+ Km,

здесь Km – элементарные произведения.

Берем двойное отрицание выражения, используем теорему де Моргана и переходим к базису { ↓ }:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Рассмотрим элементарное произведение

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

где ai =x1 или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru ; bi =x2 или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru и т.д.

Такую процедуру следует провести над каждым элементарным произведением, тогда

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Таким образом, чтобы перейти от ДНФ к функции Пирса, необходимо все элементарные произведения заключить в скобки, а затем все знаки дизъюнкции и конъюнкции заменить знаком стрелки Пирса, взять инверсии от всех переменных, заключенных в скобках, и общую инверсию от полученного выражения А записью 0↓А или А↓0. Аналогично все инверсии переменных заменить через выражение Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

При этом следует помнить, что любое произведение в сходном выражении должно содержать не менее двух переменных. Это можно получить с помощью соотношения Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

Пример.

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

2. Функция задана в КНФ:

f(x1 x2… xn)=Q1+ Q2+…+ Qm,

здесь Qi – элементарные суммы.

Берем двойное отрицание от каждой суммы

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Рассмотрим элементарную сумму

Qi= ai +bi …+li,

где ai = x1 или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru ; bi = x2 или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru и т.д.

Отсюда f(x1 x2… xn)= Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Таким образом, чтобы перейти от КНФ к функции Пирса, следует заключить в скобки все элементарные суммы, затем все знаки дизъюнкции и конъюнкции заменить знаком стрелка Пирса и выразить инверсные переменные через операцию стрелка Пирса:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

При этом следует помнить, что каждая элементарная сумма исходного выражения должна иметь не менее двух переменных, что можно получить с помощью соотношения

A=A+0 или A=A+A.

Пример.

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

3. После получения записи исходной функции в базисе {↓} перед построением структурной схемы следует рассмотреть возможность упрощения схемы за счет группировки скобочных выражений по следующим правилам:

а) Если несколько выражений, заключенных в скобках, содержат в общих для них переменных по одной переменной с инверсией, то эти инверсные переменные можно образовать на одном элементе.

Пример.

[A↓(B↓0) ↓C] ↓ [A↓B↓(C↓0)]=[A↓C↓(B↓C)] ↓ [A↓B↓(B↓C)].

б) Если несколько выражений, заключенных в скобки, содержат по одной инверсной переменной не в общих для них переменных, то эти инверсные переменные можно организовать на одном элементе.

Пример.

[A↓B↓(C↓0)] ↓ [A↓B↓(D↓0)]= ↓[A↓B↓(C↓D)] ↓ 0.

Справедливость записей правил группировки можно проверить преобразованиями в системе { ↓ }. При этом оба правила могут быть применены и одновременно.

4. Последним этапом синтеза является составление структурной схемы на элементах «ИЛИ-НЕ».

Пример. Составить структурную схему на элементах «ИЛИ-НЕ», реализующую функцию

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

1. Проводим преобразования исходя из ДНФ заданной функции:

а) построим схему по заданной ДНФ:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

б) построим схему исходя из МДНФ заданной функции:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

Используя второе правило группировки, получаем

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Для данной функции минимизации ДНФ позволила значительно упростить схему, однако это справедливо не для всех функций (рис. 2.2,а).

2. Чтобы определить минимальную структурную схему, проведем аналогичные преобразования в КНФ

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

в МКНФ

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru Таким образом, МКНФ (ABC) позволила получить минимальную структурную схему (рис. 2.2,б).

Рис. 2.2

Синтез схем на элементах типа «И-НЕ» (А|B).

1. Функция задана в ДНФ

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru Каждое элементарное произведение

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Отсюда имеем

f(x1 x2… xn)=( x1 |x2 |…| xk )|(x1 |x2|…| xn )|…|(x1 |x2|…|xl ).

Таким образом, чтобы от ДНФ перейти к базису { | }, надо заключить в скобки все элементарные произведения, заменить все знаки дизъюнкции и конъюнкции на знак операции Шеффера и записать инверсные переменные через операции Шеффера, пользуясь соотношением Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

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

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

Пример.

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

2. Функция задана в КНФ

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Каждая элементарная сумма

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Таким образом, имеем

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Для того чтобы переключательную функцию, записанную в КНФ, выразить в базисе {|}, необходимо заключить в скобки все конъюнктивные члены, заменить все знаки конъюнкции на знак операции Шеффера, взяв инверсию от каждой переменной и от выражения в целом. И выразить все инверсии через операцию Шеффера, пользуясь соотношениями Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru или Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

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

А=А+0.

Пример.

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

3. После получения записи исходной функции в базисе {|} перед построением структурной схемы следует рассмотреть возможность упрощения схемы за счет группировки скобочных выражений по следующим правилам.

1) Если несколько выражений, заключенных в скобках, содержат в общих для них переменных по одной переменной с инверсией, то эти инверсные переменные можно образовать на одном элементе.

Пример.

f(ABC)=1 | [A|(B|B)|C] | [A|B|(C|C)]=1 | [A|C|(B|C)] | [A|B|(B|C)].

а) Если несколько выражений, заключенных в скобках, содержат по одной инверсной переменной не в общих для них переменных, то эти инверсные переменные можно образовать на одном элементе.

Пример.

f’(ABCD)=1 | {[A|B|(C|C)] | [A|B|(D|D)]}=1 | {A|B|(C|D)}.

4.Последним этапом синтеза является составление структурной схемы на элементах «И-НЕ».

Пример. Построить схему на элементах «И-НЕ», реализующую функцию

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

1. Используем заданную ДНФ функции (она является минимальной)

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

2. Воспользуемся МКНФ исходной функции

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru имеет две МКНФ;

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Перейдем к базису {|}:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Все формы дали одинаково сложные структурные схемы.

Пример. Составить структурную схему на элементах типа «ИЛИ-НЕ», реализующую функцию

f(ABCD)=m0+ m2+ m4+ m5+ m6+ m7+ m10+ m11+ m13+ m14+ m15.

1. МДНФ исходной функции определим с помощью карты Вейча:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

2. Сокращенную конъюнктивную нормальную форму исходной функции определяем также с помощью карты Вейча обратной функции.

Из карты обратной функции следует, что сокращенная

ДНФ: Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Группировка обязательных импликант Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru и Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru дает общий элемент (A↓D).

Минимальные конъюнктивные формы дадут еще элементы (D↓D) или (С↓С).

В сокращенной форме обе необязательные импликанты дадут общий элемент (А↓D):

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Требуется 5 элементов типа «ИЛИ-НЕ».

Пример. Составить структурную схему на элементах типа «И-НЕ», реализующую функцию:

f(ABCD)=m5+m10+ m12+ m13+ m14.

1. Находим простые импликанты функции, используя метод Квайна:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Таблица 2.1

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Из табл.2.1 следует, что Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru и Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru - обязательные импликанты функции.

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Рассматриваем возможность группировки простых импликант с целью уменьшения числа элементов «И-НЕ» в структурной схеме.

1-я форма МДНФ. Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

Импликанты Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru и Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru объединяются по правилу 1, а Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru не объединяется с ними:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

Из полученного выражения видно, что для реализации этой функции необходимо 6 элементов «И-НЕ».

То же самое проводим для 2-й формы МДНФ:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

Однако число элементов «И-НЕ» в структурной схеме можно уменьшить, если вместо МДНФ функции использовать сокращенную ДНФ ее, т.е. ввести в выражение ДНФ функции обе необязательные импликанты:

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru .

Требуется 5 элементов (рис.3).

2. Определим МКНФ функции с помощью обратной функции:

f(ABCD)=m0+ m1+m2+ m3+m4+ m6+ m7+ m8+ m9+ m11+ m15;

Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru Синтез схем на элементах типа «НЕ-ИЛИ». - student2.ru

.

Рис.2.3

Наши рекомендации