Привет. Кажется, ты используешь AdBlock. Geektimes развивается
и существует за счет доходов от рекламы. Добавь нас в исключения.
открытое письмо как отключить
avatar

KbRadar

карма
84,0
170 голосов
рейтинг
0,2
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
42993
134
KbRadar 0,2

Комментарии (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.

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

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

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

Что обсуждают?

Парализованные люди смогли двигать ногами в результате неинвазивной электростимуляции спинного мозга (2)
Чего желает общество: стремление россиян к контролю интернета (77)
EmDrive получает заслуженное внимание со стороны научного сообщества (33)
Кому будут принадлежать роботы? (5)
Новое универсальное 2DIN головное устройство на базе Android для автомобиля. Построй свою мечту (29)
Учёные при помощи компьютерной симуляции предсказали материал с рекордной температурой плавления (9)
Google получает запросы на удаление 18 пиратских ссылок в секунду (3)
В Европе установили рекордное количество ветровых электрогенераторов общей мощностью на 2,34 ГВт (2)
Роскосмос создаёт Центр пилотируемых программ — аналог Космического центра имени Линдона Джонсона в Хьюстоне (1)
Лоукостеры-производители печатных плат с социальным уклоном (11)