8.3. Комбинационные схемы

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

≈ 63 мин чтения · пунктирное подчёркивание — наведите или нажмите, чтобы увидеть пояснение

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

Комбинационную схему собирают из одних вентилей — достаточно правила «такие входы → такой выход». Последовательностной нужны элементы, хранящие состояние, — триггеры. В этом разделе мы научимся строить, упрощать и покупать готовой именно комбинационную логику; триггерам и автоматам посвящён раздел 8.4.

8.3.1Логические тождества

≈ 9 мин3 упр.

Главное

Тождества булевой алгебры упрощают схемы; самое важное — теорема де Моргана: $\overline{A B} = \overline{A} + \overline{B}$ , $\overline{A + B} = \overline{A} \overline{B}$ .
Необычные для школьной алгебры: $A + BC = (A + B) (A + C)$ , $A + A B = A$ , $A + \overline{A} B = A + B$ .
Исключающее ИЛИ: $A \oplus B = \overline{A} B + A \overline{B} = (A + B) \overline{A B}$ .

Логическое выражение — это и есть схема: каждый знак умножения означает вентиль И, каждый плюс — ИЛИ, каждая черта — инвертор. Значит, любое преобразование выражения, сохраняющее его смысл, даёт другую схему с тем же поведением, а часто — с меньшим числом корпусов и проводов. Правила таких преобразований собраны в таблице ниже. Почти все они проверяются в уме перебором двух значений; но среди них есть и такие, которых в школьной алгебре нет.

Начнём с самого полезного для схемотехника — пары тождеств, носящих имя де Моргана.

Теорема де Моргана

\overline{A B} = \overline{A} + \overline{B}, \overline{A + B} = \overline{A} \overline{B}

Обозначения:

\overline{A B}

\overline{A} + \overline{B}

\overline{A + B}

\overline{A} \overline{B}

Иначе говоря: инвертируйте все входы и выход — и И превратится в ИЛИ, а ИЛИ в И.

Проверить первое равенство легко: $\overline{A B}$ равно нулю лишь тогда, когда обе переменные — единицы; $\overline{A} + \overline{B}$ равно нулю тоже лишь тогда, когда обе инверсии — нули, то есть $A = B = 1$ . Смысл для схем такой: один и тот же физический вентиль И-НЕ можно рисовать двумя способами — и как И с кружком на выходе, и как ИЛИ с кружками на входах. Это то самое правило изображения вентилей по выполняемой функции, которое мы применяли к сигналам с активным НИЗКИМ уровнем в разделе 8.1.

Де Морган графически: снимаем кружок с выхода, ставим кружки на каждый вход и меняем знак функции (& ↔ 1) — вентиль остаётся тем же самым.

Основные тождества булевой алгебры. Левый и средний столбцы двойственны: замените И на ИЛИ, 1 на 0 — получите соседа.
Для И	Для ИЛИ	Смешанные
$A BC = (A B) C = A (BC)$	$A + B + C = (A + B) + C = A + (B + C)$	$A (B + C) = A B + A C$
$A B = B A$	$A + B = B + A$	$A + BC = (A + B) (A + C)$
$AA = A$	$A + A = A$	$A + A B = A$
$A \cdot 1 = A$	$A + 1 = 1$	$A + \overline{A} B = A + B$
$A \cdot 0 = 0$	$A + 0 = A$	$\overline{\overline{A}} = A$
$A \overline{A} = 0$	$A + \overline{A} = 1$	$\overline{1} = 0, \overline{0} = 1$
$\overline{A B} = \overline{A} + \overline{B}$	$\overline{A + B} = \overline{A} \overline{B}$	← теорема де Моргана

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

A + BC = (A + B) (A + C)

и два поглощения —

A + A B = A

A + \overline{A} B = A + B

Почему $A + A B = A$ ? Если $A = 1$ , обе части равны 1; если $A = 0$ , слагаемое $A B$ тоже нуль. Слагаемое $A B$ «поглощается»: оно ничего не добавляет к $A$ . Похоже рассуждаем и о $A + \overline{A} B$ : когда $A = 1$ , ответ 1, а когда $A = 0$ , выражение сводится к $B$ — вместе получается $A + B$ . На схеме это означает, что инвертор и вентиль И можно выбросить.

Пример: собираем Исключающее ИЛИ

Исключающее ИЛИ (таблица ниже) выдаёт 1, когда входы различны. Отдельный вентиль такой есть в каждом семействе, но полезно уметь получить его из И, ИЛИ и НЕ — и заодно увидеть, что вариантов несколько. Самый прямой путь — выписать строки таблицы, где выход равен 1, и сложить соответствующие произведения: строка $(0, 1)$ даёт $\overline{A} B$ , строка $(1, 0)$ даёт $A \overline{B}$ .

Исключающее ИЛИ: единица при несовпадении входов.
A	B	$A \oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

Исключающее ИЛИ: две формы

A \oplus B = \overline{A} B + A \overline{B} = (A + B) \overline{A B}

Обозначения:

\overline{A} B + A \overline{B}

(A + B) \overline{A B}

Первая форма требует двух инверторов, двух И и одного ИЛИ. Вторую можно прочитать прямо словами — «хотя бы один вход единица, но не оба сразу», — а получить её нетрудно и формально, одними тождествами из таблицы.

переход ко второй форме

A \oplus B = A \overline{A} + A \overline{B} + B \overline{A} + B \overline{B} = A (\overline{A} + \overline{B}) + B (\overline{A} + \overline{B}) = (A + B) (\overline{A} + \overline{B}) = (A + B) \overline{A B} .

Приём в первом шаге — добавить два нулевых слагаемых

A \overline{A}

B \overline{B}

(каждое тождественно равно 0), чтобы затем вынести общие множители; в последнем шаге

\overline{A} + \overline{B}

свёрнуто по де Моргану в

\overline{A B}

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

Вариант 1, «по строкам таблицы»: A ⊕ B = A̅B + AB̅ — два инвертора, два И, одно ИЛИ.

Вариант 2, «хотя бы один, но не оба»: A ⊕ B = (A + B)·¬(AB) — ИЛИ, И-НЕ и И, без инверторов.

Упражнение 8.3.1 задача

Светодиод «синхронно» на пульте горит, когда два концевых датчика $A$ и $B$ находятся в одинаковом состоянии, — это функция «эквивалентность», инверсия Исключающего ИЛИ. Докажите алгебраически, что

\overline{A \oplus B} = A B + \overline{A} \overline{B} = (A + \overline{B}) (\overline{A} + B),

и сверьте ответ с таблицей истинности.

Решение

Возьмём первую форму Исключающего ИЛИ и применим де Моргана дважды — к сумме и к каждому произведению:

\overline{\overline{A} B + A \overline{B}} = \overline{\overline{A} B} \cdot \overline{A \overline{B}} = (A + \overline{B}) (\overline{A} + B) .

Это форма «произведение сумм». Перемножив скобки, получим

A \overline{A} + A B + \overline{B} \overline{A} + \overline{B} B

; крайние слагаемые нулевые, остаётся

A B + \overline{A} \overline{B}

По таблице: $A B$ даёт единицу в строке $(1, 1)$ , $\overline{A} \overline{B}$ — в строке $(0, 0)$ ; в строках с разными входами оба слагаемых нулевые. Это и есть «входы совпадают», то есть $\overline{A \oplus B}$ .

Упражнение 8.3.2

Вычислите в булевой алгебре (ответ — 0 или 1): а) $1 + 1 + 0$ ; б) $0 \cdot 1$ ; в) $\overline{1 + 0}$ ; г) $1 \oplus 1 \oplus 1$ .

а) =б) =в) =г) =

Решение

а) Знак «+» здесь — ИЛИ: результат 1, если есть хоть одна единица. Не 2 и не 0 — привычка к арифметике тут подводит чаще всего. б) И требует единиц на всех входах: $0 \cdot 1 = 0$ . в) $1 + 0 = 1$ , после инверсии — 0. г) Исключающее ИЛИ нескольких битов — это сумма по модулю 2: три единицы — нечётное количество, ответ 1 (сначала $1 \oplus 1 = 0$ , затем $0 \oplus 1 = 1$ ).

Упражнение 8.3.3 задача

