Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по проектированию цифровых устройств - файл 2а_минимизация.doc


Лекции по проектированию цифровых устройств
скачать (813.3 kb.)

Доступные файлы (11):

1_Основы алгебры логики.doc188kb.08.07.2004 05:33скачать
2а_минимизация.doc519kb.08.07.2004 06:16скачать
2_Проектиров цифр устр.doc174kb.08.07.2004 05:41скачать
3a_применение мультиплексоров.doc287kb.01.12.2001 00:22скачать
3b_Cумматоры.doc176kb.08.07.2004 05:53скачать
3c_интегральные сумматоры.doc202kb.08.07.2004 05:59скачать
3_Типовые комбинационные устройства.doc242kb.08.07.2004 06:25скачать
4_Интегральные триггеры.doc388kb.08.07.2004 06:04скачать
5_задержки в цифровых цепях.doc100kb.01.09.2004 20:00скачать
6_Проектир последоват схем.doc276kb.14.01.2007 17:22скачать
ПЦУ_программа_2002.doc111kb.01.09.2004 20:07скачать

2а_минимизация.doc



МИНИМИЗАЦИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ
Минимизация функций алгебры логики (ФАЛ) – это процедура нахождения наиболее простого представления ФАЛ в виде суперпозиции функций, составляющих функционально полную систему, при одновременной оптимизации ее технической реализации по некоторым критериям в условиях ряда ограничений. Критериями оптимизации могут быть объем оборудования (количество вентилей, корпусов), габариты, вес, энергопотребление, стоимость, быстродействие, надежность. В качестве ограничений могут выступать допустимые к использованию системы элементов, число элементов в корпусе, коэффициенты объединения по входу и разветвления по выходу логических элементов, необходимость реализации системы ФАЛ, а также ряд перечисленных выше критериев оптимизации.

Решение задачи минимизации ФАЛ в полном объеме является трудной проблемой, хотя бы потому, что ряд критериев оптимизации находятся в противоречивом отношении друг к другу, например, одновременное снижение энергопотребления и повышение быстродействия. На практике обычно решается задача оптимизации по нескольким или даже одному из критериев. Наиболее часто это делается по минимуму необходимого числа базовых логических элементов И, ИЛИ, НЕ, так как при этом в большинстве случаев удовлетворяются требования получения минимальных габаритов, веса, энергопотребления, стоимости, а также повышения быстродействия и надежности. Иногда ограничиваются еще более простой задачей представления ФАЛ в дизъюнктивной или конъюнктивной форме, содержащей наименьшее возможное число букв, когда, например, для дизъюнктивных форм, в выражении присутствует как можно меньше слагаемых, являющихся элементарными произведениями, которые в свою очередь содержат как можно меньше сомножителей. Такую задачу принято называть канонической задачей минимизации ФАЛ.


Таблица 1.

наб.


x2

x1

x0

y

0

0

0

0

0

1

0

0

1

1

2

0

1

0

0

3

0

1

1

1

4

1

0

0

1

5

1

0

1

1

6

1

1

0

1

7

1

1

1

0


Пример. ФАЛ, заданную таблицей истинности (табл. 1), можно представить следующими выражениями

(1)

(2)

(3)

(4)
В выражении (1), записанном в СДНФ, пять слагаемых по три буквы в каждом, а всего 15 букв и три инвертора, в то время как в выражении (2) три слагаемых по две буквы в каждом, а всего 6 букв и три инвертора. Выражение (2) является минимальной дизъюнктивной формой для данной ФАЛ.

В выражении (3), записанном в СКНФ, три сомножителя по три буквы в каждом, а всего 9 букв и три инвертора, в то время как в выражении (4) два сомножителя по две и три буквы, а всего 5 букв и три инвертора. Выражение (4) является минимальной конъюнктивной формой для данной ФАЛ.

Применяя скобочные формы и формы с групповыми инверсиями, выражения (2) и (4) можно еще упростить:

(5)

где 5 букв и два инвертора.

(6)

