Анализ и синтез на логически схеми
Изтегляне 1.14 Mb.
|
Свързани:
an-architectural-reassessment-of-a-villa-rustica-near-serdica, New Microsoft PowerPoint Presentation, кр цсх
- Навигация на страницата:
- 1. Минимизация на единични функции.
| Въпроси и задачи.
1). Какъв е възможният брой съвършени, нормални и минимални форми на една логическа функция? 2). Покажете всички вьзможни начини за реализиране на функцията НЕ в базисите И-НЕ и ИЛИ-НЕ. 3). ИС се характеризират с т.нар. коефициент на натоварване по изход, изразяващ се в максимален брой входове на ЛЕ, които могат да бъдат свързани към изхода на логически елемент от разглежданата схема. Посочете различни начини за преодоляване на ограничението, поставяно от коефициента на натоварване по изход. 4). Реализирайте само с една ИС 7400 (4 двувходови елемента И-НЕ) функцията (сума по модул 2). 5). Да се синтезира КЛС, реализираща логическата функция f(x4,x3,x2,x1,x0)=Vm(0,4,8,9,11,12,13,15,16,18,25,26,27,29,31)1,Vm(2,6,20,22,28,30)* а) в базис И-ИЛИ-НЕ; б) в базис И-НЕ с двувходови елементи; в) в базис И-НЕ с тривходови елементи. Да се анализират отделните реализации. Автор: С. Иванов, Ю. Петкова, С. Каров 3. Минимизация на единични и системи от булеви функции по метода на Куайн-МакКласки1999-03-25 12:24:18+02 Методът за минимизация на логически функции чрез карти на Карно (т. нар. “графичен” метод) е неудобен, когато функцията има повече от пет аргумента. Познати са и други методи за минимизация, които са приложими при по-голям брой логически променливи - метод на Куайн, метод на Нелсон, Харвардски метод, метод на Куайн-МакКласки. Предимствата на тези методи се състоят в това, че те са удобни за машинна обработка, тъй като подлежат на алгоритмизация, а броят на аргументите на функциите е практически неограничен. В настоящото пособие се разглежда методът на Куайн-МакКласки. 1. Минимизация на единични функции. Процедурата за минимизация на ЛФ по метода на Куайн-МакКласки се разделя на два основни етапа: - Първи етап - състои се в едновременната обработка на всички минтерми, влизащи в СДНФ на зададената функция, с цел намирането на пълното множество от простите й импликанти; - Втори етап - състои се в отделянето на съществените прости импликанти (тези, които задължително трябва да участват в записа на функцията) и тяхното обединяване в минимална дизюнктивна нормална форма. Методът е приложим както за напълно определени, така и за непълно определени ЛФ. При минимизиране на непълно определени ЛФ в първия етап освен минтермите участват и т.нар. неопределени минтерми (тези, за които функцията приема неопределена стойност). Това дава възможност да се намери такава съвкупност от прости импликанти, която удовлетворява и действителните, и неопределените минтерми. Във втория етап участват само задължителните импликанти. Процедурата ще бъде разгледана на базата на пример за минимизация на непълно определената логическа функция Първият етап се осъществява, като се изпълнява следната последователност от действия: 1). Функцията се представя в СДНФ. 2). Съставя се таблица на всички единични и неопределени точки на функцията f(x1, x2, ..., xn), разделени на класове S0, S1, ..., Sn където Si е клас с i на брой аргументи, равни на 1 (и с n-i аргументи, които са равни на 0). Под единична (неопределена) точка се разбира набор от стойностите на всички аргументи, за които функцията има стойност 1 (или *). Срещу всеки набор в таблицата се записва съответната стойност на функцията - 1 или *. 3). Сравнява се всеки набор от клас Si с всеки набор от клас Si+1 за всички i в диапазона [0, n-1]. За двойки, различаващи се в наборите по стойността само на една променлива xj , се образуват нови точки (импликанти), обединяващи (покриващи) и двете точки. Новите точки приемат неопределена стойност (-) за променлива xj, като останалите променливи запазват значенията си. Новите точки се отделят в клас S'i, а точките, от които се получават, се отбелязват с някакъв белег, например v. За всяка нова точка в колонката за стойността на функцията се записва 1, ако поне една от точките, участвали в нейното образуване, има единична стойност. В противен случай (когато и за двете точки стойността на функцията е * , т.е. неопределена) неопределена остава стойността на функцията и за новополучената точка. При сравняването на единствената точка от клас S0 с единствената точка от клас S1 се вижда, че те се различават само по стойността на x2. Резултатът е нова точка от клас S'0 0-00 със стойност на функцията за тази точка *. И двете точки, участвали в сравнението и формирали нова точка, се отбелязват с v. След това всеки набор от клас S1 (в случая той е единствен) се сравнява с всеки набор от клас S2. При сравнението на единствения набор от клас S1 с първия набор от клас S2 се вижда, че те се различават само по стойността на x0. Резултатният набор е 010-, а за стойност на функцията се записва 1. И двата набора, участвали в сравнението и формирали нов набор, се отбелязват c v. Следва сравняване на набора от клас S1 с втория набор от клас S2. Tе се различават по стойностите на 3 от аргументите, следователно не могат да формират нов набор. Не се отбелязва нито един от наборите, участвали в това безрезултатно сравнение. Процедурата продължава, докато се извършат всички възможни сравнения. Ако се направи аналогия с процеса на минимизация с карта на Карно, то тази стъпка е еквивалентна на определянето на всички възможни конфигурации от по две съседни клетки със стойност на функцията 1 или *. 4). Стъпка 3 се повтаря за образуване на класовете S"i въз основа на S'i и S'i+1. Променлива с неопределена стойност (-) в сравняваните точки запазва своята неопределеност и в новите точки. На базата на класовете S"i и S"i+1 се образуват класовете S'''i. Процесът продължава, докато е възможно сравняване на точките. В случая следващо сравнение е невъзможно. Ако се направи аналогия с процеса на минимизация с карта на Карно, то тази стъпка е еквивалентна на определянето на всички възможни конфигурации от по 4 (8,16,32,...) съседни клетки със стойност на функцията 1 или *. 5). Точки (импликанти), които не са взели участие в процедурата на сравняване (нямат белег v), а също така се определят със стойност на функцията 1, образуват множеството на простите (главни) импликанти. Самият вид на простите импликанти се оформя като произведение от аргументите за съответната точка, в което променливата се записва без отрицание, ако има стойност 1, с отрицание - при стойност 0 и не се включва в произведението при неопределена стойност. Отделените прости импликанти за разглежданата примерна функция са: От определения пълен набор прости импликанти трябва да бъдат отделени съществените прости импликанти, което е обект на втория етап от процедурата. Ако отново бъде направена аналогия с процеса на минимизация с карти на Карно, то първият етап е еквивалентен на определянето на всички възможно най-големи конфигурации от съседни клетки със стойност на функцията 1 или *. Вторият етап е еквивалентен на определянето на минималния брой от тези конфигурации. Вторият етап на процеса на минимизация по метода на Куайн-МакКласки включва следните стъпки: 1). Построява се т.нар. импликантна матрица (таблица на покритията). Колонките на тази матрица се обозначават с е диничните набори (минтермите) на функцията. Редовете на матрицата се обозначават с определените на първия етап прости импликанти. За всяка проста импликанта във всеки ред се отбелязват минтермите, които тя покрива. 2). Отделяне на съществените прости импликанти, ако е възможно. Ако някакъв минтерм се покрива от една единствена проста импликанта, то тази проста импликанта е съществена. Заедно с нея от таблицата отпадат всички минтерми, които се п окриват от тази съществена проста импликанта. В примера такава импликанта е , която единствена покрива минтерма 0101. Тази импликанта, определена вече като съществена, покрива и минтерма 1100, поради което той отпада от импликантната матрица. 3). Оформя се нова импликантна матрица. 4). Простите импликанти се сравняват по редове. Редът, който се покрива от друг ред, може да бъде изключен от таблицата на покритията. В примера няма редове, които покриват други редове. Простите импликанти се сравняват и по стълбове. Стълб, който покрива друг стълб, може да бъде изключен от импликантната матрица. Ако няколко стълба са идентични, от таблицата на покритията могат да бъдат изключени всички с изключение на един, който и да е той. В примера няма стълбове, които се покриват от други стълбове. 5). Ако изпълнението на стъпка 4 е довело до някаква промяна в импликантната матрица, построява се нова импликантна матрица. 6). Повтарят се стъпки 2, 3, 4, 5, докато това е възможно. В разглеждания пример това не е възможно. 7). Определя се минимално покритие на таблицата, т.е. минималният брой прости импликанти, които заедно покриват всички останали стълбове на матрицата. Възможно е да бъдат получени няколко минимални покрития, което означава, че функцията има няколко равностойни минимални дизюнктивни нормални форми. В разглеждания пример са възможни 4 минимални покрития на таблицата: 8). Записват се всички равностойни МДНФ на функцията, в които участват отделените съществени прости импликанти. В случая те са 4: Изтегляне 1.14 Mb. Сподели с приятели:
|