Преобразование входных величин с помощью карт Карно

1 23

Несмотря на то, что Булевы выражения и таблицы истинности используются для описания функционирования интегральных схем, ни один из этих способов изображения нельзя признать плодотворным при освоении современных методов логического конструирования. Карта Карно́ - графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного Булева куба. Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Другими словами в картах Карно при смещении на одну строку по вертикали или на один столбец по горизонтали изменяется лишь одна входная переменная за один шаг. Это исключает так называемые «гонки» или состязания, наблюдаемые при одновременном изменении двух и более входных переменных (рис.2.7).

Рис.2.7. Соответствие номеров строк таблицы истинности и клеток Карты Карно

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

Рис.2.8. Матрица Карно

Шесть единиц нанесены на карту в соответствии шести членам в исходном Булевом выражении. Рядом стоящие единицы объединены в группы из 2^х и 4^х единиц. Члены, дополняющие друг друга внутри контура, исключаются. Объединив оставшиеся члены функцией ИЛИ, получим минимизированное выражение в дизъюнктивной нормальной форме (ДНФ) (сумма произведений). Количество групп, объединенных контурами определяет число членов минимизированного Булева выражения:

Таблица истинности (рис.2.9) для обоих вариантов одинаковая.

Рис.2.9. Таблица истинности для булева выражения

Логические схемы, составленные в соответствии с исходным и упрощенным выражением будут выполнять одинаковые логические функции, однако, количество элементов меньше, соответственно меньше стоимость, вес, объем, выше надежность.

Чем больше размеры объединяющих контуров, тем больше переменных можно опустить. Карту Карно можно как бы «свернуть» в цилиндр с вертикальной осью или с горизонтальной осью или образовать шар, объединяя угловые единицы. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности.

Карта Карно рассматривается как поверхность фигуры под названием тор. Единичному значению функции соответствуют p-клетки карты Карно. Две соседние p-клетки на карте Карно дают импликанту первого ранга. Например, клетки 1100 и 1101 отличаются только значением переменной x₄, следовательно, они дают импликанту Х₁, Х₂, `Х₃. Две соседние импликанты первого ранга образуют импликанту второго ранга.

На карте Карно (рис.2.10) соседние клетки образуют две импликанты первого ранга и одну импликанту второго ранга. Минимизированное Булево выражение будет иметь вид

Y = Х₁, Х₂, `Х₃ + `Х₁, Х₂, Х₃+ `Х₁, `Х₄

Рис.2.10.Карта Карно для четырех переменных

Если функция имеет 5 переменных, то рисуются две карты Карно: для x₅=0 и для x₅=1. Если 6 переменных - 4 карты так, чтобы в соседних картах соседние клетки имели одинаковые координаты (Рис.2.11).

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

Рис.2.11. Варианты карт Карно

Если на картах Карно выделить все компактные группы наибольшей размерности, то получим минимизированное Булево выражение в дизъюнктивно-нормальной форме (ДНФ).

Минимизировать исходное Булево выражение и логическую схему (рис 2.4) гораздо удобнее с помощью карты Карно (Рис.2.12).

Рис.2.12. Карта Карно по таблице истинности (рис.2.3)

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

В качестве примера рассмотрим минимизацию функции 4-х переменных методом карт Карно, где две компактные группы размера 4 и одна компактная группа размера 2 (рис.2.13).