Pull to refresh

Comments 50

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

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

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

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

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

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

func xnor(v, s bool) bool {
    return v == s
}
чтобы не городить велосипеды и костыли, наверное
использование сравнения прячет логику операции. Выход элемента XOR определяется не равенством входов, а нечетностью числа единиц на них. Уже для XOR с тремя входами выражение использующее сравнение читается не лучше чем использующее И-ИЛИ-НЕ.
Таблица соответствия такая?

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

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

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

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

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

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

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

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

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

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

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

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

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

А затестить костылик не забыли случаем? xnor(1,1) возвращает неверный результат.
Вы уверены? К слову, в гите текст этой функции другой, и он больше походит на правду.
Darlington
Не могли бы вы пояснить:
1. O какой виртуальной машине вообще идет речь: собственный простенький CPU, полноценная машина со всей периферией и современным CPU, ...?
2. Каково предназначение виртуальной машины?
Only those users with full accounts are able to leave comments. Log in, please.