Упростите выражения: а) $\overline{A} + A B$ ; б) $\overline{A} (A + B)$ ; в) $A \oplus A$ ; г) $A \oplus 0$ ; д) $(A + B) (\overline{A} + B)$ ; е) $\overline{A} B + \overline{A} \overline{B} C$ .

Решение

а) По распределительному закону «наоборот»: $\overline{A} + A B = (\overline{A} + A) (\overline{A} + B) = \overline{A} + B$ (это поглощение $X + \overline{X} Y = X + Y$ при $X = \overline{A}$ ).

б) $\overline{A} A + \overline{A} B = \overline{A} B$ .

в) Одинаковые входы Исключающего ИЛИ всегда дают 0: $A \oplus A = 0$ .

г) $A \oplus 0 = A$ : при нуле на втором входе Исключающее ИЛИ просто пропускает сигнал (а при единице — инвертирует; это «управляемый инвертор»).

д) $(B + A) (B + \overline{A}) = B + A \overline{A} = B$ .

е) $\overline{A} (B + \overline{B} C) = \overline{A} (B + C) = \overline{A} B + \overline{A} C$ .

8.3.2Минимизация и карты Карно

≈ 10 мин2 упр.

Главное

При числе входов до четырёх лучший ручной метод минимизации — карта Карно.
Оси карты идут в коде Грея (00, 01, 11, 10): соседние клетки отличаются одной переменной, края «склеены».
Группа из $2^{k}$ соседних единиц — произведение без $k$ меняющихся переменных; X ставят так, как удобнее.
Мажоритарная схема: $Q = A B + A C + BC$ .

Задача: три датчика давления в системе безопасности дублируют друг друга, и один из них может «врать». Решение принимаем большинством: тревога, если сработали хотя бы два датчика из трёх. Входы $A$ , $B$ , $C$ (1 — сработал), выход $Q$ . Таблицу истинности написать нетрудно, а вот как получить из неё простую схему?

Мы только что видели, что одну функцию можно реализовать по-разному. Поиск самой экономной реализации — задача минимизации; для неё придуманы и алгебраические алгоритмы, которые выполняет компьютер (метод Квайна — Мак-Класки и его развитие). Но когда переменных не больше четырёх, удобнее всего графический приём — карта Карно. Она вдобавок помогает, если формулы вообще нет, а есть лишь таблица «вход → выход».

Минимизация картой Карно

Таблица истинностивсе комбинации входов и выход; X — если вход не влияет или комбинация не встречается
Карта Карнота же таблица, переменные по двум осям в порядке 00, 01, 11, 10
Группыобводим соседние единицы (или нули) группами по 2, 4, 8 клеток
Выражениекаждая группа — произведение; функция — их сумма

Таблица. Выписываем все восемь комбинаций $A BC$ и для каждой — выход. Если бы какая-то комбинация в системе была невозможна (например, два взаимоисключающих концевика замкнуты сразу) или выход от неё не зависел, мы поставили бы в этой строке X — «всё равно».

Голосование «двое из трёх»: выход 1, если единиц на входах две или три.
A	B	C	Q
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Карта. Раскладываем ту же таблицу на плоскость: по горизонтали — пары значений $A B$ , по вертикали — значение $C$ . Главная тонкость — порядок столбцов: не 00, 01, 10, 11, как при счёте, а 00, 01, 11, 10. В такой последовательности (это код Грея) соседние столбцы отличаются одним битом. Поэтому любые две клетки, стоящие рядом, описываются произведениями, различающимися ровно одной переменной, — и сумма таких произведений эту переменную теряет: $A BC + A B \overline{C} = A B$ .

Группы. Обводим единицы прямоугольниками по 2, 4, 8 клеток. Внутри группы из $2^{k}$ клеток меняются $k$ переменных — они из произведения выпадают, остаются только постоянные. На карте мажоритарной функции хватает трёх пар: $A B$ , $BC$ и $A C$ . Пары перекрываются в клетке 111, и это нормально: одну и ту же единицу можно накрывать сколько угодно раз.

Мажоритарная функция («двое из трёх»)

Q = A B + A C + BC

Обозначения:

A B

BC

A C

Q

Ответ выглядит самоочевидным: «тревога, если согласны первый и второй, или первый и третий, или второй и третий». Но это часто так — после того как ответ найден. Схема на трёх И и одном ИЛИ показана рядом с картой. Сгруппировав не единицы, а нули, мы получили бы выражение для инверсного выхода: $\overline{Q} = \overline{A} \overline{B} + \overline{A} \overline{C} + \overline{B} \overline{C}$ — оно выгодно, если на плате уже есть сигналы $\overline{A}$ , $\overline{B}$ , $\overline{C}$ или нужен активный НИЗКИЙ выход «тревога».

1234

Карта «двое из трёх»: три пары единиц — AB (синяя), BC (оранжевая), AC (пунктир). Обратите внимание: столбец 11 стоит перед 10.

Что здесь что (4)

Порядок столбцов 00, 01, 11, 10. код Грея: соседние столбцы отличаются одной переменной — потому их и можно объединять
Группа AB. A = B = 1 при любом C: переменная C в паре меняется и выпадает
Группа BC. B = C = 1 при любом A — две соседние клетки нижней строки
Группа AC. клетки 111 и 101 тоже соседние: отличаются только битом B

Голосование «двое из трёх» по найденной формуле Q = AB + AC + BC: три И на пары входов и общее ИЛИ.

Приёмы работы с картой

Только степени двойки. Группа должна состоять из 1, 2, 4, 8… клеток и быть прямоугольником — иначе ей не соответствует одно произведение.
Чем крупнее, тем лучше. Группа из восьми клеток на карте четырёх переменных — это одна буква; из четырёх — две буквы; пара — три. Поэтому сначала ищите самые большие группы, а мелкие добавляйте лишь для оставшихся единиц.
Края карты соприкасаются. Карта на самом деле свёрнута в бублик: верхняя строка — соседка нижней, левый столбец — соседка правого. На карте ниже единицы стоят в верхней и нижней строках ( $C D = 00$ и $10$ , то есть $D = 0$ ) в столбцах с $B = 1$ ; это одна группа из четырёх клеток, $Q = B \overline{D}$ .
Блок с дыркой. Если почти сплошной блок единиц испорчен одной-двумя нулевыми клетками, выгоднее описать его как «блок минус дырка». На второй карте ниже единицы заполняют оба столбца с $B = 1$ , кроме клетки $A = C = D = 1$ . Отсюда $Q = B \overline{A C D}$ : один 3-входовый И-НЕ и один 2-входовый И. Честная минимальная сумма произведений — $B \overline{A} + B \overline{C} + B \overline{D}$ — потребует трёх вентилей И, 3-входового ИЛИ и инверторов (а вынеся $B$ за скобку и применив де Моргана, мы вернёмся к той же «дырке»).
X — в нашу пользу. Клетку с безразличным значением считаем единицей, если это укрупняет группу, и нулём, если не помогает. Обводить все X не нужно.
Минимум на карте — ещё не лучшая схема. Иногда более длинное выражение дешевле, потому что его куски уже есть на плате в виде готовых сигналов. Функции, построенные на Исключающем ИЛИ, карта вообще не видит: их единицы стоят шахматным узором и не сливаются в группы. И наконец, решение диктует элементная база — в корпусе четыре 2-входовых вентиля, а в программируемой матричной логике доступна лишь сумма произведений с ограниченным числом слагаемых; оптимальным окажется то, что ложится на эту структуру.

Склейка краёв: верхняя и нижняя строки соседние, Q = B·D̅.

Блок с дыркой: Q = B·(ACD)′ — все клетки с B = 1, кроме A = C = D = 1 (оранжевая).

Модель: карта Карно с автоматической минимизацией

Упражнение 8.3.4 задача

Кассовый аппарат округляет сумму до десятков, и для этого ему нужен признак «цифра единиц не меньше 5». Цифра приходит в двоично-десятичном коде $D CB A$ ( $D$ — старший разряд); коды 1010–1111 не встречаются. Составьте карту Карно, найдите минимальное выражение и предложите реализацию на 2-входовых вентилях.

Решение

