Электроника:Цифровая электроника/Карты Карно/Большие карты Карно с 5-ю и 6-ю переменными

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Перевод: Макаров В. (valemak) Контакты:</br>* Habr: @vakemak</br>* Сайт: www.valemak.com</br>Перевёл статей: 656.
Проверка/Оформление/Редактирование: Мякишев Е.А.


Большие карты Карно с 5-ю и 6-ю переменными[1]

Бо́льшие карты Карно упрощают больши́е логические схемы. Но насколько больши́ми могут быть эти бо́льшие карты? Это зависит от количества входов, разветвлений, рассматриваемой логической схемы. У одной из крупных компаний, производящих компоненты программируемой логики, есть ответ:

«

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

»
— Отдел исследований компании Altera

Если по-русски – не более шести входов для большинства проектов и пяти входов для средней логической схемы. Ниже рассмотрим карту Карно с пятью переменными.

K-карта с пятью переменными

Рис. 1. Устаревшая версия карты Карно с 5-ю переменными. Для нумерации столбцов используется код Грея.
Рис. 1. Устаревшая версия карты Карно с 5-ю переменными. Для нумерации столбцов используется код Грея.

Выше показана более старая версия K-карты с пятью переменными, она ещё называется карта кода Грея. Столбцы (и строки для карты с 6-ю переменными) пронумерованы в соответствии с кодом Грея. Если выписать всю последовательность кода Грея, то примерно в её середине обнаружится симметричный участок (000001011010110111101100) – поэтому карту Карно для 5-6 переменных с кодом Грея ещё называют картой Карно с отражением. Карты Карно в таком стиле встречаются, в основном, в старых текстах. Чуть ниже представлен современный и более предпочтительный стиль.

Версия K-карты с наложением

Рис. 2. Карта Карно с 5-ю переменными, наложенная на старую версию.
Рис. 2. Карта Карно с 5-ю переменными, наложенная на старую версию.

Версия карты Карно с наложением, показанная на рисунке 2 выше, представляет собой просто две (или четыре, если взять карту с 6-ю переменными) идентичные карты, если не брать во внимание самый старший бит в 3-битных адресах для столбцов (и строк, если 6 переменных).

Если взглянуть на верхнюю часть карты, то видим, что вторая половина нумерации отличается от предыдущей карты с кодом Грея. Если игнорировать первую значащую цифру в трёхзначных числах адресации столбцов, то заметим последовательность 00, 01, 11, 10 в заголовках обеих подкарт наложенной карты. Обе подкарты разделяет условная ось, называемой «зеркальной». Кстати, ещё можно обратить внимание на то, что если на карте Карно кода Грея столбцы в правой подкарте перечислить в обратном порядке, то получим как раз карту Карно с наложением.

Последовательность для столбцов из восьми трёхзначных чисел не является кодом Грея. Хотя подпоследовательности из четырёх чисел в обеих половинах равны, если брать только два младших бита.

Давайте воспользуемся нашей картой Карно с 5-ю переменными. Разработаем схему с 5-битным двоичным входом (A, B, C, D, E), где A является старшим битом (старший разряд). Выражение на основе К-карты должно выдавать на выходе высокий логический уровень для любого простого числа, обнаруженного во входных данных.

Рис. 3. Карта Карно с 5-ю переменными (код Грея). «Высокий» выход, если вход ABCDE представляет собой простое число в двоичном виде.
Рис. 3. Карта Карно с 5-ю переменными (код Грея). «Высокий» выход, если вход ABCDE представляет собой простое число в двоичном виде.

Мы показываем решение выше на старой карте кода Грея (карта отражения) для справки. Простые числа: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Их переводим в двоичный вид и в ячейки с соответствующими адресами вносим единицы. Затем группируем заполненные ячейки. В заключение пишем упрощённый результат.

Обратите внимание, что 4-ячеечная группа A'B'E состоит из двух пар ячеек по обе стороны от «зеркальной» оси. То же верно и для двухклеточной группы AB'DE. Это группа из двух ячеек, отражающихся от «зеркальной» линии. При использовании данной устаревшей версии K-карты ищите зеркальные изображения на другой половине карты.

Выход = A'B'E + B'C'E + A'C'DE + A'CD'E + ABCE + AB'DE + A'B'C'D

