Логические элементы
Доброго времени суток, я начинаю серию статей по написанию виртуальной машины на языке Golang. Я выбрал этот язык так как он прост для чтения и имеет в стандартной библиотеке уже необходимые функции, которые пригодятся в дальнейшем.
Эта статья не несёт в себе абсолютно никакой новой информации для тех, кто умеет составлять таблицы истинности для простых логических вентилей. Если вы это умеете, то не тратьте время и переходите ко второй части.
Логический вентиль это устройство с одним или несколькими входами и одним или несколькими выходами. В этой части будем рассматривать только самые простые из них. Для моделирования вентилей мы будем использовать только сигналы 0 и 1, не используя входные, выходные характеристики реальных вентилей.
Так как мы будем работать с Golang, то каждый элемент можно представить в виде функции.
В Go функция выглядит так:
func имя(имя переменной тип переменной) тип возвращаемого значения {
//код
return имя возвращаемой переменной
}Буфер
Это самый простой элемент имеющий один вход и один выход. На практике используется для усиления сигнала или создания задержки, иногда можно заменить проводником.
| a | BUF a |
| 0 | 0 |
| 1 | 1 |
в случае с буфером наша функция будет выглядеть так:
func Buf(v bool) bool {
return v
}Инвертор
Тот же самый буфер, только на выходе инвертирует сигнал.
| a | NOT a |
| 0 | 1 |
| 1 | 0 |
в случае с инвертором функция будет выглядеть так:
func Inv(v bool) bool {
return !v
}ИЛИ
Этому элементу необходим хотя бы один сигнал равный 1, чтобы на выходе получить 1.
| a | b | a OR b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
func Or(v, s bool) bool {
return v || s
}И
Всегда возвращает 1, когда на все его входы подаётся 1, во всех остальных случаях он возвращает 0.
| a | b | a AND b |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
func And(v, s bool) bool {
return v && s
}Исключающее ИЛИ
Для того, чтобы на выходе получить 1, нужно чтобы на вход подавались разные сигналы (0 и 1) или (1 и 0). Эта операция является полезной, так как позволяет поменять местами две переменные без использования дополнительной памяти.
| a | b | a XOR b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
func Xor(v, s bool) bool {
// написать (v ^ s) мы не можем потому, что для bool такой операции в языке нет, поэтому юзаем костыль
return (v || s) && !(v && s)
}ИЛИ-НЕ
Работает как элемент ИЛИ, только к его выходу подсоединён инвертор, с которого получаем сигнал.
| a | b | a NOR b |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
func Nor(v, s bool) bool {
return !(v || s)
}И-НЕ
Элемент работает точно так же, как элемент И, только на выходе инвертируется сигнал.
| a | b | a NAND b |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
func Nand(v, s bool) bool {
return !(v && s)
}Исключающее ИЛИ с инверсией
Элемент работает точно так же, как элемент ИЛИ, только на выходе инвертируется сигнал.
| a | b | a XNOR b |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
func Xnor(v, s bool) bool {
// и тут костыль
return !((v || s) && !(v && s))
}Теперь, когда функции написаны, можно их собрать в пакет Gate, на основе которого будем реализовывать более сложные вещи. Наша иерархия пакетов будет похожа иерархию абстракций реального компьютера. Исходный код можно найти здесь.
Комментарии (50)
Grey83
16.11.2019 17:00+1В Golang нельзя сравнивать булевы переменные знаком равенства?
Я про исключающее ИЛИ.
yarick123
16.11.2019 20:30Тут речь идёт о логических элементах (схемотехники?), которые описываются операторами булевой алгебры (И, ИЛИ, НЕ). Оператор равенства к ним не относится. Поэтому, я думаю, автор его и не использует.
Grey83
16.11.2019 20:41В SourcePawn к булевым переменным можно применять как оператор равенства, так и операторы булевой логики.
Также как операторы булевой алгебры можно применять к целым числам.
Вот мне и интересно что мешает это же использовать в Go.
Вот в таком виде:
func xor(v, s bool) bool { return v != s } func xnor(v, s bool) bool { return v == s }
Darlington Автор
16.11.2019 21:21Можно, но зачем?
Grey83
16.11.2019 22:40чтобы не городить велосипеды и костыли, наверное
dasFlug
17.11.2019 09:15использование сравнения прячет логику операции. Выход элемента XOR определяется не равенством входов, а нечетностью числа единиц на них. Уже для XOR с тремя входами выражение использующее сравнение читается не лучше чем использующее И-ИЛИ-НЕ.
Grey83
17.11.2019 16:00Таблица соответствия такая?
0 0 0 -> 0
0 0 1 -> 1
0 1 0 -> 1
0 1 1 -> 0
1 0 0 -> 1
1 0 1 -> 0
1 1 0 -> 0
1 1 1 -> 1
func xor(a, b, c bool) bool { return (a != b) != c }
0 0 0 -> 1
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 -> 0
func xnor(a, b, c bool) bool { return (a == b) != c }dasFlug
17.11.2019 20:11Таблицы истинности особо и не нужны. xor на три вход это a xor b xor c. Так что у вас все правильно. Скорее это я автора не понял. Я посчитал что он хочет показать математическую суть xor в реализации на базовых логических операциях. Но тогда нужно было и без применения законов де Моргана записывать. А если это библиотека реального проекта то конечно нужно использовать сравнение.
livsius
16.11.2019 21:22+3«НЕ-И» как-то режет глаз. Общепринятая форма все-таки — «И-НЕ».
pae174
17.11.2019 17:14> «НЕ-И» как-то режет глаз. Общепринятая форма все-таки — «И-НЕ».
НЕ-И это вообще отдельные элементы — логические элементы с инверсными входами.
Сначала на входах делается инверсия а потом к результату инверсии применяется И.
livsius
16.11.2019 21:50и как уже заметил выше fougasse, можно сократить множество до минимального набора базисных функций, с помощью которых можно выразить любую произвольную. Несколько примеров минимальных наборов:
1. {«AND», «NOT»}
2. {«OR», «NOT»}
3. {«XOR»,«AND»}
eanmos
16.11.2019 23:07Вообще, достаточно всего одной операции: NOR (стрелка Пирса) или NAND (штрих Шеффера). Все остальные можно выразить через них.
livsius
16.11.2019 23:21Вообще, достаточно любого минимального набора базисных функций. Я привел 3 примера, любой из которых достаточен. Вы лишь привели пример 2-го и 3-го наборов, скомбинированных в одну функцию с новым названием.
Такое комбинирование позоляет использовать только одну функцию, но требует заковыристых их комбинаций даже в простых случаях. Своего рода brainfuck.eanmos
16.11.2019 23:36Ну, во-первых, ни одна из функций в вашем сообщений не является базисной. Во-вторых, наборы, которые вы привели отнюдь не минимальны. Базис пространства булевых функциий от двух переменных образуют штрих Шеффера и стрелка Пирса. Поэтому нам не нужно никакого «набора базисных функций», достаточно лишь одной функции: NAND или NOR.
livsius
16.11.2019 23:42А что такое базисная функция?
И эти наборы минимальны. Просто попробуйте минимизировать любой из них, если считаете что он не минимален.
Так же справедливо утверждать, что не нужно никакой одной функции NAND, достаточно лишь пары {«AND», «NOT»}.
Ваша функция NAND не дает никакого профита в общем случае относительно пары {«AND», «NOT»}.eanmos
16.11.2019 23:58Базисная функция — это функция, которая образует базис в некотором пространстве. Вроде, очевидно :)
Любой вектор в пространстве может быть выражен как линейная комбинация базиса. В нашем случае любая булева функция от двух переменных может быть выражена всего через один вектор NAND или NOR, поэтому система из двух векторов {AND, NOT} не может считаться минимальной.
Я и не говорил, что от NAND или NOR будет какой-то профит, тем более в реальном железе. Скорее, наоборот.
Просто вы захотели выразить любую произвольную булеву функцию через минимальный набор базисных функций. Я вам указал на то, что необходимо и достаточно всего одной такой функции.livsius
17.11.2019 00:39+1Вот, вот, именно, что «Любой вектор в пространстве может быть выражен как ЛИНЕЙНАЯ комбинация базиса», а в нашем случае функции являются НЕлинейными комбинациями базиса. И это ключевой момент:
По причине нелинейности, в зависимости от вида выбранных функций они могут либо вообще не образовывать базис, либо образовывать базис, размер которого опять же зависит от вида выбранных функций.
Функции «AND» и «NOT» образуют базис размерности 2, т.к. любая функция может быть выражена через их комбинацию, но после удаления любого элемента набор перестает быть базисом и больше не позволяет выразить все функции пространства. Т.е. базис на функциях {«AND», «NOT»} — минимален.
Вы выбрали другой набор базисных функций {NAND} размерности 1 и он тоже минимален.
Поймите, если размерность одного конкретного набора функций больше размерности другого — это не значит, что первый набор неминимален. Они построены на разных функциях, и, как следствие, имеют разную размерность.
И бОльшая размерность базиса не означает ни неоптимальность, ни неминимальность, ни что-то еще «плохое». Это просто другой базис.
И когда я говорил о минимальных наборах, я подразумевал не набор с минимальной размерностью. Я подразумевал все существующие базисы содержащие минимальные наборы функций.eanmos
17.11.2019 00:55Мне кажется, вы пишете какую-то ерунду. Все базисы векторного пространства содержат одинаковое количество векторов.
livsius
17.11.2019 01:00+1вы просто не понимаете.
Все базисы ЛИНЕЙНОГО векторного пространства содержат одинаковое количество векторов.
В нашем случае пространство НЕлинейно.eanmos
17.11.2019 01:04Любое векторное пространство — линейно. Это просто синонимы.
livsius
17.11.2019 01:21Хорошо. Каковы основания считать базисную функция вектором а все булевы функции их линейными комбинациями?
Я утверждаю, что любая функция является НЕЛИНЕЙНОЙ комбинацией базисных функции
Вы ваши суждения основаваете на понятиях векторного пространства и линейной комбинациях.
Попробуйте тогда, пожалуйста, представить функцию F(X0, X1) = NOT(OR(X0,X1)) в виде линейной комбинации вашей базисной функции NAND.eanmos
17.11.2019 01:59Честно говоря, я не знаю как это сделать. Вообще, у нас с вами довольно странный спор, т. к. мои (равно как и ваши, похоже) познания в математике довольно скудны. Вряд ли мы свами сможем прийти к истине :)
А вообще, я, видимо, был не прав, сказав, что "… ни одна из функций в вашем сообщений не является базисной". Если верить википедии, то все функции, которые вы перечислили являются «minimal functionally complete sets of logical connectives with arity ? 2».
fougasse
17.11.2019 09:46Вы можете привести определение нелинейной функции?
Откуда у вас в булевой алгебре нелинейные функции.livsius
17.11.2019 10:38Загляните в вики, например статья «Линейная функция»:
Там даже есть раздел «Алгебра логики» вы найдете ответ на ваш вопрос:
<<Булева функция… называется линейной, если… >>
fougasse
17.11.2019 09:44Вы бы почитали хоть теорию минимизации перед тем как спорить, а то термины, вроде, у вас правильные, а смысла в обсуждении заданной темы не имеют.
livsius
17.11.2019 10:41Не понял смысла вашей реплики, если честно.
Про минимизацию знаю. И что нам дает «теория минимизации» в данном вопросе?
Darlington Автор
16.11.2019 23:22Я знаю, что можно так выразить, я их отнёс к одной категории так как они выполняют однотипные операции и относительно несложные (1-2 входа и один выход, а по количеству вентилей, +-5 штук нужно, чтобы выразить другие операции)
GREGOR_812
17.11.2019 00:37А что подразумевается под словосочетанием «виртуальная машина»? Если честно, подозреваю, что модель компьютера с детализацией на уровне гейтов будет адски тормозить, даже если реализовать процессор уровня Intel 8080.
livsius
17.11.2019 00:57Безусловно.
Масштаб «Simulation time»->«Real time» огромен если речь идет и RTL симуляции выполнения какого-то кода на современном CPU в современных симуляторах. Если говорить о gate-level симуляции — он просто чудовищен. Не побоюсь оценить это как 1сек реальных -> 100 часов симуляцииGREGOR_812
17.11.2019 04:30Ага, я именно об этом и думал когда писал. У меня маленький SPI-контроллер на пару тысяч ячеек на RTL-уровне симулировался реально десятки минут, за это время прогонялась примерно сотня посылок по 16 байт
evkochurov
17.11.2019 18:18func xnor(v, s bool) bool { // и тут костыль return !(v || s) && !(v && s) }
А затестить костылик не забыли случаем? xnor(1,1) возвращает неверный результат.Darlington Автор
17.11.2019 21:41Не забыл, всё в порядке с этим элементом
evkochurov
17.11.2019 22:21Вы уверены? К слову, в гите текст этой функции другой, и он больше походит на правду.
Alyoshka1976
17.11.2019 23:35
Аргументы 1 и 1, результат 0 — не соответствует приведенной для нее таблице истинности
Вот ссылка на «песочницу», можете проверить:
https://play.golang.org/p/LEOA0f4KKwj
livsius
18.11.2019 17:41Darlington
Не могли бы вы пояснить:
1. O какой виртуальной машине вообще идет речь: собственный простенький CPU, полноценная машина со всей периферией и современным CPU, ...?
2. Каково предназначение виртуальной машины?
fougasse
Хотя бы про базисы вспомнить не мешало бы, тогда можно одни ф-ии через другие выражать, если вы уже решили "иерархию реального компьютера" делать.
gleb_l
Основная сложность «иерархии реального компьютера» в принципиально разной трактовке физического времени — аппаратура суть асинхронная, а программный тред — синхронен. В результате все, что каким-либо образом в аппаратуре тактируется, имеет обратные связи, триггерные эффекты, или образует гонки, нужно будет эмулировать вместе с временным доменом — то есть снепшотить предыдущее состояние, обсчитывать послндовательно, и производить следующее. Если временных доменов несколько — welcome просчитывать состояния элементов, завязанных больше, чем на один из них. В итоге эмуляция целого процессора, даже такого, как 8080 (он, кстати, даже не полностью статический — значит, какой-то функционал у него завязан на величине физических задержек) — очень нетривиальная задача. И способ описания базовых кирпичей здесь потеряется после первого же эмалированного регистра
fougasse
Да вы что, вот это новости.
Я для вас открою тайну, что и ЛЭ асинхронны, и проблемы начнутся задолго до "эмали" на регистрах.
livsius
Задержками ЛЭ как раз таки можно пренебречь, пока рабочая частота находится в пределах границ работоспособности. Ведь нам неинтересна виртуальная машина, которая сбоит из-за завышенной частоты clock'а, правда?
А вот clock domain crossing эффекты есть всегда. Они вносят в модель недетерминированность даже на уровне симуляции.
fougasse
Какая виртуальная машина?
Снова термины есть, а смысла нет.
livsius
Если вам суслика не видно, это еще ничего не значит.
Вообще ощущение, что вы не утруждаетесь вникнуть в текст, но очень хотите поучать и возражать.
Прочтите хотя бы начало статьи топикстартера для начала, тогда и поговорим.
livsius
gleb_I, согласен с вами:
Выглядит, как-будто коллега замахнулся на 2 неподъемные для одного человека задачи:
1. Написание собственного Digital HW симулятора.
2. Написание HW модели машины (Gate-level или RTL — тут уже не важно. Оба варианты неподъемны)
nckma
Хм… ну так-то на RTL, тот же Verilog, даже один человек вполне в состоянии написать простой процессор. И симулятор тоже.
livsius
Виртуальная машина — это не простой процессор. Это сложный процессор и куча сложной периферии. Даже если исходить из предположения, что человек уже обладает всеми полноценными знаниями об устройстве hardware на уровне регистров (процессора, периферийных контроллеров (PCIexpress, USB, SATA, MEmory Controller, etc)) — В совокупности сложность написания виртуальной машины хотя бы отдаленно приближающейся к современной реальной неподъемна для одного человека.
nckma
Может я пропустил — где написано про архитектуру именно ПК компьютера? Может это какая абстрактная машина?
livsius
Возможно вы правы. Автор не раскрывает деталей.
Я интуитивно воспринял это как инструмент для исследования/экспериментирования с современными ПО и/или железом.