(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.9 является короткой, опытный программист может загрустить, разглядывая ее структуру. Глубина вложений во внутреннем цикле for составляет четыре уровня, а число проходов, которые, возможно, необходимо будет выполнить, порядка MAX VARS-MAX CUBES. Да-да, это показатель степени, а не сноска! Если выбрать величину MAX CUBES равной 1000 (это значение в большой степени произвольно, но, в действительности, для многих функций этого может оказаться совсем не достаточно), то внутренний цикл будет выполняться миллиарды и миллиарды раз. Конечно, максимальное число минтермов у функции и переменных равно 2 , и поэтому, по всем правилам, следовало бы объявить в программе в табл. 4.9 значение MAX CUBES равным по меньшей мере 2, чтобы иметь возможность обработать максимально возможное число 0-мерных кубов. Такое объявление не было бы чрезмерно завышенным. Если у функции и переменных есть терм-произведение, равный одной переменной, то фактически понадобятся 2 минтермов, чтобы покрыть этот терм-произведение. На самом деле, в случае больших кубов ситуация еще хуже. Число возможных т-мерных подкубов и-мерного куба равно ()х2 ~ , где биномиальный коэффициент () - это число способов, какими можно распределить нули и единицы по остающимся переменным. Для функции 16 переменных худший случай имеет место при т= 5; существует 8 945 664 возможных 5-мерных подкуба 16-мерного куба. Полное число различных ш-мерных подкубов w-мерного куба для всех значений т равно 3 . Так что в общем случае профамме минимизации может потребоваться гораздо больше памяти, чем это предусмотрено в профамме в табл. 4.9. Существует несколько приемов, с помощью которых можно оптимизировать необходимый объем памяти и время счета в профамме в табл. 4.9 (см. задачи 4.77-4.80), но их применение дает ничтожный результат по сравнению с непреодолимой комбинаторной сложностью задачи. Таким образом, даже при теперешних быстрых компьютерах и фомадной памяти прямое применение алгоритма Куина-Мак-Класки для нахождения простых импликант обычно бывает офани-чено функциями лишь небольшого числа переменных (менее 15-20). *4.4.3. Нахождение минимального покрытия по таблице простых импликант После того как найден список всех простых импликант комбинационной логической функции, наступает второй этап процедуры ее минимизации - выбор минимального подмножества простых импликант, покрывающих все единицы функции. В алгоритме Куина-Мак-Класки для этого используется двумерный массив, называемый таблицей простых импликант {prime-implicant table). На рис. 4.43(a) приведена небольшая, но показательная таблица простых импликант, возникающая в задаче минимизации логической функции с картой Карно, представленной на рис. 4.35. Каждому минтерму функции соответствует один столбец, а каждой простой импликанте - одна строка. Каждый элемент таблицы представляет минтермы
Рис. 4.43.Таблицы простых импликант: (а) исходная таблица; (Ь) выделение особенных элементов, равных 1, и существенных простых импликант; (с) вид таблицы после исключения существенных простых импликант; (d) обнаружение перекрываемых строк; (е) таблица с существенной простой импликантой второго порядка как результат исключения перекрываемых строк Выбор простых импликант по таблице осуществляется путем последовательного выполнения шагов, аналогичных тем, которые мы совершали в разделе 4.3.5, используя картьЕ Карно: 1. Находим особенные элементы, равные 1. Их легко найти в таблице, беря столбцы с единственной единицей, как показано нарис. 4.43 (Ь). 2. Включаем все существенные простые импликанты в минимальную сумму. Существенной простой импликанте соответствует строка, содержащая галочку в одном столбце с особенным элементом, равным 1, или в большем числе таких столбцов. 3. Исключаем из рассмотрения существенные простые импликанты и покрываемые ими элементы, равные 1 (минтермы). В таблице это осуществляется вычеркиванием соответствующих строк и столбцов, выделенных цветом на рис. 4.43(b). Если остаются какие-либо строки, в которых нет галочек, то они тоже вычеркиваются; соответствующие простые импликанты являются избыточными {redundant prime implicants), то есть полностью покрываемыми существенными простыми импликантами. Остающаяся на этом шаге таблица меньших размеров показана на рис. 4.43(c). 4. Исключаем из рассмотрения все простые импликанты, которые перекрываются другими простыми импликантами с той же или меньшей стоимостью реализации. В таблице это делается путем вычеркивания тех строк, у которых отмеченные галочками столбцы образуют подмножество множества, собой бит, равный 1 в том и только в том случае, когда простая импликанта данной строки покрывает минтерм данного столбца (на рисунке эти элементы отмечены галочкой). столбцов, отмеченных галочками в другой строке; вычеркиваются также все, кроме одной, строки в множестве строк с идентичными наборами столбцов, отмеченных галочками. Эти действия иллюстрируются рисунком (d); в результате этих действий таблица сокращается еще больше и принимает вид, указанный на рис. 4.43(e). При реализации функции на ПЛУ можно считать, что все ее простые импликанты имеют одинаковую стоимость, поскольку ко входам всех вентилей И можно подвести все входные сигналы. В противном случае необходимо отсортировать и разобрать простые импликанты на группы по числу входов у вентилей И. 5. Находим особенные элементы, равные 1, и включаем в минимальную сумму все существенные простые импликанты второго порядка. Здесь, как и выше, существенной простой импликанте второго порядка соответствует строка, содержащая галочку в одном столбце с особенным элементом, равным 1, или в большем числе таких столбцов. 6. Если все оставшиеся столбцы покрываются существенными простыми импликантами второго порядка, как это имеет место на рис. 4.43(e), то задача решена. Если на предыдущем шаге существенные простые импликанты второго порядка не найдены, то мы возвращаемся к шагу 3 и повторяем наши действия. В противном случае необходимо воспользоваться методом ветвления, рассмотренным в разделе 4.3.5. Согласно этому методу берем строки по одной, предполагаем, что выбранная строка является существенной, и рекурсивно выполняем (чертыхаясь) шаги З-б. Хотя алгоритм отбора простых импликант, основанный на таблице простых импликант, является довольно простым, необходимая структура данных в соответствующей компьютерной программе колоссальна, так как приходится оперировать с числом битов порядка р 2 , где р - число простых импликант, а п - число битов на входе (предполагается, что заданная функция принимает значение 1 для большинства комбинаций переменных). Хуже всего, что для выполнения шагов, беспечно описанных нами выше в нескольких предложениях, требуются офомные по объему вычисления. *4.4.4. Другие методы минимизации Хотя предыдущие разделы и служат введением в алгоритмы минимизации логических функций, эти методы ни в коем случае не являются самыми новыми и самыми замечательными. Подталкиваемые все возрастающей плотностью кристаллов СБИС, многие исследователи нашли более эффективные способы минимизации комбинационных логических функций. Их результаты можно отнести, Фубо говоря, к одной из трех категорий: 1. Вычислительные усовершенствования. Обычно в улучшенных алгоритмах используются специально приспособленные структуры данных или в другой очередности выполняются шаги, что позволяет снизить требования к памяти и сократить время счета по классическим алгоритмам. 2. Эвристические методы. В некоторых случаях задачи минимизации оказываются слишком большими, чтобы их решать, используя точный алгоритм. С ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |