Цифровые схемы - метод K-Map

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

Чтобы преодолеть эту трудность, Карно ввел метод упрощения булевых функций простым способом. Этот метод известен как метод карты Карно или метод K-карты. Это графический метод, который состоит из 2 n ячеек для 'n' переменных. Соседние ячейки отличаются только позицией одного бита.

K-Maps для 2-5 переменных

Метод K-Map наиболее подходит для минимизации булевых функций от 2 переменных до 5 переменных. Теперь давайте поговорим о K-Maps для 2-5 переменных одна за другой.

2 Переменная K-Map

Количество ячеек в 2-х переменных K-map равно четырем, поскольку количество переменных равно двум. На следующем рисунке показаны 2 переменные K-Map .

2 Переменная K-Map
  • Существует только одна возможность группировки 4 смежных минимальных терминов.

  • Возможные комбинации группировки 2 смежных минимальных терминов: {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) и (m 1 , m 3 )}.

3 Переменная K-Map

Количество ячеек в 3-х переменных K-map равно восьми, поскольку количество переменных равно трем. На следующем рисунке показаны 3 переменных K-Map .

3 Переменная K-Map
  • Существует только одна возможность группировки 8 смежных минимальных терминов.

  • Возможные комбинации группировки 4 смежных минимальных терминов: {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (м 1 , м 3 , м 5 , м 7 ), (м 3 , м 2 , м 7 , м 6 ) и (м 2 , м 0 , м 6 , м 4 )}.

  • Возможные комбинации группировки 2 смежных минимальных терминов: {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) , (м 5 , м 7 ), (м 7 , м 6 ), (м 6 , м 4 ), (м 0 , м 4 ), (м 1 , м 5 ), (м 3 , м 7 ) и ( м 2 , м 6 )}.

  • Если x = 0, то 3-х переменная K-карта становится 2-х переменной K-map.

4 переменная K-карта

Количество ячеек в 4-х переменных K-map равно шестнадцати, поскольку количество переменных равно четырем. На следующем рисунке показана 4 переменная 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 ) , (C 2 , C 3 ), (C 3 , C 4 ), (C 4 , C 1 )}.

  • Если w = 0, то 4-х переменная K-карта становится 3-х переменной K-map.

5 переменных K-Map

Количество ячеек в 5-переменной переменной K-map равно тридцати двум, поскольку количество переменных равно 5. На следующем рисунке показана 5-переменная K-Map .

5 переменных K-Map
  • Существует только одна возможность группировки 32 смежных минимальных терминов.

  • Существует две возможности группировки 16 смежных минимальных терминов. то есть группировка минимальных членов от m 0 до m 15 и от m 16 до m 31 .

  • Если v = 0, то 5 переменных K-map становятся 4 переменными K-map.

В вышеупомянутых всех K-картах мы использовали исключительно обозначение минимальных терминов. Точно так же вы можете использовать исключительно обозначение Макс. Терминов.

Минимизация булевых функций с использованием K-Maps

Если мы рассмотрим комбинацию входных данных, для которых булева функция равна '1', то мы получим булеву функцию, которая находится в стандартной сумме форм продуктов после упрощения K-карты.

Точно так же, если мы рассмотрим комбинацию входов, для которых булева функция равна '0', то мы получим булеву функцию, которая находится в стандартном произведении формы сумм после упрощения K-карты.

Следуйте этим правилам для упрощения K-карт , чтобы получить стандартную сумму продуктов формы.

  • Выберите соответствующую K-карту на основе количества переменных, присутствующих в булевой функции.

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

  • Проверьте возможности группировки максимального количества соседних. Это должно быть полномочия двух. Начните с максимальной степени двух и до минимальной степени двух. Наибольшая мощность равна числу переменных, рассматриваемых в K-карте, а наименьшая мощность равна нулю.

  • Каждая группа будет давать буквальный или один товарный термин. Это известно как главный импликант . Первичный импликант называется существенным первичным импликантом , если хотя бы один «1» не покрывается какими-либо другими группировками, а охватывает только эта группировка.

  • Запишите все основные и важные основные факторы. Упрощенная булева функция содержит все основные простые импликанты и только необходимые простые импликанты.

Примечание 1 - Если выходы не определены для некоторой комбинации входов, то эти выходные значения будут представлены символом «x» . Это означает, что мы можем рассматривать их как «0» или «1».

Примечание 2 - Если не нужны термины, присутствующие также, тогда не обращайте внимания на 'x' в соответствующих ячейках K-карты. Рассмотрим только те «x», которые не важны для группирования максимального числа соседних. В этих случаях рассматривайте значение «все равно» как «1».

пример

Упростим следующую булеву функцию f (W, X, Y, Z) = WX'Y '+ WY + W'YZ', используя K-map.

Данная булева функция находится в виде суммы произведений. Он имеет 4 переменные W, X, Y и Z. Итак, нам требуется 4 переменных K-map . K-карта с четырьмя переменными , соответствующая заданным условиям продукта, показана на следующем рисунке.

Пример минимизации

Здесь 1s помещены в следующие ячейки K-карты.

  • Ячейки, которые являются общими для пересечения строки 4 и столбцов 1 и 2, соответствуют термину продукта WX'Y ' .

  • Ячейки, которые являются общими для пересечения строк 3 и 4 и столбцов 3 и 4, соответствуют термину продукта WY .

  • Ячейки, которые являются общими для пересечения строк 1 и 2 и столбца 4, соответствуют термину продукта W'YZ ' .

Нет возможности сгруппировать 16 соседних или 8 соседних. Есть три возможности группировки 4 смежных. После этих трех группировок не останется ни одной группы. Таким образом, нам не нужно проверять для группировки 2 смежных. K-карта с четырьмя переменными с этими тремя группировками показана на следующем рисунке.

Три группировки

Здесь мы получили три основных импликанта WX ', WY & YZ'. Все эти основные факторы важны по следующим причинам.

  • Два из них (m 8 и m 9 ) из группы четвертого ряда не охватываются никакими другими группами. Только четвертая группа строк охватывает эти два.

  • Одиночная 15 ) группа квадратной формы не охватывается никакими другими группами. Только группа квадратной формы покрывает это.

  • Два (m 2 & m 6 ) четвертой группы столбцов не охватываются никакими другими группами. Только четвертая группа столбцов охватывает эти два.

Следовательно, упрощенная булева функция

f = WX '+ WY + YZ'

Следуйте этим правилам для упрощения K-карт , чтобы получить стандартное произведение суммы форм.

  • Выберите соответствующую K-карту на основе количества переменных, присутствующих в булевой функции.

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

  • Проверьте возможности группировки максимального количества соседних нулей. Это должно быть полномочия двух. Начните с максимальной степени двух и до минимальной степени двух. Наибольшая мощность равна числу переменных, рассматриваемых в K-карте, а наименьшая мощность равна нулю.

  • Каждая группировка будет давать буквальное или однозначное выражение. Это известно как главный импликант . Первичный импликант называется существенным первичным импликантом , если хотя бы один «0» не покрывается какими-либо другими группировками, а охватывает только эта группировка.

  • Запишите все основные и важные основные факторы. Упрощенная булева функция содержит все основные простые импликанты и только необходимые простые импликанты.

Примечание. Если не имеют значения термины, присутствующие, тогда не обращайте внимания на 'x' в соответствующих ячейках K-карты. Рассмотрим только те значения x, которые полезны для группировки максимального количества смежных нулей. В этих случаях обрабатывайте значение «все равно» как «0».

пример

Упростим следующую булеву функцию: $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $, используя K-map.

Данная булева функция находится в произведении формы Макса. Он имеет 3 переменные X, Y & Z. Итак, нам требуется 3 переменных K-map. Данные условия Max: M 0 , M 1 , M 2 и M 4 . 3- переменная K-карта с нулями, соответствующими заданным условиям Max, показана на следующем рисунке.

Главные Импликанты

Нет возможности сгруппировать 8 смежных нулей или 4 смежных нуля. Существует три возможности группировки 2 смежных нулей. После этих трех группировок не остается ни одного нулевого значения как несгруппированного. K-карта с тремя переменными с этими тремя группировками показана на следующем рисунке.

разгруппированы

Здесь мы получили три простых импликанта X + Y, Y + Z и Z + X. Все эти простые импликанты существенны, потому что один ноль в каждой группировке не охватывается никакими другими группировками, кроме их отдельных группировок.

Следовательно, упрощенная булева функция

f = (X + Y). (Y + Z). (Z + X)

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

Вследствие этого проверка и группировка смежных (минимальные условия) или смежных нулей (максимальные условия) будут затруднены. Мы обсудим метод Tabular в следующей главе, чтобы преодолеть трудности метода K-map.