где 5 букв и один инвертор.
В настоящее время в теории проектирования логических схем наиболее полно исследованы именно задачи минимизации дизъюнктивных и конъюнктивных нормальных форм, обеспечивающих рациональное решение при синтезе комбинационных схем, на входах которых доступны как переменные, так и их инверсии. Парафазное представление переменных легко обеспечивается, если они снимаются с выходов триггеров, используемых в качестве запоминающих ячеек разрабатываемых цифровых устройств.

Справедливости ради надо отметить, что сформулированная выше задача минимизации ФАЛ являлась чрезвычайно актуальной в тот период времени, когда разработка цифровых устройств велась на электромеханических переключательных элементах, дискретных радиокомпонентах и интегральных схемах малой степени интеграции.

Достигнутые в настоящее время схемотехнологические успехи в микроэлектроники, в частности создание схем средней, большой и сверхбольшой интеграции, таких как мультиплексоры, постоянные запоминающие устройства (ПЗУ), программируемые логические матрицы (ПЛМ) и другие разновидности программируемых логических интегральных схем, позволяют реализовать очень сложные системы ФАЛ практически, используя один корпус без каких-либо процедур минимизации.
Пример. Используя ПЗУ типа КР556РТ16 или К1623РТ2 с организацией 8К8, можно реализовать систему восьми ФАЛ, зависящих от 13 переменных.
Учитывая, что такие БИС дороги, требуют сложной аппаратно-програмной поддержки для их программирования, а очень часто в инженерной практике решаются более простые задачи, рассмотрим вопросы минимизации ФАЛ, остановившись на некоторых, нашедших наибольшее распространение, методах минимизации ФАЛ.

К настоящему времени широкое применение получили:

1. Расчетный метод (метод непосредственных преобразований).

2. Расчетно-табличный метод (метод Квайна-Мак Класки).

3. Метод Петрика (развитие метода Квайна-Мак Класки).

4. Табличный метод (карты Карно).

5. Метод гиперкубов.

6. Метод факторизации.

7. Метод функциональной декомпозиции и др.

Первый метод применяется при числе переменных n <= 3 и основан на использовании операций склеивания, поглощения и развертывания [1, 2]. Ниже он будет рассмотрен подробно.

Второй и третий методы используются при n 16 в профессиональных разработках и ориентированы на использование САПР с применением ЭВМ [3 - 8]. Здесь они рассматриваться не будут. Четвертый метод является самым распространенным инженерным методом минимизации ФАЛ для n 6 и будет подробно рассмотрен.

Шестой метод не имеет каких-либо существенных достижений при решении общих задач, более простых, чем метод перебора всех формул ФАЛ даже для n = 3. Практически он используется для уменьшения сложности минимальных ДНФ и КНФ, полученных с использованием первого или четвертого методов. Он основан на использовании скобочных форм и форм с групповыми инверсиями [3, 4, 8].

Седьмой метод основан на представлении ФАЛ, зависящей от n переменных, в виде суперпозиций функций, зависящих от меньшего числа переменных, для которых можно применить выше перечисленные методы и здесь не рассматривается [5, 7].
Исходной формой для большинства методов являются либо таблица истинности, либо одна из совершенных форм СДНФ или СКНФ. Если ФАЛ задана в другом виде, то предполагается, что она сначала переводится в СДНФ или СКНФ с использованием основных законов булевой алгебры [1, 2]. Далее будут рассмотрены методы минимизации ФАЛ, представленной в СДНФ.

При выполнении процедур канонической минимизации большую роль играют понятия импликанты и простой импликанты ФАЛ.

Булева функция называется импликантой булевой функции , если на любом наборе значений переменных , на котором значение функции ‘Z’ равно 1, значение функции ‘Y’ также равно 1.

Простой импликантой функции ‘y’ называется всякое элементарное произведение , являющееся импликантой функции ‘Y’ и такое, что никакая его собственная часть (то есть произведение, полученное из произведения ‘Z’ выбрасыванием одного или нескольких сомножителей ) уже не является импликантой функции ‘y’. Так как в дальнейшем будут использоваться только простые импликанты, опустим слово “простые”, то есть если в тексте встречается понятие “импликанта”, то надо помнить, что имеется в виду “простая импликанта”.
В общем случае минимизация ФАЛ, заданной в СДНФ, требует выполнения процедур следующих трех этапов:

^ 1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами которой являются изолированные (несклеивающиеся) элементарные произведения. Этот этап основан на выполнении всех возможных склеиваний друг с другом сначала конституент единицы, а затем произведений меньшего ранга (импликант). Отметим, что существуют ФАЛ, у которых СДНФ совпадает с СокрДНФ.

^ 2 этап - переход от СокрДНФ к тупиковой ДНФ (ТДНФ). ТДНФ - это форма ФАЛ, членами которой являются импликанты, среди которых нет ни одной лишней. Лишней импликантой называется член ФАЛ, удаление которого из выражения не изменяет ФАЛ. Отметим, что возможны случаи, когда в СокрДНФ нет лишних импликант. Иногда из одной СокрДНФ можно получить несколько различных ТДНФ. Термин “тупиковая” говорит о том, что дальнейшая минимизация в рамках нормальных форм уже невозможна.

3 этап - переход от ТДНФ к минимальной форме. Этот этап основывается на использовании групповых инверсий и скобочных форм, не является систематическим и во многом определяется опытом разработчика.
^

РАСЧЕТНЫЙ МЕТОД


Пусть нам требуется минимизировать ФАЛ, заданную выражением (1).

1 этап. Выполняем операции склеивания конституент единицы. Для упорядочения этой процедуры запишем выражение (1) в виде нескольких строк по следующему правилу: первая строка - это исходное уравнение, вторая строка - это вторая конституента и все последующие, третья строка - это третья конституента и все последующие и т.д. Это допустимо, так как в булевой алгебре действует закон тавтологии.
(7)
Производится проверка на склеивание первого члена в каждой строке со всеми остальными в данной строке. В первой строке склеиваются первая и третья конституенты, во второй строке -первая со второй и четвертой, в третьей строке первая конституента с остальными не склеивается, и в последней строке конституенты склеиваются. Поскольку все конституенты участвовали хотя бы в одном склеивании, то в СокрДНФ ни одной конституенты не будет. После этой процедуры получаем следующее выражение:

(8)

Дальнейшее склеивание не может быть выполнено, так как все члены выражения (8) являются изолированными.

2 этап. Необходимо выявить лишние импликанты в выражении (8). Это можно сделать двумя способами. При первом способе развертывают одну импликанту до конституент единицы, а затем смотрят, не поглощаются ли эти конституенты остальными импликантами. Первая импликанта развертывается до суммы

,

причем конституента не поглощается ни одной импликантой, следовательно, импликанта не является лишней. Вторая импликанта развертывается до суммы , причем обе конституенты поглощаются остальными импликантами, следовательно, импликанта лишняя. Продолжим эту процедуру, оставив пока импликанту в выражении (8). Импликанта развертывается до суммы , причем обе конституенты поглощаются остальными импликантами, следовательно, импликанта лишняя. Продолжим, оставив в выражении (8) и эту импликанту. Развертывание последней импликанты дает сумму , в которой конституента не поглощается ни одной импликантой, следовательно, импликанта не является лишней. Выявлены две лишнии импликанты, но это не значит, что обе они могут быть отброшены, так как каждая из них проверялась при вхождении второй в выражение (8). Следовательно, отбросить наверняка можно одну из них, а затем снова произвести проверку возможности отбросить и другую. Если отбросить импликанту , то проверка показывает, что импликанта не будет лишней, а если отбросить , то не будет лишней. Итак, можно отбросить одну из выявленных двух импликант и в результате получаются две ТДНФ одинаковой сложности, содержащих по шесть букв:
(9)

(10)
3 этап. Выражение (9) можно записать в виде

(11)

Оно содержит пять букв и требует три инвертора. Применив закон двойного отрицания и правило де-Моргана, выражение (11) можно преобразовать:

(12)

Последнее выражение содержит пять букв и требует два инвертора.

Аналогично можно упростить и выражение (10):

(13)
Второй способ выявления лишних импликант заключается в следующем. На значение истинности функции влияет только та импликанта, которая сама равна 1. Любая импликанта принимает значение 1 только на одном наборе своих аргументов. Но если именно на этом наборе сумма остальных импликант также обращается в 1, то рассматриваемая импликанта не влияет на значение истинности функции даже в этом единственном случае, то есть является лишней.

