Протоколы передачи данных Протокол с выборочным повтором Сети Петри высокоуровневый протокол управления каналом код Хэмминга Метод выборочного повтора протокол скользящего окна

Электроника

Минимизация Булевых функций. Карты Карно

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

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

Количество полупроводниковых структур определяется по следующим правилам:

Одни выход логического элемента И или ИЛИ эквивалентен одному полупроводниковому диоду. Анализ нелинейных цепей Общие понятия об элементах нелинейных цепей Цепи, которые изучались ранее, относятся к классу линейных цепей. Параметры элементов этих цепей. Параметры элементов этих цепей - сопротивлений, индуктивностей, емкостей - не зависит от значений приложенных к ним напряжений или протекающих через них токов.

Операция НЕ эквивалентна одному полупроводниковому транзистору.

Например:

здесь: 4 – диода, 1 – транзистор.

Рассмотрим технологию минимизации на примерах (из предыдущего параграфа), исходная алгебраическая форма:

Пример 1: =

 

Минимизация завершена.

Пример 2:

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

Основополагающим для составления карт Карно является два термина.

Ранг слагаемого – это количество двоичных переменных, образующих элементарное произведение.

Соседние элементы – такие элементарные произведения, которые отличаются друг от друга только на одну инверсию. Например: .

Рассмотрим построение карт Карно на примере 4-х переменных. Вид шаблона карт Карно следующий:

27 - 1

A, B, C, D - двоичные переменные

Боковые и верхние ризки указывают на то, что переменные в этих полях при построении этих  элементарных произведений берутся без инверсии, в противном случае – с инверсией. Каждая ячейка – элементарное произведение всех четырех переменных.

Запишем номер набора для этих четырех переменных.

27 - 2

Данный шаблон является основой для задания Булевой функции в виде карты Карно.

Исходным для заполнения является табличный или числовой способ задания Булевых функций. Там, где Булева функция принимает единичное значение, в номера тех наборов вписывается единица.

Например:

Соответствующая этой ф-ии карта Карно:

1

1

1

1

1

Например:

Соответствующая этой функции карта Карно:

1

1

1

1

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

Автоматизм минимизации Булевой функции, записанной в виде карты Карно следующий:

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

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

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

4) Для отдельно заполненной единицей ячейки слагаемое четвертого ранга в результирующем выражении записывается полностью.

5) В процессе минимизации можно одну и ту же клетку задействовать несколько раз.

Пример 1:

29 - 1 F = B

Пример 2:

29 - 2 Результат минимизации

В цифровой электронике все схемы делят на комбинационные и последовательные.

Комбинационные – схемы, которые математически полностью можно описать в рамках Булевой алгебры.

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


На главную