Единицы — в клетках 5, 6, 7, 8, 9; клетки 10–15 — X. Карта (строки $B A$ , столбцы $D C$ ):

Синяя группа — два правых столбца целиком ( $D = 1$ ): в них настоящие единицы 8 и 9, остальное — X. Оранжевая — $C = 1$ , $A = 1$ (клетки 5, 7, 13, 15). Пунктирная — $C = 1$ , $B = 1$ (6, 7, 14, 15). Итого

Q = D + C A + CB = D + C (A + B) .

Без безразличных клеток пришлось бы писать

D \overline{C} \overline{B} + \overline{D} C A + \overline{D} CB

— по лишней букве в каждом произведении. Реализация по второй форме: ИЛИ над

A

B

, И с

C

, ИЛИ с

D

— три 2-входовых вентиля, инверторы не нужны. Проверка: 4 = 0100 →

D = 0

A + B = 0

→ 0, верно; 6 = 0110 →

C = 1

B = 1

→ 1, верно.

Упражнение 8.3.5 задача

В микроконтроллерной игрушке нужно перемножать два 2-битных числа $A_{1} A_{0} \times B_{1} B_{0}$ (от 0 до 3) и получать 4-битное произведение $P_{3} P_{2} P_{1} P_{0}$ , но без умножителя — на вентилях. Найдите выражения для каждого бита, для $P_{2}$ постройте карту Карно.

Решение

Самые простые биты видны сразу. $P_{0} = A_{0} B_{0}$ (произведение нечётно, только если оба сомножителя нечётные). $P_{3} = 1$ только для $3 \times 3 = 9$ : $P_{3} = A_{1} A_{0} B_{1} B_{0}$ .

$P_{2}$ (произведения 4 и 6: $2 \times 2$ , $2 \times 3$ , $3 \times 2$ ). Карта (строки $B_{1} B_{0}$ , столбцы $A_{1} A_{0}$ ):

Единицы образуют квадрат $A_{1} B_{1}$ без угла $A_{0} = B_{0} = 1$ (там $3 \times 3 = 9$ , бит 2 равен нулю). Две пары:

P_{2} = A_{1} \overline{A_{0}} B_{1} + A_{1} B_{1} \overline{B_{0}} = A_{1} B_{1} \overline{A_{0} B_{0}}

— снова «блок с дыркой».

$P_{1}$ на карте даёт четыре разрозненных пары (минимальная сумма — четыре произведения по три буквы). Но если вспомнить, как умножают столбиком, получится короче: $P_{1} = A_{1} B_{0} \oplus A_{0} B_{1}$ . Проверка на $3 \times 3$ : оба слагаемых равны 1, сумма по модулю 2 — 0, и действительно $9 = 100 1_{2}$ . Знание структуры задачи опять дало схему проще формального минимума — функции с Исключающим ИЛИ на карте не видны.

8.3.3Готовые комбинационные функции в микросхемах

≈ 27 мин9 упр.

Главное

Ходовые комбинационные функции выпускаются готовыми микросхемами средней степени интеграции (СИС).
Схема выборки и мультиплексор выбирают вход по адресу; дешифратор возбуждает один выход из $2^{n}$ .
Передающий вентиль КМОП — двунаправленный ключ, пропускает и аналоговый сигнал, но не усиливает.
Сумматоры, компараторы, схемы чётности, приоритетные шифраторы наращиваются до любой разрядности.

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

Ниже — справочная «витрина» таких микросхем; наведите указатель на карточку, чтобы увидеть, что делает каждая. Затем разберём их по очереди.

12345678

Готовые комбинационные СИС: что делает, типовой номер, сколько входов и выходов.

Что здесь что (8)

Схема выборки. четыре канала сразу: уровень SEL решает, идёт на выходы четвёрка A или четвёрка B
Мультиплексор. трёхбитный адрес CBA указывает, какой из 8 входов попадёт на выход
Демультиплексор. один вход отправляется на тот выход, номер которого задан адресом
Дешифратор. по 3-битному коду один из 8 выходов становится НИЗКИМ, остальные ВЫСОКИЕ
Приор. шифратор. сообщает номер самого старшего из поданных запросов
Сумматор. суммирует два 4-битных числа с учётом входного переноса
Компаратор. отвечает, какое из двух чисел больше или они равны
Схема чётности. считает бит чётности 9-битного слова — внутри дерево Исключающих ИЛИ

Счетверённая 2-входовая схема выборки

Представьте четырёхполюсный тумблер на два положения, только электронный: '157 содержит четыре канала с общим управлением. Пока вход ВЫБОР (SEL) НИЗКИЙ, на выходы $Q_{1}$ – $Q_{4}$ проходят сигналы с входов $A_{1}$ – $A_{4}$ ; при ВЫСОКОМ SEL — с входов $B_{1}$ – $B_{4}$ . Есть и вход разрешения $\overline{E}$ : если подать на него ВЫСОКИЙ уровень, все выходы принудительно станут НИЗКИМИ независимо от остального. Идея входа разрешения встретится нам ещё многократно — у мультиплексоров, дешифраторов, памяти.

Как работает '157 (X — значение не влияет на выход).
$\overline{E}$	SEL	$A_{n}$	$B_{n}$	$Q_{n}$
В	X	X	X	Н
Н	Н	Н	X	Н
Н	Н	В	X	В
Н	В	X	Н	Н
Н	В	X	В	В

'157 — четыре двухпозиционных селектора с общими SEL и ~E.

'151 — «восемь в один»: код CBA выбирает вход, ~E разрешает работу.

У той же функции есть родственники: '158 — с инверсными выходами, '257 и '258 — с выходами на три состояния (прямыми и инверсными соответственно); последние удобны, когда выходы селектора сидят на общей шине.

Упражнение 8.3.6 задача

Arduino должна читать один из двух датчиков — $A$ или $B$ — по одной управляющей линии $S$ ( $Q = A$ при $S = 0$ , $Q = B$ при $S = 1$ ), а под рукой только микросхема '00 с четырьмя 2-входовыми И-НЕ. Хватит ли её? Нарисуйте схему и оцените задержки.

Решение

Нужная функция — $Q = A \overline{S} + BS$ . Любая сумма произведений ложится на два яруса И-НЕ, потому что по де Моргану $\overline{\overline{X} \overline{Y}} = X + Y$ :

Q = \overline{\overline{A \overline{S}} \cdot \overline{BS}} .

Вентиль 1 (входы соединены) даёт

\overline{S}

; вентиль 2 — И-НЕ над

A

\overline{S}

; вентиль 3 — И-НЕ над

B

S

; вентиль 4 объединяет их выходы. Ровно четыре вентиля — одного корпуса '00 хватает.

Путь от $A$ или $B$ до выхода — две задержки вентиля, от $S$ — до трёх (через инвертор). Из-за этой разницы при переключении $S$ в момент, когда $A = B = 1$ , на выходе может проскочить короткий нулевой «провал» — статический риск. Его убирает избыточное слагаемое $A B$ (на карте Карно — группа, перекрывающая стык двух основных групп): тогда при $A = B = 1$ выход удерживается независимо от $S$ .

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

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

Последний пункт заслуживает отдельного внимания. Селектор ставят на плату рядом с источниками сигналов, а к панели ведут лишь управляющую линию SEL: её подтягивают резистором к питанию, а однополюсный тумблер на панели просто замыкает её на землю. Через провод при этом течёт постоянный уровень, который не боится ни длины, ни ёмкости. Управление логикой постоянными уровнями называют «холодной коммутацией» — в отличие от «горячей», когда через переключатель идут сами сигналы.

Слева — «горячее» переключение: сигнал A или B путешествует к тумблеру и назад. Справа — холодное: сигналы остаются на плате у '157, а тумблер только сажает на землю подтянутую к +5 В линию SEL; конденсатор на ней гасит наводки.

Совет. Линию, по которой идёт постоянный управляющий уровень, можно смело зашунтировать конденсатором на землю от наводок; с сигнальной линией так поступать нельзя — конденсатор съест сам сигнал.

Передающие вентили

