Переключательные функции и методы их минимизации

Основы переключательных функций и их представление

Современная цифровая электроника, вычислительная техника и системы автоматики строятся на базе устройств, которые оперируют всего двумя состояниями: включено и выключено, истина и ложь, напряжение есть и напряжения нет. Для математического описания таких систем используется специальный аппарат.

Переключательная функция (также известная как булева функция или логическая функция) — это математическая основа работы любого цифрового устройства, от простейшего калькулятора до современного процессора.

> Переключательной функцией называется такая функция от нескольких аргументов, все аргументы которой и само значение функции принимают значения только из множества {0, 1}.

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

Например, если система зависит от 3 датчиков (аргументов), то существует уникальных комбинаций их состояний. Для каждой из этих 8 комбинаций переключательная функция должна определить итоговый результат: 0 или 1.

Базовые логические операции

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

Инверсия (NOT, логическое отрицание). Обозначается чертой над переменной или знаком . Меняет значение переменной на противоположное. Если на входе 1, на выходе 0.

Конъюнкция (AND, логическое умножение). Обозначается знаком или . Результат равен 1 только в том случае, если все входные переменные равны 1. В остальных случаях результат равен 0.

Дизъюнкция (OR, логическое сложение). Обозначается знаком или . Результат равен 1, если хотя бы одна из входных переменных равна 1.

Для наглядности сведем результаты этих операций для двух переменных и в единую таблицу.

| | | Инверсия | Конъюнкция | Дизъюнкция | |:---:|:---:|:---:|:---:|:---:| | 0 | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 0 | 0 | 1 | | 1 | 1 | 0 | 1 | 1 |

Понимание этих трех операций позволяет перейти к способам представления более сложных логических зависимостей.

Способы представления переключательных функций

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

Табличный способ (Таблицы истинности)

Самый очевидный и наглядный способ задать переключательную функцию — перечислить все возможные комбинации входных переменных и указать для каждой из них значение функции. Такая таблица называется таблицей истинности.

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

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

!Схема преобразования таблицы истинности в логическую цепь

Аналитический способ (Формулы)

Таблицы истинности удобны для функций от 2-4 переменных. Если переменных 10, таблица будет состоять из строк, что делает ее нечитаемой. В таких случаях используют аналитическую форму — запись в виде алгебраического выражения.

Любую таблицу истинности можно перевести в формулу. Наиболее стандартизированным подходом является использование Совершенной дизъюнктивной нормальной формы (СДНФ).

Алгоритм построения СДНФ по таблице истинности:

Найти в таблице истинности все строки, где значение функции равно 1.

Для каждой такой строки составить логическое произведение (конъюнкцию) всех переменных. Этот элемент называется минтермом.

Если переменная в строке равна 1, она записывается в минтерм без изменений. Если переменная равна 0, она записывается с инверсией.

Соединить все полученные минтермы знаком логического сложения (дизъюнкции).

Рассмотрим пример. Пусть функция равна 1 в двух случаях: когда и когда . Для первой строки () минтерм будет выглядеть как . Для второй строки () минтерм будет . Итоговая функция в СДНФ: .

Зачем нужна минимизация переключательных функций

Полученная аналитическая форма (например, СДНФ) точно описывает логику работы устройства, но она редко бывает оптимальной.

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

Стоимость производства (больше кремния, сложнее плата).

Энергопотребление (каждый элемент потребляет ток).

Быстродействие (сигналу нужно время, чтобы пройти через каждый логический вентиль).

Надежность (чем больше элементов, тем выше вероятность поломки).

Процесс упрощения логического выражения без изменения его таблицы истинности называется минимизацией переключательных функций.

> Цель минимизации — понижение стоимости технической реализации и повышение эффективности цифровой схемы путем сокращения числа логических операций.

Представьте, что после составления СДНФ мы получили формулу: . Для ее реализации потребуется два элемента умножения, один элемент сложения и один инвертор. Однако, применяя законы логики, мы можем вынести за скобки: . Поскольку переменная плюс ее инверсия всегда дают 1 (), формула сокращается до , что равно просто .

