2. Проста неразделителна (пресичаща се) декомпозиция (ПНД).
При неразделителната декомпозиция сечението на множествата на свързаните и свободните аргументи не е празното множество.
YЗZ№0.
Това означава, че някои от аргументите участват и в двете множества.
YЗZ=W.
W={w1, w2, ..., wr} - множество от аргументите, които са едновременно и свободни, и свързани;
X =YUZUW
Функцията f(x1, x2, ..., xn) допуска проста неразделителна декомпозиция във вида:
f(x1,x2,...,xn)=Ф2(Ф1(w1,w2,...,wr,y1,y2,...,yq),w1,w2,...,wr,z1,z2,...,zp)
ако картата на Карно, редовете на която съответстват на комбинациите от стойностите на свързаните променливи w1, w2, ..., wr, y1, y2, ..., yq, може да бъде разделена на подкарти, редовете на които съответстват на комбинациите от стойностите на общите променливи , така че да удовлетворяват условията за ПРД.
С други думи, подкартите се проверяват за ПРД. Ако тя е възможна, възможна е и ПНД.
Представена графично, ПНД за функцията f(x1, x2, ..., xn) изглежда по следния начин (фиг.4.10):
Пример: Да се провери възможна ли е ПНД за функцията
f=Vm(4,7,11,12,15); n=4
Представяме функцията с карта на Карно.
Нека Y={x1, x0}; Z={x3, x2, x0}
Y ЗZ=W={x0}
Построяваме нова карта на Карно, чиито редове са означени с комбинациите от свързаните аргументи, а стълбовете - с комбинациите от свободните аргументи.
На базата на “абсурдните” комбинации (x0=0 и x0=1) се получава карта на непълно определена функция. Трябва да се провери дали тази функция допуска ПРД.
Доопределяме функцията по начина показан на фиг.4.11.
За комбинациите от свободните аргументи x0, x3, x2 - 000, 010 и 100 подкартите са запълнени само с нули. Приемаме, че за останалите комбинации от свободните аргументи - 001, 011, 110, 101 и 111 подкартите са запълнени съгласно функцията . При това доопределяне функцията допуска ПРД, а следователно и ПНД от вида:
Минимизираме тази функция.
Получава се:
Структурната схема, реализираща тази функция, е показана на фиг.4.12., а принципната с хема - на фиг.4.13.
Разбира се, това е един от вариантите за доопределяне на функцията при този избор на свободни и свързани аргументи. Вероятно при друго доопределяне или при избор на други свободни и свързани аргументи би се получил по-добър резултат. Дали това е така, трябва да се провери.
За съжаление не винаги усилията за търсене на декомпозиционни форми на функциите са напълно оправдани. В някои случаи може да се окаже, че МДНФ на функцията се реализира с по-малък разход на логически елементи, отколкото декомпозиционната й форма.
Ако дадена функция не допуска нито ПРД, нито ПНД, се преминава към търсене на многократна (непроста) декомпозиция.
Сподели с приятели: |