Алгебра переключательных схем
Как говорилось в начале лекции 6, в 1938 году Клод Шеннон показал, что алгебра логики применима для описания самых разных процессов, в том числе релейных и транзисторных схем.
Принципы работы и тех и других примерно одинаковы: переключатели (будь это реле или транзисторы) могут находиться в состояниях “включен” и “выключен”, и соответствуют логическим переменным. Работает или не работает вся схема целиком (в том или ином смысле – “включена” она или “выключена”) определяет значение “функции” этих переменных.
Релейные схемы
В случае рэлейных схем, реле обозначается следующим образом:
Реле, которые должны быть открыты и закрыты одновременно, обозначаются одной буквой.
Реле, которые должны быть открыты в противофазе с другими, обозначаются отрицанием соответствующей переменной и изображаются сплошной линией:
Вся схема считается “истинной” (включенной), если через нее протекает ток, и “ложной” (выключенной) в обратном случае.
Логические операции транслируются очевидным образом. Конъюнкция соответствует последовательному соединению реле, а дизъюнкция – параллельному.
В настоящий момент, релейные схемы практически не используются в вычислительной технике: им на смену пришли транзисторные.
Транзисторные схемы
Транзисторные схемы работают достаточно похожим образом, и строятся на основе полевых транзисторов с изолированным затвором, так же известные как МОП-транзисторы (MOSFET), выполняющих роль переключателя. Однако, критерием “истинности” или “ложности” всей схемы является не протекающий ток, а значение напряжения (условно “высокое” или “низкое”)
Принципы работы полевых транзисторов
Полевые транзисторы состоят из двух полупроводниковых терминалов p- или n-типа (называемых исток (Source) и сток (Drain)), помещенных в субстрат соответственно n- или p-типа. N-тип соответствует электронной, а p-тип – дырочной проводимости. Сам транзистор обозначается по типу терминалов.
Так же присутствуют два терминала, называемых база (base) и затвор (gate), которые, собственно, и обеспечивают управление транзистором.
При приложении напряжения между базой и затвором, электроны или дырки притягиваются к области затвора, создавая канал проводимости между истоком и стоком. Изменение электрического поля между базой и затвором изменяет сопротивление этого канала.
Встречаются МОП-транзисторы с собственным (или встроенным) (depletion mode transistor) и индуцированным (или инверсным) каналом (enhancement mode transistor). Встроенный канал означает, что при нулевом напряжении затвор-база, канал транзистора открыт (т.е. проводит ток); для закрытия канала нужно приложить к затвору напряжение определенной полярности. Канал приборов с индуцированным каналом закрыт (не проводит ток) при нулевом напряжении затвор-база; для открытия канала нужно приложить к затвору напряжение определенной полярности. Полярность напряжения определяется типом проводников в транзисторе (N- или P-тип).
Часто терминал базы подключают напрямую к истоку.
Реализация логических операций на МОП-транзисторах
Независимо от типа транзистора, он может быть “настроен” таким образом, чтобы либо переходить в “открытое” состояние при подаче высокого напряжения (соответствующего логической единице) на затвор, либо низкого (соответствующего логическому нулю), и в “закрытое” в противном случае. При проектировании логических схем, имеет значение только этот фактор.
В этом контексте, транзисторы, переходящие в “открытое” состояние при подаче логической единицы на затвор, называются прямыми, а в “закрытое” – инверсными. При проектировании логики, часто используются следующие обозначения:
Как правило, прямые транзисторы реализуются на NMOS, а инверсные – на PMOS.
На основе этих двух типов строятся микросхемы типа CMOS (КМОП – комплементарная структура металл-оксид-полупроводник, она же COS-MOS), состоящие из симметрично расположенных p- и n-канальных полевых транзисторов. Использование симметричных схем позволяет значительно уменьшить ток активации схемы, и снизить энергопотребление.
Штрих Шеффера может быть реализован, например, так:
Логические схемы
На основе логических элементов строятся логические схемы. На логических схемах не рассматривается внутреннее устройство элементов, поэтому все логические схемы полностью эквивалентны логическим формулам, которые их выражают.
Для обозначения логических элементов, соответствующих базовым логическим операциям используются следующие обозначения:
Полусумматор
- Полусумматор
- Электронная логическая схема, выполняющая суммирование двух двоичных разрядов.
Имеет, ясно, два входа, и два выхода, один из которых – значение младшего разряда (сумма, s), а второй – старшего (перенос, p).
| a | b | s | p |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Из таблицы истинности видно, что \[s = a \oplus b\] \[p = a \,\&\,b\]
Составляя СДНФ:
\[s = (a \,\&\,\;\overline{b}\;) \vee(\;\overline{a}\; \,\&\,b)\] \[p = a \,\&\,b\]
Логическая схема тогда будет иметь вид:
Преобразуя к штриху Шеффера:
\[s = (a | (b|b)) | ((a|a) | b)\] \[p = (a|b)|(a|b)\]
Можно заметить, что \[(x|(x|y)) = \;\overline{x}\; \vee(x\,\&\,y) = \;\overline{x}\; \vee y = (x|(y|y))\]
Тогда
\[s = (a | (a|b)) | ((a|b) | b)\] \[p = (a|b)|(a|b)\]
Составим логическую схему:
На схемах можно изображать полусумматор следующим образом:
Сумматор
- Сумматор
- Электронная логическая схема, выполняющая суммирование двоичных кодов.
Сумматор работает следующим образом: при сложении двух двоичных разрядов, у нас есть перенос из предыдущего разряда \(p_i\), плюс значения \(a_i\), \(b_i\) текущего разряда. Результатом работы должна быть цифра суммы в текущем разряде \(s_i\) и перенос в следующий разряд \(p_{i+1}\).
Составим таблицу истинности
| \(a_i\) | \(b_i\) | \(p_i\) | \(s_i\) | \(p_{i+1}\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Исходя из таблицы истинности, можно (например, составив СДНФ и упростив ее), вывести следующие формулы:
\[ p_{i+1} = a_i \,\&\,b_i \vee a_i \,\&\,p_i \vee b_i \,\&\,p_i \]
\[ s_i = (\;\overline{p_{i+1}}\; \vee a_i \,\&\,b_i \,\&\,p_i) \,\&\,(a_i \vee b_i \vee p_i) = a_i \oplus b_i \oplus p_i \]
В соответствии с этими формулами можно составить логическую схему:
Мы составили схему одноразрядного сумматора.
Так же сумматор можно получить, соединив два полусумматора:
Или на элементах И-НЕ:
Одноразрядный сумматор является стандартным элементом, и на схемах изображается следующим образом:
Многоразрядный сумматор получается при соединении нескольких одноразрядных каскадом:
При этом, первый “перенос” (вход) берется равным нулю, а последний (выход) \(P\) является признаком переполнения.
Триггеры
Результаты операций, как и сами операнды, надо где-то как-то хранить. Для этого используются логические элементы, известные как триггеры.
- Триггер
- Логический элемент, способный хранить один разряд двоичного числа.
RS-триггер
Представляет собой простейший триггер. Имеет следующую схему:
По сути, состоит из двух элементов ИЛИ-НЕ, соединенных кольцом.
Имеет следующую таблицу истинности:
| R | S | Q |
|---|---|---|
| 0 | 0 | Q |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 🕱 |
При подаче нулей на оба входа, хранится ранее установленное значение. При подаче 1 на вход S (Set), значение устанавливается в 1, при подаче 1 на вход R (Reset), значение сбрасывается в 0.
Подавать 1 на оба входа одновременно запрещено, поскольку в таком случае \(Q=\;\overline{Q}\; = 0\). При подаче после этого нулей на оба входа, состояние триггера не определено (зависит от внутренних характеристик элементов)
SR-триггер
Близким по смыслу является \(\;\overline{SR}\;\) триггер, который представляет собой два соединенных кольцом элемента И-НЕ:
Отличие от \(RS\)-триггера в том, что входы инвертированны и меняются местами.
Таблица истинности:
| \(\;\overline{R}\;\) | \(\;\overline{S}\;\) | \(Q\) |
|---|---|---|
| 0 | 0 | 🕱 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | Q |
Подавать 0 на оба входа одновременно запрещено, поскольку в таком случае \(Q=\;\overline{Q}\; = 1\). При подаче после этого 1 на оба входа, состояние триггера не определено (зависит от внутренних характеристик элементов)
D-триггер
D-триггер представляет собой более удобную версию, поскольку сохраняет значение одного входа.
Имеет следующую схему:
Имеет два входа, D (Data) и E (Enable).
Таблица истинности:
| E | D | Q |
|---|---|---|
| 0 | 0 | Q |
| 0 | 1 | Q |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
D-триггеры широко используются для реализации сдвиговых регистров. Сдвиговые же регистры используются, например, при приведении порядков чисел с плавающей запятой.
JK-триггер
Близкий аналог RS-триггера, J соответствует S, а K – R.
Отличием является тот факт, что при подаче на оба входа единиц, триггер меняет состояние на противоположное.
В чистом виде, однако, это не слишком удобно, поскольку при подаче единиц на оба входа, состояние будет меняться с высокой частотой. Поэтому JK-триггер используют в модификации с изменением по синхроимпульсу.
T-триггер
Получается из JK подачей на \(J=K=T\). По сути, переключает состояние при подаче логической 1. На основе T-триггера можно сделать простейший счетчик: если соединить выход одного T-триггера со входом E другого, то это эффективно понизит частоту переключения второго вдвое по сравнению с первым.
Мультиплексор
- Мультиплексор
- логический элемент, имеющий несколько сигнальных входов, один (или более) управляющих входов и один выход
- позволяет передавать сигнал с одного из входов на один выход
Простейший вариант – однобитный мультиплексор с двумя сигнальными входами – использует однобитный управляющий вход. В общем случае, число бит управляющего входа должно быть не менее \(\ceil {\log_2 N},\) где \(N\) – число сигнальных входов, \(\ceil \cdot\) – округление вверх, т.к. именно столько бит необходимо для выбора одного из сигнальных входов (следует из числа возможных комбинаций \(x\) бит равного \(2^x\))
| S | A | B | Z |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
По таблице истинности легко можно составить формулу:
\[Z = (A \,\&\,\;\overline{S}\;) \vee(B \,\&\,S)\]
Или, на основе штриха Шеффера:
\[Z = (A | (S|S)) | (B | S)\]
Мультиплексор считается базовым компонентом логических схем, часто изображается одним блоком и помечается символами “MS” (от “multiple select”) или “MUX” (от “multiplexor”)
Демультиплексор
- Демультиплексор
- логический элемент, предназначенный для переключения сигнала с одного входа на один из выходов.
- функционально противоположен мультиплексору
Т.е. позволяет подключить один вход к различным выходам.
Аналогично мультиплексору, битность управляющего входа по меньшей мере \(\ceil{\log_2 N},\) где \(N\) – число выходов.
| S | X | A | B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
По таблице истинности несложно построить логические формулы для выходов:
\[A = X\,\&\,\;\overline{S}\;\] \[B = X\,\&\,S\]
Или на основе штриха Шеффера:
\[A = (X|(S|S))|(X|(S|S))\] \[B = (X|S)|(X|S)\]
Выражение для \(A\) можно дополнительно упростить, используя тот же подход, что и в случае сумматора, произведя замену \(X|(S|S) = (X|(X|S))\):
\[A = (X|(X|S))|(X|(X|S))\]
Демультиплексор считается базовым компонентом логических схем, часто изображается одним блоком и помечается символами “DX” (от “demultiplexor”), “DS”, “DMX”, “DMS”.