Вместо четырех логических элементов нам теперь нужен ровно ноль — выход напрямую соединяется со входом . Экономия ресурсов составила 100%.

!Сравнение сложной логической схемы и ее минимизированного варианта

Способы минимизации логических функций

В современной схемотехнике применяется несколько основных методов минимизации, выбор которых зависит от количества переменных и требуемой степени автоматизации.

1. Алгебраический метод

Основан на применении законов булевой алгебры (законы поглощения, склеивания, де Моргана и др.). Метод заключается в последовательном преобразовании формулы. Главный недостаток — отсутствие четкого алгоритма. Инженер должен сам "увидеть", какие законы применить, что делает метод сложным для функций с числом переменных больше трех.

2. Метод минимизирующих карт (Карты Карно)

Графический метод минимизации. Таблица истинности перестраивается в специальную двумерную матрицу (карту Карно или карту Вейча), где соседние ячейки отличаются только одной переменной. Это позволяет визуально находить группы единиц и объединять их, автоматически исключая лишние переменные. Метод идеален для ручной минимизации функций от 3 до 5 переменных.

3. Метод Квайна — Мак-Класски

Строгий аналитический алгоритм, который состоит из двух этапов: нахождение всех простых импликант (операции склеивания и поглощения) и выбор минимального покрытия. В отличие от карт Карно, этот метод не требует визуального анализа и легко программируется. Именно алгоритм Квайна — Мак-Класски (и его современные эвристические модификации) лежит в основе программного обеспечения для автоматизированного проектирования электроники (EDA).

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

Минимизация методом непосредственных алгебраических преобразований

В предыдущей статье мы выяснили, что любую таблицу истинности можно превратить в математическую формулу — Совершенную дизъюнктивную нормальную форму (СДНФ). Однако полученные таким образом выражения часто получаются громоздкими. Реализация сложной формулы «в лоб» требует большого количества электронных компонентов, что удорожает производство и снижает надежность устройства.

Для решения этой проблемы применяется минимизация переключательных функций — процесс упрощения логического выражения при сохранении его исходной логики работы. Самым базовым и исторически первым способом решения этой задачи является метод непосредственных алгебраических преобразований.

> Метод непосредственных алгебраических преобразований заключается в последовательном применении законов и тождеств алгебры логики (Boolean algebra) к исходному выражению с целью сокращения количества переменных и логических операций.

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

Основные законы алгебры логики

Чтобы успешно минимизировать функции, необходимо знать базовые тождества. В алгебре логики нет чисел «2» или «3», есть только и . Это порождает уникальные свойства операций конъюнкции (логического умножения, AND) и дизъюнкции (логического сложения, OR).

Сведем основные законы, необходимые для преобразований, в таблицу. В формулах ниже , и — это логические переменные, принимающие значения или , знак означает логическое умножение, знак означает логическое сложение, а черта над переменной — это инверсия (логическое отрицание).

| Название закона | Для логического сложения | Для логического умножения | Описание | | :--- | :--- | :--- | :--- | | Идемпотентности | | | Повторение одного и того же сигнала не меняет результат. | | Операции с константами | , | , | Прибавление истины всегда дает истину, умножение на ложь всегда дает ложь. | | Исключенного третьего | | | Событие либо происходит, либо нет. Третьего не дано. | | Де Моргана | | | Отрицание суммы равно произведению отрицаний, и наоборот. |

Помимо этих специфических правил, в алгебре логики работают привычные нам переместительный (), сочетательный и распределительный законы.

Ключевые приемы минимизации

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

1. Закон склеивания

Закон склеивания позволяет объединить два слагаемых, которые отличаются только одной переменной (в одном слагаемом она прямая, а в другом — инверсная), и полностью избавиться от этой переменной.

Математически это записывается так:

