Люди смотрят на циклическое гнездо в логических цепях?

11

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

Меня беспокоит две вещи:

  1. Там не было ничего, как формальное доказательство.
  2. Я не видел это нигде.

Кто-нибудь расследовал точные заявления такого рода?

В поисках имени профессора я нашел небольшую веб-страницу и книгу (глава 4), в которой обсуждается эта таксономия.

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

Раду ГРИГОРЕ
источник
Возможно, это лучше всего рассматривать как способ структурирования структуры крупномасштабной цифровой схемы (точно так же, как было бы неплохо использовать подпрограммы в крупномасштабной компьютерной программе), а не как формальную нижнюю границу? (Глава 14 книги, которую вы связали, содержит множество теорем с доказательствами, но они, похоже, предполагают, что вы следуете определенным принципам при разработке схемы?)
Юкка Суомела
1
Юкка может быть прав. Возьмите пример триггера (одноконтурная система) против конечного автомата (двухконтурная система, как обычно реализуется). Разве вы не можете встроить логику комбинационного перехода FSM (которая не имеет петель) непосредственно в петлю триггера? Конечно, одноразрядный FSM не очень интересен. Он может быть только постоянным или чередоваться каждый цикл. Последний, конечно, представляет собой T-триггер с клеммой T, подключенной к 1 проводу. Но та же самая идея работает для банка шлепанцев.
В Вогнсен

Ответы:

5

Вы должны взглянуть на кандидатскую диссертацию (позже опубликованную в виде монографии) Томаса Федера: Стабильные сети и графики продуктов , где он изучил сложность поиска стабильных конфигураций сетей , которые в точности представляют собой схемы с «петлями», как вы упомянули.

Дай Ле
источник