Архитектура компьютерных систем 1 часть. Логические вентили

Логические элементы


Доброго времени суток, я начинаю серию статей по написанию виртуальной машины на языке 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, на основе которого будем реализовывать более сложные вещи. Наша иерархия пакетов будет похожа иерархию абстракций реального компьютера. Исходный код можно найти здесь.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 50

    +3

    Хотя бы про базисы вспомнить не мешало бы, тогда можно одни ф-ии через другие выражать, если вы уже решили "иерархию реального компьютера" делать.

      0

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

        0

        Да вы что, вот это новости.
        Я для вас открою тайну, что и ЛЭ асинхронны, и проблемы начнутся задолго до "эмали" на регистрах.

          0
          Задержками ЛЭ как раз таки можно пренебречь, пока рабочая частота находится в пределах границ работоспособности. Ведь нам неинтересна виртуальная машина, которая сбоит из-за завышенной частоты clock'а, правда?
          А вот clock domain crossing эффекты есть всегда. Они вносят в модель недетерминированность даже на уровне симуляции.
            0

            Какая виртуальная машина?
            Снова термины есть, а смысла нет.

              0
              Если вам суслика не видно, это еще ничего не значит.
              Вообще ощущение, что вы не утруждаетесь вникнуть в текст, но очень хотите поучать и возражать.
              Прочтите хотя бы начало статьи топикстартера для начала, тогда и поговорим.
          +2
          gleb_I, согласен с вами:
          Выглядит, как-будто коллега замахнулся на 2 неподъемные для одного человека задачи:
          1. Написание собственного Digital HW симулятора.
          2. Написание HW модели машины (Gate-level или RTL — тут уже не важно. Оба варианты неподъемны)
            0
            Хм… ну так-то на RTL, тот же Verilog, даже один человек вполне в состоянии написать простой процессор. И симулятор тоже.
              0
              Виртуальная машина — это не простой процессор. Это сложный процессор и куча сложной периферии. Даже если исходить из предположения, что человек уже обладает всеми полноценными знаниями об устройстве hardware на уровне регистров (процессора, периферийных контроллеров (PCIexpress, USB, SATA, MEmory Controller, etc)) — В совокупности сложность написания виртуальной машины хотя бы отдаленно приближающейся к современной реальной неподъемна для одного человека.
                0
                Может я пропустил — где написано про архитектуру именно ПК компьютера? Может это какая абстрактная машина?
                  0
                  Возможно вы правы. Автор не раскрывает деталей.
                  Я интуитивно воспринял это как инструмент для исследования/экспериментирования с современными ПО и/или железом.
        +2
        В Golang нельзя сравнивать булевы переменные знаком равенства?
        Я про исключающее ИЛИ.
          0
          Тут речь идёт о логических элементах (схемотехники?), которые описываются операторами булевой алгебры (И, ИЛИ, НЕ). Оператор равенства к ним не относится. Поэтому, я думаю, автор его и не использует.
            0
            В SourcePawn к булевым переменным можно применять как оператор равенства, так и операторы булевой логики.
            Также как операторы булевой алгебры можно применять к целым числам.
            Вот мне и интересно что мешает это же использовать в Go.
            Вот в таком виде:
            func xor(v, s bool) bool {
                return v != s
            }
            
            func xnor(v, s bool) bool {
                return v == s
            }
            0
            Можно, но зачем?
              0
              чтобы не городить велосипеды и костыли, наверное
                0
                использование сравнения прячет логику операции. Выход элемента XOR определяется не равенством входов, а нечетностью числа единиц на них. Уже для XOR с тремя входами выражение использующее сравнение читается не лучше чем использующее И-ИЛИ-НЕ.
                  0
                  Таблица соответствия такая?

                  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
                  }
                    0
                    Таблицы истинности особо и не нужны. xor на три вход это a xor b xor c. Так что у вас все правильно. Скорее это я автора не понял. Я посчитал что он хочет показать математическую суть xor в реализации на базовых логических операциях. Но тогда нужно было и без применения законов де Моргана записывать. А если это библиотека реального проекта то конечно нужно использовать сравнение.
            +4
            «НЕ-И» как-то режет глаз. Общепринятая форма все-таки — «И-НЕ».
              –1
              Возможно
                0
                Лучше и правда поправить
                  0

                  Точно

                  0
                  > «НЕ-И» как-то режет глаз. Общепринятая форма все-таки — «И-НЕ».

                  НЕ-И это вообще отдельные элементы — логические элементы с инверсными входами.
                  Сначала на входах делается инверсия а потом к результату инверсии применяется И.
                  +1
                  и как уже заметил выше fougasse, можно сократить множество до минимального набора базисных функций, с помощью которых можно выразить любую произвольную. Несколько примеров минимальных наборов:
                  1. {«AND», «NOT»}
                  2. {«OR», «NOT»}
                  3. {«XOR»,«AND»}
                    +1
                    Вообще, достаточно всего одной операции: NOR (стрелка Пирса) или NAND (штрих Шеффера). Все остальные можно выразить через них.
                      +1
                      Вообще, достаточно любого минимального набора базисных функций. Я привел 3 примера, любой из которых достаточен. Вы лишь привели пример 2-го и 3-го наборов, скомбинированных в одну функцию с новым названием.
                      Такое комбинирование позоляет использовать только одну функцию, но требует заковыристых их комбинаций даже в простых случаях. Своего рода brainfuck.
                        +1
                        Ну, во-первых, ни одна из функций в вашем сообщений не является базисной. Во-вторых, наборы, которые вы привели отнюдь не минимальны. Базис пространства булевых функциий от двух переменных образуют штрих Шеффера и стрелка Пирса. Поэтому нам не нужно никакого «набора базисных функций», достаточно лишь одной функции: NAND или NOR.
                          0
                          А что такое базисная функция?
                          И эти наборы минимальны. Просто попробуйте минимизировать любой из них, если считаете что он не минимален.
                          Так же справедливо утверждать, что не нужно никакой одной функции NAND, достаточно лишь пары {«AND», «NOT»}.
                          Ваша функция NAND не дает никакого профита в общем случае относительно пары {«AND», «NOT»}.
                            0
                            Базисная функция — это функция, которая образует базис в некотором пространстве. Вроде, очевидно :)

                            Любой вектор в пространстве может быть выражен как линейная комбинация базиса. В нашем случае любая булева функция от двух переменных может быть выражена всего через один вектор NAND или NOR, поэтому система из двух векторов {AND, NOT} не может считаться минимальной.

                            Я и не говорил, что от NAND или NOR будет какой-то профит, тем более в реальном железе. Скорее, наоборот.

                            Просто вы захотели выразить любую произвольную булеву функцию через минимальный набор базисных функций. Я вам указал на то, что необходимо и достаточно всего одной такой функции.
                              +2
                              Вот, вот, именно, что «Любой вектор в пространстве может быть выражен как ЛИНЕЙНАЯ комбинация базиса», а в нашем случае функции являются НЕлинейными комбинациями базиса. И это ключевой момент:
                              По причине нелинейности, в зависимости от вида выбранных функций они могут либо вообще не образовывать базис, либо образовывать базис, размер которого опять же зависит от вида выбранных функций.
                              Функции «AND» и «NOT» образуют базис размерности 2, т.к. любая функция может быть выражена через их комбинацию, но после удаления любого элемента набор перестает быть базисом и больше не позволяет выразить все функции пространства. Т.е. базис на функциях {«AND», «NOT»} — минимален.

                              Вы выбрали другой набор базисных функций {NAND} размерности 1 и он тоже минимален.

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

                              И когда я говорил о минимальных наборах, я подразумевал не набор с минимальной размерностью. Я подразумевал все существующие базисы содержащие минимальные наборы функций.
                                0
                                Мне кажется, вы пишете какую-то ерунду. Все базисы векторного пространства содержат одинаковое количество векторов.
                                  +1
                                  вы просто не понимаете.
                                  Все базисы ЛИНЕЙНОГО векторного пространства содержат одинаковое количество векторов.
                                  В нашем случае пространство НЕлинейно.
                                    +1
                                    Любое векторное пространство — линейно. Это просто синонимы.
                                      0
                                      Хорошо. Каковы основания считать базисную функция вектором а все булевы функции их линейными комбинациями?
                                      Я утверждаю, что любая функция является НЕЛИНЕЙНОЙ комбинацией базисных функции
                                      Вы ваши суждения основаваете на понятиях векторного пространства и линейной комбинациях.
                                      Попробуйте тогда, пожалуйста, представить функцию F(X0, X1) = NOT(OR(X0,X1)) в виде линейной комбинации вашей базисной функции NAND.
                                        0
                                        Честно говоря, я не знаю как это сделать. Вообще, у нас с вами довольно странный спор, т. к. мои (равно как и ваши, похоже) познания в математике довольно скудны. Вряд ли мы свами сможем прийти к истине :)

                                        А вообще, я, видимо, был не прав, сказав, что "… ни одна из функций в вашем сообщений не является базисной". Если верить википедии, то все функции, которые вы перечислили являются «minimal functionally complete sets of logical connectives with arity ≤ 2».
                                          0

                                          Вы можете привести определение нелинейной функции?
                                          Откуда у вас в булевой алгебре нелинейные функции.

                                            0
                                            Загляните в вики, например статья «Линейная функция»:
                                            Там даже есть раздел «Алгебра логики» вы найдете ответ на ваш вопрос:
                                            <<Булева функция… называется линейной, если… >>
                                    –1

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

                                      0
                                      Не понял смысла вашей реплики, если честно.
                                      Про минимизацию знаю. И что нам дает «теория минимизации» в данном вопросе?
                            0
                            Я знаю, что можно так выразить, я их отнёс к одной категории так как они выполняют однотипные операции и относительно несложные (1-2 входа и один выход, а по количеству вентилей, +-5 штук нужно, чтобы выразить другие операции)
                          0
                          А что подразумевается под словосочетанием «виртуальная машина»? Если честно, подозреваю, что модель компьютера с детализацией на уровне гейтов будет адски тормозить, даже если реализовать процессор уровня Intel 8080.
                            0
                            Безусловно.
                            Масштаб «Simulation time»->«Real time» огромен если речь идет и RTL симуляции выполнения какого-то кода на современном CPU в современных симуляторах. Если говорить о gate-level симуляции — он просто чудовищен. Не побоюсь оценить это как 1сек реальных -> 100 часов симуляции
                              0
                              Ага, я именно об этом и думал когда писал. У меня маленький SPI-контроллер на пару тысяч ячеек на RTL-уровне симулировался реально десятки минут, за это время прогонялась примерно сотня посылок по 16 байт
                            0
                            func xnor(v, s bool) bool {
                            // и тут костыль
                                return !(v || s) && !(v && s)
                            }

                            А затестить костылик не забыли случаем? xnor(1,1) возвращает неверный результат.
                              0
                              Не забыл, всё в порядке с этим элементом
                                +1
                                Вы уверены? К слову, в гите текст этой функции другой, и он больше походит на правду.
                                  +1

                                  image
                                  Аргументы 1 и 1, результат 0 — не соответствует приведенной для нее таблице истинности
                                  Вот ссылка на «песочницу», можете проверить:
                                  https://play.golang.org/p/LEOA0f4KKwj

                                +1
                                исправил
                                  0
                                  Darlington
                                  Не могли бы вы пояснить:
                                  1. O какой виртуальной машине вообще идет речь: собственный простенький CPU, полноценная машина со всей периферией и современным CPU, ...?
                                  2. Каково предназначение виртуальной машины?

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

                                  Самое читаемое