Анализ и синтез на логически схеми
Минимизация на системи от булеви функции
Изтегляне 1.14 Mb.
|
Свързани:
an-architectural-reassessment-of-a-villa-rustica-near-serdica, New Microsoft PowerPoint Presentation, кр цсх
| 2. Минимизация на системи от булеви функции.
Логическите схеми с повече от един изход се описват със система от ЛФ. В случая този преобразувател на n-разряден входен набор в r-разряден изходен набор се описва със система от r логически функции. В общия случай всяка функция зависи от различен брой променливи, но разглеждайки променливите, от които дадена функция не зависи, като несъществени, винаги може да се счита, че всяка функция от системата зависи от всички входни променливи. Оттук и задаването на системата от функции може да се осъществи по всеки от познатите начини, като за всеки набор на входните променливи се записват стойностите на всяка функция от системата. Задачата за най-проста реализация на логическата схема, описвана от система от функции, се различава в някои характерни детайли от описаните дотук решения на тази задача за една единствена функция. Преди всичко възможно е в МДНФ на няколко функции от системата да се среща една и съща импликанта. В съответната схема тази проста импликанта се реализира с единствен логически елемент, чийто изход се използва многократно. (Тук трябва да се следи за непревишаване на коефициента на натоварване по изход на този логически елемент.) По-нататък, като се има предвид тази възможност, в процеса на преобразуване на логическите функции от системата трябва да има стремеж към получаване на повече такива импликанти, които при това принадлежат на възможно по-голям брой функции от системата. Възможни са три различни подхода за реализация на многоизходни схеми, които илюстрират казаното. ПЪРВИ ПОДХОД. За всяка функция от системата, разглеждана самостоятелно, се получава МДНФ. При синтеза на схемата еднаквите импликанти се реализират еднократно. Пример: Зададена е системата от три логически функции: Да се синтезира схемата, реализираща тези функции. Всяка функция поотделно се минимизира чрез карта на Карно. Схемата, синтезирана в базис И-ИЛИ-НЕ, е показана на фиг.3.1. Изходите на елементите, реализиращи импликантите x2x1 и се използват съответно двукратно и трикратно, тъй като x2x1 участва в fa и fb, а участва и в трите функции. ВТОРИ ПОДХОД: Отделя се обща подфункция , която приема стойност 1 за даден набор, само в случай че всички функции приемат стойност 1 за този набор. Всяка функция от системата ще се реализира по следната схема ( фиг.3.2.): Следователно fi* се получава от fi, като наборите, за които Ф приема стойност 1, се считат за неопределени. Намират се МДНФ на Ф и системата от fi* непълни функции за всяка поотделно. Този подход се прилага към разгледания пример. След минимизацията се получава: Схемата, реализираща тези логически изрази, има вида, показан на фиг.3.3. К ато се направи сравнение между схемата на фиг.3.2. и схемата на фиг.3.3., се вижда предимството на втория подход - необходимите за реализация логически елементи са по-малко на брой. Този подход е подходящ, когато функциите се припокриват в значителна степен. Тъй като при разгледаните два подхода за минимизация се използват картите на Карно, то е валидно ограничението, което те налагат за броя на аргументите на логическите функции - този брой не може да надвишава пет. ТРЕТИ ПОДХОД: Системата от функции се опростява като цяло по метода на Куайн-МакКласки. Подходът ще бъде илюстриран със същия пример, както и първите два. Процедурата за минимизиране на система от булеви функции се състои от два етапа: 1) Получаване на множеството от всички възможни многоизходни общи импликанти; 2) Определяне на множеството от минимален брой общи многоизходни прости импликанти за реализиране на системата от функции. Първият етап включва следните стъпки: 1). Образуване на таблицата от всички набори (точки) от аргументи, за които f1, f2,... fm имат единични или неопределени стойности. Пълното множество от тези набори се разделя на подмножества S0, S1,... , Sn, където Si съдържа всички такива набори, в които i на брой променливи имат стойност 1. Всеки набор е съпроводен с признак (функционален идентификатор), който показва кои функции приемат за този набор стойност 1, т.е. на кои функции принадлежи този набор. Например наборът 1100 има признак 110, което означава, че първата и втората функция приемат стойност 1 за този набор. 2 ).Отеделните набори от тази таблица се сравняват, за да се получат класовете S'i, така както при единични функции. В резултат на успешно сравняване се получава нов функционален идентификатор, който представлява поразрядно логическо произведение от функционалните идентификатори на сравняваните набори. Ако се получи нулев функционален идентификатор, то резултатът от сравняването на наборите няма да бъде проста многоизходна импликанта и този ред може да бъде изключен от таблицата. Ако в резултат от успешно сравнение се получи признак, който е идентичен с признака на един от двата или и на двата сравнявани набора, то съответният набор (набори) не се явява проста многоизходна импликанта, отбелязва се с някакъв знак (например v) и по-нататък може да бъде изключен от таблицата. Прилагайки тези правила, се получава таблицата за S'i. 3). Сравняването на наборите продължава, докато е възможно. Наборите, които не са отбелязани, дават множеството от простите многоизходни импликанти. При следващото сравняване на наборите се получава таблицата за S"i. Очевидно е, че в разглеждания пример не е възможно следващо сравняване. Множеството от многоизходни прости импликанти е: - участва във функциите fa, fb, и fc; - участва във функциите fa, fb, и fc; - участва във функциите fa, fb, и fc; - участва във функциите fa и fb; - участва във функциите fb и fc; - участва във функциите fa и fb; - участва във функцията fb. Вторият етап от процедурата се отнася до определянето на минимален брой съществени прости импликанти за реализиране на системата от функции. Като инструмент се използва импликантна матрица. Тя се построява за единичните набори на функциите (включително и за непълно определените функции), при това за всяка функция се отделя група от колонки. За да се постави отметка за покритие, необходимо е импликантата, озаглавяваща реда, освен да покрива даден минтерм и да принадлежи на функцията, в чиято група е този минтерм. Принадлежността на импликантите към дадена функция се определя от функционалния идентификатор. Импликантната матрица се обработва по същия начин, както и при единична функция. За разглеждания пример импликантната матрица има следния вид: За импликантите 11 - 0, - 11 - и 11 - - няма отметки за функцията fc, тъй като те не й принадлежат, съгласно функционалните идентификатори. Импликантите 11 - 1 и 11 - - не принадлежат на функцията fa. От таблицата се вижда, че импликантата 0-10 единствена покрива минтерма 0010, следователно тя задължително трябва да участва в минималната форма на системата от функции и затова се определя като съществена. Тъй като признакът за тази импликанта е 111, то тя ще участва в изразите и за трите функции. Тази импликанта покрива и минтерма 0110, поради което стълбовете на този минтерм отпадат от таблицата. Импликантата 11-0 е съществена за функцията fa, тъй като тя единствена покрива минтерма 1100.Поради това този стълб, а също и стълбът 1110 отпадат от таблицата. Тази импликанта участва и в fb (съгласно функционалния идентификатор) и затова тя може да се определи като съществена и за тази функция. Поради тази причина от таблицата за fb ще отпадне стълбът 1110. Стълбът 1111 за функцията fa се покрива от стълба 0111, поради което стълбът 0111 отпада от таблицата за тази функция. От таблицата за fa остава единствено стълбът 1111, който се покрива от две импликанти: -111 и -11-. Коя от тях ще бъде избрана за съществена, зависи от определянето на съществените импликанти за другите две функции. Импликантата 11-1 единствена покрива стълба 1101 за функцията fc, следователно тя трябва да бъде определена като съществена за тази функция. Поради тази причина от таблицата за fc отпада стълбът 1111. Тази импликанта участва и в fb (съгласно функционалния идентификатор) и може да бъде определена като съществена и за тази функция. Поради тази причина от таблицата за fb отпада стълбът 1111. След отделянето до този момент на съществените прости импликанти и отпадането на стълбовете, които ги покриват, от таблицата на покритията за функцията fa остава единствено стълбът 1111, за функцията fb - стълбът 0111 и за функцията fc - стълбът 0111. Тези стълбове се покриват от различни прости импликанти за всяка функция, но единствената проста импликанта, която участва и в трите функции, е -111, следователно тя трябва да бъде определена като съществена. В резултат се получават следните изрази за системата от логически функции fa, fb и fc: Схемата, реализираща тази функция, има вида, показан на фиг.3.4. Изтегляне 1.14 Mb. Сподели с приятели:
|