Где — итоговая функция, и — логические переменные, — логическое умножение, — логическое сложение, — инверсия переменной .

Рассмотрим реальный пример. Допустим, мы проектируем систему управления кондиционером. Пусть — датчик присутствия людей в комнате ( — люди есть, — никого нет). Пусть — датчик освещенности ( — свет включен, — темно).

Изначально алгоритм задан так: «Включить кондиционер, если люди есть и свет включен (), ИЛИ если люди есть и свет выключен ()».

Применяя алгебру, мы выносим общий множитель за скобки:

По закону исключенного третьего, выражение в скобках всегда равно (свет либо включен, либо выключен). Получаем:

Вывод: датчик освещенности является фиктивной переменной. Кондиционер должен работать просто тогда, когда в комнате есть люди, независимо от света. Мы сэкономили один датчик и два логических вентиля.

!Визуализация закона склеивания

2. Закон поглощения

Закон поглощения применяется, когда одно простое слагаемое полностью перекрывает (поглощает) более сложное слагаемое, в состав которого оно входит.

Формула поглощения выглядит следующим образом:

Где — функция, и — переменные, — дизъюнкция, — конъюнкция.

Представьте систему выдачи кредита в банке. Условие — у клиента идеальная кредитная история. Условие — у клиента зарплата выше 500 000 руб. в месяц.

Правило банка звучит так: «Одобрить кредит, если у клиента идеальная история (), ИЛИ если у него идеальная история и при этом высокая зарплата ()».

Очевидно, что вторая часть правила избыточна. Если у клиента идеальная история (), кредит одобрят в любом случае, и проверять зарплату уже не нужно. Математически это доказывается вынесением за скобки:

По закону операций с константами, единица плюс что угодно дает единицу (). Следовательно, . Сложное условие поглотилось простым.

Пошаговый пример минимизации сложной функции

Давайте применим полученные знания для минимизации функции от трех переменных, заданной в СДНФ. Допустим, после составления таблицы истинности мы получили следующее выражение:

Где — переключательная функция, — входные аргументы, — их инверсии.

Шаг 1. Группировка слагаемых. Разобьем выражение на две пары, чтобы найти общие множители. Первая пара: Вторая пара:

Шаг 2. Применение закона склеивания к парам. В первой паре общий множитель — это . Выносим его за скобки:

Во второй паре общий множитель — это . Выносим его:

Шаг 3. Финальное склеивание. Подставим полученные упрощенные блоки обратно в функцию:

Теперь мы снова видим общий множитель, на этот раз это переменная . Выносим ее:

Поразительный результат! Исходная схема требовала 12 операций умножения, 3 операции сложения и несколько инверторов. После алгебраических преобразований выяснилось, что результат зависит исключительно от состояния датчика . Переменные и оказались полностью фиктивными.

Преимущества и недостатки метода

Алгебраический метод — это мощный инструмент, который должен быть в арсенале любого инженера-схемотехника или программиста, работающего с низкоуровневой логикой.

К его преимуществам относятся:

Отсутствие необходимости в дополнительных графических построениях или таблицах.

Развитие глубокого интуитивного понимания того, как работают логические элементы.

Возможность быстро упростить небольшие фрагменты кода (например, сложные условия if в программировании).

Однако у метода есть существенный недостаток — отсутствие строгого, детерминированного алгоритма. Инженер должен самостоятельно «увидеть», какие слагаемые лучше сгруппировать и какой закон применить. Если переменных становится больше трех-четырех, выражение разрастается до десятков символов, и человеческий мозг перестает замечать скрытые возможности для склеивания или поглощения.

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

Визуальная минимизация с помощью карт Карно

В предыдущей статье мы познакомились с алгебраическим методом минимизации переключательных функций. Мы выяснили, что с помощью законов поглощения и склеивания можно существенно упростить логическое выражение. Однако у этого подхода есть серьезный изъян: он требует развитой интуиции. Когда количество переменных превышает три или четыре, формула разрастается, и человеческий мозг перестает замечать скрытые возможности для упрощения.