Применим это правило к выражению (8). Импликанта принимает значение 1 на наборе , . Подставив этот набор в оставшуюся сумму , получим , что говорит о том, что первая импликанта не является лишней. Импликанта принимает значение 1 на наборе , . Подставив этот набор в сумму , получим , что говорит о том, что импликанта лишняя.

Оставим пока эту импликанту и продолжим анализ других импликант. Импликанта принимает значение 1 на наборе , . Подставив этот набор в сумму , получим , что говорит о том, что импликанта лишняя.

Оставляем и ее и продолжаем процедуру. Импликанта принимает значение 1 на наборе, . Подставив этот набор в сумму , получаем , что говорит о том, что импликанта не является лишней.

Как и в первом случае нельзя отбрасывать обе обнаруженные лишние импликанты, так как каждая из них проверялась при вхождении второй в оставшуюся сумму. Опустим рассмотрение дальнейших процедур, так как они аналогичны процедурам, выполненным первым способом.

Можно сделать вывод, что даже для этого простого примера пришлось выполнять достаточно много однообразных действий, требующих внимания и времени, поэтому расчетный метод минимизации ФАЛ применяется в основном для ФАЛ, зависящих от двух или трех переменных.
^ ТАБЛИЧНЫЙ МЕТОД
При этом методе два первых этапа выполняются при помощи специальных карт, впервые предложенных Вейтчем [9] и модернизированных карт Карно [10]. Практическое применение получили именно карты Карно, а не диаграммы Вейтча, и хотя с момента опубликования их оригинальных работ прошло 45 лет, до сих пор многие авторы называют карты Карно диаграммами Вейтча.

Поскольку работы [9] и [10] являются библиографическими редкостями, так как их можно найти только в крупнейших библиотеках, приведем цитату из работы [3]: “Матрица Вейтча отличается от матрицы Карно расположением столбцов и строк. В то время как Карно пользуется циклическим порядком следования символов, а именно 00, 01, 11, 10, Вейтч располагает символы в порядке возрастания двоичных чисел, а именно 00, 01, 10, 11. Столбцы или строки 00 и 01, так же как столбцы или строки 10 и 11, являются в матрице Вейтча соседними, но столбцы или строки 01 и 10 в ней не являются ни соседними, ни крайними. Хотя матрица Вейтча и обладает некоторыми преимуществами по сравнению с алгебраическими методами, матрица Карно более удобна в обращении и не требует столь большой затраты времени”. Итак, табличный метод минимизации ФАЛ это метод, основанный на использовании карт Карно.

Карта Карно является специальной формой таблицы истинности ФАЛ, позволяющей не только задать ФАЛ, но и выполнить первый и второй этапы минимизации. Таблица истинности (см. табл. 1) содержит 2n строк, в которых наборы n переменных расположены в линейной лексикографической последовательности, а также столбец значений ФАЛ на этих наборах. Напомним, что в таблице истинности переменные с большим весом располагаются на левой позиции набора.



Таблица 1.

наб.


x2

x1

x0

y

0

0

0

0

0

1

0

0

1

1

2

0

1

0

0

3

0

1

1

1

4

1

0

0

1

5

1

0

1

1

6

1

1

0

1

7

1

1

1

0

Карта Карно содержит 2n клеток (квадратов), расположенных в виде строки (n = 1, 2), либо в виде двумерной матрицы (n ≥ 2). Каждая клетка, как и строка в таблице истинности, соответствует одному набору. Для того, чтобы можно было производить минимизацию ФАЛ, необходимо в смежных в геометрическом смысле клетках карты расположить соседние наборы. Это можно обеспечить, если наборы переменных, определяющих “координаты” клетки карты Карно, расположить в циклическом коде Грея, у которого каждое следующее значение отличается от предыдущего только в одном разряде.

На рис. 1 представлена так называемая эталонная карта Карно для n = 3. Она служит для указания расположения переменных, как координат клеток, так и наборов этих переменных. Координатой клеток в горизонтальном направлении служат наборы переменных, а координатой клеток в вертикальном направлении служит одна переменная .


^ Рис. 1. Эталонная карта Карно для n = 3.



Известно, что каждая из n переменных встречается в половине наборов без инверсии, а в другой половине с инверсией. Три толстые линии, расположенные с внешней стороны карты Карно, указывают, что в соответствующих им половинах клеток указанная рядом с этой линией переменная встречается в наборе без инверсии и, соответственно, в другой половине с инверсией. Так как переменным, , , условно присваиваются “веса” соответственно 20 = 1, 21 = 2 и 22 = 4, то восемь наборов в клетках карты Карно будут расположены так, как указано на рис.1. Итак, расположение переменных как координат клеток карты Карно и номеров наборов в эталонной карте должны строго соответствовать друг другу. Можно произвольно поменять местами переменные , , , но тогда обязательно надо поменять местами и расположение наборов.

Правильность оформления эталонной карты Карно можно проверить следующим образом. Если толстую линию, соответствующую переменной протянуть вправо по горизонтали над клетками карты Карно, то она пройдет над клетками, в которых минимальный номер набора должен совпадать с весом переменной , равным 22 = 4. Аналогично толстая линия, соответствующая переменной , при перемещении вниз по вертикали пройдет над клетками, в которых минимальный номер набора должен совпадать с весом переменной , равным 21 = 2. Это должно выполняться для всех переменных.

Несмотря на то, что карты Карно изображаются на плоскости, с точки зрения обеспечения соседства их клеток карты нужно считать трехмерными объектами, так как клетки, расположенные на концах одних и тех же строк и столбцов, также являются соседними. Так карту для трех переменных следует рассматривать как цилиндр со склеенными правым и левым краями. Карту Карно для четырех переменных (см. рис. 4,а) нужно считать склеенной не только по правому и левому краям, но и по верхнему и нижнему. Таким образом, карта Карно для четырех переменных должна рассматриваться как поверхность тора.

Рабочая карта Карно, соответствующая табл.1, будет иметь вид, представленный на рис. 2.

Рис. 2. Рабочая карта Карно для ФАЛ, заданной табл. 1



Буква y рядом с косой линией, расположенной в левом верхнем углу карты Карно, обозначает реализуемую функцию, а цифры 0 и 1 в клетках карты указывают значения этой функции на соответствующих наборах. Полученную рабочую карту Карно можно интерпретировать как компактное представление ФАЛ в СДНФ (по значениям истинности), либо в СКНФ (по значениям ложности). Дальнейшее изложение ведется в предположении, что минимизация ведется в дизъюнктивных формах.

Процесс минимизации с помощью карт Карно базируется на использовании операции склеивания и основан на следующих положениях:

  1. На картах Карно необходимо выделить монолитные области единичных клеток, образующих строку, столбец, прямоугольник или квадрат и содержащие одну, две, четыре, восемь и т. д. клеток. Эти выделенные области (или контуры покрытия) будут соответствовать импликантам. Очевидно, что одна изолированная 1-я клетка будет соответствовать конституенте единицы. Две смежные клетки будут соответствовать импликанте, ранг которой r = n - 1, четыре смежные клетки будут соответствовать импликанте, ранг которой r = n - 2 и т.д.

  2. Переменные, от которых импликанта не зависит, входят в соответствующий выделенный контур как в виде , так и в виде , а остальные переменные только либо в виде , либо в виде .

  3. На основании закона тавтологии любая 1-я клетка может быть включена в любое число различных контуров.

  4. Для получения минимальных ТДНФ в карте Карно не должно быть лишних покрытий, то есть каждую 1-ю клетку достаточно использовать хотя бы один раз.

  5. Существуют эквивалентные покрытия для получения различных минимальных ТДНФ.

  6. Существуют функции, для которых СДНФ совпадает с минимальной ТДНФ (в этом случае на карте Карно все 1-е клетки изолированные).

  7. Если в карте Карно нет ни одной 1, то ФАЛ эквивалентна константе 0; если нет ни одного ^ 0, то ФАЛ эквивалентна константе 1; если единицы занимают половину клеток карты Карно и представляют из себя монолитный массив в виде строки, столбца, прямоугольника или квадрата, то соответствующая импликанта состоит из одной переменной со знаком или без знака инверсии.

С учетом сказанного на ка­ртах Карно рис. 3 можно выделить три контура, содержащих по две 1(единицы).

Рис. 3. Рабочие карты Карно с двумя эквивалентными покрытиями



Два варианта покрытия обусловлены тем, что ^ 1 в клетке с набором 5 может образовать контур из двух клеток либо с набором 4 (рис. 3,а), либо с набором 1 (рис. 3,б). Поясним получение импликанты для контура, образованного двумя клетками в нижней строке карты. Переменная входит в этот контур только с инверсией, переменная входит в этот контур и с инверсией и без инверсии, поэтому по ней осуществляется склеивание, и она исчезает, переменная входит в этот контур только без инверсии, поэтому импликанта имеет вид . Другой способ определения импликанты будет показан ниже. Для выявленных двух покрытий можно записать:

(14)

(15)
Простота получения уравнений (14) и (15) показывает существенное преимущество табличного метода карт Карно перед расчетным методом.

На рис. 4 показаны эталонные карты Карно для n = 4, 5 и 6, причем карты Карно для n = 5 и 6 можно рассматривать как соответственно две и четыре карты Карно для n= 4, имеющие общие границы (они выделены толстыми центральными линиями). Карты Карно для n = 4, являющиеся составной частью карт Карно для n = 5 и 6 и имеющие общие границы, называются соседними. Правило соседства, для какой либо клетки в этих случаях, будет выглядеть так: для любой выделенной клетки соседними являются четыре соседние клетки в карте Карно для n = 4 и клетки, расположенные в соседних картах Карно для n = 4 симметрично выделенной клетке относительно границ соседних карт Карно.
^ Пример. Для клетки с набором 25 на рис. 4,б соседними являются клетки с номерами наборов 9, 27, 17, 24 и 29. Для клетки с набором 2 на рис. 4,б соседними являются клетки 3, 10, 0, 18 и 6. Для клетки с набором 43 на рис. 4,в соседними являются клетки с наборами 59, 42, 35, 41 и 47, 11. Для клетки с набором 22 на рис. 4,в соседними являются клетки с наборами 23, 30, 20, 6 и 54, 18.

Рис. 4. Эталонные карты Карно для n = 4, 5 и 6.



Рассмотрим еще несколько примеров для функций, зависящих от 4-х, 5-ти и 6-ти переменных. На рис. 5,а четыре 1-е клетки образуют квадрат, которому соответствует импликанта . На рис. 5,б контур, выделенный штриховой линией, оказывается лишним, так как все его клетки являются составными частями четырех контуров из двух клеток. Из карты Карно (рис. 5,б) получаем:

(16)

Для карты Карно (рис. 5,в) покажем еще один способ определения импликант, соответствующих выделенным контурам, состоящих в данном случае из двух столбцов. Для левого контура запишем минимальный и максимальный наборы. Таковыми являются наборы 2 и 14. Запишем их двоичные представления 0010 и 1110 одно на другом 1110. Переменные, соответствующие позициям с наложенными 0 и 1, склеиваются, а совпадающие позиции соответствуют искомой импликанте . Аналогичная процедура для правого контура дает импликанту . В итоге получаем:

(17)
Рис. 5. Рабочие карты Карно произвольных ФАЛ,

з
ависящих от четырёх переменных

Если теперь на той же карте Карно выделить контуры, соответствующие импликантам и (см. рис. 5,г), то окажется, что общая часть этих контуров будет содержать нулевые клетки.

Для ФАЛ, представленной на рис. 5,д, можно записать:

(18)

Преобразуем это выражение:

(19)

Если на той же карте Карно выделить контуры, соответствующие импликантам (см. рис. 5,е), то окажется, что общая часть этих контуров содержит нуль. Теперь можно сделать следующий вывод: если в карте Карно можно выделить два пересекающихся контура с общей нулевой частью, то импликанты, соответствующие этим контурам, объединяются знаком операции “сумма по mod2”.

Картам Карно, показанным на рис. 6,а-г, соответствуют следующие выражения:

(20)

(21)

(22)

(23)

Р
ис. 6.
Рабочие карты Карно произвольных ФАЛ,

зависящих от пяти и шести переменных
В работе [11] рассмотрен способ минимизации функций пяти и шести переменных с помощью одной карты Карно для n = 4.
Карты Карно удобно использовать и для минимизации неполностью определенных функций. Пусть требуется выработать осведомительный сигнал о том, что содержимое одноразрядного двоично-десятичного счетчика равно 6 или 7. Выходные переменные его четырех двоичных разрядов обозначим . Очевидно, что на наборах 0 - 5 и 8, 9 , на наборах 6 и 7 , а наборов 10 - 15 никогда не будет в нормально работающем двоично-десятичном счетчике и, следовательно, значение на этих наборах безразлично. Безразличные значения ФАЛ на картах Карно обозначаются каким-либо символом: крестиком, чертой, буквой и т. п. Карта Карно для этого случая приведена на рис. 7.

Рис. 7. Рабочая карта Карно неполностью определённой ФАЛ



Доопределив безразличные значения на наборах 14 и 15 единицами, получим следующее минимальное выражение:

(24)
После реализации этой функции она становится полностью определенной, то есть на безразличных наборах, включенных в контур, будут реализовываться значения 1, а на невключенных в контур - значение 0.

Сформулируем в заключение достоинства и недостатки метода минимизации ФАЛ с помощью карт Карно. Достоинства:

1. Основным достоинством применения карт Карно является компактность, простота и наглядность представления полностью и неполностью определенных функций.

2. Их применение оправдано для n = 2 ÷ 6, а при определенных навыках даже для n = 7 и 8, что соответствует большинству реально встречающихся инженерных задач.

3. Карты Карно можно использовать для минимизации ФАЛ, заданных как в СДНФ, так и в СКНФ.

4. Удобно минимизировать системы булевых функций, так как на картах Карно легко выделять общие части реализуемой системы ФАЛ.

5. Легко находятся минимальные комбинации контуров по их виду на карте Карно.

6. На одной карте Карно можно изобразить систему ФАЛ, в каждой из которых одна 1 или один 0 (например, ДС 1 из 4; 8; 16; … с активной “1” или “0”).

7. Для построения карты Карно не обязательно задавать её в СДНФ или СКНФ (можно подставить значения наборов в любой вид ФАЛ и заносить значения ФАЛ на этом наборе в соответствующую клетку карты Карно).

8. Карты Карно сразу позволяют реализовать первые два этапа минимизации (склеивание и выявление лишних импликант).

Недостатки:

1. Затруднительно использовать карты Карно при n > 6.

2. Метод не является алгоритмически систематическим, многое зависит от навыков разработчика. Удобство обращения и экономия времени во многом зависит от его способности распознавать оптимальные конфигурации покрытия карт Карно.

ЛИТЕРАТУРА

1. Воробьев Н.В. Введение в булеву алгебру // Chip News. - 1997. - № . - с. .

2. Воробьев Н.В. Формы представления и классификация функций алгебры логики // Chip News. - 1997. - № . - с. .

3. Колдуэлл С. Логический синтез релейных устройств. Пер. с англ. -М.: Изд-во иностранной литературы. 1962. -740с.

4. Глушков В.М. Синтез цифровых автоматов. -М.: Физматгиз. 1962. -476с.

5. Фридман А., Менон П. Теория и проектирование переключательных схем. -М.: Мир. 1978. -580с.

6. Миллер Р. Теория переключательных схем, т.1 -Комбинационные схемы: Пер. с англ. -М.: Наука, Главная редакция физико-математической литературы. 1970. -416с.

7. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. -2-е изд., перераб. и доп. -М.: Радио и связь. 1990. -496с.

8. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов: (Учебник для вузов по спец. “Электрон. вычисл. машины”). -2-изд., перераб. и доп. -Мн.: Высш. школа. 1980. -336с.

9. Veitch E. W., A chart method for simplifying truth functions, Proc. of Association for Computing Machinery, Pittsburgh, Pennsylvania, Meeting May 2 and 3,1952, p. 127-133.

10. Karnaugh M., The map method for synthesis of combinational logic circuits, AIEE Trans., part 1, Communications and Electronics, 72 (1953), November, 593-599.

11. Гольденберг Л.М. Цифровые устройства на интегральных схемах в технике связи / Гольденберг Л.М., Бутыльский Ю.Т., Поляк М.Н. -М.: Связь. 1979. -232с.


Скачать файл (813.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации