Проектирование и синтез комбинационных схем

Комбинационные схемы и этапы их проектирования

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

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

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

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

!Интерактивная модель системы предупреждения

Язык логики: от слов к математике

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

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

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

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

Четыре этапа проектирования

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

!Схема этапов проектирования комбинационной схемы

1. Словесное описание и постановка задачи

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

> Хорошо сформулированное словесное описание — это половина успеха. Ошибка на этом этапе приведет к тому, что вы идеально спроектируете схему, которая делает совершенно не то, что нужно заказчику.

2. Формализация (составление таблицы истинности)

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

3. Минимизация логической функции

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

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

Зачем нужна минимизация в реальном мире?

Снижение стоимости: Меньше логических элементов (вентилей) — дешевле производство чипа.

Уменьшение габаритов: Оптимизированная схема занимает меньше площади на кремниевом кристалле.

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

Снижение энергопотребления: Меньше транзисторов — меньше потребление тока и меньше нагрев.

4. Синтез логической схемы

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

Практический пример: Система электронного голосования

Чтобы закрепить понимание этапов, пройдем весь путь проектирования на конкретном примере.

Этап 1: Словесное описание Нам нужно спроектировать систему тайного голосования для жюри из трех человек. У каждого члена жюри есть кнопка («За»). Решение принимается большинством голосов. Если два или три члена жюри нажали кнопку, загорается зеленая лампа (решение принято). Если кнопку нажал только один человек или никто не нажал — лампа не горит.

Определяем переменные:

Входы: , , (кнопки трех членов жюри. — нажал, — не нажал).

Выход: (зеленая лампа. — горит, — не горит).

Этап 2: Формализация Составим таблицу истинности. У нас 3 входа, значит будет строк.

| A | B | C | Y (Результат) | Пояснение | |---|---|---|---|---| | 0 | 0 | 0 | 0 | Никто не проголосовал | | 0 | 0 | 1 | 0 | Проголосовал только C | | 0 | 1 | 0 | 0 | Проголосовал только B | | 0 | 1 | 1 | 1 | Проголосовали B и C (большинство) | | 1 | 0 | 0 | 0 | Проголосовал только A | | 1 | 0 | 1 | 1 | Проголосовали A и C (большинство) | | 1 | 1 | 0 | 1 | Проголосовали A и B (большинство) | | 1 | 1 | 1 | 1 | Проголосовали все трое |

Этап 3: Минимизация Если записать функцию «в лоб» по строкам, где , мы получим сложное выражение:

Такая схема потребует множества элементов. Применив законы склеивания и поглощения булевой алгебры (или карту Карно), мы можем значительно упростить это выражение. Логика подсказывает: решение принимается, если согласны А и В, ИЛИ согласны В и С, ИЛИ согласны А и С.

Минимизированная функция выглядит так:

Этап 4: Синтез Теперь читаем полученную формулу и переводим её в «железо»:

Нам понадобятся три логических элемента «И» (для операций умножения: , , ).

Выходы этих трех элементов нужно подать на входы одного логического элемента «ИЛИ» на три входа (для операции сложения).

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

Проектирование одновыходной комбинационной схемы

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

Одновыходная схема решает задачу, ответом на которую является простое «да» или «нет» ( или ). Представьте себе систему управления автомобильным кондиционером: муфта компрессора (единственный выход) должна включиться, если двигатель заведен, кнопка «A/C» нажата, а температура в салоне выше заданной. Вся эта сложная логика сводится к одному управляющему сигналу.

Канонические формы: стандартизация логики

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

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

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

Для каждой такой строки записываем логическое произведение (операция «И») всех входных переменных. Если переменная в этой строке равна , мы пишем ее с инверсией (с чертой сверху), если — без инверсии. Такое произведение называется минтермом.

Складываем все полученные минтермы с помощью логического сложения (операция «ИЛИ»).

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

Таблица истинности для этой задачи будет содержать строк. Сирена сработает () в пяти случаях:

(только кнопка)