Чтобы решить эту проблему, в 1952 году Эдвард Вейч предложил графический способ представления логических функций, который годом позже усовершенствовал Морис Карно. Этот метод получил название карты Карно (Karnaugh maps) и стал стандартом де-факто в инженерной практике для ручной минимизации цифровых схем.

> Карта Карно — это графическое представление таблицы истинности логической функции в виде двумерной сетки, где ячейки расположены таким образом, что логически соседние комбинации оказываются соседними и геометрически.

Главная идея метода заключается в том, чтобы перевести абстрактные алгебраические преобразования в простую визуальную задачу поиска и объединения прямоугольных блоков.

Секрет расположения: код Грея

Если мы возьмем обычную таблицу истинности для четырех переменных, комбинации нулей и единиц в ней идут в стандартном двоичном порядке: от до . Но если мы просто перенесем их в двумерную таблицу по порядку, визуального чуда не произойдет.

Чтобы метод работал, координаты строк и столбцов в карте Карно размечаются с использованием кода Грея (Gray code). Это специальная система счисления, в которой любые два соседних значения отличаются ровно на один бит (одну позицию).

Рассмотрим разницу на примере двух переменных. В таблице ниже представлены десятичные числа, их обычный двоичный код и код Грея.

| Десятичное число | Стандартный двоичный код | Код Грея | Отличие от предыдущего (в битах) | | :--- | :--- | :--- | :--- | | 0 | 00 | 00 | - | | 1 | 01 | 01 | 1 бит | | 2 | 10 | 11 | 1 бит (в двоичном — 2 бита) | | 3 | 11 | 10 | 1 бит |

Обратите внимание на переход от числа 1 к числу 2. В обычном двоичном коде меняются сразу оба бита (с на ). В коде Грея меняется только первый бит (с на ).

Именно это свойство позволяет применять закон склеивания визуально. Если в двух соседних клетках карты Карно стоят единицы, мы точно знаем, что их координаты отличаются только одной переменной. Следовательно, эту переменную можно исключить.

!Сетка карты Карно с кодом Грея

Тороидальная топология

Еще одна важная особенность карт Карно — их тороидальная топология. Плоская таблица на бумаге на самом деле представляет собой развертку трехмерной фигуры — тора (или, проще говоря, бублика).

Это означает, что края карты логически замкнуты друг на друга:

Самая верхняя строка является соседней для самой нижней строки.

Самый левый столбец является соседним для самого правого столбца.

Четыре угловые клетки карты также считаются соседями и могут быть объединены в одну группу.

Представьте себе экран в старой видеоигре вроде Pac-Man: когда персонаж уходит за левый край экрана, он тут же появляется с правого края. Карта Карно работает по точно такому же принципу.

Правила визуального склеивания

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

Объединять можно только те клетки, в которых стоят единицы (нули игнорируются).

Группы должны иметь форму прямоугольника или квадрата.

Количество клеток в одной группе должно быть степенью двойки: и так далее.

Одна и та же клетка может входить в несколько разных групп (пересечение разрешено).

Необходимо охватить все единицы на карте минимальным количеством групп.

Каждая группа должна быть максимально возможного размера.

Чем больше клеток в группе, тем сильнее упрощается формула. Например, в карте на 4 переменные (всего 16 клеток) объединение 2 клеток убирает 1 переменную. Объединение 4 клеток убирает 2 переменные. Если вам удалось объединить сразу 8 клеток, из четырех исходных переменных в формуле останется только одна!

Практический пример минимизации

Давайте спроектируем логику срабатывания домашней сигнализации. У нас есть три входных сигнала: — состояние системы (1 — охрана включена, 0 — выключена). — датчик входной двери (1 — открыта, 0 — закрыта). — датчик окна (1 — открыто, 0 — закрыто).

Где — логические переменные.

