Цифровые схемы - метод K-Map
В предыдущих главах мы упростили булевы функции, используя булевы постулаты и теоремы. Это трудоемкий процесс, и нам приходится переписывать упрощенные выражения после каждого шага.
Чтобы преодолеть эту трудность, Karnaughпредставил метод упрощения булевых функций простым способом. Этот метод известен как метод карты Карно или метод K-карты. Это графический метод, который состоит из 2 n ячеек для n переменных. Соседние ячейки различаются только позицией одного бита.
K-карты для 2-5 переменных
Метод K-Map лучше всего подходит для минимизации булевых функций от 2 переменных до 5 переменных. Теперь давайте обсудим K-Maps для 2–5 переменных по очереди.
2 переменная K-карта
Количество ячеек в К-карте 2 переменных равно четырем, поскольку число переменных равно двум. На следующем рисунке показано2 variable K-Map.
Есть только одна возможность сгруппировать 4 соседних минимальных термина.
Возможные комбинации группировки 2 соседних min термов: {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) и (m 1 , m 3 )}.
3 переменная K-карта
Количество ячеек в К-карте с 3 переменными равно восьми, так как количество переменных равно трем. На следующем рисунке показано3 variable K-Map.
Есть только одна возможность сгруппировать 8 соседних мин. Терминов.
Возможные комбинации группировки 4 соседних min термов: {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (m 1 , m 3 , m 5 , m 7 ), (m 3 , m 2 , m 7 , m 6 ) и (m 2 , m 0 , m 6 , m 4 )}.
Возможные комбинации группировки 2 соседних min термов: {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) , (m 5 , m 7 ), (m 7 , m 6 ), (m 6 , m 4 ), (m 0 , m 4 ), (m 1 , m 5 ), (m 3 , m 7 ) и ( м 2 , м 6 )}.
Если x = 0, то K-карта с 3 переменными становится K-картой с 2 переменными.
4 переменных K-Map
Количество ячеек в К-карте с 4 переменными равно шестнадцати, поскольку количество переменных равно четырем. На следующем рисунке показано4 variable K-Map.
Есть только одна возможность сгруппировать 16 соседних минутных терминов.
Пусть R 1 , R 2 , R 3 и R 4 представляют минимальные члены первой строки, второй строки, третьей строки и четвертой строки соответственно. Точно так же C 1 , C 2 , C 3 и C 4 представляют минимальные члены первого столбца, второго столбца, третьего столбца и четвертого столбца соответственно. Возможные комбинации группировки 8 соседних минимальных терминов: {(R 1 , R 2 ), (R 2 , R 3 ), (R 3 , R 4 ), (R 4 , R 1 ), (C 1 , C 2 ) , (С 2 , С 3 ), (С 3 , С 4 ), (С 4 , С 1 )}.
Если w = 0, то K-карта с 4 переменными становится K-картой с 3 переменными.
5 переменных K-Map
Количество ячеек в K-карте с 5 переменными равно 32, так как количество переменных равно 5. На следующем рисунке показано 5 variable K-Map.
Есть только одна возможность сгруппировать 32 соседних минимальных термина.
Есть две возможности сгруппировать 16 соседних мин. Терминов. то есть группировка минимальных терминов от m 0 до m 15 и m 16 до m 31 .
Если v = 0, то K-карта с 5 переменными становится K-картой с 4 переменными.
Во всех вышеупомянутых K-картах мы использовали исключительно обозначение минимальных терминов. Точно так же вы можете использовать исключительно обозначение терминов Max.
Минимизация булевых функций с помощью K-Maps
Если мы рассмотрим комбинацию входов, для которых логическая функция равна '1', то мы получим логическую функцию, которая находится в standard sum of products форма после упрощения K-карты.
Точно так же, если мы рассмотрим комбинацию входов, для которых логическая функция равна '0', то мы получим логическую функцию, которая находится в standard product of sums форма после упрощения K-карты.
Следуйте этим rules for simplifying K-maps для получения стандартной формы суммы продуктов.
Выберите соответствующую K-карту на основе количества переменных, присутствующих в логической функции.
Если булева функция задана как сумма минимальных термов, то поместите их в соответствующие минимальные ячейки на K-карте. Если логическая функция задана как сумма продуктов, поместите их во все возможные ячейки K-карты, для которых действительны данные условия продукта.
Проверьте возможности группировки максимального количества соседних. Это должно быть степень двойки. Начните с наибольшей степени двойки и до наименьшей степени двойки. Наивысшая степень равна количеству переменных, рассматриваемых в K-карте, а наименьшая степень равна нулю.
Каждая группа дает буквальный или один термин продукта. Он известен какprime implicant. Главный импликант называетсяessential prime implicant, если хотя бы одна '1' не покрывается никакими другими группами, а покрывается только этой группой.
Запишите все основные импликанты и основные импликанты. Упрощенная логическая функция содержит все основные простые импликанты и только необходимые простые импликанты.
Note 1 - Если выходы не определены для некоторой комбинации входов, то эти выходные значения будут представлены как don’t care symbol ‘x’. Это означает, что мы можем рассматривать их как «0» или «1».
Note 2- Если также присутствуют термины «безразлично», поместите «х» в соответствующие ячейки K-карты. Учитывайте только безразличные 'x', которые помогают сгруппировать максимальное количество соседних. В таких случаях считайте значение «безразличие» как «1».
пример
Разрешите нам simplify следующая логическая функция, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ используя K-карту.
Данная логическая функция находится в форме суммы произведений. Он имеет 4 переменные W, X, Y и Z. Итак, нам требуется4 variable K-map. В4 variable K-map с теми, которые соответствуют данным условиям продукта, показано на следующем рисунке.
Здесь единицы помещаются в следующие ячейки K-карты.
Ячейки, которые являются общими для пересечения строки 4 и столбцов 1 и 2, соответствуют термину продукта, WX’Y’.
Ячейки, которые являются общими для пересечения строк 3 и 4 и столбцов 3 и 4, соответствуют термину продукта, WY.
Ячейки, которые являются общими для пересечения строк 1 и 2 и столбца 4, соответствуют термину продукта, W’YZ’.
Нет возможности группировать ни 16 соседних, ни 8 соседних. Есть три возможности сгруппировать 4 соседних. После этих трех группировок не остается ни одной разгруппированной. Таким образом, нам не нужно проверять группировку 2-х соседних. В4 variable K-map с этими тремя groupings показано на следующем рисунке.
Здесь мы получили три основных импликанта WX ', WY и YZ'. Все эти основные импликантыessential по следующим причинам.
Два (m8 & m9)группы четвертой строки не попадают ни в какие другие группы. Только четвертая группа строк охватывает эти две строки.
Один (m15)группировки квадратной формы не покрываются никакими другими группировками. Только квадратная группа покрывает это.
Два (m2 & m6)группы четвертого столбца не попадают ни в какие другие группы. Только четвертая группа столбцов охватывает эти две.
Следовательно simplified Boolean function является
f = WX’ + WY + YZ’
Следуйте этим rules for simplifying K-maps для получения стандартного произведения сумм.
Выберите соответствующую K-карту на основе количества переменных, присутствующих в логической функции.
Если логическая функция задана как произведение максимальной формы термов, тогда поместите нули в соответствующие ячейки максимума термов на K-карте. Если логическая функция задана как произведение суммы сумм, то поместите нули во все возможные ячейки K-карты, для которых действительны заданные члены суммы.
Проверьте возможности группировки максимального количества соседних нулей. Это должно быть степень двойки. Начните с наибольшей степени двойки и до наименьшей степени двойки. Наивысшая степень равна количеству переменных, рассматриваемых в K-карте, а наименьшая степень равна нулю.
Каждая группировка даст буквальный или один суммарный член. Он известен какprime implicant. Главный импликант называетсяessential prime implicant, если хотя бы один '0' не покрывается никакими другими группами, а покрывается только эта группа.
Запишите все основные импликанты и основные импликанты. Упрощенная логическая функция содержит все основные простые импликанты и только необходимые простые импликанты.
Note- Если также присутствуют термины «безразлично», поместите «х» в соответствующие ячейки K-карты. Рассмотрим только безразличный «x», который помогает сгруппировать максимальное количество соседних нулей. В таких случаях значение безразличия следует рассматривать как «0».
пример
Разрешите нам simplify следующая булева функция $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $ с использованием K-карты.
Данная логическая функция является продуктом формы максимальных условий. Он имеет 3 переменных X, Y и Z. Итак, нам требуется 3 переменных K-map. Указанные условия Max: M 0 , M 1 , M 2 и M 4 . 3variable K-map с нулями, соответствующими заданным параметрам Max, показано на следующем рисунке.
Нет возможности сгруппировать 8 соседних нулей или 4 соседних нуля. Есть три возможности сгруппировать 2 соседних нуля. После этих трех группировок не остается ни одного нуля в разгруппированном виде. В3 variable K-map с этими тремя groupings показано на следующем рисунке.
Здесь мы получили три простые импликанты X + Y, Y + Z и Z + X. Все эти простые импликанты суть essential потому что один ноль в каждой группе не покрывается никакими другими группами, за исключением их индивидуальных группировок.
Следовательно simplified Boolean function является
f = (X + Y).(Y + Z).(Z + X)
Таким образом, мы можем легко упростить логические функции до 5 переменных, используя метод K-map. Для более чем 5 переменных сложно упростить функции с помощью K-Maps. Потому что количествоcells в K-карте получает doubled включив новую переменную.
Из-за этого проверка и группировка соседних единиц (минимальные члены) или соседних нулей (максимальные члены) будут усложнены. Мы обсудимTabular method в следующей главе, чтобы преодолеть трудности метода K-map.