Мой последний пост представил тривиальную, но необходимую фишку Не. Прежде чем я отойду от первого проекта, я хотел бы упомянуть одну последнюю фишку, которую я нашел интригующей и особенно трудной для решения. Этот чип называется мультиплексор, или, сокращенно, мультиплексор. Этот чип имеет гораздо более сложную спецификацию, чем чип Не.
Как это работает
Микросхема мультиплексора имеет три входа, которые я обозначу как «a», «b» и «sel», сокращенно от «селектор». Чип мультиплексора также имеет единственный выход. Функциональность, которую мы хотим от этого чипа, заключается в том, что когда вход «sel» равен 0, выход должен быть равен «a». Если «sel» равно 1, выход должен быть равен «b». Следовательно, из этой информации мы можем вывести следующую таблицу истинности.
MUX CHIP TRUTH TABLE | a | b | sel | out | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |
Это более сложная таблица, чем та, которая была сгенерирована из чипа «Не». Из-за этого вы, вероятно, не сможете найти решение, просто взглянув на эту таблицу. Вам нужно будет разбить эту информацию на куски, чтобы ее было легче усваивать.
Комбинационная логика против последовательной логики
Чтобы разбить эту проблему на куски, мы должны сначала понять разницу между этими двумя формами логики. Почти каждая проблема, с которой мы сталкивались как программисты, была последовательной по своей природе. Мы применяем фильтры, которые направляют результаты по разным ветвям логики. Если бы мы подошли к этому чипу с последовательной логикой, это выглядело бы примерно так:
1. if(sel ==0)
2. {return a;}
3. else
4. {return b;}
Что делает это выразительно последовательным по своей природе, так это тот факт, что эта логика должна выполняться строка за строкой, начиная сверху и продвигаясь к низу. Поэтому он должен иметь некоторое представление о том, где он находится в настоящее время, и он также должен знать, куда двигаться дальше. По сути, происходит то, что программа начинается с первой строки. Если первая строка верна, она переместится на вторую строку. Если это не так, ему придется перейти на третью строку. Проблема с попыткой построить микросхему низкого уровня с логикой такого типа заключается в том, что мы работаем с напряжением. Следовательно, для всех намерений и целей не существует понятия времени. Все происходит мгновенно. Хорошо, если последовательная логика не работает, тогда что нам нужно? Здесь на помощь приходит комбинационная логика.
Эти три диска — отличный пример комбинационной логики. Нет чувства времени или порядка выполнения. Цвет, который вы видите, строго основан на цвете или комбинации цветов, которые перекрываются. Итак, как мы можем применить эту логику к микросхеме мультиплексора? Здесь мы вынуждены заняться булевой алгеброй. Хотя обещаю, будет весело.
Булева алгебра
Что такое Булева алгебра? Булева алгебра — это особый вид математики, который имеет дело исключительно с числами 0 и 1. Поскольку числа имеют столь ограниченную область применения, вы увидите, что мы можем брать сложные выражения и упрощать их намного больше, чем можно было бы ожидать.
Сначала давайте еще раз взглянем на эту таблицу истинности и посмотрим, сможем ли мы извлечь какую-нибудь полезную информацию.
MUX CHIP TRUTH TABLE | a | b | sel | out | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |
Нам нужна какая-то формула, которая будет соответствовать этой таблице истинности. Первое, что вы хотите сделать, пытаясь вывести формулу (или спроектировать микросхему) из таблицы истинности, — это извлечь сценарии, в которых вывод или результат был равен единице. Это приводит к гораздо более простой таблице
| a | b | sel | out | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |
Отсюда мы можем разработать формулу для каждой строки. Простой способ думать об этом — посмотреть на входные данные строки, а затем переписать переменные так, чтобы они работали как длинный оператор «И». Как мы знаем, оператор «И» возвращает истину только в том случае, если оба ввода верны, поэтому первая строка будет преобразована во что-то вроде этого:
Итак, в этом случае мы знаем, что если мы возьмем «НЕ» из «а», затем «И», что вместе с «b» и «с» мы получим желаемый результат. HDL для этого будет выглядеть так:
Если бы нам была дана только одна линия, вышеуказанный чип работал бы идеально. Но на самом деле есть три разных сценария, где выход тоже один. Так как же нам получить формулу, определяющую каждый из этих случаев? Мы делаем то же самое, что и выше, но затем просто «ИЛИ» эти операторы вместе. Вот так:
Как видите, на данный момент это становится несколько громоздким. Но я все же конвертирую это как есть в HDL, чтобы показать, что оно работает как есть.
Конечно, если вы поместите приведенный выше код в компилятор и запустите его на тестах, которые он проходит с честью. Но что-то мне подсказывает, что мы можем немного упростить этот чип. Итак, давайте вернемся и запишем все выражение, которое мы обнаружили до сих пор. Если мы попытаемся сделать это одним оператором, это будет выглядеть так:
(Not(a) & b & sel) Or (a & NOT(b) & NOT(sel)) Or (a & b & NOT(sel)) Or (a & b & sel)
«В булевой алгебре «И» что-то эквивалентно умножению, потому что, поскольку два числа, которые вы умножаете, могут быть только единицей или нулем, результатом умножения может быть только единица, если оба умножаемых числа равны единице. Для «ИЛИ» что-то эквивалентно сложению, потому что аналогичным образом вы получите единицу, только если одно из чисел, которые вы складываете, равно единице. Наконец, везде, где вы видите «НЕ», вы можете заменить его символом «-», чтобы его было легче читать. Итак, давайте перепишем приведенное выше выражение, заменив операции «И» и «ИЛИ» на умножение и сложение, а также удалив все операции «НЕ».
(-absel)+(a-b-sel)+(ab-sel)+(absel)
Если мы посмотрим на приведенную выше формулу, то увидим, что есть несколько повторяющихся факторов, которые можно упростить. Давайте начнем с удаления «sel», где это возможно.
(-abSEL)+(a-b-sel)+(ab-sel)+(abSEL) sel(-ab+ab) + a-b-sel + ab-sel
Оказывается, мы можем еще больше упростить «sel(-ab+ab)», вынеся из него «b».
sel(-aB+aB) + a-b-sel + ab-selsel(b(-a+a)) + a-b-sel + ab- sel
Теперь мы закончили с «-a + a». Что всегда будет равно единице, потому что если «а» было равно нулю, то ноль + НЕ (ноль) равно единице и наоборот. Поэтому мы можем еще больше упростить выражение.
sel(b(-a+a)) + a-b-sel + ab- sel sel(b(1)) + a-b-sel +ab-sel sel(b) + a-b-sel+ab-sel
Итак, теперь давайте сделаем то же самое, но сосредоточимся на удалении «-sel», где мы можем
sel(b) + a-b-SEL+ab-SEL sel(b) + -sel(A-b +Ab)sel(b) + -sel(a(-b+b))sel(b) + -sel(a(1)) sel(b) + -sel(a)
Точно так же мы сократили огромное выражение до чего-то управляемого. Теперь, как нам преобразовать это обратно в HDL? Давайте вспомним, что везде, где вы видите умножение, замените его на «И», где вы видите отрицательный символ, замените его на «НЕ». Везде, где вы видите символ добавления, замените его на «ИЛИ». Нравится:
sel(b) + -sel(a) (sel & b) Or (NOT(sel) & a)
Это гораздо более простое выражение, которое можно переписать на HDL следующим образом.
Теперь, если вы прогоните любое из значений из приведенной выше таблицы истинности в этой формуле, вы обнаружите, что все они волшебным образом работают. Таким образом, триумф комбинационной логики привел нас к созданию полезной микросхемы мультиплексора.
Первоначально опубликовано на сайте georgefabish.com 20 января 2019 г.