Допустим, мы хотим, чтобы тревога срабатывала, если система находится в режиме охраны, и при этом открыта дверь, либо открыто окно, либо открыто и то, и другое. Исходная неоптимизированная формула в совершенной форме выглядит так:

Где — функция тревоги, и — инверсии переменных (закрытые дверь и окно), — логическое умножение (И), — логическое сложение (ИЛИ).

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

Первая группа объединяет состояния, когда система включена и открыто окно, независимо от двери. Переменная (дверь) меняет свое значение внутри этой группы, поэтому мы ее отбрасываем. Остается: .

Вторая группа объединяет состояния, когда система включена и открыта дверь, независимо от окна. Переменная (окно) отбрасывается. Остается: .

Итоговая минимизированная функция:

Где — итоговый сигнал тревоги, — наши датчики.

Мы избавились от инверсий и сократили количество логических операций с 8 до 3. Схема стала дешевле и надежнее.

!Процесс объединения ячеек на карте Карно

Границы применимости метода

Карты Карно — это элегантный и наглядный инструмент, но он имеет свои физические ограничения.

* Идеально для 3-4 переменных: Карта легко рисуется на листе бумаги, все соседние связи очевидны. * Сложно для 5-6 переменных: Карта становится трехмерной. Для 5 переменных () приходится рисовать две карты 4x4 и представлять, что одна лежит поверх другой. Для 6 переменных () — четыре слоя. * Невозможно для : Человеческий мозг не способен визуализировать многомерные гиперкубы. При количестве переменных больше шести визуальный метод полностью теряет смысл.

Кроме того, визуальный метод невозможно запрограммировать. Компьютер не имеет "глаз", чтобы обводить прямоугольники. Поэтому для автоматизированного проектирования сложных процессоров и микроконтроллеров, где количество переменных исчисляется десятками, применяются строгие табличные алгоритмы. Самым известным из них является метод Квайна — Мак-Класски, который мы детально разберем в следующей статье.

Алгоритмические подходы: методы Квайна и Квайна — Мак-Класки

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

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

Метод Квайна: от визуального к формальному

В 1952 году американский логик и философ Уиллард Ван Орман Куайн (Квайн) предложил систематический способ минимизации булевых функций. Его подход полностью исключал интуицию и опирался исключительно на последовательное применение законов булевой алгебры.

> Метод Квайна — это алгоритм минимизации логических функций, основанный на исчерпывающем попарном применении операции склеивания ко всем возможным термам с последующим удалением избыточных элементов через операцию поглощения.

В основе метода лежат два фундаментальных тождества:

Склеивание:

Поглощение:

Где и — произвольные логические выражения или переменные, — инверсия переменной , — логическое умножение (конъюнкция), — логическое сложение (дизъюнкция).

Алгоритм Квайна работает надежно, но имеет существенный недостаток: на первом этапе необходимо сравнить каждый элемент функции с каждым другим элементом. Если функция содержит десятки состояний, количество попарных сравнений возрастает лавинообразно. Это делает классический метод Квайна крайне неэффективным даже для компьютеров.

Метод Квайна — Мак-Класки: оптимизация поиска

В 1956 году инженер Эдвард Мак-Класки усовершенствовал алгоритм Квайна, предложив элегантный способ сократить количество ненужных сравнений. Этот модифицированный алгоритм стал стандартом и получил название метод Квайна — Мак-Класки.

Главная инновация Мак-Класки заключалась в сортировке исходных данных. Вместо того чтобы сравнивать всё со всем, он предложил перевести логические состояния в двоичный код и сгруппировать их по количеству единиц (весу Хэмминга).

!Блок-схема алгоритма Квайна — Мак-Класки

Шаг 1: Группировка минтермов

Рассмотрим практический пример. Допустим, мы проектируем контроллер управления лифтом, логика которого описывается функцией четырех переменных: . Функция выдает сигнал разрешения движения (единицу) только для следующих десятичных номеров состояний: .