В КМОП есть элемент, которого нет в ТТЛ, — передающий вентиль. Это два МОП-ключа, p-канальный и n-канальный, включённые параллельно и управляемые противофазно (как они устроены, мы разбирали в разделе 3.3). Пока ключ замкнут, сигнал любой формы в пределах от 0 до $U_{пит}$ — хоть логический, хоть аналоговый — проходит через сопротивление порядка сотен ом; разомкнутый ключ имеет практически бесконечное сопротивление.

Вход и выход у такого ключа условны: сигнал идёт в любую сторону. В микросхеме 4066 четыре таких двунаправленных ключа, у каждого свой управляющий вход: ВЫСОКИЙ уровень замыкает ключ, НИЗКИЙ размыкает. Внутри КМОП-микросхем передающие вентили используются повсеместно, а снаружи с ними удобно коммутировать и логические уровни КМОП, и аналоговые сигналы.

Ловушка. Передающий вентиль — только ключ. Он не усиливает, не восстанавливает фронты и уровни и не даёт разветвления по выходу: что подано на вход, то (с потерей на сопротивлении ключа) и выйдет.

1234

Один ключ 4066: p- и n-канальный транзисторы параллельно, затворы — в противофазе. При УПР = В открыты оба, и сигнал проходит в любую сторону.

Что здесь что (4)

p-канальный ключ. открыт при $\overline{УПР}$ = Н; лучше всего проводит напряжения, близкие к питанию
n-канальный ключ. открыт при УПР = В; лучше всего проводит напряжения, близкие к земле
Вход / выход. направления нет: любой вывод может быть входом
Противофазное управление. транзисторы открываются и закрываются одновременно и дополняют друг друга — сопротивление мало во всём диапазоне 0… $U_{пит}$

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

Упражнение 8.3.7 задача

Усилитель для наушников должен брать звук либо с телефона ( $X_{1}$ ), либо с FM-приёмника ( $X_{2}$ ) — по логическому сигналу $S$ от кнопки. Покажите, как сделать коммутатор на ключах 4066 и одном инверторе. Для чего инвертор? Что произойдёт в момент переключения, если ключи замыкаются быстрее, чем размыкаются?

Решение

Источники $X_{1}$ и $X_{2}$ подключаем к двум ключам 4066, вторые выводы ключей соединяем — это выход на усилитель. Сигнал $S$ идёт прямо на управление ключа 2, а на ключ 1 — через инвертор. При $S = 0$ замкнут ключ 1 (звучит телефон), при $S = 1$ — ключ 2 (приёмник). Инвертор гарантирует, что в установившемся режиме замкнут ровно один ключ: без него оба управлялись бы одним уровнем и замыкались бы вместе.

Если замыкание опережает размыкание («замыкание до размыкания»), то на десятки—сотни наносекунд замкнуты оба ключа: телефон и приёмник оказываются соединены друг с другом через два сопротивления ключей (сотни ом), течёт уравнительный ток, а на выходе — смесь сигналов. Для звука это короткий щелчок, для других применений — перегрузка источников. Аналоговые мультиплексоры поэтому характеризуются в паспорте свойством «размыкание до замыкания» (break-before-make); в ответственных случаях между выключением одного ключа и включением другого делают паузу. Но в паузе разомкнуты оба ключа, и выход «висит» — его полезно привязать резистором к земле (или к средней точке, если сигнал двуполярный относительно неё), иначе усилитель может поймать наводку.

Мультиплексоры

Схема выборки из двух — это простейший, 2-входовый мультиплексор. Готовые бывают на 4 входа (обычно по два в корпусе), на 8 и на 16. Логика у всех одна: на адресные входы подают двоичный номер, и на выход проходит сигнал с входа с этим номером. Восемь входов требуют трёх битов адреса, шестнадцать — четырёх.

Возьмём цифровой мультиплексор '151. Помимо трёх адресных входов $C$ , $B$ , $A$ и восьми входов данных, у него есть вход разрешения (строб) $\overline{E}$ с активным НИЗКИМ уровнем и два выхода — прямой и инверсный. Пока $\overline{E}$ ВЫСОКИЙ, мультиплексор выключен: $Q$ держится НИЗКИМ, $\overline{Q}$ — ВЫСОКИМ, что бы ни было на адресе и данных.

Мультиплексор «8 в 1» ('151)

Q = D_{4 C + 2 B + A} при \overline{E} = Н

Обозначения:

C, B, A

D_{i}

\overline{E}

В семействе КМОП мультиплексоры двух видов

	Цифровой мультиплексор ('151, '153)	Аналоговый мультиплексор (4051, 4053)
Устройство	вентили с входным порогом	передающие вентили + дешифратор
Уровни на выходе	восстанавливаются «чистые», как у любого элемента ТТЛ	просто пропускает входной уровень
Разветвление по выходу	есть	нет
Направление	только вход → выход	двунаправленный — работает и демультиплексором

В КМОП, как видно из сравнения, мультиплексоры бывают двух сортов. Цифровые (например, '153) построены из вентилей: входной сигнал сравнивается с порогом, и на выходе формируются полноценные логические уровни, как у любой ТТЛ-микросхемы. Аналоговые — это набор передающих вентилей с дешифратором внутри: 4051 выбирает один из восьми, 4053 содержит три независимых переключателя на два положения.

У аналоговых свой характер: выход не имеет нагрузочной способности и не «чистит» уровни, зато сигнал может идти в обе стороны — и тогда мультиплексор превращается в демультиплексор (о нём чуть ниже).

Упражнение 8.3.8 задача

Метеостанция опрашивает четыре датчика-компаратора (сигналы $D_{0}$ – $D_{3}$ ) через одну линию, выбирая датчик адресом $A_{1} A_{0}$ . Постройте такой 4-входовый мультиплексор тремя способами: а) на И, ИЛИ и инверторах; б) из трёх 2-входовых схем выборки; в) на буферах с тремя состояниями и дешифраторе «1 из 4». Когда стоит выбрать способ (в)?

Решение

а) Прямо по определению: $Q = D_{0} \overline{A_{1}} \overline{A_{0}} + D_{1} \overline{A_{1}} A_{0} + D_{2} A_{1} \overline{A_{0}} + D_{3} A_{1} A_{0}$ . Нужны два инвертора для адресных линий, четыре 3-входовых И и один 4-входовый ИЛИ. Готовая микросхема с такой логикой — '153 (в корпусе их две).

б) Дерево из схем выборки: одна по адресу $A_{0}$ выбирает между $D_{0}$ и $D_{1}$ , другая (тоже по $A_{0}$ ) — между $D_{2}$ и $D_{3}$ , третья по $A_{1}$ — между результатами первых двух. Сигнал проходит две ступени.

