Умение генерировать код Грея позволяет строить карты большего размера. Фактически, всё, что нам нужно сделать, это взять со столбцов последовательность Грея слева направо в верхней части карты с тремя переменными и применить её сверху-вниз с левой стороны карты с четырьмя переменными:
Рис. 1. Для карты Карно от 4-х переменных берём заголовки столбцов карты Карно от 3-х переменных и применяем их к строкам.
Редукция K-карт от 4-х переменных
Следующие четыре карты Карно от 4-х переменных иллюстрируют сокращение булевых выражений, которые слишком утомительны для методов булевой алгебры. Безусловно, редукцию (переход от сложного к простому) можно сделать и с помощью булевой алгебры, но удовольствия от этого будет мало.
Карты Карно работают быстрее и проще, особенно если необходимо выполнить множество логических сокращений.
Рис. 2. Упрощаем A'B'CD + A'BCD + ABCD + AB'CD + ABC'D' + ABCD + ABC'D + ABCD' с помощью карты Карно до AB + CD.
На рисунке 2 выше логическое выражение содержит семь членов Суммы-Произведений. Они отображаются в виде ячеек с единицами сверху-вниз и слева-направо на K-карте. Например, первый член A'B'CD – это ячейка с 1-й строки, 3-го столбца, соответствующий местоположению на карте при A = 0, B = 0, C = 1, D = 1.
Остальные члены размещены аналогичным образом. На рисунке обведены две группы по четыре единицы, охватывающие группы как можно большего размера.
Горизонтальная группа, отмеченная синим пунктиром, соответствует логическому AB. Вертикальная группа, отмеченная красным пунктиром, соответствует логическому CD. Поскольку выделено две группы, в результате получаем упрощённую Суммы-Произведений Вых. = AB + CD в которой только два произведения.
Чтобы понять следующий пример (рисунок 3 ниже), можно мысленно «сложить» углы карты, словно салфетку, после чего четыре ячейки физически станут смежными, в результате чего получается группа из 4-х соседних ячеек. Мы можем сделать такой финт именно потому, что заголовки столбцов и строк идут в порядке, совпадающем с последовательностью кода Грея, из-за чего верхняя строка является смежной с нижней, а крайний левый столбце является смежным с крайним правым.
Рис. 3. Из-за того, что геометрия карты Карно основана на коде Грея, четыре угловых ячейки являются смежными!
Четыре ячейки на рисунке 3 выше представляют собой группу, потому что все они имеют общие логические переменные B' и D'. Другими словами, всегда B = 0 и D = 0 для этих четырёх ячеек.
По отношению к четырем угловым ячейкам остальные переменные (A, C) в некоторых случаях равны 0, а в других случаях равны 1.
Таким образом, эти переменные (A, C) не участвуют в этой группе из четырёх ячеек. Эта единственная группа выходит из карты как единое произведение, обозначающее упрощённый результат: Вых. = B'D'.
А для этой K-карты просто сверните верхний и нижний края в цилиндр, образуя восемь соседних ячеек:
Рис. 4. Из-за того, что геометрия карты Карно основана на коде Грея, верхняя и нижняя строки являются смежными!
Эта группа из восьми ячеек имеет одну общую логическую переменную: B = 0. Следовательно, одна группа из восьми ячеек покрывается одним членом: B'. Исходное восьмичленное логическое выражение упрощается до Вых. = B'.
Члены Суммы-Произведений в K-картах для 4-х переменных
В приведённом на рисунке 5 ниже логическом выражении аж девять членов, три из которых содержат три логических переменных (или их дополнений) вместо четырёх. Возникает резонный вопрос: как интерпретировать такие члены на карте Карно, если всего переменных во всём выражении четыре, а в каком-то члене – три? В то время как четыре логических переменных (или их дополнения) в одном члене соответствуют одной ячейке на карте Карно, то член с тремя логическими переменными охватывает пару ячеек (недостающая переменная в этом члене как бы принимает значения и 0 и 1).
Рис. 5. Всего в логическом выражении используется 4 переменных (и их дополнений), но если в каком-то члене только три переменных, то этот член соответствует не одной ячейке, а паре ячеек.
Шесть членов Суммы-Произведений (с четырьмя логическими переменными в каждом члене) отображаются обычным образом, как делали раньше, в виде отдельных ячеек. Три члена Суммы-Произведений (с тремя логическими переменными в каждом члене) отображаются как пары ячеек, это показано на рисунке 5 выше.
Обратите внимание, что мы пока что отображаем члены исходного логического выражения в K-карту, а не извлекаем их на данном этапе.
Для упрощения мы имеем возможность сформировать две группы по восемь штук. Ячейки в углах – общие для обеих групп. Это очень хорошо для упрощения. Фактически, это приводит к наилучшему решению, чем если бы сформировали одну группу из восьми ячеек и вторую группу из четырёх ячеек (в этом случае нет ячеек, общих для обеих групп). Окончательное оптимальное решение Вых. = B' + D'.
А теперь разберём такое неупрощённое логическое выражение, которое уже перенесли на карту Карно:
Рис. 6. Изолированная ячейка соответствует члену выражения, который останется неизменным даже после упрощения.
Три ячейки (в трёх углах карты) можно сгруппировать по две ячейки (при этом одна из ячеек будет входить в обе группы). Четвёртая ячейка с единицей не является смежной с какой-либо из трёх остальных. Её не с чем совмещать, что частенько случается при решении задач «реального мира». В этом случае логический член ABCD никак не изменяется в процессе упрощения. Результат: Вых. = B'C'D' + A'B'D' + ABCD.
Зачастую можно упростить несколькими способами, каждый из которых одинаково минимизирует затраты (то есть, среди нескольких способов может формально не оказаться наилучшего). Вот такой случай:
Рис. 7. На этой карте Карно можно сгруппировать двумя (эквивалентными в плане минимизации) разными способами.
Оба приведённых на рисунке 7 выше результата содержат по четыре члена в Сумме-Произведений, в каждом члене по три логических переменных. Оба способа являются одинаково допустимыми решениями с минимальными затратами. Разница в окончательном решении связана с тем, как именно сгруппированы ячейки, как показано в левой и правой части рисунка 7 выше.
Решение с минимальными затратами – это действующая логическая схема с минимальным количеством вентилей и минимальным количеством входов.
А вот ещё пример. Здесь, как обычно, отображаем неупрощённое булево уравнение и сформируем группу из четырёх ячеек в качестве первого шага упрощения (левая часть рисунка 8 ниже). Может быть неочевидно, как оптимально подобрать оставшиеся клетки (напоминаю, что количество ячеек в группе должно быть обязательно степенью двойки и сама группа должна иметь форму прямоугольника).
Рис. 8. Упрощаем логическое выражение с помощью карты Карно, определив четыре четырёхячеечные группы, перекрывающих друг друга.
Добавим три ячейки, создав ещё одну группу перекрывающуюся с первой (средняя часть рисунка 8 выше). Но как поступить с оставшимися двумя ячейками? Метод с минимальными затратами - сгруппировать их с соседними ячейками в группы по четыре (правая часть рисунка 8 выше).
И снова напоминаю – не пытайтесь группировать по три ячейки. Размеры групп должны быть степенями двойки, то есть 20 = 1, 21 = 2, 22 = 4, 23 = 8, ...
Ниже мы приводим ещё один пример, имеющий два равнозначных возможных решения с минимальными затратами. Начинаем с формирования пары групп по четыре ячейки (обведённые красным и синим овалами на рисунке 9) после того, как логическое выражение отображено на карте Карно.
Рис. 9. Куда пристроить последнюю несгруппированную ячейку?
Оба решения зависят от того, сгруппирована ли одна оставшаяся ячейка с красной или синей группой из четырёх ячеек, образовав третью группу из двух ячеек. Эта третья группа соответствует либо ABC', либо ABD, на ваш выбор. С точки зрения минимизации между обоими способами разницы нет.
В любом случае на эту ячейку распространяется любой из этих двух членов Суммы-Произведений (в зависимости от выбора). Окончательные результаты показаны выше на рисунке 9.
И наконец, на последнем рисунке 10 ниже у нас пример упрощения с использованием карты Карно (слева) или методами булевой алгебры (справа). Нанесите C' на карту как совокупность всех ячеек, относящихся к C = 0, это 8 ячеек в левой половине карты. Это первая группа. Затем отобразите единственную ячейку, относящуюся к ABCD.
Эту единственную ячейка группируем с соседней ячейкой (состоящей также в первой группе из 8-ми ячеек), как показано на рисунке 10 ниже, что позволяет упростить до ABD. Конечный результат: Вых. = C' + ABD.
Рис. 10. Этот пример упростим и с помощью карты Карно и методами булевой алгебры.
Этот последний случай – редкий пример задачи с четырьмя переменными, которую можно уменьшить с помощью булевой алгебры без особых усилий, если, конечно, вы не подзабыли теоремы.
