Компиляция логической схемы, с чего начать?

Question

[keldish]

Написал редактор функциональных блоков. Блоки только И, ИЛИ, НЕ, исключающее ИЛИ. Эту часть доделал, мне нравится, теперь нужно запустить эмуляцию. С чего начать, где и что почитать? Может кто объяснит в двух словах?
Мысли такие - по умолчанию на входах всех блоков "0", сами блоки выставляют выхода в зависимости от своего назначения. следуя с верху вниз и слева на право, исходя из выставленных пользователем связей меняем входа и соответственно выхода блоков пока не добираемся до выхода со схемы. Вот тут вопросы полезли. Расположение блоков в редакторе произвольно и значит возможны ошибки. Также возможны обратные связи (пока думаю записывать значение и подставлять в следующей итерации). Вот тут мысль останавливается.

Answer 1

[hint000]

записывать значение и подставлять в следующей итерации

Хорошая, годная мысль.

Расположение блоков в редакторе произвольно и значит возможны ошибки

Логика работы, конечно, не должна зависеть от расположения блоков на экране. Блоки вызывают друг друга рекурсивно, чтобы определить состояния своих входов. Каждый блок должен помнить состояния своих входов и выходов для текущего момента времени и, возможно, для предыдущего момента. Отдельно каждый блок имеет флаг, показывающий, было ли уже вычислено состояние выхода на текущий момент. Флаг гарантирует конечность рекурсивных вызовов, т.к. если выход уже вычислен, то сразу возвращаемся из рекурсии.
(Делал очень-очень давно подобную штуку, только не для логических элементов, а для аналоговых СВЧ-блоков, сам удивляюсь, что ещё что-то помню о том проекте).

Comments

[keldish]

ВХОД1 ---
................AND -----
ВХОД2 ---
..............................OR ---- ВЫХОД1
ВХОД3 ---NOT -----

1. ВЫХОД1 вызывает блок OR
..1.1. Блок ОR вызывает блок AND
....1.1.1 Блок AND вызывает ВХОД1
....1.1.2 Блок AND вызывает ВХОД2
....1.1.2 Блок AND возвращает True или False
..1.2. Блок OR вызывает блок NOT
....1.2.1 Блок NOT вызывает ВХОД3
....1.2.2 Блок NOT возвращает True или False
..1.3. Блок OR возвращает True или False
2. ВЫХОД1 возвращает True или False

многое прояснилось, спасибо
вопрос с обратными связями пока не ясен (как их определить)

[hint000]

keldish,

вроде как решение но сколько мы будем гулять кругами не известно

Один общий цикл по всем блокам (в любом порядке). Начали вычислять N-ый блок, он вызвал всех, кто висит у него на входах, получил от них результат, вычислил свой результат. Перешли к следующему блоку в цикле. При этом часто в цикле будем натыкаться на блок, который уже вычислен (флаг поднят) (потому что его раньше вызывал другой блок), в этом случае пропускаем блок, чтобы не вычислять повторно. Если повторных вычислений не делаем, то кругами не ходим. Каждый блок на каждом шаге вычисляется ровно один раз, не больше и не меньше, значит никаких кругов. Не меньше одно раза, потому что в цикле перебираем все блоки. А не больше, потому что при уже поднятом флаге вычисления пропускаем.
Благодаря такой схеме обратные связи разрешаются сами собой, не требуется как-то проверять их наличие.

Существенное усложнение алгоритма потребуется, если нужно учитывать конечное быстродействие блоков (заданное, возможно даже различное у всех блоков), может быть актуально, если работа всей схемы не синхронизируется тактовым генератором.

[keldish]

мне понравился вариант который описан в комментарии выше
но двигаясь от конца к началу, мы рано или поздно дойдем до блока
вход которого зависит от выхода блока который (еще не обсчитанный) и вызвал его обсчет.

там ниже я еще ответил посмотрите пожалуйста

[hint000]

keldish, да... вот теперь я чуть лучше вспоминаю свой проект :) У меня там изначально по условиям задачи в цепи обратной связи был блок, задерживающий сигнал. Т.е. у такого блока выход был равен входу N шагов назад. Это исключало проблему. Если вы сделаете так, что выход считается для следующего такта после определения состояния входов. Или, что то же самое, для вычисления выхода на данном такте нужно знать состояния входов на предыдущем такте. Ну а в начальный момент везде нули (не только на входах, но и на выходах тоже, даже на выходе НЕ) - это знаем без вычислений.