(температура и кнопка)

(дым и кнопка)

(дым и температура)

(сработали все три)

Запишем СДНФ для нашей функции:

Эта формула абсолютно точно описывает работу системы. Однако, если мы попытаемся собрать устройство прямо по ней, нам потребуется 5 элементов «И» (каждый на 3 входа), 5 инверторов и один огромный элемент «ИЛИ» на 5 входов. Это дорого, громоздко и неэффективно.

Карты Карно: визуальная минимизация

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

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

!Интерактивная карта Карно для 3 переменных

Правила работы с картой Карно для минимизации функции:

Переносим единицы из таблицы истинности в соответствующие ячейки карты.

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

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

Карта обладает свойством тора: левый край считается соседним с правым, а верхний — с нижним.

Цель — охватить все единицы минимальным количеством максимально больших контуров.

Каждый контур превращается в упрощенное логическое произведение. Переменные, которые внутри контура меняют свое значение (от к ), сокращаются и исчезают из формулы.

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

Минимизированная функция: . Вместо горы радиодеталей нам теперь нужен всего один элемент «И» и один элемент «ИЛИ».

Переход к универсальному базису

В теории мы используем три базовых элемента: И (AND), ИЛИ (OR), НЕ (NOT). Однако на заводах по производству микросхем делать разные типы транзисторных сборок невыгодно. Гораздо дешевле штамповать миллионы абсолютно одинаковых элементов.

В цифровой электронике существуют универсальные базисы — логические элементы И-НЕ (NAND) и ИЛИ-НЕ (NOR). Используя только элементы И-НЕ, можно собрать любую мыслимую логическую схему, включая обычные И, ИЛИ и НЕ.

> Представьте, что вы строите дом, и у вас есть только один тип кирпича. Благодаря особой форме этого кирпича, вы можете выкладывать из него и прямые стены, и арки, и колонны. Элемент И-НЕ — это такой универсальный «кирпич» цифровой схемотехники.

Чтобы перевести нашу минимизированную функцию в базис И-НЕ, инженеры применяют правило двойной инверсии (двойное отрицание не меняет сути) и законы де Моргана.

Теперь вся схема состоит исключительно из операций умножения с инверсией. Это позволяет реализовать устройство на стандартных дешевых микросхемах.

Динамические параметры: когда время имеет значение

До этого момента мы рассматривали комбинационные схемы как идеальные математические объекты. Изменился вход — мгновенно изменился выход. В реальном мире физика диктует свои правила.

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

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

!Временная диаграмма статического риска сбоя

Разница во времени прохождения сигналов по разным путям порождает опасное явление — гонки сигналов (или риск сбоя, hazard).

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

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

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

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

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

Синтез комбинационных многовыходных схем

В предыдущих материалах мы научились проектировать устройства, которые выдают единственный ответ: «да» или «нет». Однако в реальной цифровой технике большинство задач требует одновременного управления целым набором сигналов. Процессору нужно выдать 32-битный результат вычисления, контроллеру дисплея — зажечь нужные сегменты цифры, а роутеру — направить пакет данных на один из множества портов. Для решения этих задач применяются многовыходные комбинационные схемы.

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

!Схема совместного использования логики

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

Мультиплексоры и демультиплексоры: управление потоками

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

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

Рассмотрим простейший мультиплексор «2 в 1». У него есть два информационных входа ( и ), один адресный вход () и один выход (). Логическое уравнение такого устройства выглядит так:

Где:

— итоговый сигнал на выходе;

— управляющий сигнал (если , работает левая часть уравнения, если — правая);

— данные на информационных входах.

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

Шифраторы и дешифраторы: переводчики цифрового мира

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

Дешифратор (Decoder) преобразует двоичный код на своих входах в активный сигнал только на одном из выходов.

> Представьте умный замок в камере хранения. Вы вводите на клавиатуре двоичный пин-код 101 (число 5 в десятичной системе). Дешифратор внутри замка анализирует этот код и подает напряжение только на пятый провод, который открывает дверцу ячейки №5. Остальные провода остаются обесточенными.

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

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

Арифметические схемы: как компьютер считает

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

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

Логика полусумматора описывается двумя уравнениями:

Где:

— логическая операция «Исключающее ИЛИ» (XOR). Она выдает , только если входы разные ( или ). Если входы одинаковые ( или ), сумма в текущем разряде равна .

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

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

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

!Интерактивный полный сумматор

Синтез на основе ПЗУ и ПЛМ

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

Один из самых изящных способов реализовать любую комбинационную функцию — использовать Постоянное запоминающее устройство (ПЗУ), или ROM (Read-Only Memory).

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

Например, нам нужна сложная схема с 4 входами и 3 выходами. Мы берем ПЗУ на 16 ячеек (), где каждая ячейка хранит 3 бита. Подавая на вход комбинацию 1011 (адрес 11), ПЗУ просто выдает заранее записанные 3 бита ответа. Никакой минимизации, никаких карт Карно — чистая табличная подстановка.

Недостаток ПЗУ в том, что при увеличении числа входов размер памяти растет экспоненциально. Если входов 20, потребуется более миллиона ячеек, даже если полезных комбинаций всего пара сотен.

Для оптимизации применяют Программируемые логические матрицы (ПЛМ). ПЛМ состоит из двух матриц: матрицы элементов «И» и матрицы элементов «ИЛИ». Инженер (с помощью специального программатора) буквально пережигает микроскопические предохранители внутри чипа, создавая нужные связи. Матрица «И» формирует только те логические произведения (термы), которые реально нужны, а матрица «ИЛИ» собирает их для нужных выходов. Это позволяет создавать компактные и быстрые многовыходные схемы.

Динамические параметры: проблема перекоса

В предыдущей статье мы обсуждали задержку распространения сигнала и риск сбоя (гонки сигналов) в одновыходных схемах. В многовыходных схемах эта проблема выходит на новый уровень и называется перекосом сигналов (skew).

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

Представьте, что дешифратор должен переключить выходной код с 01 на 10. В идеальном математическом мире это происходит мгновенно. В реальности левый бит может переключиться с на за 2 наносекунды, а правый бит с на — за 3 наносекунды. В течение одной наносекунды на выходе будет присутствовать ошибочный код 11.

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

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

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

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

Понимание динамики критически важно. Именно динамические параметры определяют, почему один процессор работает на частоте 2 ГГц, а другой — на 5 ГГц, и почему плохо спроектированная схема может выдавать случайные ошибки, даже если ее таблица истинности абсолютно верна.

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

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

> Представьте себе садовый шланг. Когда вы открываете кран, вода не появляется на другом конце шланга мгновенно. Ей нужно время, чтобы заполнить пустой объем и дойти до конца. В электронике роль «объема» играет паразитная емкость транзисторов и проводов, а роль «воды» — электрический заряд.

Инженеры различают два типа задержек:

— время задержки при переходе выходного сигнала от низкого уровня к высокому (от к , Low-to-High).

— время задержки при переходе выходного сигнала от высокого уровня к низкому (от к , High-to-Low).

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

Где:

— средняя задержка распространения (от англ. propagation delay);

— время переключения выхода в единицу;

— время переключения выхода в ноль.

Время задержки измеряется в наносекундах (нс, секунды) или пикосекундах (пс, секунды).

| Семейство логики | Технология | Типичная задержка на вентиль () | | :--- | :--- | :--- | | Стандартная ТТЛ (74xx) | Биполярные транзисторы | ~10 нс | | Быстрая КМОП (74HC) | Полевые транзисторы | ~9 нс | | Современные процессоры | FinFET (нанометровые нормы) | ~10-50 пс |

Критический путь схемы

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

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

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

Рассмотрим пример. Допустим, у нас есть схема, состоящая из трех элементов: НЕ (задержка 1 нс), И (задержка 2 нс) и ИЛИ (задержка 3 нс).

