(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Программные средства foundation обсуждаются в Обзоре литературы. В примере на рис. 4.40(c) мы видим, что существует терм-произведение, который покрывает остающиеся клетки, содержащие 1, в F и G одновременно. X Y I I Z\ 00 01 11 10
х-Y-Z- Y F-G G = X-Y + ...
X Y Z F = X-Y + X-Y-Z X Y 2 u. G = X-Y + X-Y-Z Рис. 4.40. Карты Карно для совокупности, состоящей издвух функций: (а) карты Л/1Я функций F и G; (Ь) карта для 2-произведения F - G; (с) редуцированные карты для F и G после исключения существенных простых импликант и покрываемых ими единиц *4.4. Программные методы минимизации Очевидно, что логическая минимизация может быть очень сложной и запутанной процедурой. При практическом проектировании логических схем вы, вероятнее всего, встретитесь с задачами минимизации двоякого рода, а именно: со случаями функций небольшого числа переменных - с этими случаями вы сможете разобраться сами, пользуясь описаннь[ми выше методами, - и с более сложнь[ми схемами со многими выходами, в отношении которых вы будете беспомощны, не имея под рукой подходящей программы минимизации. Вы знаете, что в случае функций небольшого числа переменных минимизацию можно осуществить визуально, используя карты Карно. В этом параграфе мы покажем, что те же самые операции можно производить (по крайней мере, в принципе) в случае функций со сколь угодно большим числом переменных, используя табличный метод, называемый алгоритмом Куина-Мак-Класки (Quine-McClusky algorithm). Подобно другим алгоритмам, алгоритм Куина-Мак-Класки можно представить в виде программы для компьютера. Как и в методе, основанном на картах Карно, алгоритм выполняется в два шага: (а) нахождение всех простых импликант функции и (Ь) выбор минимального набора простых импликант, который покрывает функцию. Алгоритм Куина-Мак-Класки часто описывают в терминах заполняемых вручную таблиц и выполняемых вручную проверок. Поскольку, однако, никто никогда не делает этого вручную, для нас более естественно описать данный алгоритм в терминах структур данных и функций на языке профаммирования высокого уровня. Цель этого параграфа заключается в том, чтобы дать представление о сложно- сти вычислений, производимых при решении большой задачи минимизации. Мы рассматриваем только полностью определенные функции для логических схем с одним выходом; задачи с безразличными комбинациями переменных и со многими выходами решаются на основе алгоритмов, являющихся непосредственной модификацией алгоритма, применяемого в случае схем с одним выходом (см. Обзор литературы). *4.4.1. Представление термов-произведений Отправным моментом в алгоритме минимизации Куина-Мак-Класки служит таблица истинности или эквивалентный ей список минтермов для рассматриваемой функции. Если функция задана иначе, то сначала ее необходимо преобразовать в одну из упомянутых форм. Например, в произвольном логическом выражении с п переменными можно разнести множители по слагаемым (возможно, применяя по ходу дела теорему Де Моргана), чтобы придти к выражению вида сумма произведений . Когда такое выражение получено, каждый терм-произведение с р переменными порождает 2 минтермов в списке минтермов. В разделе 4.1.6 было обьяснено, что минтерм логической функции п переменных можно представить в виде и-разрядного двоичного целого числа (номера минтерма), в котором каждый бит указывает, берется ли дополнение соответствующей переменной, или она входит в минтерм непосредственно. Однако алгоритму минимизации приходится иметь дело также с термами-произведениями, которые не являются минтермами, поскольку какие-то переменные в них отсутствуют вовсе. Таким образом, в общем случае мы должны предусмотреть три возможности для каждой переменной в терме-произведении: 1 - переменная входит в терм-произведение непосредственно; О - переменная входит в терм-произведение в виде дополнения; X - переменная отсутствует в терме-произведении. Строка из и таких символов служит представлением терма-произведения в виде куба {cube representation). Если, например, число переменных в терме-произведении может доходить до 8 (Х7, Х6.....XI, ХО), то запись термов-произведений в виде кубов имеет вид: Х7Х6Х5Х4ХЗХ2Х1 ХО =01101110, ХЗХ2Х1 ХО =хххх1110, Х7 Х5 Х4 ХЗ Х2 XI s 1x01 lOIx, Х6 =х1хххххх. Заметьте, что, ради удобства, мы назвали переменные именно так, как бывают указаны разряды в и-разрядном двоичном целом числе. Согласно терминологии параграфа 2.14, где были введены и-мерные кубы и /я-мерные подкубы, строка 1x01101 х представляет собой 2-мерный подкуб 8-мерного куба, а строка 01101110 - 0-мерный подкуб 8-мерного куба. Однако в литературе по минимизации обычно подразумевается, что максимальная размерность куба или подкуба равна и, и поэтому /я-мерный подкуб просто называют /я-мерным кубом или, для краткости, кубом ; в данном параграфе мы будем следовать этой традиции. Чтобы задать терм-произведение в компьютерной программе, можно воспользоваться структурой данных с п элементами, каждый из которых принимает одно из трех возможных значений. На языке С терм-произведение можно описать следующими объявлениями: typedef enum {complemented, uncomplemented, doesntappear> TRIT; typedef TRIT[16] CUBE; /* Represents a single product term with up to 16 variables */ Однако эти объявления не приводят к сколько-нибудь эффективному внутреннему представлению кубов. Как мы увидим дальше, с кубами легче манипулировать, используя обычные компьютерные операторы, если терм-произведение с и переменными представлен в программе двумя и-разрядными словами, как это предлагается сделать в следующем примере: #define MAX VARS 16 /* Max # of variables in a product term */ typedef unsigned short WORD; /* Use 16-bit words */ struct cube { WORD t; /* Bits 1 for uncomplemented variables. */ WORD f; /* Bits 1 for complemented variables. */ >; typedef struct cube CUBE; CUBE PI, P2, P3; /* Allocate three cubes for use by program. */ Здесь слово WORD - это 16-разрядное двоичное целое; терм-произведение с 16 переменными представлен двумя словами WORD, как показано на рис. 4.41(a). В первом слове в структуре CUBE битом 1 отмечается каждая переменная, входящая в терм-произведение непосредственно [символ t - от trae (истина)]; во втором слове битом 1 отмечается каждая переменная, входящая в терм-произведение в виде дополнения [символ f - от false (ложь)]. Если в каком-то определенном разряде стоит О в обоих словах WORD, то соответствующая переменная отсутствует; наличие 1 в одном и том же разряде в обоих словах WORD не предусматривается. Таким образом, программная переменная Р1 нарис. 4.41(b) представляет собой терм-произведение Р1 =Х15 Х12 Х10 - Х9 Х4 XI ХО. При желании представить логическую функцию F с числом переменных до 16, содержащую не более 100 термов-произведений, мы могли бы объявить массив из 100 структур CUBE: CUBE F[1003; /* Storage for a logic function with up to 100 product terms. */ Воспользовавшись описанным представлением куба, можно на языке С кратко и эффективно записать функции, оперирующие термами-произведениями обычным образом. В табл. 4.8 приведены несколько таких функций. В соответствии с двумя из этих функций на рис. 4.42 показано, как можно сравнить два куба и объединить их, если это возможно, согласно теореме Т10: term X + term X = term. Эта теорема говорит о том, что два терма-произведения можно объединить, если они различаются только в одной переменной, которая в один из термов входит в виде дополнения, а в другой - непосредственно. Объе линнно и , ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |