11 мая 2010 в 23:17

Схемотехника. Минимизация логических функций

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


Зачем это нужно?


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

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

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

Минимизация логических функций при помощи карт Карно


Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

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

image

Возможность поглощения следует из очевидных равенств

image

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

image

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

image

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:
image
В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.
image

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

image

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

  1. Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2n (n целое число = 0…\infty) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
  2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
  3. Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
  4. Область должна быть как можно больше, а кол-во областей как можно меньше;
  5. Области могут пересекаться;
  6. Возможно несколько вариантов накрытия.


Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Karnough map 2 1 1.PNG Karnough map 2 1 2.PNG Karnough map 2 1 3.PNG Karnough map 2 1 4.PNG Karnough map 2 1 5.PNG Karnough map 2 1 6.PNG Karnough map 2 1 7.PNG Karnough map 2 1 8.PNG
\overline{X1}\ \overline{X2} \overline{X1}\ X2 X1\ X2\ X1\ \overline{X2} \overline{X2} \overline{X1} {X2}\ {X1}\
Karnough map 2 1 9.PNG Karnough map 2 1 10.PNG Karnough map 2 1 11.PNG Karnough map 2 1 12.PNG Karnough map 2 1 13.PNG Karnough map 2 1 14.PNG
S1\vee S2 = S1\vee S2 = S1\vee S2 = S1\vee S2 = S1\vee S2 = S1\vee S2 =
=X1X2\vee =X1\overline{X2}\vee =X2\vee X1 =X1\vee\overline{X2} =\overline{X1}\vee\overline{X2} =X2\vee \overline{X1}
\vee\overline{X1}\ \overline{X2} \vee\overline{X1}X2

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид:
image
В формате КНФ:
image
+45
26726
124
KbRadar 41,0

Комментарии (41)

+5
KbRadar #
Именно. Лучший вариант изложения. Надеюсь, что топик на хабре, привлечет внимание как можно большего числа людей.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
+5
Zhenek #
ну ты шутишь? где это видано, чтобы тролям разрешали картинки постить? Обнули карму и юзай хтмл теги
НЛО прилетело и опубликовало эту надпись здесь
+2
KbRadar #
Ну и чтобы оправдать частичный копипаст, готов ответить на все возникшие вопросы и привести примеры для интересующихся. В этом и состоит суть сего топика.
+6
Ag47 #
Ну в общем, то всё это было в универе…

Хотя, вохможно, это интересно:
В процессе минимизации той или иной логической функции, обычно учитывается, в каком базисе эффективнее будет реализовать ее минимальную форму при помощи электронных схем.

Можно про это подробнее? Есть, конечно, ощущение, что это просто сравнение этого
ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Logic_Nikolay.PNG
(внимание: парсер бьёт ссылку на двоеточии)
и этого
upload.wikimedia.org/wikipedia/commons/thumb/2/2f/%7Elogic_Nikolay.PNG/200px-%7Elogic_Nikolay.PNG
но всё же.
+1
KbRadar #
В случае реализации схемы на базиах и-не или-не, следует выбирать верный метод минимизации. А на схемах в ссылках представлена реализация ДНФ и КНФ функции.
+2
d0b #
Да, был у нас такой предмет на первом курсе. Прикладная Теория Цифровых Автоматов (все его просто называли ПТиЦА:))
Вот только помниться там еще методы были, такие как метод Квайна, Квайна-Мак Класки, неопределенных коэффициентов…
Наверное один из самых толковых предметов, хотя казался невероятно сложным :)
НЛО прилетело и опубликовало эту надпись здесь
+1
KbRadar #
В учебных целях это следует уметь делать самостоятельно.
+1
mChief #
А еще неплохо в учебных целях самому написать такую программу
+2
gribozavr #
apt-get install qmc
0
SKaDi #
В Electronic Workbench (старом и в Multisim новом) есть Logic Converter. Все в нем есть — таблица истинности в формулу или сразу в схему и наоборот. Это когда в учебных целях некогда или уже умеешь.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
+1
DemonShi #
Заманчивые у Вас картинки, а внутри скукота, которую преподают в универах :)
+1
Xab #
сначала теория, потом практика. думаю автор этих топиков постепенно именно к этому и подходит.
+1
DemonShi #
Да, я понимаю, что это важные и нужные знания, но для человека, знакомящегося со схемотехникой это скукота.
+1
Xab #
Да, это тоже довольно естественно, но всегда (в успешном исходе) наступает просветление и пробегает мысль: «о, вот именно это мне и втирали на лекциях, а я думал, что муть, и вовсе не пригодится».
НЛО прилетело и опубликовало эту надпись здесь
0
KbRadar #
Пишите конечно, интересующиеся всегда найдутся.
+1
Arceny #
Ой, это же моя РГР :-) ТОлько красиво нарисованая…
НЛО прилетело и опубликовало эту надпись здесь
+1
vittore #
минимизацию делают до того как на плис реализовывать ваще то
+6
Shemet #
>Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно.