Путь №1 идет напрямую через элемент ИЛИ: задержка составит 3 нс.

Путь №2 идет через элементы И, а затем ИЛИ: нс.

Путь №3 (критический) идет через НЕ, затем И, затем ИЛИ: нс.

!Схема логического устройства с выделенным критическим путем

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

Связь между задержкой и частотой описывается базовой формулой:

Где:

— максимальная тактовая частота (в Герцах);

— суммарное время задержки по критическому пути (в секундах).

Если критический путь процессора составляет 0,5 наносекунды ( с), то его максимальная частота составит Гц, то есть 2 ГГц. Чтобы сделать процессор быстрее, инженерам нужно либо уменьшать задержку самих транзисторов (переходить на новый техпроцесс), либо менять архитектуру схемы так, чтобы сократить количество вентилей на критическом пути.

Гонки сигналов и статический риск сбоя

Разница во времени прохождения сигналов по разным путям порождает одно из самых неприятных явлений в цифровой схемотехнике — гонки сигналов (race condition), которые приводят к риску сбоя (hazard).

Сбой (или «глюк») — это кратковременное появление неверного сигнала на выходе схемы в момент переключения входов.

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

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

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

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

Что произойдет в динамике:

Момент времени 0 нс: становится . Левый элемент И мгновенно (для простоты) видит и выдает .

В этот же момент правый элемент И все еще получает старый сигнал от инвертора (инвертор еще не успел переключиться). Правый элемент видит и тоже выдает .

Оба элемента И выдают нули. Элемент ИЛИ собирает их и выдает на общий выход .

Момент времени 2 нс: Инвертор наконец-то срабатывает и выдает . Правый элемент И видит . Выход возвращается в .

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

!Интерактивная временная диаграмма гонок сигналов

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

Методы борьбы с перекосом и сбоями

Разница во времени прибытия сигналов называется перекосом (skew). Чтобы бороться с перекосом и устранять риски сбоев, инженеры применяют несколько методов:

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

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

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

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

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

Но что делать, если перед нами стоит задача спроектировать блок управления микропроцессором, где на входе 16 сигналов, а на выходе — 32? Карта Карно для 16 переменных — это математический кошмар, состоящий из 65 536 ячеек. Минимизировать такую функцию вручную невозможно, а полученная схема из вентилей будет настолько запутанной, что время задержки сигнала (тот самый критический путь, о котором мы говорили ранее) станет непредсказуемым.

Инженеры нашли элегантный выход из этой ситуации. Они задали себе вопрос: зачем каждый раз вычислять значение логической функции, если можно заранее вычислить все возможные ответы и просто запомнить их? Так родилась идея реализации комбинационных схем с помощью постоянного запоминающего устройства (ПЗУ, или ROM — Read-Only Memory).

ПЗУ как универсальная таблица подстановки

В повседневной жизни мы постоянно используем принцип ПЗУ.

> Представьте, что вам нужно узнать квадрат числа 7. Вы можете вычислить его в уме: . Это алгоритмический подход (аналог схемы из логических вентилей). А можете открыть таблицу умножения на задней обложке тетради, найти строку «7», столбец «7» и прочитать готовый ответ «49». Таблица умножения — это и есть ПЗУ.

В цифровой электронике ПЗУ — это микросхема памяти, которая хранит заранее записанные данные. У любой микросхемы памяти есть два главных интерфейса:

Адресная шина — набор входов, на которые подается двоичный код (номер ячейки памяти).

Шина данных — набор выходов, на которых появляется содержимое выбранной ячейки.

Главный секрет синтеза схем на ПЗУ звучит так: входы комбинационной схемы подключаются к адресной шине ПЗУ, а выходы схемы снимаются с шины данных.

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

!Схема преобразования таблицы истинности в структуру ПЗУ

Внутреннее устройство ПЗУ

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

Дешифратор адреса (Decoder). Если у ПЗУ есть адресных входов, дешифратор преобразует их в внутренних линий. При любой комбинации нулей и единиц на входе, активной (равной единице) становится только одна внутренняя линия. Мы подробно разбирали работу дешифраторов в статье о многовыходных схемах.

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

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