Переведем эти числа в двоичный код и разобьем на группы по количеству единиц:

| Группа | Десятичное число | Двоичный код () | Количество единиц | | :--- | :--- | :--- | :--- | | G0 | 0 | 0000 | 0 | | G1 | 1 | 0001 | 1 | | | 2 | 0010 | 1 | | | 8 | 1000 | 1 | | G2 | 9 | 1001 | 2 | | | 10 | 1010 | 2 |

Секрет этого разбиения прост: закон склеивания работает только для тех двоичных наборов, которые отличаются ровно на один бит. Следовательно, успешное склеивание возможно только между соседними группами (G0 с G1, G1 с G2). Нам больше не нужно сравнивать элементы из G0 с элементами из G2 — это математически бессмысленно.

Шаг 2: Попарное склеивание

Начинаем сравнивать каждый элемент группы G0 с каждым элементом группы G1. Если они отличаются одной позицией, мы ставим на это место прочерк (символ того, что переменная исключена).

Сравниваем G0 (0000) и G1: * 0000 и 0001 дают 000- (склеили 0 и 1) * 0000 и 0010 дают 00-0 (склеили 0 и 2) * 0000 и 1000 дают -000 (склеили 0 и 8)

Теперь сравниваем G1 и G2: * 0001 и 1001 дают -001 (склеили 1 и 9) * 1000 и 1001 дают 100- (склеили 8 и 9) * 0010 и 1010 дают -010 (склеили 2 и 10) * 1000 и 1010 дают 10-0 (склеили 8 и 10)

Шаг 3: Повторное склеивание

Полученные новые термы с одним прочерком снова разбиваются на группы и сравниваются. Склеивать можно только те термы, у которых прочерк стоит на одном и том же месте.

Сравниваем результаты: * 000- (0,1) и 100- (8,9) отличаются только первым битом. Результат: -00-. * -000 (0,8) и -001 (1,9) отличаются последним битом. Результат: -00-.

Как видим, мы получили одинаковый результат -00-, который покрывает исходные состояния . Дубликаты мы просто удаляем.

Аналогично склеиваем оставшиеся пары: * 00-0 (0,2) и 10-0 (8,10) дают -0-0. * -000 (0,8) и -010 (2,10) дают -0-0.

Снова удаляем дубликат. У нас остались два финальных выражения: -00- и -0-0. Дальнейшее склеивание невозможно, так как прочерки стоят в разных местах. Эти несклеиваемые остатки называются простыми импликантами.

Импликантная матрица и поиск минимального покрытия

Нахождение простых импликант — это только половина дела. Теперь из них нужно собрать итоговую формулу, которая будет максимально короткой, но при этом охватит все исходные единичные состояния функции.

Для этого строится импликантная матрица (таблица покрытий). По столбцам записываются исходные десятичные числа, а по строкам — найденные простые импликанты. На пересечении ставится крестик, если импликанта покрывает данное число.

!Импликантная матрица

| Простая импликанта | Покрываемые числа | 0 | 1 | 2 | 8 | 9 | 10 | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | P1: -00- | 0, 1, 8, 9 | X | X | | X | X | | | P2: -0-0 | 0, 2, 8, 10 | X | | X | X | | X |

Далее мы ищем столбцы, в которых стоит только один крестик.

В нашем примере число 1 покрывается только импликантой P1. Значит, P1 является существенной (ядровой) импликантой — мы обязаны включить ее в итоговую формулу, иначе схема не сработает для состояния 1. То же самое касается числа 2, которое покрывается только P2.

Поскольку P1 и P2 вместе покрывают абсолютно все столбцы (0, 1, 2, 8, 9, 10), наша итоговая минимальная функция состоит из их суммы.

Переведем двоичный код обратно в алгебраический вид. Прочерк означает отсутствие переменной, 0 — инверсию, 1 — прямую переменную: * P1 (-00-): переменные и вычеркнуты. Остается . * P2 (-0-0): переменные и вычеркнуты. Остается .

Итоговая минимизированная функция:

Где — сигнал разрешения движения лифта, — входные датчики, — инвертированные значения датчиков, — логическое И, — логическое ИЛИ.

Сравнение методов минимизации

Чтобы лучше понять место алгоритмических подходов в схемотехнике, сравним изученные методы:

| Характеристика | Алгебраический метод | Карты Карно | Метод Квайна — Мак-Класки | | :--- | :--- | :--- | :--- | | Основа метода | Интуиция и знание законов | Визуальное распознавание образов | Строгий математический алгоритм | | Оптимальное число переменных | 2-3 | 3-4 (максимум 6) | Любое (ограничено только мощностью ПК) | | Возможность автоматизации | Нет | Нет | Да (идеально для программирования) | | Сложность освоения | Высокая | Низкая | Средняя |

Метод Квайна — Мак-Класки стал историческим прорывом, проложившим путь к созданию современных систем автоматизированного проектирования (САПР). Хотя сегодня для минимизации функций с сотнями переменных используются еще более продвинутые эвристические алгоритмы (например, Espresso), все они концептуально опираются на идеи, заложенные Куайном и Мак-Класки в середине XX века.

Практическое применение минимизации логических функций в схемотехнике

На протяжении предыдущих частей курса мы погружались в математический аппарат булевой алгебры. Мы изучили законы логики, научились визуально группировать переменные с помощью карт Карно и освоили строгий алгоритм Квайна — Мак-Класки. Но математика ради математики редко интересует инженеров. Главный вопрос: как эти абстрактные нули и единицы превращаются в реальные процессоры, контроллеры и системы управления?

Любое логическое выражение — это чертеж физического устройства. В этой статье мы разберем, как минимизация переключательных функций напрямую влияет на габариты, стоимость и скорость работы современной электроники.

От математики к кремнию: физический смысл логики

В цифровой электронике базовые логические операции выполняются специальными электронными схемами — логическими вентилями (logic gates). Каждый вентиль состоит из микроскопических переключателей — транзисторов.

Операция конъюнкции реализуется вентилем И (AND*). Операция дизъюнкции — вентилем ИЛИ (OR*). Операция инверсии — вентилем НЕ (NOT*).

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

> Схемотехника — это искусство перевода математических формул на язык физических компонентов с максимальной эффективностью.

Если мы возьмем сложную, неминимизированную функцию, нам потребуется огромное количество вентилей. А каждый вентиль — это физический объект на кремниевом кристалле, который занимает место, потребляет ток и требует времени на срабатывание.

Три кита аппаратной оптимизации

Зачем инженеры тратят столько усилий на минимизацию? Ответ кроется в трех фундаментальных параметрах любой цифровой схемы.

Стоимость и площадь кристалла

Чем больше логических операций в функции, тем больше транзисторов нужно для ее реализации. Площадь кремниевого кристалла — один из самых дорогих ресурсов в IT-индустрии. Уменьшая количество переменных и термов в уравнении, мы напрямую сокращаем физический размер микрочипа. Меньший размер означает, что на одной кремниевой пластине поместится больше процессоров, что радикально снижает их себестоимость.

Задержка распространения сигнала

Электрический сигнал не проходит через транзисторы мгновенно. Каждому логическому вентилю требуются пикосекунды на переключение состояния. Это время называется задержкой распространения.

Если логическая функция имеет сложную многоуровневую структуру, сигнал должен пройти через длинную цепочку вентилей. Минимизация позволяет сократить количество логических уровней. Чем короче путь сигнала, тем выше тактовая частота, на которой может работать процессор.

Энергопотребление и тепловыделение

Каждый раз, когда транзистор переключается из 0 в 1 и обратно, он потребляет порцию энергии и выделяет тепло. Схема, состоящая из 100 вентилей, будет греться сильнее и разряжать батарею смартфона быстрее, чем схема, выполняющая ту же задачу с помощью 20 вентилей.