в) Каждый датчик подключён к общему проводу через свой буфер с тремя состояниями; разрешения буферов приходят с выходов дешифратора «1 из 4» (половина '139), на адрес которого подан $A_{1} A_{0}$ . В любой момент к проводу подключён ровно один датчик.

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

Наращивание

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

Мультиплексор наращивается особенно легко. Два '151 дают 16 входов: младшие три бита адреса подаём на обе микросхемы, а четвёртый, старший бит разрешает одну из них и (через инвертор) запрещает другую. Выход запрещённого '151 остаётся НИЗКИМ, так что выходы можно собрать вентилем ИЛИ. У мультиплексоров с выходами на три состояния не нужен и он — выходы соединяют напрямую.

1234

«Шестнадцать в один»: два '151, инвертор на старшем адресе и ИЛИ на выходах.

Что здесь что (4)

Старший адресный бит A₃. напрямую запрещает верхний '151 (при A₃ = 1) и через инвертор — нижний (при A₃ = 0)
Инвертор. даёт $\overline{A_{3}}$ на вход $\overline{E}$ второй микросхемы — разрешена всегда ровно одна
Младшие адреса A₀–A₂. общие для обеих микросхем
Вентиль ИЛИ. выход запрещённого '151 НИЗКИЙ и ИЛИ не мешает, поэтому на выход проходит сигнал разрешённого

Демультиплексоры и дешифраторы

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

Самый ходовой — '138, «1 из 8». Три бита кода на входе делают НИЗКИМ выход с соответствующим номером, на остальных семи остаётся ВЫСОКИЙ уровень. Входов разрешения целых три: G1 активен ВЫСОКИМ уровнем, $\overline{G2A}$ и $\overline{G2B}$ — НИЗКИМ. Дешифратор работает, только когда активны все три; в противном случае все выходы ВЫСОКИЕ.

123

'138, дешифратор «1 из 8»: НИЗКИЙ только выход с номером кода; разрешён, когда G1 = В, а G̅2̅A̅ и G̅2̅B̅ = Н.

Что здесь что (3)

Адрес A0–A2. 3-битный код — номер выхода, который станет НИЗКИМ
Входы разрешения. G1 — активный ВЫСОКИЙ, $\overline{G2A}$ и $\overline{G2B}$ — активные НИЗКИЕ; работать дешифратор будет, только если активны все три
Выходы Y0–Y7. активные НИЗКИЕ: выбранный — Н, остальные — В; при запрете все В

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

У '138 есть младший собрат '139 — два дешифратора «1 из 4» в одном корпусе, у каждого по одному входу разрешения с активным НИЗКИМ уровнем. А то, что у '138 входы разрешения разной полярности, позволяет наращивать его без дополнительных элементов: две микросхемы дают «1 из 16», как на рисунке.

Шестнадцать выходов из двух '138 без единого вентиля: A₃ идёт на G̅2̅A̅ верхней микросхемы (активна при A₃ = 0) и на G1 нижней (активна при A₃ = 1).

Упражнение 8.3.9 задача

Контроллер склада автоматических ячеек выбирает одну из 24 ячеек пятибитным адресом $A_{4} \dots A_{0}$ (коды 0–23) и должен опустить в НИЗКИЙ уровень линию выбранной ячейки. Соберите дешифратор «1 из 24» из трёх '138. Нужны ли дополнительные вентили? Что произойдёт при адресах 24–31?

Решение

Младшие биты $A_{2} A_{1} A_{0}$ подаём на адресные входы всех трёх '138. Старшие $A_{4} A_{3}$ выбирают микросхему через входы разрешения (G1 активен ВЫСОКИМ, $\overline{G2A}$ и $\overline{G2B}$ — НИЗКИМ):

№ 0 (ячейки 0–7, $A_{4} A_{3} = 00$ ): G1 = +5 В, $\overline{G2A} = A_{4}$ , $\overline{G2B} = A_{3}$ ;
№ 1 (8–15, $A_{4} A_{3} = 01$ ): G1 = $A_{3}$ , $\overline{G2A} = A_{4}$ , $\overline{G2B}$ — на землю;
№ 2 (16–23, $A_{4} A_{3} = 10$ ): G1 = $A_{4}$ , $\overline{G2A} = A_{3}$ , $\overline{G2B}$ — на землю.

Каждая микросхема разрешена ровно при своей комбинации старших битов, и ни одного вентиля не требуется — хватает разной полярности входов разрешения. При $A_{4} A_{3} = 11$ (адреса 24–31) запрещены все три: микросхема № 0 видит ВЫСОКИЕ $\overline{G2A}$ и $\overline{G2B}$ , № 1 — ВЫСОКИЙ $\overline{G2A}$ , № 2 — ВЫСОКИЙ $\overline{G2A}$ . Все 24 линии остаются ВЫСОКИМИ — ни одна ячейка не выбрана, что и требуется для несуществующих адресов. (Свободный вход $\overline{G2B}$ у № 1 и № 2 можно отдать общему сигналу разрешения, но у № 0 он занят — для общего разрешения там понадобился бы вентиль.)

У КМОП-мультиплексоров на передающих вентилях демультиплексор получается бесплатно: ключи двунаправленны, достаточно поменять местами «вход» и «выходы».

Ловушка. Работая демультиплексором, аналоговый мультиплексор оставляет невыбранные выходы не НИЗКИМИ, а отключёнными. Логика, подключённая к ним, увидит «висящий» вход, поэтому на каждом выходе нужен нагрузочный резистор (или его эквивалент) — так же, как у выхода ТТЛ с открытым коллектором.

Особая разновидность дешифраторов — преобразователи кодов; они есть во всех семействах. Всем знаком дешифратор для семисегментного индикатора: на вход подаётся цифра в двоично-десятичном коде (BCD), а на выходах сразу семь сигналов — какие сегменты зажечь, чтобы получилась нужная цифра. Микросхема '47 к тому же содержит мощные выходные каскады, которые могут прямо питать сегменты. По-хорошему её следовало бы называть преобразователем кода, но название «дешифратор» за ней закрепилось.

Упражнение 8.3.10 задача

Вы делаете собственный шрифт для индикатора и хотите сами управлять нижним левым сегментом e. Он светится в цифрах 0, 2, 6, 8 и погашен в остальных. На входе — BCD-код $D CB A$ ( $D$ — старший разряд), коды 10–15 не встречаются. Найдите минимальную логику.

Решение

Карта Карно (строки $B A$ , столбцы $D C$ ): единицы в клетках 0, 2, 6, 8, X в 10–15:

Синие кусочки в четырёх углах — это одна группа: углы карты соседствуют попарно и по горизонтали, и по вертикали. В ней $C = 0$ и $A = 0$ : произведение $\overline{C} \overline{A}$ (клетки 0, 2, 8, 10). Оранжевая группа — вся нижняя строка $B A = 10$ : произведение $B \overline{A}$ (клетки 2, 6, 14, 10). Итого

e = \overline{C} \overline{A} + B \overline{A} = \overline{A} (\overline{C} + B) .

Вторая форма — два инвертора, один ИЛИ и один И. Заметьте, что все нечётные цифры гасят сегмент: множитель

\overline{A}

это и выражает. Проверка: 4 = 0100:

\overline{A} = 1

, но

\overline{C} + B = 0

→ погашен, верно; 6 = 0110:

B = 1

→ горит, верно. Для стандартного шрифта, конечно, берут готовый '47 (в КМОП — 4511), но собственные символы проектируются именно так.

Приоритетный шифратор

Обратная задача дешифратора: на входах несколько линий-запросов, и нужно получить двоичный номер активной. Но что, если активны сразу несколько? Приоритетный шифратор отвечает однозначно: он выдаёт номер самого старшего из активных входов, а младшие игнорирует. Так устроено обслуживание прерываний в микропроцессорных системах (кто важнее, того и обслуживают), и так же работает самый быстрый, параллельный АЦП, о котором речь пойдёт в разделе 9.3. Готовые микросхемы: '148 — восемь входов и трёхбитный номер, '147 — десять входов и номер в BCD.

Приоритетный шифратор — обратная задача дешифратора

Запросы 0…7

Приоритетный шифратор '148

Код номера (3 бита)

Упражнение 8.3.11 задача

В баке четыре поплавковых датчика уровня воды на разной высоте: $I_{0}$ (нижний) … $I_{3}$ (верхний); датчик выдаёт 1, если вода выше него. Нужно передать на индикатор двухбитный номер самого высокого сработавшего датчика $Y_{1} Y_{0}$ и отдельный сигнал $V$ «вода есть хотя бы у одного датчика». Спроектируйте этот 4-входовый приоритетный шифратор так, чтобы он работал правильно и при неисправном (залипшем) нижнем датчике.

Решение

Требование «работать и при залипшем датчике» и означает, что смотреть надо только на старший активный вход, не предполагая, что ниже него всё сработало. Таблица (X — безразлично):

$I_{3}$	$I_{2}$	$I_{1}$	$I_{0}$	$Y_{1} Y_{0}$	$V$
1	X	X	X	11	1
0	1	X	X	10	1
0	0	1	X	01	1
0	0	0	1	00	1
0	0	0	0	XX	0

Старший бит номера равен 1 для датчиков 3 и 2: $Y_{1} = I_{3} + I_{2}$ . Младший — для номеров 3 и 1; номер 1 побеждает, только если датчик 2 молчит: $Y_{0} = I_{3} + \overline{I_{2}} I_{1}$ . Наличие воды: $V = I_{3} + I_{2} + I_{1} + I_{0}$ (или экономнее $V = Y_{1} + I_{1} + I_{0}$ ). Итого — два ИЛИ, инвертор, И и ИЛИ для $V$ . Без выхода $V$ не обойтись: «вода только у нижнего датчика» и «воды нет совсем» дают одинаковый код $Y_{1} Y_{0} = 00$ .

Сумматоры и другие арифметические устройства

Сложение — самая частая арифметика в цифровой технике, и сумматоры выпускаются готовыми. Микросхема '283 (её предшественник — '83) складывает два 4-разрядных числа $A$ и $B$ и выдаёт 4-разрядную сумму $S$ и бит переноса $П_{вых}$ . Чтобы складывать длинные числа, у неё есть ещё и вход переноса $П_{вх}$ : туда подают выходной перенос соседнего, младшего сумматора. Две микросхемы складывают байты, четыре — 16-разрядные слова.

