Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 67
Текст из файла (страница 67)
*/ Хчогп« С1.е " С2.1) Ечог61 С1Л " С2,1; гегигп( (*ччгвг ичогв() вв Овеоое(хчогпю )) чо16 СовЬ«ве(СОВЕ С1, СОВЕ С2, СОВЕ «Сз) /«совыпев с1 ппв сз пв1пе пьеогеп т1О, епв вгогее вье «/ /* геви11 1п сз. Ьвввпев совь(ппые(сз,сз) 1в хгие. «/ ( сз-ох с1.г ь с2.и; СЗ->1 С1.1 Ь С2,1) *4.4.2. Нахождение простых импликант путем объединения термов-произведений Первый шаг в алгоритме Куина-Мак-Класки состоит в определении всех простых импликант логической функции.
С помощью карт Карно мы делаем это визуально, находя «возможно больший прямоугольный набор единиц». В данном алгоритме это осуществляется систематически путем повторного применения теоремы Т10 для обьединения минтермов, 1-мерных кубов, 2-мерных кубов и т.д.; в результате получаются кубы возможно большей размерности (наименьшие возможные термы-произведения), покрывающие только такие комбинации переменных, для которых значение функции равно! . В табл. 4.9 приведена программа на языке С, реализующая этот алгоритм для функций с числом переменных до 1б.
Для того чтобы оперировать т-мерными кубами, число которых равно МАХ ЧАГ(Я, используются двумерные массивы со))ее1в(1 1з )и сосете(( 1в(1 1з 1. 0-мерные кубы (мннтермы) вводятся пользователем. Начиная с 0-мерных кубов, программа на каждом уровне проверяет все 1иг Опеопе ряске ч) гвх опев, Ь! опав 0) 1 ° (ь-о; ьоих та(в) И (ч Ь 1) опев++1 ч ч»1; геиигп((опев 1)); ? 4.4. Программные методы минимизации 28т /«вехи«пи ггие «1 с1 ппв с2 его 1вепи1оп1. «/ /«Веоигпв игие 11 ч Ьвв е*вои1у опе 1 Ыг. ° / /«Орххп1ххпе гье «реей о( ГЫв гоМ1пе 1в огьмое1 /«епв 1« 1ехх ев еп ехег«1ее Гог иЬе Ьеоаег.
*/ 288 Глава 4. Принципы проекпврования комбинационных логических схем возможные пары кубов и объединяет их, когда это возможно, в кубы следующего уровня. Те кубы, которые объединяются в куб следующего уровня, помечак)тся как «покрытые» [сочеге(]); остающиеся не покрытыми кубы являются простыми импликантами. Табл.
4.9. Программа на языке С, которая находит простые импли канты по алто ритму Куина-Мак-Кваски паве[ив ТВОЕ ааеттпе РА(ЛЕ О аае11ив ИАХ СОВЕБ БО чоха юв1пы ( СОВЕ сиЬев[ИАХ ЧАВЯ+1) [ИАХ СОВЕЯ]; Апс со»атее [ИАХ ЧАВЯ+1] [ИАХ СОВЕБ] ~ тпо ппаСиЬвв[ИАХ ЧАВЯ»1); 1пт ю; /» Чети« ау а 1п вп ю"сиЬв, т.е., ' '1ече1 а. '' «/ 1пс ], к, р; /» 1па1сев тиса сье сиьев от сочегва вггву. »/ СОВЕ СВОРСиЬе~ Апо Хоииа; /» 1птс1а1тае пш«Ьег о1 а-сиЬ«в ас еасЬ 1вче1 а. «/ 1от (в 0; ю<ИАХ ЧАВБ«1; ю»+) пиаеиЬ«всв] = О; /» Веаа в 1мс ог а1псепив (О-сиьвв) вирр11ва ьу сьв ивет, всот1пя сьев»/ /» 1п сье <сьев[0,]] виьвттву, еесс1»Б почет«а[0,]] со Хв1ве тот вась «/ /» атис«та, впа ввсстпя пшисиьев[О] со сье соса] пшвьег оч атпсвпов теаа.
»/ ВеваИщоетав; Чог (ю=с; а<ИАХ ЧАВБ; и«+) /» Оо Хот «11 1еч«1в вхсерт СЬе 1авс '/ тот () О; ]<пшвСиЬевЫ ; ]»+) /» Оо Хот в11 сиЬее вс ив[в Хече1 «/ тот Сс ]+1; Ь<пш«СиЬевЫ; Ь++) /«Оо Хат осЪ«т сиЬев аи СЬ1в Хече1 «/ 11 (Соаьтпиьте(<исав[а) []), Ь [а] [ ])) ( /* Ивть СЬв сиЬев вв сочвгва. »/ сочетеа Ы [)] ТВОЕ; <очес«а[а][Ь) ЧВОЕ; /«Сшив[ив 1псо вв (в+1)-сиье, всоге 1п сварсиье. Соаптпе(сиЬев Ы []], сивое[а] [К], АсеюрсиЬе); Чоипа РА(БЕ; /» Бее хг вв'че Бепегасва сЬтв опе Ьв1оге. »/ Гог (р 0; р<пшиСиЬев[~в+1); р++) (Еяиа1сииев(<сьев[а»1][р],С«арСиЬе)) тоипа ТВОЕ; 11 (! Асс<и)) ( /» Ааа сье печ сиье со сьв пвхс 1«че1. «/ поюсиьев[в«1] пиисиьев[и»1] + 1; сиЬвв(а+1] [исаев»ее[а+8-1) СеарСиЬе; сочвтеа [а+1] [пиаСиЬев [ю+1] -1] ГАЬБЕ; Чот (а=О; ю<ИАХ ЧАВБ; ю++) / Оо тот в11 1«че)в «/ Хат (] 0; )<пиюсиье»Ы; ]++) /* Оо гот в11 сиЬ«в вс сь1» 1ече) */ /» Рг1пс ипсочвтеа сиьев — сьеве вге сье ргтае 1ар11свпсв, »/ тт (!сочетеаЫ [])) РттпсСиЬв(сиЬев[а][]]); 4 4.
Программные методы минимизации 289 Несмотря на то, что программа в табл 4 9 является короткой, опытный программист может загрустить, разглядывая ее структуру. Глубина вложений во внутреннем цикле бог составляет четыре уровня, а число проходов, которые, возможно, необходимо будет выполнить, порядка мдх еРВБ 14РЛ СБВЕБ . Да-да, это показатель степени, а не сноска! Если выбрать величину И~Х СВЕЕВ равной 1000 (это значение в большой степени произвольно, но, в действительности, для многих функций этого может оказаться совсем недостаточно), то внутренний цикл будет выполняться миллиарды и миллиарды раз. Конечно, максимальное число минтермов у функции и переменных равно 2", и поэтому, по всем правилам, следовало бы объявить в программе в табл.
4.9 значение МЛЛ СУВЕЯ равным по меньшей мере 2, чтобы иметь возможность н обработать максимально возможное число 0-мерных кубов. Такое объявление не было бы чрезмерно завышенным. Если у функции и переменных есть терм- произведение, равный одной переменной, то фактически понадобятся 2" ' минтермов, чтобы покрыть этот терм-произведение. На самом деле, и случае больших кубов ситуация еше хуже. Число возможных т мерных подкубов п мерного куба равно (" )х2" и, где биномиальный коэффициент (и )-это число способов, какими можно распределить нули и единицы по остающимся переменным. Для функции 16 переменных худший случай имеет место при т = 5; существует 8 945 664 возможных 5-мерных подкуба 16- мерного куба.
Полное число различных т-мерных подкубов п-мерного куба для всех значений т равно 3". Так что в общем случае программе минимизации может потребоваться гораздо больше памяти, чем это предусмотрено в программе в табл. 4.9. Существует несколько приемов, с помощью которых можно оптимизировать необходимый объем памяти и время счета в программе в табл.
4.9 (см. задачи 4.77-4.80), но их применение дает ничтожный результат по сравнению с непреодолимойй комбинаторной сложностью задачи. Таким образом, даже при теперешних быстрых компьютерах и громадной памяти прямое применение алгоритма Куина-Мак-Класки для нахождения простых импликант обычно бывает ограничено функциями лишь небольшого числа переменных (менее 15-20). *4.4.3. Нахождение минимального покрытия по таблице простых импликант После того как найден список всех простых импликант комбинационной логической функции, наступает второй этап процедуры ее минимизации — выбор минимального подмножества простых импликант, покрывающих все единицы функции.
В алгоритме Купив-Мак-Класки для этого используется двумерный массив, называемый таблицей простых кипликант (ргГте-ппр1ГсапГ ГаЫе). На рис. 4.43(а) приведена небольшая, но показательная таблица простых импликант, возникающая в задаче минимизации логической функции с картой Карно, представленной на рис. 4.35. Каждому минтерму функции соответствует один столбец, а каждой простой им ил и канте — одна строка. Каждый элемент таблицы представляет 290 Глава 4. Принципы пРоектирования комбинационных лотэтческих схем собой бит, равный 1 в том и только в том случае, когда простая импликанта данной строки покрывает м и итеры данного столбца (на рисунке эти элементы отмечены галочкой).
минтирмы (Ь) (а) простые импли канты (е) и, чй, (с) Ри с.4.43.таблицы простых им пли кант; (а) исходная таблица; (Ь) выделение особенных элементов, равных 1, и существенных простых импликант; (с) вид таблицы после исключения существенных простых импликант; (т)) обнаружение перекрываемых строк; (е) таблица с существенной простой импликаитой второго порядка как результат исключения перекрываемых строк Выбор простых импликаит по таблице осуществляется путем последовательного выполнения шагов, аналогичных тем, которые мы совершали в разделе 4.3.5, используя карты Карно: 1.
Находим особенные элементы, равные 1. Их легко найти в таблице, беря столбцы с единственной единицей, как показано парис. 4.43 (Ь). 2. Включаем все существенные простые импликанты в минимальную сумму. Существенной простой импликанте соответствует строка, содержащая галочку в одном столбце с особенным элементом, равным 1, или в большем числе таких столбцов. 3.
Исключаем из рассмотрения существенные простые импликанты и покрываемые ими элементы, равные 1 (минтермы), В таблице это осуществляется вычеркиванием соответствующих строк и столбцов, выделенных цветом на рис. 4.43(Ь). Если остакпся какие-либо строки, в которых нет галочек, то они тоже вычеркиваются; соответствующие прорытые илттиканты являются избылточными (гет(ипт(алг ргтте тир!!сапгк), то есть полностью покрываемыми существенными простыми импликантами.
Остающаяся на этом шаге таблица меньших размеров показана на рис. 4.43(с). 4. Исключаем из рассмотрения все простые импликанты, которые «перекрыва.: ются» другими простыми импликантами с той же или меньшей стоимостьЮ реализации. В таблице это делается путем вычеркивания тех строк, у кото рых отмеченные галочками столбцы образуют подмножество множества, 4.4. Программные методы минимизации 291 столбцов, отмеченных галочками в другой строке; вычеркиваются также все, кроме одной, строки в множестве строк с идентичными наборами столбцов, отмеченных галочками. Этн действия иллюстрируются рисунком (д); в результате этих действий таблица сокращается еше больше и принимает вид, указанный на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