Не мог Вейч изобрести карты Карно. )
Он изобрел «диаграммы Вейча», которые кстати намного удобнее для человека, чем карты Карно, при небольшом количестве переменных.
+3
XBR #
ой, буквально сегодня лектор рассказывал эту тему по основам дискретной математики.
вот только называл это диаграммами Вейче
+1
ooprizrakoo #
Двенадцать лет назад «проходил» Карты Карно, функции алгебры логики, и т.п. Тогда это казалось ненужной ерундой, которую использовали только изобретатели ламповых ЭВМ и непонятно для чего оставили в учебных программах…
Топик заставил меня немножко поностальгировать по тому времени :)
И приятно осознавать, что МСТ (МикроСхемоТехника), самый страшный предмет, действительно дает нужную и полезную информацию (для тех, конечно, кто связывают свою работу с этой сферой)
0
Gruxon #
Тема интересная и ностальгическая. Кроме института, не то что не использовал, но даже не видел, тех кто использует.

Люди! Ради любопытства, отзовитесь пожалуйста, те, кто в своей работе реально разрабатывает логику на дискретных элементах, даже хотя бы любители, кто ради хобби этим занимается. Сколько вас тут?
+1
gribozavr #
На дискретных элементах — нет. Но эта теория активно используется в цифровой схемотехнике. Вот построим, например, сумматор. Сначала что? Таблица истинности. А реализовать как? Вот и минимизируешь. А потом хочешь, например, групповой перенос на 4 разряда — и тут уже табличку можно писать минут 10, а потом ещё неизвестно сколько минимизировать и искать ошибки. А так пользуемся формулами, но вывели-то мы их как? Через минимизацию.
0
Nattfodd #
Как раз сейчас изучаю эту премудрость в универе. И хотя дико не охота — топики на хабре помогают преодолевать лень :).

Так что присоединяюсь к вопросу — где в жизни оно может понадобиться?
0
CLR #
Я это учил вначале в колледже, потом в университете, я знал где это можно использовать, но также знал что мне оно в жизни «никогда не пригодится». И лишь через несколько лет после окончания учебы мне это пригодилось, причем внезапно в быту, когда я решил сделать автоматическое управление светом на даче :) Поскольку особо усердия я во время учебы не прилагал (кто ж мог знать что мне такое вообще в голову взбредет), пришлось учиться заново. Мораль сей басни такова — учите пока есть время, все подряд, знания лишними никогда не бывают, даже если вам читают труд Маркса «Das Kapital».
–1
SwampRunner #
Ох как же я ненавидел это на втором курсе
0
t0ster #
Подскажите как составлять таблицу истинности для проверки. Спасибо.
0
vittore #
Вообще это самый простой способ минимизации.
Интересно было бы почитать про минимизацию монотонными и пороговыми функциями
0
stas_agarkov #
когда-то, курсе на 2-м, я написал программу для минимизации логических функций
files.mail.ru/YCO5CK
0
imwode #
Позанимаюсь-ка я некрофилией, может поможете мне? Я пытаюсь для начала сделать достаточно простую вещь — синтезировать автомат обработчика нажатия кнопки. Второй день читаю пособия и статьи (например эту), и все никак не могу ухватить основной смысл.

Вводные: у нас есть кнопка. Она может быть нажата и не нажата. При нажатии кнопки запускается дебаунс-таймер и отмеряет интервал короткого нажатия кнопки. Если во время работы этого таймера кнопку отпустили, возвращаемя в исходное положение. Если таймер отработал и кнопка все еще нажата, запускается таймер измерения интервала длинного нажатия. Если во время работы этого таймера кнопка отпущена, фиксируем короткое нажатие и уходим в исходное состояние. И т.д.

Я сделал такую кпарту переходов и выходов:
docs.google.com/spreadsheet/ccc?key=0AnPYVBxHxxhBdHVfdngxX3RYaFRuck1mcjF2cWNFWUE

Последующее курение пособий показало, что я, похоже, неправильно понял суть входов. Т.е. вход должен быть один — x1(кнопка). Вход может быть в состоянии 0 или 1.

Дальше непонятно чем же все-таки являются таймеры — это входы или состояния? Еще периодически встречается термин «функции возмущения», но с ними вообще ничего непонятно.

А на следующем этапе мне еще нужно будет преобразовать это в структурный автомат и синтезировать логическую схему. Мааамаааа.
НЛО прилетело и опубликовало эту надпись здесь

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.