Если нужно не только складывать, используют арифметико-логическое устройство (АЛУ). Классика — 4-разрядное '181: оно выполняет сложение, вычитание, сдвиг, сравнение и набор логических операций, а наращивается до любой длины слова. Арифметика на таких микросхемах занимает от единиц до десятков наносекунд, смотря по семейству.

Четырёхразрядный сумматор: два слагаемых, входной перенос, сумма и выходной перенос.

Байтовый сумматор из двух четвёрок: выходной перенос младшей половины становится входным переносом старшей, вход переноса младшей заземлён; результат — 9 бит.

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

Существуют и более сложные арифметические микросхемы:

умножители 8×8 и 16×16 бит; для цифровой обработки сигналов — умножители-накопители, которые не только перемножают, но и суммируют произведения (до 32×32 бита с 64-битным результатом и запасными разрядами, чтобы сумма не переполнилась); одна операция занимает 25–50 нс, а ЭСЛ-умножитель 16×16 справляется примерно за 5 нс;
корреляторы, которые сравнивают поразрядно две битовые последовательности (скажем, по 64 бита, сдвигаемые во внутренних регистрах) и выдают число совпадающих битов; часть позиций можно исключить маской, а тактовая частота — десятки мегагерц;
самые сложные — процессоры с плавающей запятой: сложение, умножение, тригонометрические функции, экспонента, корни по стандарту IEEE 754 со словами до 80 бит. Таковы сопроцессоры 8087, 80287, 80387 и 68881, работавшие в паре со «своими» микропроцессорами и выдававшие порядка 10 Мфлопс.

25–50 нсумножитель-накопитель

≈5 нсЭСЛ-умножитель 16×16

80 битслово FPU

~10 Мфлопссопроцессор

Упражнение 8.3.12

Счётчик энергии в умном щитке накапливает 20-битную сумму на пяти 4-разрядных сумматорах с последовательным переносом. Задержки одной микросхемы: от входов данных до выхода переноса — 14 нс, от входа переноса до выхода переноса — 9 нс, от входа переноса до выходов суммы — 13 нс. Найдите наихудшее время сложения (до установления старших битов суммы).

t =нс

Решение

