Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 68
Текст из файла (страница 68)
4.43(е). При реализации функции на ПЛУ можно считать, что все ее простые импликанты имеют одинаковую стоимость, поскольку ко входам всех вентилей И можно подвести все входные сигналы. В противном случае необходимо отсортировать и разобрать простые имплнканты на группы по числу входов у вентилей И. 5, Находим особенные элементы, равные 1, и включаем в минимальную сумму все существенные простые импликанты второ~о порядка. Здесь, как и выше, существенной простой импликанте второго порядка соответствует строка, содержащая галочку в одном столбце с особенным элементом, равным 1, или в большем числе таких столбцов.
6. Если все оставшиеся столбцы покрываются существенными простыми импликантами второго порядка, как это имеет место на рис. 4.43(е), то задача решена. Если на предыдущем шаге существенные простые импликанты второго порядка не найдены, то мы возвращаемся к шагу 3 и повторяем наши действия. В противном случае необходимо воспользоваться методом ветвления, рассмотренным в разделе 4.3.5. Согласно этому методу берем строки по одной, предполагаем, что выбранная строка является существенной, и рекурсивно выполняем (чертыхаясь) шаги З-б.
Хотя алгоритм отбора простых импликант, основанный на таблице простых им пли кант является довольно простым, необходимая структура данных в соответствующей компьютерной программе колоссальна„так как приходится оперировать с числом битов порядка р . 2", где р — число простых импликант, а и- число битов на входе (предполагается, что заданная функция принимает значение 1 для большинства комбинаций переменных). Хуже всего, что для выполнения шагов, беспечно описанных нами выше в нескольких предложениях, требуются огромные по объему вычисления. '4.4.4. Другие методы минимизации Хотя предыдущие разделы и служат введением в алгоритмы минимизации логических функций, эти методы ни в коем случае не являются самыми новыми и самыми замечательными.
Подталкиваемые все возрастающей плотностью кристаллов СВИС, многие исследователи нашли более эффективные способы минимизации комбинационных логических функций. Их результаты можно отнести, грубо говоря, к одной из трех категорий; 1. Вычислительные усовершенствования. Обычно в улучшенных алгоритмах используются специально приспособленные структуры данных или в другой очередности выполняются шаги, что позволяет снизить требования к памяти и сократить время счета по классическим алгоритмам, 2. Эырисеически«методы. В некоторых случаях задачи минимизации оказываются слишком большими, чтобы их решать, используя «точный» алгоритм.
С 292 Глава 4. Принципы проектирования комбинационных логических схем такими задачами можно пытаться справиться путем сокращений и угадываний, основанных на хорошем знании предмета, результатом чего бывает уменьшение во много рвз объема памяти и времени счета по сравнению с тем, что требует «точный» алгоритм. В противоположность выводу доказуемо минимального выражения для логической функции, эвристическими методами пытаются найти «почти минимальное» выражение. Даже в тех случаях, когда задачу можно решить «точным» методом, эвристический подход часто приводит к лучшему решению, которое оказывается в десятки раз более быстрым.
Самая улачная эвристическая программа Езргеззо-11 справляется с большинством задач, давая минимальный или почти минимальный результат (сводя функцию к одному или к двум термам- произведениям), включая задачи с несколькими десятками переменных и несколькими сотнями термов-произведений. 3. Другой взгляд на вещи. Как упоминалось выше, минимизацию схем с несколькими выходами можно осуществить напрямую методами, которые представляют собой простейшую формальную модификацию методов минимизации схем с одним выходом. Однако, подойдя к задаче минимизации схем со многими выходам н как к задаче многозначной (недвоич ной) логики, авторам алгоритма Езргеззо-МУ удалось достичь значительно лучших результатов по сравнению с Езргеззо-П. Более подробно об этих методах см.
ссылки в Обзоре литературы. *4.5. Паразитные импульсы на выходе логических схем Методы анализа, о которых шла речь в параграфе 4.2, не учитывают задержку в схеме и предсказывают только поведение схемы в установившемся рвжкие (вгеаау-вгагв Ьвйазпаг). Другими словами, эти методы позволяют находить сигнал на выходе схемы как функцшо входных сигналов в предположении, что входные сигналы сохраняют свои значения в течение относительно длительного времени по сравнению с задержками в электронных цепях. Однако в параграфе З.б было объяснено, что в действительности задержка между изменением входного сигнала и соответствующим изменением выходного сигнала у реальной логической схемы не равна нулю и зависит от многих факторов.
Из-за задержек переходной процесс (ггапяепг дейли)аг) в логической схеме может отличаться от того, что предсказывает анализ ее поведения в установившемся режиме. В частности на выходе схемы может возникать короткий импульс (выброс, всплеск), часто называемый паразитным импульсом (г»юкам, д)йсй), тогда как анализ поведения в установившемся режиме предсказывает; что выходной сигнал не должен изменяться. Говорят, что существует источник опасности (Йагагф, когда в схеме может возникать такой паразитны й импульс. Возникает паразитны й импульс в действительности или нет — зависит от точных значений задержек и от других электрических характеристик схемы.
Поскольку этн параметры трудно контролировать в серийном производстве схем, проектировшик должен побеспокоиться об устранении источников опасности (возиолснасти возникновения парвзитного импульса) лаже в том случае, когда сбой может 4.5. Парааитные импульсы на выходе логических схем 293 наступить лишь при наихудшей комбинации логических значений и электрических параметров.
*4.5.1. Статические источники опасности Единичный слоалоичкский источник опасности (згайс-1 йа аЫ) — это возможность возникновения нулевого паразнтного импульса на выходе схемы, когда ожидается — согласно статическому анализу функции, реализуемой этой схемой, что выходной сигнал будет в точности оставаться постоянным и равным 1. Формальное определение состоит в следующем. Олредклеииьч Единичный статический источник опасности — это две комбинации входных сигналов, такие что: (а) при переходе от одной комбинации к другой меняется только один из входных сигналов, (Ь) обе комбинации дают 1 на выходе и возможно кратковременное появление на выходе О в течение переходного процесса, вызванного изменением входного сигнала. Рассмотрим, например, логическую схему, приведенную парис.
4А4(а). Предположим, что оба входных сигнала Х и т равны 1, а 2 изменяется от 1 до О. Тогда временные диаграммы будут такими, как показано на рис. 4А4(Ь), где мы предположили, что задержка распространения в каждом вентиле и ннаерторе равна одному и тому же единичному отрезку времени. Несмотря на то, что «статический» анализ предсказывает наличие 1 на выходе при обеих комбинациях входных сигналов Х, У, Е = 1!1 и Х, У, 2 = 1! О, временные диаграммы показывают, что Г проваливается до О в течение единичного отрезка времени при переходе 2 от 1 до О из-за задержки в инверторе, на выходе которого вырабатывается сигнал Е'. (Ь) о 1 тР о (а) х Ук о хк 0 к о рис.
4.44. Схема с единичным статическим источником опасности: (а) принци- пиальная схема; (Ь) временные диаграммы Нулевой статический источник опасности (лгаг!с-О )оагага) — зто возможность возникновения единичного паразитного импульса, когда ожидается, что на выходе схемы будет постоянный О: Олределеииео Нулевой статический источник опасности — это две соседние комбинации входных сигналов, такие что; (а) при переходе от одной комбинации к другой меняется только один из входных сигналов, (Ь) обе комбинации дают О на выходе н возможно кратковременное появление на выхоле 1 в течение переходного процесса, вызванного изменением входного сигнала.
Поскольку нулевой статический источник опасности является двойственным по отношению к единичному статическому источнику опасности. в схеме или-и 294 Глава 4. Принципы проектирования комбинационных логических слвм двойственной по отношению к схеме, изображенной на рис.4.44(а), имеется нулевой статический источник опасности. Схема ИЛИ-И с четырьмя нулевыми источниками опасности представлена на рис. 4.45(а). Один из источников опасности имеет место тогда, когда Чl, Х, у = 0 „ сигнал х изменяется так, как показано на рис.
4.45(Ь). Вы, по-видимому, сможете сами найти три других источника опасности, а также устранить их все, после того как изучите следующий раздел. (з) (а) г ' а ка о яхта о Рис. 4.45. Схема с нулевыми статическими источниками опасности: (а) принципиальная схема; (Ь) временные диаграммы *4.5.2. Нахождение статических источников опасности по картам Карно Карты Карно позволяют обнаружить статические источники опасности в двухуровневой схеме, реализующей сумму произведений или произведение сумм. Наличие или отсутствие источников опасности зависит от способа реализации заданной логической функции. В правильно построенной двухуровневой схеме И-ИЛИ, реализующей сумму произведений, нет нулевых статических источников опасности. Такой источник опасности существовал бы в схеме указанного вида только в том случае, если бгя на входы одного и того же вентиля И были поданы одновременно и свм входной сигнал и его инверсия, но это было бы глупо.
Однаю в такой схеме могут быть единичные статические испнники опасности. Их существование можно предвидеть, разглядывая карту Карно, где обведены термы-произведения, соответствующие в схеме вентилям И. На рис. 4.46(а) показана карта Карно для схемы, приведенной на рис. 4.44. Из карты следует, что не существует одного терма-произведения, который покрывает обе комбинации переменных Х, у, Е = 111 и Х, у, Л = 110. Таким образом интуитивно ясно, что выходной сигнал может на короткое время «проваливаться» до О, если сигнал на выходе вентиля И, покрывающего одну из комбинации переходит в 0 до того, как сигнал на выходе вентиля И, покрывающего другую комбинацию переменных, переходит в 1.
Способ исключения этого источника опасности очевиден: просто вводим лишний терм-произведение (вентиль И), что бы покрыть опасную пару комбинаций переменных, как показано парне. 4,46("). Оказывается, что лишний терм-произведение является консенсусом (солт«лзвз) двух исходных термов; и в самом общем слУчае для исключения источников опас ности необходимо добавлять консенсусные термы. Соответствующая схема, в которой нет источников опасности, показана на рис.
4.47, 4.5. Паразитные импульсы на выходе логических схем 296 Х (а) х И 1О Х 7' У 7 У 7 г=х 7'+У 7 г =Х 7'+ У 7+Х.У Р с. 4.4б. Карта Карно для схемы, изображенной на рис, 4.44: (а) согласно исой конструкции; ()э) вариант, в котором единичный статический источник опасности устранен У Другой пример приведен парис. 4 48. В этом примере для устранения единичных статических источников опасности необходимо добавить три терма-произведения. (а) Х у' 7' ах (Ь) уг'Х, ОО О1 11 1О а х.у О1 а 7 О1 и х г' х г=х у г -а г+а у г=х у'г+а 7+ау +а"х у'+у г+ а х г Рис 4 49.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