[keldish]

да я об этом и говорю.
задержка на ОДИН шаг назад

[hint000]

keldish, такую задержку нужно делать у каждого элемента, тогда не придётся искусственно определять обратную связь. Если все элементы работают с задержкой (хотя бы на один шаг), то проблемы нет.

[keldish]

нет не думаю что это правильное направление

Answer 2

[Александр Скуснов]

Если бы не было обратных связей, то можно просто написать декларации в любом порядке (функциональный язык Hasell):

f1 = x1 && x2

f2 = x1 || x2

f3 = f1 xor f2

f4 = not f3

Для обратных связей можно взять пример языка CFC Codesys программируемых контроллеров. Каждый блок нумеруется и вычисляется один раз за скан программы. А уж как реализовать порядок - это вам решать.

Comments

[keldish]

вот о порядке обработки и вопрос
можно проходить по кругу все блоки и если известны все входные сигналы обрабатывать выход и ставить пометку на блоке как "обработанный" в этой итерации
замыкаем круг пока все имеющиеся блоки не будут обозначены как "обработанные"
переходим к следующей итерации

вроде как решение но сколько мы будем гулять кругами не известно

Answer 3

[xmoonlight]

Сначала нужно построить общую формулу по граф.схеме.
Затем, разложить на независимые группы и построить таблицу состояний: сверху - время, слева - элементы.
Так сможете понять: что считаем параллельно, а что - последовательно.

Обратную связь без тактового генератора - нереально сделать.
Вот пример простейшей схемы.

Контроль завершения эмуляции при рекурсивных передачах состояний от блока к блоку без тактового генератора, можно сделать с помощью валидации первого выходного сигнала на всех выходах всей схемы. Как только все выходы (выходы всей схемы, а не выходы отдельных элементов!) получили значение - останавливаем процесс.

Вот тут основные элементы и законы и тождества алгебры логики.
Можно добавить недостающие элементы и посмотреть: каков порядок действий при вычислении и как делается упрощение логических формул.

Comments

[keldish]

провода присутствуют
синхросигналом можно считать итерации обсчета
в крайнем случае можно добавить блок генератора с задаваемой частотой
но вопрос вообще не об этом

[xmoonlight]

keldish, вопрос - в логике составления полной формулы и построения таблицы истинности?
Или в чём-то другом?

[keldish]

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

[xmoonlight]

keldish, сначала нужно построить общую формулу по граф.схеме.
Затем, разложить на независимые группы и построить таблицу состояний: сверху - время, слева - элементы.
Так сможете понять: что считаем параллельно, а что - последовательно.

Обратную связь без тактового генератора - нереально сделать.
Вот пример простейшей схемы (с серией 155ЛА3 - лично работал!).

Контроль завершения эмуляции при рекурсивных передачах состояний от блока к блоку без тактового генератора, можно сделать с помощью валидации первого выходного сигнала на всех выходах всей схемы. Как только все выходы получили значение - останавливаем процесс.

[xmoonlight]

keldish, Вот тут основные элементы и законы и тождества алгебры логики.
Можно добавить недостающие элементы и посмотреть: каков порядок действий при вычислении и как делается упрощение логических формул.

[keldish]

я к сожалению Вас не понимаю
у меня есть "нарисованная схема"


я знаю все блоки на схеме (они пронумерованы) и их функции
я знаю все связи (начало - номер блока, конец - номер блока и номер выхода)

на первом шаге (пока каким-то не ведомым способом определяем обратную связь) и значение ee подставляем равное False

по алгоритму описанному в комментарии к первому ответу расчитываем значение ВЫХОДА
запоминаем выход с блока используемый в обратной связи

на втором и всех последующих шагах считаем по тому-же алгоритму подставляя в значение обратной связи запомненную на предыдущем шаге величину.

повторяем шаг второй до остановки эмуляции

тем самым реализуется "тактовый генератор"