Хуже всего, когда перенос возникает в самой младшей микросхеме и проходит через все остальные: 14 нс (данные → перенос в первой) + $3 \times 9$ нс (перенос транзитом через вторую, третью и четвёртую) + 13 нс (перенос → сумма в пятой) = 54 нс. Каждые лишние четыре разряда добавляют ещё 9 нс — задержка растёт линейно, поэтому в длинных сумматорах переносы групп вычисляют параллельно схемой ускоренного переноса ('182).

Компараторы и схемы чётности

Задача «больше, меньше или равно» решается цифровым компаратором. Микросхема '85 сравнивает два 4-разрядных числа $A$ и $B$ и выдаёт три сигнала: $A < B$ , $A = B$ , $A > B$ . Для длинных чисел у неё есть три входа наращивания — на них подают результат сравнения младших разрядов от соседней микросхемы.

Компаратор '85: три выхода результата и три входа, на которые приходит итог сравнения младших разрядов.

Упражнение 8.3.13 задача

Кодовый замок: восемь тумблеров задают секретный код $K_{7} \dots K_{0}$ (каждый тумблер замыкает свою линию на землю, линии подтянуты резисторами к +5 В), а клавиатура выдаёт набранный 8-битный код $X_{7} \dots X_{0}$ . Постройте сигнал «код верен» на вентилях Исключающее ИЛИ. Сколько понадобится корпусов?

Решение

Разомкнутый тумблер даёт ВЫСОКИЙ уровень $K_{i}$ , замкнутый — НИЗКИЙ. Разряд совпадает, если $X_{i} \oplus K_{i} = 0$ . Восемь вентилей Исключающее ИЛИ — два корпуса '86 — дают восемь сигналов несовпадения; код верен, когда все они НИЗКИЕ:

ВЕРНО = \overline{(X_{7} \oplus K_{7}) + (X_{6} \oplus K_{6}) + \dots + (X_{0} \oplus K_{0})}

— 8-входовый ИЛИ-НЕ (например, КМОП 4078). Итого три корпуса. На схеме в логике заданных уровней выходы Исключающих ИЛИ подписывают «

\overline{совпадает}_{i}

», а ИЛИ-НЕ рисуют как И с инверсными входами: «верно, если совпали все разряды». Тумблеры кода — образцовая холодная коммутация: через них идут только постоянные уровни.

Последний представитель витрины — формирователь и контролёр чётности. При передаче или записи к слову добавляют ещё один бит — бит чётности, а при приёме проверяют, сходится ли он: одиночная ошибка (один перевернувшийся бит) обязательно его нарушит. Соглашений два: при чётной чётности общее число единиц вместе с дополнительным битом чётно, при нечётной — нечётно. Микросхема '280 принимает 9-разрядное слово и выдаёт оба варианта. Внутри у неё только вентили Исключающее ИЛИ, соединённые деревом.

Чётность байта деревом: семь вентилей «=1», но любой бит проходит только через три из них; цепочка из тех же семи вентилей дала бы семь задержек.

Бит чётности

P = b_{0} \oplus b_{1} \oplus b_{2} \oplus \dots \oplus b_{n - 1}

Обозначения:

P

b_{i}

\oplus

Упражнение 8.3.14

Для 12-битного слова с датчика нужно формировать бит чётности на 2-входовых вентилях Исключающее ИЛИ. Сколько вентилей потребуется? Через сколько вентилей пройдёт сигнал в худшем случае, если соединить их сбалансированным деревом, и сколько — если цепочкой?

Вентилей =Уровней дерева =Уровней цепочки =

Решение

Каждый 2-входовый вентиль превращает два сигнала в один, то есть уменьшает их число на единицу. Из 12 сигналов надо получить один — значит, вентилей 11 при любом способе соединения (Исключающее ИЛИ ассоциативно, порядок объединения роли не играет). В дереве число сигналов на каждом уровне примерно вдвое меньше: 12 → 6 → 3 → 2 → 1, всего $⌈ lo g_{2} 12 ⌉ = 4$ уровня. В цепочке каждый вентиль добавляет к результату по одному биту, и первый бит проходит все 11. Нужен бит нечётной чётности вместо чётной — ставят на выходе ещё один вентиль Исключающее ИЛИ с управляющим входом (управляемый инвертор).

Программируемые логические устройства и другие функции

Наконец, свою собственную комбинационную (и даже последовательностную) логику можно «зашить» в микросхему, внутри которой — массив вентилей с программируемыми связями. Главных разновидностей две: ПМЛ (по-английски PAL — логика с программируемой матрицей И) и ПЛМ (PLA — матрица, в которой программируются и И, и ИЛИ). ПМЛ стоят недорого, гибки и давно стали обычным инструментом разработчика; подробно о них — в следующем пункте.

Среди готовых СИС встречаются и менее известные функции: КМОП-элемент мажоритарной логики, сообщающий, что активно большинство входов; двоично-десятичная схема дополнения до 9 (для вычитания в десятичной арифметике); «барабанный сдвигатель» (barrel shifter), который за одно действие сдвигает входное слово на заданное число разрядов и наращивается на любую длину.

8.3.4Реализация произвольных таблиц истинности

≈ 17 мин4 упр.

Главное

$n$ -входовый мультиплексор реализует любую таблицу от $lo g_{2} n$ переменных, а с одним инвертором — от $lo g_{2} n + 1$ .
Дешифратор плюс вентили ИЛИ даёт сразу несколько функций: выходы дешифратора — минтермы.
ПЗУ реализует любую таблицу, если хватает адресных входов; объём растёт экспоненциально с числом входов.
ПМЛ: программируемые И, фиксированные ИЛИ; ПЛМ программируется целиком.

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

От простого к мощному

Мультиплексор

Дешифратор + ИЛИ

ПЗУ

ПМЛ, ПЛМ

Мультиплексор как обобщённая таблица истинности

Посмотрите на мультиплексор иначе: его адрес — это номер строки таблицы истинности, а на информационных входах стоит столбец выхода. Если подать переменные функции на адресные входы, а на $D_{0}$ – $D_{7}$ — постоянные ВЫСОКИЕ и НИЗКИЕ уровни, переписанные из таблицы, то $n$ -входовый мультиплексор выдаст любую функцию от $lo g_{2} n$ переменных без единого внешнего элемента. На рисунке слева 8-входовый мультиплексор выдаёт признак «нечётное число единиц в коде CBA» — функцию, для которой карта Карно ничего не упрощает.

Менее очевидно, что тот же мультиплексор плюс один инвертор справляется с функцией вдвое большей таблицы — от $lo g_{2} n + 1$ переменных. Возьмём 4-битное число $A_{3} A_{2} A_{1} A_{0}$ (0…15) и признак «делится на 3» (0, 3, 6, 9, 12, 15). Старшие три бита подаём на адрес; каждый адрес выбирает пару чисел, отличающихся только битом $A_{0}$ .

Совет. Секрет: внутри пары выход — функция одного-единственного бита

A_{0}

, а таких функций всего четыре: всегда Н, всегда В,

A_{0}

\overline{A_{0}}

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

Для «делится на 3» получается так: пара 0–1 — кратно только 0, на вход $D_{0}$ подаём $\overline{A_{0}}$ ; пара 2–3 — кратно 3 (нечётное), $D_{1} = A_{0}$ ; в паре 4–5 кратных нет, $D_{2} = Н$ ; далее $D_{3} = \overline{A_{0}}$ (число 6), $D_{4} = A_{0}$ (9), $D_{5} = Н$ , $D_{6} = \overline{A_{0}}$ (12), $D_{7} = A_{0}$ (15). Карта Карно для этой функции не находит ни одной группы: минимальная сумма — шесть произведений по четыре буквы, около десятка вентилей против одного корпуса с инвертором.

Мультиплексор вместо логики: на входах — столбец таблицы «нечётное число единиц в CBA» (C — старший разряд).

1234

«Число A₃A₂A₁A₀ делится на 3»: старшие биты — на адрес CBA, на входы — уровень Н или младший бит A₀, прямой или через инвертор.

Что здесь что (4)

D0 = ¬A₀. пара 0–1: делится только 0 — чётное число пары, нужен инвертор
D1 = A₀. пара 2–3: делится 3 — нечётное число пары, бит A₀ подаётся напрямую
D2 = Н. пара 4–5: ни одно число не делится на 3
Адрес C, B, A. старшие биты A₃A₂A₁ выбирают пару чисел

Упражнение 8.3.15 задача

Учебный стенд показывает 4-битное число $A_{3} A_{2} A_{1} A_{0}$ (0…15), и светодиод должен загораться, если число — из ряда Фибоначчи: 0, 1, 2, 3, 5, 8, 13. Реализуйте функцию на 8-входовом мультиплексоре и одном инверторе: разбейте числа на пары по трём старшим битам и для каждой пары решите, что подать на информационный вход. Проверьте схему на числах 12 и 13.

Решение

Пары и решения:

Пара ( $A_{3} A_{2} A_{1}$ )	Числа	Фибоначчи?	Вход мультиплексора
000	0, 1	да, да	В
001	2, 3	да, да	В
010	4, 5	нет, да	$A_{0}$
011	6, 7	нет, нет	Н
100	8, 9	да, нет	$\overline{A_{0}}$
101	10, 11	нет, нет	Н
110	12, 13	нет, да	$A_{0}$
111	14, 15	нет, нет	Н

Итак: $D_{0} = D_{1} = В$ , $D_{2} = D_{6} = A_{0}$ , $D_{4} = \overline{A_{0}}$ (через инвертор), $D_{3} = D_{5} = D_{7} = Н$ — пригодились все четыре варианта. Проверка: 13 = 1101, адрес $A_{3} A_{2} A_{1} = 110$ выбирает $D_{6} = A_{0} = 1$ — светодиод горит; 12 = 1100, тот же вход даёт $A_{0} = 0$ — погашен, верно. Для сравнения, минимизация картой Карно даёт $\overline{A_{3}} \overline{A_{2}} + A_{2} \overline{A_{1}} A_{0} + \overline{A_{2}} \overline{A_{1}} \overline{A_{0}}$ — три произведения, 3-входовый ИЛИ и инверторы, то есть два-три корпуса.

Упражнение 8.3.16

Электронный игральный кубик выдаёт значение 1…6 трёхбитным кодом $CB A$ ( $C$ — старший разряд; коды 0 и 7 не встречаются). Пара диагональных светодиодов на «грани» горит при значениях 2, 3, 4, 5, 6. Если считать коды 0 и 7 безразличными, эту пару можно включать одним вентилем. Каким?

Решение

Не горит пара только при значении 1 = 001, то есть когда $C = 0$ и $B = 0$ . Значит, $Q = C + B$ : 2 = 010 и 3 = 011 дают $B = 1$ , 4, 5, 6 дают $C = 1$ ; код 0 был бы погашен, код 7 — горел бы, но оба не встречаются. Вариант $C \oplus B$ ошибочно гасит 6 = 110, $CB$ горит лишь при 6 (и 7), $B + A$ зажёг бы 1. Остальные группы светодиодов кубика тоже обходятся почти без логики: центральный горит при нечётных значениях ( $Q = A$ ), вторая диагональ — при 4, 5, 6 ( $Q = C$ ), средняя пара — только при 6 ( $Q = CB$ , так как 7 не бывает).

Дешифратор как обобщённая таблица истинности

Если функций от одних и тех же входов нужно сразу несколько, удобнее дешифратор. Каждый его выход — это одна строка таблицы истинности, то есть произведение всех входных переменных (прямых или инверсных), равное 1 ровно на одной комбинации. Такие произведения называют минтермами; на карте Карно каждый минтерм — одна клетка. Любая функция — это ИЛИ над теми минтермами, где она равна 1, и с дешифратором остаётся только собрать нужные выходы вентилями.

Пример — перевод десятичной цифры из BCD в код Грея (каждая следующая цифра отличается от предыдущей одним битом; так кодируют положения датчиков угла и переключателей, чтобы на переходе не возникало ложных промежуточных кодов):

Цифра	BCD	Код Грея
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101

BCD-цифру подаём на адрес дешифратора «1 из 10» '42. Его выходы активны НИЗКИМ уровнем, поэтому ИЛИ над нужными минтермами превращается в И-НЕ (это то же ИЛИ, нарисованное в отрицательной логике): бит $G_{1}$ , например, равен 1 для цифр 2, 3, 4, 5, и на его И-НЕ заводят выходы с этими номерами. В отличие от выходов самого дешифратора, выходные биты здесь не исключают друг друга: при цифре 5 активны сразу $G_{2}$ , $G_{1}$ и $G_{0}$ .

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

123

Десятичная цифра → код Грея через минтермы: каждый бит кода — И-НЕ над теми НИЗКИМИ выходами дешифратора, где этот бит равен 1 (ИЛИ в отрицательной логике).

Что здесь что (3)

Дешифратор '42. BCD-код DCBA делает НИЗКИМ один из 10 выходов — это минтермы
И-НЕ для G3. собирает выходы 8 и 9: И-НЕ над активными НИЗКИМИ сигналами — это их ИЛИ
И-НЕ для G0. выходы 1, 2, 5, 6, 9 — цифры, у которых младший бит кода Грея равен 1

ПЗУ

Следующий шаг — микросхемы, внутренние связи которых задаёт сам пользователь. Формально это память (о памяти и регистрах мы ещё поговорим подробно), но после того как содержимое записано, такая микросхема ведёт себя как чисто комбинационная схема. Бывают и программируемые устройства с триггерами — регистровые ПМЛ, о них в разделе 8.6.

ПЗУ (постоянное запоминающее устройство) хранит для каждого входного адреса своё слово — обычно 4 или 8 бит, которые появляются на параллельных выходах. Скажем, ПЗУ 1K×8 имеет 10 адресных входов ( $2^{10} = 1024$ комбинации) и для каждой выдаёт 8 бит.

Отсюда главное свойство: в ПЗУ можно записать любую комбинационную таблицу истинности, если хватает адресных входов. Таблица умножения 4×4 бита, например, — это 8 входов и 8 выходов, и она умещается в 1K×8 с запасом. Как и программируемая логика, ПЗУ энергонезависимо: содержимое не пропадает при отключении питания.

Сколько нужно ПЗУ под таблицу истинности

объём = 2^{n} \times m бит

Обозначения:

n

m

2^{n}

1234

ПЗУ 1K × 8 как таблица истинности: 10 переменных на адресе, 8 функций на выходах.

Что здесь что (4)

Адрес A0–A9. 10 входов — $2^{10} = 1024$ ячейки: столько строк в таблице истинности
Выбор кристалла CE. активный НИЗКИЙ: включает микросхему (удобно, когда ПЗУ несколько)
Разрешение выходов OE. активный НИЗКИЙ: подключает выходы с тремя состояниями к шине
Данные D0–D7. 8 выходов — 8 функций от одних и тех же 10 переменных

ПЗУ различаются тем, как в них попадает содержимое:

масочные — данные «впечатаны» на заводе при изготовлении кристалла;
программируемые пользователем (ППЗУ) — внутри тонкие перемычки, которые пережигают, как предохранители, подавая адрес и специальные управляющие сигналы; это биполярные микросхемы, быстрые (25–50 нс), но прожорливые (0,5–1 Вт), объёмом от 32×8 до 8K×8;
стираемые (СППЗУ, EPROM) — бит хранится зарядом на плавающем затворе МОП-транзистора, а стирают всё содержимое ультрафиолетом: несколько минут под мощной лампой через кварцевое окошко в корпусе. Они бывают n-МОП и КМОП, медленнее (около 200 нс, лучшие КМОП — до 35 нс), зато экономичны и вместительны (8K×8 … 128K×8). Та же микросхема в корпусе без окна — однократно программируемая (ОКП, OTP), она дешевле;
электрически стираемые (ЭСППЗУ, EEPROM) — их и записывают, и стирают прямо на плате от обычного питания +5 В.

Виды ПЗУ

	Масочное	ППЗУ (пережигаемое)	СППЗУ (EPROM), ОКП	ЭСППЗУ (EEPROM)
Программирует	завод	пользователь, один раз	пользователь; стирание УФ (ОКП — один раз)	пользователь, прямо в схеме
Время доступа	—	25–50 нс	~200 нс (КМОП до 35 нс)	—
Объём	—	32×8 … 8K×8	8K×8 … 128K×8	—

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

Упражнение 8.3.17

Какой объём ПЗУ (в килобитах, 1 Кбит = 1024 бит) нужен для табличной реализации: а) сумматора двух 4-разрядных чисел без знака (сумма вместе с переносом); б) умножителя двух 6-разрядных чисел без знака?