!Сравнение неминимизированной и минимизированной логической схемы

Практический пример: система управления освещением

Рассмотрим реальную задачу. Допустим, мы проектируем контроллер умного дома, который включает свет на лестнице. У нас есть три датчика:

— датчик движения на первом этаже.

— датчик движения на втором этаже.

— датчик освещенности (1 — на улице темно, 0 — светло).

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

Где — сигнал включения лампы, — состояния датчиков, — логическое И, — логическое ИЛИ, и — инвертированные значения.

Для аппаратной реализации этой формулы потребуется: * Два вентиля НЕ (для и ) * Шесть вентилей И (для умножения внутри скобок) * Два вентиля ИЛИ (для сложения скобок)

Итого: 10 логических элементов.

Теперь применим законы булевой алгебры (в частности, закон склеивания и распределительный закон), чтобы минимизировать функцию:

Посмотрим на новую схему: * Один вентиль ИЛИ (для ) * Один вентиль И (для умножения результата на )

Итого: 2 логических элемента.

| Характеристика | Исходная схема | Минимизированная схема | Улучшение | | :--- | :--- | :--- | :--- | | Количество вентилей | 10 шт. | 2 шт. | В 5 раз меньше | | Логические уровни (задержка) | 3 уровня | 2 уровня | На 33% быстрее | | Сложность разводки плат | Высокая (много пересечений) | Низкая (простые связи) | Значительное |

Мы только что сэкономили 80% аппаратных ресурсов, просто применив математику перед тем, как браться за паяльник.

Универсальные логические базисы: И-НЕ и ИЛИ-НЕ

В теории мы оперируем базисом И, ИЛИ, НЕ. Однако на практике заводы по производству микрочипов редко используют эти элементы в чистом виде.

В технологии КМОП (CMOS), на которой строится подавляющее большинство современной электроники, самым простым, быстрым и дешевым в производстве вентилем является И-НЕ (NAND). Вентиль И-НЕ требует всего 4 транзистора, тогда как обычный вентиль И требует 6 транзисторов (он собирается из И-НЕ и дополнительного инвертора).

Именно здесь на помощь снова приходит математика, а именно — законы де Моргана:

Где — это операция И-НЕ, а — операция ИЛИ-НЕ. Благодаря этим законам любую, даже самую сложную переключательную функцию можно преобразовать так, чтобы она состояла исключительно из элементов И-НЕ. Это называется универсальным логическим базисом.

> Перевод минимизированной функции в базис И-НЕ (NAND) — стандартный этап промышленного проектирования, позволяющий создавать однородные, легко масштабируемые кристальные структуры.

Современные САПР и автоматический синтез

Сегодня инженеры редко минимизируют функции вручную. При проектировании современных процессоров, содержащих миллиарды транзисторов, используются языки описания аппаратуры.

Инженер описывает поведение системы на высоком уровне абстракции, а специальная программа — синтезатор (входящая в состав Систем Автоматизированного Проектирования, САПР) — берет на себя всю математическую работу.

!Интерфейс современной системы автоматизированного проектирования (САПР)

Внутри этих программ работают мощные эвристические алгоритмы, которые являются прямыми потомками метода Квайна — Мак-Класки. Они анализируют миллионы логических состояний, находят простые импликанты, удаляют избыточные связи и транслируют результат в оптимальную сеть из вентилей И-НЕ.

Заключение курса

Мы прошли путь от базовых понятий булевой алгебры до промышленной схемотехники. Переключательные функции — это не просто абстрактная математика. Это фундаментальный язык, на котором работает любая цифровая техника.

Умение минимизировать логические выражения позволяет инженерам создавать устройства, которые работают быстрее, стоят дешевле и потребляют меньше энергии. Независимо от того, проектируете ли вы простую схему для гаражных ворот или архитектуру нового нейропроцессора, принципы оптимизации, заложенные Карно, Куайном и Мак-Класки, остаются неизменными.