Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 66
Текст из файла (страница 66)
Существует 2" — п — 1 таких функций. В вашем примере, к счастью, п = 2 и есть только одна функция-произведение Р 6, которую надо рассматривать. На рис. 4.40 повторены карты Карно для функций Е и О и приведена карта Карно для Р. 6; в общем случае карта для т-произведения получается путем операции И над картами всех т его компонент. Простая импликанта схемы со многими выходами (ти1>1р1«-оигриг рште 1тр11сапг) для набора из и функций- это простая импликанта одной из и функций или одной из функций-произведений. Первый шаг минимизации в случае многих выходов состоит в нахождении всех простых импликант схемы со многими выходами. Каждая простая импликанта т-произведения является кандидатом на включение в логические выражения, относящиеся к соответствующим т выходам схемы.
Если бы мы попытались минимизировать набор из 8 функций, мы должны были бы найти простые им пликанты для 2« — 8 — 1 = 247 функций-произведений, а также для 8 заданных функций. Очевидно, что минимизация схемы со многими выходами — занятие не для слабонервных! После того, как простые импликанты схемы со многими выходами найдены, мы пьпаемся упростить задачу, выбирая существенные среди них. Особенной клеткой, содержащей ! (Йюйпди(л)>ей 1-се11), на карте, относящейся к той или иной функции одиночного выхода Г, называется содержащая 1 клетка, которая покрывается точно одной простой импликаитой функции Г или простой импликантой одной из функций-произведений, в которые входит Е На рис. 4.40 особенные клетки, содержащие 1, заштрихованы. Су>и«ственной простой импликантой (ельеп11а1 рлте 1тр11сапг) определенной функции одиночного выхода является простая импликанта, покрывающая особенную клетку, содержащую 1.
Как и в случае минимизации с одним выходом, существенные простые импликанты должны быть включены в решение, обеспечивающее минимальную стоимость реализации. В остающейся части алгоритма речь идет только о клетках, содержащих 1 не покрываемых существенными простыми импликантами. Заключительный этап состоит в выборе минимального набора простых импликант, чтобы покрыть остающиеся клетки, содержащие 1. На этом этапе мы должны рассматривать все п функций одновременно, включая возможность совместного использования одних и тех же компонентов; летали этой процедуры 4.4.
Программные методы минимизации 283 обсуждаются в Обзоре литературы. В примере на рис.4.40(с) мы видим, что су ще- ствует терм-произведение, который покрывает остающиеся клетки, содержащие 1, в Г и О одновременно. (с) „„х 00 01 11 1О о (а) (Ь) 7'1, 0О О1 И 1О 'ЕЕБ). Х' У 7 т ,Д.=Щ). Х' ' У ' 7 е=х т+х' т 7 У 7 т Е=Х У+... ООО1 О 1 '1) )7 хт7 ' 1 — 7 — 1 х 0О О1 И 1О се -Х.г е=х' т+х.т 7 Рис. 4 40. Карты Карно для совокупности, состоящей из двух функций: (а) карты для функций Р и 8; (Ь) карта для 2-произведения Р 6; (с) редуцированные карты для Р и О после исключения существенных простых импликант и покрываемых ими единиц "4.4.
Программные методы минимизации Очевидно, что логическая минимизация может быть очень сложной и запутанной процедурой. При практическом проектировании логических схем вы, вероятнее всего, встретитесь с задачами минимизации двоякого рода, а именно: со случаями функций небольшого числа переменных — с этими случаями вы сможете разобраться сами, пользуясь описанными выше методами, — и с более сложными схемами со многими выходами, в отношении которых вы будете беспомощны, не имея под рукой подходящей программы минимизации. Вы знаете, что в случае функций небольшого числа переменных минимизацию можно осуществить визуально, используя карты Карно.
В этом параграфе мы покажем, что те же самые операции можно производить (по крайней мере, в принципе) в случае функций со сколь угодно большим числом переменных, используя табличный метод, называемый алгоритмом Куина — Мак-Класки Ян(ле— МсС(иЫу а)дог17)вл). Подобно другим алгоритмам, алгоритм Куина — Мак-Класки можно представить в виде программы для компьютера. Как и в методе, основанном на картах Карно, алгоритм выполняется в два шага: (а) нахождение всех простых импликант функции и (Ь) выбор минимального набора простых импликант, который покрывает функцию.
Алгоритм Кунна — Мак-Класки часто описывают в терминах заполняемых вручную таблиц и выполняемых вручную проверок. Поскольку, однаиэ, никто никогда не делает этого вручную, для нас более естественно описать данный алгоритм в терминах структур данных и функций на языке программирования высокого уровня. Цель этого параграфа заключается в том, чтобы дать представление о сложно- 284 Глава 4. Принципы проектирования ковебинационных логических схем сти вычислений, производимых прн решении большой задачи минимизации. Мы рассматриваем только полностью определенные функции для логических схем с одним выходом; задачи с безразличными комбинациями переменных и со многими выходами решаются на основе алгоритмов, являющихся непосредственной модификацией алгоритма, применяемого в случае схем с одним выходом (см, Обзор литературы). '4.4.1.
Предстввлениетермов-произведений Отправным моментом в алгоритме минимизации Куина-Мак-Класки служит таблица истинности или эквивалентный ей список минтермов лля рассматриваемой функции. Если функция задана иначе, то сначала ее необходимо преобразовать в одну из упомянутых форм. Например, в произвольном логическом выражении с и переменными можно разнести множители по слагаемым (возможно, применяя по ходу дела теорему Де Моргана), чтобы придти к выражению вида «сумма произведений». Когда такое выражение получено, каждый терм-произведение с р переменными порождает 2" г минтермов в списке минтермов.
В разделе 4.1.6 было обьяснено, что минтерм логической функции и переменных можно представить в виде и-разрядного двоичного целого числа (номера минтерма), в котором каждый бит указывает, берется ли дополнение соответствующей переменной, или она входит в минтерм непосредственно. Однако алгоритму минимизации приходится иметь дело также с термами-произведениями, которые не являются минтермами, поскольку какие-то переменные в них отсутствуют вовсе. Таким образом, в общем случае мы должны предусмотреть три возможности для каждой переменной в терме-произведении: 1 — переменная входит в терм-произведение непосредственно; Π— переменная входитвтерм-произведениев вндедополнения; х — переменнаяотсутствует втерме-произведении.
Строка из и таких символов служит представлением герма-произведения в виде куба(сиб«гергезешабоп). Если, например, число переменных в терме-произведении может доходить до 8 (Х7, Хб,..., Х1, ХО), то запись термов-произведений в виде кубов имеет вид: Х7' Хб Х5.Х4'.ХЗ Х2 Х1.ХО' и01101110, ХЗ Х2 Х1 ХО' ихххх1110, Х7 Х5' Х4 ХЗ Х2' Х1 и1х01101х, Хб и х1хххххх. Заметьте, что, ради удобства, мы назвали переменные именно так, как бывшот указаны разряды в и-разрядном двоичном целом числе.
Согласно терминологии параграфа 2.14, где были введены и-мерные кубы " т-мерные подкубы, строка 1х01101х представляет собой 2-мерный подкуб 8- мерного куба, а строка 01101110 — О-мерный подкуб 8-мерного куба Однако в литературе по минимизации обычно подразумевается, что максимальная размерность куба или подкуба равна и, и поэтому и-мерный подкуб просто называют «и-мерным кубом» или, для краткости, «кубом»; в данном параграфе мы будем следовать этой традиции. 4.4.
Программные методы минимизации 285 Чтобы задать терм-произведение в компьютерной программе„можно воспользоваться структурой данных с и элементами, каждый нз которых принимает одно из трех возможных значений. На языке С терм-произведение можно описать следующими объявлениями: туредег ешли 1сошр1ешепсед, ппсошр1ешепсе4, доеепсарреагг ТВТТ; Суренея ТЕХТ[161 СОВЕ; /ь Вергевепгв а в1пЕ1е ргодпсг сегш язсЬ пр Со 16 таг1аЬХев */ Однако этн обья ален ля не приводят к сколько-нибудь эффективному внутреннему представлению кубов.
Как мы увидим дальше, с кубами легче манипулировать, используя обычные компьютерные операторы, если терм-произведение с л переменными представлен в программе двумя и-разрядными словами, как это предлагается сделать в следующем примере; «дебзпе МАХ 'тАВВ 16 /«Мвх я оГ тегзаЬТев 1п а ргоппсс сегш */ СурепЕГ ППВ1ЕПЕ4 ВЬОГГ 'ЯОВВ; /Ь ОВЕ 16-Ь1С ЯОГ4В */ всгпсс спЬе ( 'кОВО с; /» Вьсв 1 Тот ппсошр1ешепсеп таг1аЬ1ев.
*/ '«ОВО Т; /» В1св 1 1ог сошр1ешепсел твгзаЬ1ев. */ у! сурепег всгпсс спЬе СОВЕ; СОВЕ Р1, Р2, РЗ; /е А11осасе гпгее спЬев Тот пве Ьу ргойгаш. ь/ Здесь слово ЫОВΠ— зто 16-разрядное двоичное целое; терм-произведение с 1б переменными представлен двумя словами НОВО, как показано на рис, 4.41(а). В первом слове в структуре СОВЕ битом 1 отмечается каждая переменная, входящая в терм-произведение непосредственно [символ с -от «1гце» (нстнна)); во втором слове битом 1 отмечается каждая переменная, входящая в терм-произведение в виде дополнения [символ Š— от «га!зе» (ложь)1.
Если в каком-то определенном разряде стоит 0 в обоих словах НОВО, то соответствующая переменная отсутствует; наличие 1 в одном и том же разряде в обоих словах ЖОЕО не предусматривается. Таким образом, программная переменная Р1 на рис. 4.41(Ь) представляет собой терм-произведение Р! =Х15.Х12' Х10' Х9 Х4' Х! ХО. Прижеланиипредставить логическую функцию Р с числом переменных до 1б, содержашую не более 100 термов-произведений, мы могли бы объявить массив из 100 струкгур СОВЕ: СОВЕ Г[1003; /* Язогайе Тог а Хобзс Зппсе1оп язсЬ пр со 100 ргоппсе сегшв.
«/ Воспользовавшись описанным представлением куба, можно на языке С кратко н эффективно записать функции, оперирующие термами-произведениями обычным образом. В табл. 4.8 приведены несколько таких функций. В соответствии с двумя нз этих функций на рис. 4.42 показано, как можно сравнить два куба и объединить их, если это возможно, согласно теореме Т10: 1епп Х+ 1еггп Х' = 1епп. Эта теорема говорит о том, что два терма-произвеления можно объединить, если онн различаются только в одной переменной, которая в один из термов входит в виде дополнения, а в другой -непосредственно, Объевнча 286 Глава 4. Принцнпы проектирования комбинационных логических ехаял лт-мерных кубов дает(т+ 1)-мерный куб. Используя представление термов-про изведений в виде кубов, можно проиллюстрировать применение теоремы об объединении следующими примерами: 010+ 000 =ОхО, 00111001 ь 00111000 =001!100х, 101ххОхО+ 101хх!хО =101ххххО, х11!хх001! Ох000х+ х!1! хх00010хОООх =х11!х»б)(яг!(55)(Ос (а) 151413 121110 9 8 7 8 5 4 3 2 1 О спввт -В ха еоу»сияет (Ь) 1514131211109978543210 91» Рис.
4.41. Внутреннее представление термов-произведений с числом пере- менных до 16 в программе на языке ОЛ (а) формат в общем случае; (Ь) Р! = Х16 . Х12' Х10' . Х9 Х4' . Х1 . ХО (а) с»: / дА, можно абьединяа Раенм и содер. 1 жн ццну 1 ~ НЕТ, нельзя обьеди- нять сз: с» с сз г кок поразрядная операция ИСКЛЮЧАЮЩЕЕ ИЛИ (Ь) с»: »но = поразрядная логическая операция И Рис. 4.42. Операции с кубами: (а) определение того, можно ли объединить два куба на основании теоремы Т10: 1еггп Х + 1еггп . Х' = 1егпц (Ь) объединение термов по теореме Т10 табл. 4.8. Функции сравнения и объединения кубов, используемые в програм- ме минимизации гвг еч п)сиьев(с(же с), саве с2) ( и«гиги ( (С(З Ся.е) М (С)м — СО.Г) ); 1пе СОвЫПВЬ1е(СОВЕ С1, СОВЕ С2) ( /«ееиигпв хгие 11 с( впа ся О111ег (в оп1у опе чвгхеые, */ ВОЕО гчомг, гчога(; /«чыоь пррееге ггие (п апе епв Ее1ее хп хье огьег.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