а) =Кбитб) =Кбит

Решение

а) Адрес — оба слагаемых, $4 + 4 = 8$ разрядов, $2^{8} = 256$ ячеек. Наибольшая сумма $15 + 15 = 30$ занимает 5 разрядов ( $30 < 32$ ). Объём $256 \cdot 5 = 1280$ бит = 1,25 Кбит.

б) Адрес — $6 + 6 = 12$ разрядов, $2^{12} = 4096$ ячеек; произведение до $63 \cdot 63 = 3969 < 4096$ требует 12 разрядов. Объём $4096 \cdot 12 = 49152$ бит = 48 Кбит. Каждый лишний бит сомножителей учетверяет число ячеек: для 16×16 бит понадобилось бы больше четырёх миллиардов слов по 32 бита — тут таблица уже бессмысленна, и нужен настоящий умножитель.

Программируемая логика: ПМЛ и ПЛМ

Программируемая логика — это кристалл, на котором уже стоят сотни вентилей, а соединения между ними задаёт пользователь, примерно как содержимое ПЗУ. Два основных вида — ПМЛ (PAL; название — торговая марка фирмы Monolithic Memories) и ПЛМ. В биполярных вариантах связи — пережигаемые перемычки, их программируют один раз; в КМОП — транзисторы с плавающим затвором, которые стираются ультрафиолетом или электрически.

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

12345

Внутри ПМЛ, в миниатюре: вертикали — входы и их инверсии, горизонтали — входы вентилей И; крестик — оставленная связь. Здесь прошито A⊕B = A̅B + AB̅. В двух нижних строках связи не тронуты, там одновременно A и A̅ — эти произведения тождественно равны 0 и сумме не мешают.

Что здесь что (5)

Входы и их инверсии. каждый входной сигнал заведён в матрицу и прямым, и проинвертированным
Сохранённая перемычка (крестик). подключает этот сигнал ко входу вентиля И; в первой строке получилось $\overline{A} B$
Вентиль И (произведение). на деле многовходовый: вход на каждом пересечении строки с вертикалями
Неиспользуемые произведения. все перемычки целы — в произведении есть и $A$ , и $\overline{A}$ , оно равно 0
Фиксированный ИЛИ. в ПМЛ подключён жёстко; в ПЛМ и эта матрица программируется

В комбинационной ПМЛ каждый выход (с тремя состояниями) снимается с вентиля ИЛИ, а тот собирает несколько многовходовых вентилей И. Возьмём 16L8: у неё восемь выходов, каждый с 7-входовым ИЛИ, то есть до семи произведений на выход. Каждому И доступны сигналы с 10 входных выводов и с 8 выходов (их заводят обратно в матрицу), все в прямом и инверсном виде. Ещё по одному 32-входовому И на выход управляет его третьим состоянием.

16входов (до)

Lактивный НИЗКИЙ

8выходов (до)

7произведений на выход

Отсюда и имя: до 16 входов, до 8 выходов, буква L — выходы активны НИЗКИМ уровнем. У ПЛМ свободы больше: программируется и матрица ИЛИ, так что любое произведение можно направить на любой выход (или на несколько).

ПМЛ против ПЛМ

	ПМЛ (PAL)	ПЛМ (PLA)
Матрица И	программируется	программируется
Матрица ИЛИ	фиксирована	программируется
Быстродействие	выше — одна программируемая матрица	ниже — две
Цена и распространённость	дешевле, фаворит разработок	гибче, реже

Чтобы прошить ПМЛ или ПЛМ, нужен программатор: он пережигает перемычки (или программирует другие элементы связи), а затем читает результат и сверяет его с заданием. Управляет им компьютер с программой-компилятором.

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

Хотя ПЛМ гибче, на практике чаще берут ПМЛ: сигнал в ней проходит только одну программируемую матрицу, поэтому она быстрее, к тому же дешевле, а её возможностей обычно хватает. Более поздние ПМЛ с «макроячейками» на выходах и с выходами, которые можно заводить обратно, гибкость ещё добавляют.

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

Упражнение 8.3.18

Сигнализация теплицы с пятью датчиками влажности $A$ – $E$ должна поливать грядку, когда «сухо» показывают не меньше трёх датчиков из пяти. Можно ли сделать это на одном выходе ПМЛ 16L8 (не более 7 произведений на выход, один проход через матрицу)?

Решение

Функция «не меньше трёх из пяти» равна 1, если единицы стоят хотя бы на трёх входах. Её простые импликанты — все произведения из трёх букв: $A BC$ , $A B D$ , …, $C D E$ — их $(3 5) = 10$ . Каждое обязательно: набор ровно с тремя единицами (например, 11100) покрывает только «своё» произведение, крупнее группу не сделать. Выход 16L8 инверсный, но перейти к инверсии не помогает: «не больше двух из пяти» — то же «трое из пяти» для проинвертированных входов, и тоже 10 произведений. Решение — на одном выходе собрать сумму пяти произведений, завести её по обратной связи в матрицу и на втором выходе сложить с остальными пятью (6 произведений). Тот же урок, что и для карт Карно: результат определяется структурой ПМЛ, а не только самой функцией.