Практический пример: Аппаратный возводитель в квадрат

Давайте спроектируем устройство, которое принимает на вход 3-битное двоичное число и выдает на выходе его квадрат .

Если бы мы делали это на вентилях, нам пришлось бы составлять сложные уравнения. С ПЗУ все сводится к трем шагам.

Шаг 1. Определение размерности. Входное число имеет 3 бита. Значит, у нашего ПЗУ будет 3 адресных входа (). Количество ячеек памяти составит . Максимальное входное число — это (в двоичном коде ). Его квадрат равен . Чтобы записать число в двоичном виде (), нам потребуется 6 бит. Значит, у ПЗУ должно быть 6 выходов данных (). Нам нужна микросхема ПЗУ размером бит.

Шаг 2. Составление таблицы истинности (карты прошивки). Мы просто вычисляем квадраты всех чисел от 0 до 7 и переводим их в двоичный код.

| Вход X (Десятичный) | Адрес ПЗУ () | Выход Y () | Данные в ПЗУ () | | :--- | :--- | :--- | :--- | | 0 | 000 | 0 | 000000 | | 1 | 001 | 1 | 000001 | | 2 | 010 | 4 | 000100 | | 3 | 011 | 9 | 001001 | | 4 | 100 | 16 | 010000 | | 5 | 101 | 25 | 011001 | | 6 | 110 | 36 | 100100 | | 7 | 111 | 49 | 110001 |

Шаг 3. Прошивка. Мы берем чистую микросхему ПЗУ и с помощью специального прибора (программатора) записываем правый столбец таблицы в соответствующие адреса. Схема готова! Никаких карт Карно, никаких гонок сигналов.

!Интерактивный симулятор ПЗУ для возведения в квадрат

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

Использование ПЗУ для синтеза комбинационных схем кардинально меняет подход инженера. У этого метода есть неоспоримые преимущества:

* Нулевое время на проектирование логики. Не нужно ничего минимизировать. Таблица истинности — это и есть готовый проект. * Легкость модификации. Если в логике найдена ошибка или нужно изменить алгоритм работы, не нужно перепаивать провода и менять микросхемы. Достаточно просто «перепрошить» ПЗУ новыми данными. * Предсказуемые динамические параметры. Вспомните прошлую статью: в схемах на вентилях сигналы идут разными путями, вызывая перекосы и глюки. В ПЗУ время доступа к любой ячейке памяти одинаково. Задержка распространения сигнала строго фиксирована и указана в паспорте микросхемы. * Многовыходность «из коробки». Добавление нового выхода не требует создания новой схемы, достаточно взять ПЗУ с большей разрядностью шины данных.

Однако в инженерии не бывает идеальных решений. За простоту приходится платить, и у ПЗУ есть серьезные недостатки:

* Экспоненциальный рост объема. Это главная проблема. Если у вашей функции 4 входа, нужно всего 16 ячеек памяти. Но если входов 20 (что нормально для современных контроллеров), вам потребуется ячеек, то есть более 1 миллиона! При этом большинство ячеек могут хранить нули, то есть память будет расходоваться впустую. * Скорость работы. Чтение данных из матрицы памяти ПЗУ обычно происходит медленнее, чем прохождение сигнала через 2-3 быстрых логических вентиля, специально оптимизированных под конкретную задачу.

Проблема экспоненциального роста объема памяти привела инженеров к мысли: если в таблице истинности много нулей, зачем хранить их все? Что если сделать программируемым не только матрицу ИЛИ (данные), но и матрицу И (дешифратор), чтобы схема реагировала только на нужные комбинации входов?

Эта идея легла в основу Программируемых логических матриц (ПЛМ) и современных ПЛИС (FPGA), которые стали стандартом в современной цифровой электронике. Но базовый принцип — замена жестко спаянных проводов на программируемую структуру — начался именно с ПЗУ.