На рисунке 4 ниже мы показываем наиболее распространённую версию К-карты с 5 переменными, карту наложения.

Рис. 4. Карта Карно с 5-ю переменными (наложение). «Высокий» выход, если вход ABCDE представляет собой простое число в двоичном виде.
Рис. 4. Карта Карно с 5-ю переменными (наложение). «Высокий» выход, если вход ABCDE представляет собой простое число в двоичном виде.

Если сравнить шаблоны на обеих картах, некоторые ячейки в правой половине карты будут смещены, поскольку адресация в верхней части карты отличается. Нам также придётся по-другому подходить к выявлению общности между двумя половинами карты («зеркальный» подход для карт наложения уже не работает).

Наложите одну половину карты на другую половину. Любое перекрытие верхней и нижней карт является потенциальной группой. На рисунке ниже показано, что группа AB'DE (отмечена серым кружочком) состоит из двух расположенных друг над другом ячеек. Группа A'B'E (отмечена синим овалом) состоит из двух уложенных друг на друга пар ячеек.

Рассмотрим группу A'B'E и совпадения по переменным для этих 4-х ячеек. Здесь верен шаблон ABCDE = 00××1 для этой группы. То есть A, B, E – это одни и те же 001 для всех ячеек этой группы. И CD = ××, то есть значения этих переменных для ячеек группы варьируются, они могут быть равны как 0, так и 1. Поскольку ABCDE = 00××1, тогда CD = ×× отбрасываем, группа из 4 клеток покрывается шаблоном A'B'××E = A'B'E.

Рис. 5. Карта Карно с 5-ю переменными (наложение). Разместим подкарты одну под другой (если смотреть с такого ракурса, то создаётся впечатление, что карты перекрываются), чтобы показать наложение, позволяющее группировать ячейки.
Рис. 5. Карта Карно с 5-ю переменными (наложение). Разместим подкарты одну под другой (если смотреть с такого ракурса, то создаётся впечатление, что карты перекрываются), чтобы показать наложение, позволяющее группировать ячейки.

Приведенная выше К-карта наложения с пятью переменными показана в виде стека (т.е. «стопкой») подкарт.

Ниже приводится пример карты Карно с шестью переменными. Мы мысленно сложили друг под другом четыре подкарты, чтобы увидеть группу из 4-х ячеек, соответствующую Вых. = C'F'.

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

Компаратор величин (используемый для иллюстрации работы K-карты с 6-ю переменными) сравнивает два двоичных числа, указывая, равны ли они, больше или меньше друг друга на трёх соответствующих выходах. Компаратор с тремя битами имеет два входа A2A1A0 и B2B1B0. Этот «сравниватель» на интегральной схеме (модели 7485) на самом деле будет иметь четыре входа, но приведённая ниже карта Карно должна иметь разумный размер. Мы будем решать только для выхода A > B (т.е. схема определяет, является ли A больше B или нет).

K-карта с шестью переменными

На рисунке 8 ниже карта Карно с 6-ю переменными помогает упростить логику нашего 3-битного компаратора величин. Это тип карты с наложением. Двоичный адресный код в верхней и нижней левой части карты не является полным 3-битным кодом Грея.

Хотя 2-битные адресные коды четырёх дополнительных карт кодом Грея таки являются. Найдите повторяющиеся выражения, сложив четыре дополнительных подкарты друг на друга (так, как на рисунке 6 выше). Могут найтись ячейки, общие для всех четырёх подкарт, хотя в приведённом на рисунке 8 ниже примере таких случаев нет. В примере ниже есть ячейки, общие для 2-3-х подкарт, но не для всех четырёх.

Рис. 7. Принципиальная схема компаратора величин. На вход подаются два числа. На трёх выходах – меньше, равенство или больше?
Рис. 7. Принципиальная схема компаратора величин. На вход подаются два числа. На трёх выходах – меньше, равенство или больше?

Результатом выхода A > B будет неравенство ABC > XYZ на карте Карно с 6-ю переменными, изображённой на рисунке 8 ниже. ABC – это двоичные числа в заголовках строк. XYZ – это двоичные числа в заголовках столбцов (т.е. на входе мы подаём два 3-битных числа, которые нужно сравнить).