да на визуализации мы возможно не увидим предыдущие шаги из-за скорости обработки (можем ввести пошаговую отладку)

думаю что так можно будет создавать и триггеры

все ПОКА складывается у МЕНЯ, кроме определения обратной связи

[xmoonlight]

keldish, формулу логическую для рисунка напишите - мне просто интересно как Вы это сделаете.

[keldish]

шаг первый
(вх1 * вх2)+0=ВЫХОД

все последующие шаги
(вх1 * вх2)+ВЫХОД_предыдущего_шага=ВЫХОД

[hint000]

keldish, ксати, хороший пример схемы. Подадим ноль на хотя бы на один вход и посмотрим. Если реализовывать упрощённое моделирование, то выход будет переключать состояние на каждом шаге. Независимо от того, какому промежутку времени равен этот шаг. То есть получим меандр, но его частота неопределена. На реальном железе частота будет определяться быстродействием (задержкой переключения) логических элементов. В зависимости от целей всего этого моделирования (нужен ли высокий уровень реалистичности процессов или это лишь "учебный макет"), так вот, в зависимости от этого можно или оставить как есть, или придётся усложнять алгоритм.

[keldish]

примерно также как Вы опишете RS триггер на двух ИЛИ-НЕ

[keldish]

весь проект задуман как ПОТРЕНИРОВАТЬСЯ, только для своего утешения
реальной оценки быстродействия не нужно (будем называть его учебным)

ОСТАЛСЯ таки вопрос как определить обратную связь
возможно графами еще на этапе создания "рисунка" можно даже подсветить ее другим цветом
как предупреждение

[xmoonlight]

keldish, Поправка: ВЫХОД_предыдущего_шага => NOT ВЫХОД_предыдущего_шага
Полностью согласен с hint000
Могу предложить вариант: один такт - один пройденный логический элемент.

[keldish]

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

[xmoonlight]

keldish, я про сигналы на выходах каждого логического блока говорю.
Это как раз и будут шаги.
Верно?

[keldish]

новый рисунок


задача свелась к определению цикла в графе
можем при окончании "рисования" новой связи, начинать проходить в глубину по всем блокам и если приходим на себя считать проведенную линию обратной связью. (на рисунке линия b .

опять грабли если мы сначала проведем линию b, а затем линию a. то данный подход определит за обратную связь линию a, что не верно.

[keldish]

xmoonlight, нет, не думаю

[xmoonlight]

keldish, Выдавливанием сигнала. Из выхода на вход.
Нет входа - выход (провод) хранит состояние.
Пришёл сигнал на вход - заменили значение на входе пришедшим, посчитали, заменили на выходе.

Нужно от каждого входа сделать как-бы "бегунок" и его же множить на "перекрёстках" провода.
А направление путей - всегда от выхода ко входу.

[keldish]

xmoonlight, правильно определив линию обратной связи
реализовать задержку сигнала на один цикл будет не сложно.

[xmoonlight]

keldish, не нужно её (обратную связь) определять вообще.
Почитайте коммент выше - я добавил.

[keldish]

давайте уже не будем скакать, пишите здесь

[xmoonlight]

keldish,
Алгоритм: "выдавливание".
Термин: провод(ник) - это все входы и выходы элементов этого провода.
Кто хранит состояния схемы: входы и выходы.
Кто хранит промежуточные состояния от шага к шагу (наш "бегунок"): провод.
Направление движения "бегунка" - всегда вперёд.

Поэтому и не нужно определять/искать тип связи: прямая она или обратная.

[keldish]

не понял

[xmoonlight]

keldish, ок.
можно ту же схему с обозначениями всех проводов по номерам слева направо?
и я - напишу алгоритм по ней.

[keldish]

[xmoonlight]

keldish, (замечу, что 4=a и 5=6=b)

По-шагам:
1. 1-2 (сразу два "бегунка")
2. 3-4 ("бегунок" только на 3-ке, 4-ка: не определена)
3. 5 (и "бегунок" на выходе)
4. 3-4 ("бегунок" только на 4-ке, 3-ка хранит состояние)
5. 5 (и "бегунок" на выходе)
.....

[keldish]

как мы определяем что 4 шаг на 3-4

[xmoonlight]

keldish, вектор направления прохождения сигнала.