Анализ и синтез на логически схеми
Проста разделителна (непресичаща се) декомпозиция
Изтегляне 1.14 Mb.
|
Свързани:
an-architectural-reassessment-of-a-villa-rustica-near-serdica, New Microsoft PowerPoint Presentation, кр цсх
| 1. Проста разделителна (непресичаща се) декомпозиция.
Функцията f(x1, x2, ..., xn), допускаща проста разделителна декомпозиция (ПРД), може да бъде записана във вида: f(x1, x2, ..., xn)=Ф2(Ф1(x1, x2, ...xs), (xs+1, ..., xn) Множеството от свързаните аргументи Y се състои от Y={x1, x2, ..., xs}. Множеството от с вободните аргументи Z се състои от Z={xs+1, xs+2, ..., xn}. Сечението на двете множества е празното множество, т.е. те не се пресичат: Представена графично, ПРД за функцията f(x1, x2, ..., xn) изглежда както е показано на фиг.4.1. Предимствата на това представяне на функцията чрез ПРД са очевидни: и Ф1, и Ф2 са функции на по-малко на брой променливи, отколкото f; Ф1 може да бъде реализирана като функционално устройство и евентуално да се използва многократно. Въпросът за ПРД ще бъде изяснен на базата на следния пример: Да се провери за декомпозируемост логическата функция на 4 променливи f=Vm(2,3,6,7,9,11,14,15) Функцията се представя с карта на Карно (фиг.4.2а): Следва разлагане на функцията по Шенон по отношение на x3 и x2. Получава се: От първия ред на картата на Карно, който представлява модифицирана (“изтеглена”) карта за функцията f(0, 0, x1, x0) (фиг. 4.2б), се определя нейната стойност: f(0,0,x1,x0)=x1 Аналогично от втория, четвъртия и третия ред (фиг.4.2в,г,д) се определят: f(0,1,x1,x0)=x1 f(1,0,x1,x0)=x1 f(1,1,x1,x0)=x0 Функциите f(0, 0, x1, x0)=x1, f(0, 1, x1, x0)=x1 и f(1, 0, x1, x0)=x1 могат да бъдат означени като Ф1(x1, x0), а функцията f(1, 1, x1, x0)=x0 - като Ф2(x1, x0). Очевидно не е възможно представяне на функцията f(x3, x2, x1, x0) във вид за ПРД f(x3,x2,x1,x0)=Ф2(Ф1(x1,x0),x3,x2), тъй като бяха определени две различни функции за аргументите x1 и x0, съответно Ф1(x1, x0)=x1 и Ф2(x1, x0)=x0. Следователно за функцията f(x3, x2, x1, x0) не е възможна ПРД относно свободните аргументи x3 и x2. Следва втори опит, при който в качеството на свободни аргументи се и збират x1 и x0. От първия стълб на картата на Карно се определя: От втория стълб се определя: От четвъртия стълб се определя: От третия стълб се определя: Ако функцията се определи като Ф1(x3,x2), а функцията - като , то функцията f(x3, x2, x1, x0) може да бъде представена във вида: т.е. тя допуска ПРД за свободните аргументи x1 и x0. Записът на функцията Ф2(Ф1, x1, x0) представлява нейната СДНФ. Тази функция трябва да бъде минимизирана, за да се синтезира схемата, която ще я реализира. С лед минимизация с картата на Карно се получава: Схемата, реализираща функцията, има структурата, показана на фиг.4.3. Тази схема може да бъде реализирана в произволен базис. Реализацията в базис И-ИЛИ-НЕ е показана на фиг.4.4. Ако функцията бъде определена като , Ф1(x3, x2) а функцията бъде определена като Ф1(x3, x2), то отново е възможно представяне на функцията f(X) във вида: След минимизация се получава Схемата, реализираща тази функция, е показана на фиг.4.5. Може да бъде направено следното обобщение: за да бъде възможна проста разделителна декомпозиция за дадена функция, тя трябва да може да бъде представена във вида където β1(Z) е логическото произведение от свободните аргументи, за което функцията f(X) може да бъде определена като Ф1(Y); β0(Z) е логическото произведение от свободните аргументи, за което функцията f(X) може да бъде определена като ; е логическото произведение от свободните аргументи, за което функцията f(X) може да бъде определена като логическа 1 и βY(Z) е логическото произведение от свободните аргументи, за което функцията f(X) може да бъде определена като логическа 0 . Това правило е дефинирано през 1959г. от сътрудника на Харвардския Университет Ашенхърст. То може да бъде изказано и по друг начин: Проста разделителна декомпозиция от вида f(x1, x2, ..., xn)=Ф2(Ф1(x1, x2, ..., xs), xs+1, ..., xn) е възможна само тогава, когато получените 2n-s подкарти на Карно за свързаните аргументи x1, x2, ..., xs са запълнени по един от следните четири начина: - само с 0; - само с 1; - в съответствие с функцията Ф1; - в съответствие с функцията инверсия на . В случай на непълно определена логическа функция възможностите за декомпозиране трябва да се проверят за всяка от реализиращите я пълни функции, като подкартите на Карно се доопределят така, че да се удовлетворяват изискванията за ПРД. Да проверим допуска ли ПРД следната непълно определена ЛФ: f=Vm(1,2,3,7,14,15)1, Vm(6,10)x Представяме функцията с карта на Карно (фиг.4.6.). П роверките се правят за една, две и т.н. до (n-1) свободни променливи. Започваме с една свободна променлива. 1 ). Нека x3 е свободна променлива. От получените под-карти (фиг.4.7.) се вижда, че нито една от двете под-функции не може да се до-определи така, че да се удо-влетворяват изискванията за декомпозируемост. 2). Нека x2 е свободна променлива. Подкартите са показани на фиг.4.8. Отново е невъзможна ПРД. Правим проверка за декомпозируемост на функцията при два свободни аргумента. 1). Нека x3 и x2 са свободни аргументи. Всички редове на картата на Карно представляват “изтеглени” подкарти за различните стойности на свободните аргументи x3 и x2. Вижда се, че четирите подфункции не могат да бъдат доопределени така, че да удовлетворяват условията за ПРД. 2). Свободни аргументи са x1 и x0. Стълбовете на картата на Карно представляват “изтеглените” подкарти за различните стойности на x1 и x0. Отново е невъзможна ПРД. 3). Свободни аргументи са x3 и x0. Подкартите са следните: Не е възможно доопределяне на подфункциите, което да удовлетворява изискванията за ПРД. 4). Свободни аргументи са x2 и x1. Отново е невъзможна ПРД. 5). Нека x2 и x0 са свободни аргументи. ПРД е невъзможна. 6). Правим проверки при свободни аргументи x3 и x1. Ако и двете неопределени стойности доопределим като 1, можем да приемем, че първата подкарта е запълнена съгласно функцията , втората е запълнена само с единици, третата - само с нули, а четвъртата - съгласно функцията . Условията за декомпозируемост се удовлетворяват, следователно е възможна ПРД от вида f(x3, x2, x1, x0)=Ф2(Ф1(x2, x0), x3, x1), т.е. След минимизация се получава: Схемата, реализираща тази функция, има вида, показан на фиг.4.9. П роцедурата за търсене на ПРД може да бъде обобщена и описана по следния начин: 1).Нанасяне на функцията в карта на Карно. 2).Избиране на свободни аргументи (от един до n-1 на брой). 3).Проверка на подкартите (след доопределяне) за удовлетворяване поне едно от условията за декомпозируемост. 4).Ако условията за декомпозируемост се удовлетворяват, се преминава към т.5)., а иначе към т.2). 5).Запис на получената декомпозирана форма и минимизация. При наличието на достатъчно опит проверките за декомпозируемост до ПРД могат да се извършват върху самата карта на Карно за функцията, без да се извличат подкарти. В общия случай броят на необходимите проверки нараства твърде бързо. Изтегляне 1.14 Mb. Сподели с приятели:
|