Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
Какова практическая ценность представленного материала? Было бы интересно увидеть какие-то прикладная примеры
На схемы, не зависящие от скорости, в свое время возлагались большие надежды, как на конкурента традиционных синхронных схем. Я не знаю, как обстоит дело сейчас, но мне кажется надежды не оправдались. Я рассматриваю свои упражнения с этой тематикой, как математические упражнения на хорошо известном материале, ну как игры с простыми числами, например.
mocoment я вложил код в ответ на ваш комментарий.
f=True
for i in range (0,8):
if Q[i]==3:
j = i^1
if (Q[j]!=2):
f=False
break
j = i^2
if (Q[j]!=1):
f=False
break
if Q[i]==5:
j = i^1
if (Q[j]!=4):
f=False
break
j = i^4
if (Q[j]!=1):
f=False
break
if Q[i]==6:
j = i^2
if (Q[j]!=4):
f=False
break
j= i^4
if (Q[j]!=2):
f=False
break
if Q[i]==7:
j= i^1
if (Q[j]!=6):
f=False
break
j=i^2
if (Q[j]!=5):
f=False
break
j=i^4
if (Q[j]!=3):
f=False
break
j=i^3
if (Q[j]!=4):
f=False
break
j=i^5
if (Q[j]!=2):
f=False
break
j=i^6
if (Q[j]!=1):
f=False
break
mocoment, я вложил интересующий вас код в этот комментарий:
f=True
for i in range (0,8):
if Q[i]==3:
j = i^1
if (Q[j]!=2):
f=False
break
j = i^2
if (Q[j]!=1):
f=False
break
if Q[i]==5:
j = i^1
if (Q[j]!=4):
f=False
break
j = i^4
if (Q[j]!=1):
f=False
break
if Q[i]==6:
j = i^2
if (Q[j]!=4):
f=False
break
j= i^4
if (Q[j]!=2):
f=False
break
if Q[i]==7:
j= i^1
if (Q[j]!=6):
f=False
break
j=i^2
if (Q[j]!=5):
f=False
break
j=i^4
if (Q[j]!=3):
f=False
break
j=i^3
if (Q[j]!=4):
f=False
break
j=i^5
if (Q[j]!=2):
f=False
break
j=i^6
if (Q[j]!=1):
f=False
break
В статье "On Hazard-Free Implementation of Speed-Independent Circuits" Кондратьев, Кишиневский и Яковлев по поводу дистрибутивных схем пишут следующее. В терминах диаграммы переходов, причинно-следственная связь ИЛИ соответствует понятию детонационного состояния. Т.е. Ваш алгоритм каким-то образом отсекает (или должен отсекать) детонационные состояния.
Предлагаемый алгоритм выявляет состояния, в которых происходит нарушение и дистрибутивности, и полумодулярности схемы, причем используется совокупный признак этих нарушений, который оказывается компактнее из раздельных признаков. Строго говоря, обнаруживается не само состояние-нарушитель, а его предшественник, а отсекается, по вашему меткому выражение не такое состояние, а схема, его содержащая.
Я в этом цикле статей неоднократно говорил, что рассматриваю схемы, заданные на всем множестве 2**n состояний, что никак не влияет на локальное определение последовательности, дистрибутивности и полумодулярности.
Первый алгоритм анализа схем на предмет независимости от скорости
W. D. Frazer and D. E. Muller, “ A method for factoring the action of asynchronous circuits,” AIEE Fall General Meeting, 1960
основан на следующей идее:
Диаграмма переходов является дистрибутивной относительно состояния U, если каждое состояние V, достижимое из U, не является конфликтным и не является детонантным относительно какого-либо из своих элементов.
Состояние V схемы S называется конфликтным, если в V возбуждаются два элемента zj и zi, и zi стабилен в состоянии W, которое отличается от V только одной цифрой, соответствующей элементу zj. Другими словами, для элемента zi происходит переход сигнала типа 1*->1 или 0*->0, в то время как zj изменяет выходной сигнал.
Состояние W называется детонантным относительно элемента zi, если существует пара различных состояний U и V, непосредственно следующих за W (т.е., W->U, W->V), так что zi стабилен в состоянии W и возбуждается в обоих состояниях V и U.
Схема называется живой, если её граф состояний является сильно связным.
Все именно так, я лишь подчеркиваю, что совместная проверка на дистрибутивность и полумодулярность (детонантность и конфликтность состояния в ваших терминах) имеет более компактное условие, чем отдельные проверки этих факторов.
Если взглянуть что изменилось с 1960, а именно, кто ссылается на Фразера-Маллера, мы увидим, что это кооператив "Трасса". А если почитать статью этого кооператива на английском языке, то окажется, что анализ на полумодулярность можно делать гораздо быстрее, чем Вы. А именно, рассматривать только параллельные переключения. Впрочем, на малых размерностях преимущество может быть и не заметно.
Все так, но я не анализирую схемы а считаю их и тут при любой скорости анализа можно сосчитать только до n=3. А признаки отбраковывающие нужные схемы я определил из удобства кодирования схем и их компактности. При этом для полумодулярных и дистрибутивных схем я и рассматриваю только параллельные переключения.
Это ограничение имеет место только для задачи подсчета количества тех или иных схем, т.к. при этом надо хотя бы сосчитать до (2**n)**(2**n). А так-то предложенное кодирование схем позволяет проанализировать любую схему при более широком наборе n. То, что при этом рассматриваются все 2**n состояний схемы не сильно усложняет задачу. Но спасибо, своими комментариями вы подсказали мне нему будущей статьи.
Наберитесь терпения, мой друг, и все узнаете своевременно или даже раньше.
Интересно было бы узнать, но кто вам мешает?
Мешает отсутствие элементной базы чтобы собрать такие счётчики. Там даже при n=3 вылазят монстры. Их декомпозиция означает добавление сигнала. Это, в свою очередь, означает доопределение таблицы истинности определенным Вами образом. Это доопределение делает из добавленного элемента монстра. Замкнутый круг. Во всех смыслах.
Да вы правы, за повышение качества схемы приходится платить ее сложностью. С другой стороны использование чистого базиса, например И-НЕ обеспечивает "критические" состояния, которые, как показано в статье "Последовательные схемы ч.4", делают ненадежным ее функционирование. Да и сами элементы И-НЕ, если посмотреть их транзисторную реализацию выглядят достаточно монструозно и их использование это просто дань традиции.
Здесь как в научной байке: Докладчик только начал выступление, - "Есть целый ряд проблем...", как сразу получил вопрос, - "Какой ряд Вы называете целым"? Что такое ненадёжное функционирование? Вы говорите про последовательные схемы, которые могут быть реализованы без нарушения полумодулярности на 2И(ИЛИ)-НЕ с нагрузочной способностью два. Реализация такого элемента - это четыре транзистора. Монструозность, вернее неприемлимая задержка и увеличенное энергопотребление появляются, если количество входов превышает пять. Для элементов, реализующих (анти)монотонные функции пяти и менее входов (давно) найдены минимальные транзисторные схемы. Однако, вернёмся к счётчикам в коде Грея. Если взять n=3 и гамильтонов цикл, известный как coil-in-the-box, то Ваш метод даст маллеровский пайплайн из трёх С-элементов. Однако, если игнорировать устойчивые состояния 000 и 111 (don't care), то мы получим просто кольцо из трёх инверторов. И кто из них счётчик Грея?
Что такое ненадежное функционирование объясняется в статье, ссылку на которую я привел в предыдущем ответе. Что такое монструозность (в простоте - избыточность) транзисторной реализации И-НЕ поясняется на примере статьи "Распознавание цифровых схем...", которая вам наверняка известна. Никакого моего метода синтеза схем в моей статье нет - я только считаю количество схем. Пайплан здесь вообще не при чем. Более того - как бы вы не доопределяли схемы генераторов (ведь о них идет речь?) в состояниях 000 и 111 - они все равно остаются схемами, подсчитаны предложенными алгоритмами и отнесены к классу, соответствующему их поведению на всем множестве (2**n) состояний.
Да, это оно. В конце статьи "Последовательные схемы ч.4" приведены формулы для маллеровского пайплайна, который в русской традиции называют распределителем импульсов и делают на простых элементах, типа 2И-НЕ. И то как этот пайплайн превращается в кольцо инверторов показано. Но это "правильный" способ. Я говорю про "неправильный", игнорировать 000 и 111, что даёт то же самое кольцо. Отсюда вывод - в этом, частном, случае правильный способ "равен" неправильному. Переформулирую ранее заданный вопрос - можно ли считать кольцо из инверторов распределителем? Вы вообще вычеркнули его из последовательных схем. По поводу названия "критические состояния" - какое-то оно слишком истеричное. Да, возможно, в космосе от Солнца может прилететь поток протонов с высокой энергией, который выведет схему из рабочего цикла в эти состояния, откуда нет выхода. Но самое последнее предложение в "ч.4" гласит фактически, что элементы схемы рисуют без специального входа установки в начальное состояние, но в реальном устройстве такие входы обязательно есть. А значит и состояния совсем не критические.
Кольцо из трех элементов, даже если это классические С элементы с одним инвертором на одном из двух входов перестает быть пайплайном. Вообще говоря пайплайн это не устройство, а принцип его функционирования. Кроме того есть и другие способы доопределения схемы в состояниях 000 и 111, которые делают распределитель последовательным относительно и этих состояний.
Кольцо из трех инверторов не является последовательной схемой (и даже полумодулярной) относительно состояний 000 и 111. Можно их, конечно, игнорировать, но я уже много раз говорил, что подсчитываю схемы последовательные, дистрибутивные и полумодулярные относительно всех 2**n состояний.
Ну и последнее - с учетом входов установки схема перестает быть такой уж компактной. Тем более, что я-то изучаю схемы без внешних входов.
Не надо требовать от математической модели всеядности. Она (модель) на это не претендует. А если принять эти не раз оговоренные ограничения модели, то и спорить не о чем.
Имеется в виду чтобы в рабочих состояниях схема вела себя как исходная. Да, всегда. Один способ сделать критические состояния тупиковыми мы обсуждали, другой - задать им переход в соседнее рабочее состояние или определить цепочку таких переходов. Одним транзистором тут, конечно, уже не обойтись
По первому способу - точно не всегда, поскольку устойчивые состояния - это не don't care. Более того, этот способ не выводит схему из тупика. Мой вопрос был по второму способу - всегда ли переход в соседнее состояние или по цепочке эквивалентен don't care? Наверняка не всегда и даже не известно "лучше" он или "хуже" первого. В том смысле, что даёт большее количество эквивалентов после минимизации.
Вообще говоря минимизация эквивалентное преобразование, т.е. не должна влиять на поведение схемы, т.ч. ваше умозаключение лишено логики. А кроме того, я не могу обсуждать то, что выходит за рамки сделанных в статье предположений, а именно схемы подсчитываются схемы принадлежащие тому или иному классу для всех состояний. Т.о. схемы полностью определены и никаких don't care не имеют. Вопросы синтеза схем не рассматриваются.
Хорошо, выходит за рамки, но "критические" состояния есть не только в последовательных схемах, но также в дистрибутивных и в полумодулярных. Такие схемы с критическими состояниями можно было посчитать и дать несколько примеров в развернутом виде. Я не утвеждал, что минимизация влияет на поведение схемы, я утвеждал, что результат минимизации может быть одинаков для схемы, которая выходит из критических состояний и для схемы, где эти состояния игнорируются. Это можно было бы проверить на примерах. Но Вы не хотите их приводить.
Спасибо! Я обязательно учту ваши замечания при написании следующей статьи, если таковое случится.
Ещё раз попробую угадать название следующей статьи - уж не параллельно-последовательные схемы ли это? Книга 1986 на стр. 258 гласит: В параллельно-последовательных схемах каждая переменная возбуждается только после того, как в результате изменения своих значений станут устойчивыми все ранее возбужденные переменные. Класс параллельно-последовательных схем является подклассом дистрибутивных и образует расширение класса последовательных схем.
Не угадали. Да и будет ли статья я еще не знаю.
Спасибо, что напомнили.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Дистрибутивные схемы, ч.1