Рис. 8. Карта Карно с шестью переменными (наложение) для выхода A > B компаратора величин.
Рис. 8. Карта Карно с шестью переменными (наложение) для выхода A > B компаратора величин.

Если ABC больше XYZ, выводится 1 (и 0, если AB). В первой строке ABC = 000, это число не может быть больше любого из значений XYZ. Во всей этой строке нет единиц. Во второй строке, ABC = 001, только первая ячейка ABCXYZ = 001000 удовлетворяет условию, что АВС (= 001) больше , чем XYZ (= 000). В первую ячейку второй строки вводится единственная в этой строке 1. Четвёртая строка, ABC = 010, содержит пару единиц. Третья строка, АВС = 011 имеет тройку единиц. Таким образом, мало-помалу заполняем карту единицами в любых ячейках, где ABC больше чем XYZ.

При группировании ячеек, если есть возможность, формируйте группы со смежными подкартами. В данном примере в трёх подкартах из четырёх можно найти ячейки, которые можно так сгруппировать (когда группа включает в себя ячейки из разных подкарт). Ищите в таком порядке следующие группы:

  1. 1 группа из 16 ячеек
  2. 2 группы по 8 ячеек
  3. 4 группы по 4 ячейки

Группа из 16 ячеек AX' занимает всю нижнюю левую подкарту; однако глобального совпадения в данном примере с другими подкартами нет.

Все заполненные ячейки нижней левой подкарты можно разделить на 2 группы по 8 ячеек, каждая состоит из 2-х рядов по 4 ячейки. Совпадений с другими подкартами тоже нет.

Среди четырёх групп из 4-х ячеек на нижней левой подкарте одна из групп имеет совпадения на других двух подкартах (верхней левой и нижней правой), они показаны на карте Карно (рисунок 8 выше) с соответствующими членами Суммы-Произведений. Показано окончательное упрощение Суммы-Произведений для всех семи членов.

Подсчитав единицы на всей карте, видим, что их всего 16 + 6 + 6 = 28 штук. Без логической редукции с помощью К-карты в нашем выходе СуП было бы 28 членов в Сумме-Произведений, каждый с 6-ю входами. Карта Карно дала семь членов упрощённой Суммы-Произведений, в каждом из которых не более чем 4 входа. Настолько радикально упрощать – в этом-то и кроется суть карт Карно!

Схему подключения на основе итогового логического выражения рисовать не будем. Однако можно прикинуть список деталей нашего 3-битного компаратора величин, определяющего, является ли неравенство ABC > XYZ истинным. Всего понадобится 4 ТТЛ-детали:

  • Модель 7410 (1 шт.) – тройной вентиль И-НЕ с 3-мя входами (AX', ABY', BX'Y').
  • Модель 7420 (2 шт.) – двойной логический элемент И-НЕ с 4-мя входами (ABCZ', ACY'Z', BCX'Z', CX'Y'Z').
  • Модель 7430 (1 шт.) – вентиль И-НЕ с 8-ю входами для вывода итогового результата от входных 7-ми элементов.

Итог (для всей главы «Карты Карно»)

  • Булева алгебра, карты Карно и САПР (автоматизированное проектирование) – это методы логического упрощения. Цель упрощения логики – получить решение с минимальными затратами.
  • Решение с минимальными затратами – это допустимая логическая редукция с минимальным количеством вентилей и минимальным количеством входов.
  • Диаграммы Венна позволяют визуализировать логические выражения, облегчая переход к картам Ка́рно.
  • Ячейки карты Ка́рно организованы в порядке кода Грея, что позволяет визуализировать избыточность в логических выражениях, что в свою очередь позволяет произвести упрощение.
  • Более распространённые выражения Сумма-Произведений (СуП, также известна как сумма минтермов) реализуются как логические элементы И (произведения), которые передаются в единый логический элемент ИЛИ (сумма).
  • Выражения Суммы-Произведений (логика И/ИЛИ) эквивалентны реализации И-НЕ/И-НЕ. Все вентили И и ИЛИ заменяются на И-НЕ.
  • Реже используемые выражения Произведение-Сумм (ПрС) реализуются как логические элементы ИЛИ (суммы), входящие в единый элемент И (произведение). Выражения Произведение-Сумм основаны на нулях (макстермах) отображаемых на карте Карно.

См.также

Внешние ссылки