Comments 14
К сожалению при публикации этой статьи я допустил в тексте и в программе на листинге 1 ошибку - в главном цикле область изменения переменной I указана до 255, тогда как следует до 256. Соответственно полученное число ПМС из двух элементов должно быть равным 98.
Приношу извинения немногочисленным читателям, если таковые будут.
Статья исправлена.
Таки, а что мешало опубликовать код как блок кода, а не как картинку? Аналогичный вопрос с формулами.
Ну, и финальный код кажется можно упростить до проверки наборов
if (Q[j]==0) or (Q[j]==1) or (Q[j]==4) or (Q[j]==5):превращается в
if Q[j] in (0,1,4,5):а там и вовсе блоки превращаются во что-то такое
f = (Q[i^1] not in (0,1,4,5)) and (Q[i^2] not in (0,2,4,6))
# ну или как два выражения
f = (Q[i^1] not in (0,1,4,5))
f = f and (Q[i^2] not in (0,2,4,6))Спасибо. Наверное вы правы, но я не специалист по программированию вообще и по Питону в частности. Поэтому пишу программы только для утилитарных целей - не до красоты и лаконичности. Для меня интерес представляют схемы из логических элементов и их статистические свойства.
Кажется после питона немного почитать мануал по использованию разметки хабра не должно быть каким-то рокет сайенс.
Поэтому пишу программы только для утилитарных целей
ну, так через пол года откроете свой же код и ахнете над понаписанным. чуть-чуть идиоматичней переписать и самому станет удобнее использовать и расширять свои же утилиты. Ну, или ИИ попросите переписать, с питоном должны справиться.
А вообще в статье не хватает вводных о предмете. Ни что за полумодулярные системы, ни с чего вообще возникла задача чего-то там посчитать, про какую скорость вообще речь от которой никто не зависит.
Про программирование вы совершенно правы, что касается предмета исследований, то термины типа схемы не зависящие от скорости, полумодулярные или последовательные хорошо известны специалистам в области асинхронной схемотехники именно на которых и рассчитана эта статья, причем первая, попавшая на Хабр, так-то дальше песочницы меня и не пропускали. Для них, этих специалистов, это букварь и толковать эти термины лишний раз я посчитал излишним. А вот подсчетом таких схем никто не занимался, вот я и заинтересовался этой темой.
Математика довольно универсальна в этом плане и есть некоторый шанс, что ваши расчёты вполне могут всплыть не только в схемотехнике, но где-нибудь ещё, а то и вовсе кто-нибудь уже пробовал посчитать что-то похожее. Но когда обрезаются вводные и делается жёсткая привязка к некой узкой области, то рассмотреть подобные связи несколько проблемно.
К сожалению автор является (точнее являлся) специалистом именно в узкой области, где занимались созданием полумодулярных схем, обладающих некоторыми преимуществами перед синхронными и вопрос об их подсчете никогда не стоял. Оценка же их количества показала, что эта задача имеет слишком высокую вычислительную сложность, а результаты для малых количеств элементов можно оценивать просто как подарок.
Во-первых, основные понятия были введены не в 1961, а на шесть лет раньше:
D. E. Muller, Theory of asynchronous circuits. Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955.
Во-вторых, замкнутые схемы, вернее схемы, которые можно замкнуть, - это довольно ограниченное подмножество всех полумодулярных схем. Почему? Потому что внешняя среда зачастую не может быть реализована схемой из-за неразрешимых конфликтов полной кодировки (CSC conflicts).
В-третьих, приведённый алгоритм подсчитывает заведомо избыточные схемы. Почему? Потому что на практике схемы, как правило, определены на маленьком подмножестве всех 2^n состояний. Пусть, в качестве примера, это будет ровно половина от 2^n. В оставшуюся половину состояний схема просто не заходит. Эта, "пустая" половина в Вашем алгоритме "обрабатывается" с помощью устойчивых состояний. Другими словами, если следующее состояние равно предыдущему, то мы имеем соответствующее значение функций в таблице истинности. Т.е. булевы функции, подлежащие минимизации доопределяются строго определённым образом. Можно и нужно доопределять их произвольным образом с помощью don't care. Минимизация таблицы истинности с большим количеством don't care зачастую даёт гораздо более компактный результат. Другое дело, что в случае don't care возникает вопрос правильных начальных условий. Таких, при которых схема является полумодулярной.
На счет истории предмета комментатор очевидно прав. На счет ограниченности модели - замечание, скорее всего, неактуально в силу вычислительной сложности даже при введенных ограничениях. Десять элементов в схемотехнике ерунда, а различных даже замкнутых схем 2**10240. Вопрос оптимальности схем здесь, как впрочем и у Мюллера, вообще не рассматривается, т.к. он определяется выбранным элементным базисом.
На всякий случай нужно сказать, что в работе
Ю. В. Мамруков. Анализ апериодических схем и асинхронных процессов. Диссертация к.т.н. ЛЭТИ, 1984.
1. Предложены формулы для определения множеств конфликтных состояний и решения задач обратной и прямой достижимости. На основе этих формул разработаны методы полного анализа и анализа рабочего множества, ориентированные на формульное представление множеств состояний.
2. Предложены алгоритмы полного анализа и анализа рабочего множества, ориентированные на табличное представление множеств состояний, отличающиеся высокой скоростью.
3. Введено понятие редукции схемы по самонезависимой переменной и исследованы ее свойства. Предложен метод сокращения трудоемкости анализа за счет снижения их размерности, основанный на использовании редукции.
Более того на основе этого под руководством В.И. Варшавского была разработана система автоматического анализа схемы на полумодулярность успешно проработавшая много лет. Но никто и никогда не применял эту систему для подсчета таких схем, вероятно и в силу ее неэффективности. Одно дело за несколько секунд проверить одну схему, и совсем иное - несколько миллионов. Даже те упрощенные алгоритмы, что предложены авторы позволяют решить эту проблему только для n<4.
А всё потому, что автор настаивает на своей постановке задачи. А ведь есть возможность увеличить n до семи. Для этого нужно поступить по-математически, а именно использовать известные результаты. В частности, рассмотреть только живые схемы. Точнее, диаграммы переходов, а ещё точнее - все специальные поддиаграммы переходов в том, что Вы называете "схема номер такой-то". Что такое специальные поддиаграммы? Это сильно связные графы. В данном случае на гиперкубе. Существуют алгоритмы их построения (до n=7), которые значительно проще, чем полный перебор астрономического количества вариантов. Возможно, даже есть библиотека таких графов. В подтвеждение сказанного см.:
T.-A. Chu. Synthesis of self-timed VLSI circuits from graph-theoretic specifications. PhD thesis, MIT, 1987.
Определение 5.1. Граф состояний является «живым», если он является сильно связным, каждый переход разрешен в некотором состоянии и имеет согласованное назначение состояний. Это означает, что каждое состояние, достижимое из начального состояния системы, является воспроизводимым, т.е. множество состояний образует эквивалентный класс, в котором любые два состояния взаимно достижимы. Это понятие «живости» подразумевает, что каждый переход в цепи может быть разрешен бесконечно часто, поскольку он разрешен по крайней мере в одном состоянии, которое может быть достигнуто из любого другого состояния схемы.
A. V. Yakovlev, "Synthesis of Hazard-free Asynchronous Circuits from Generalized Signal-Transition Graphs." Technical Report №377, 1992.
На стр. 4 - схема является живой, если её диаграмма состояний является сильно связным графом.
P. A. Beerel and T. H. Y. Meng, “Semi-modularity and testability of speed-independent circuits,” Integration, vol. 13, no. 3, pp. 301-322, 1992.
Определение 2.3. Граф состояний является «живым», если лежащий в его основе ориентированный граф является сильно связным, и каждый переход каждого сигнала разрешен в некотором допустимом состоянии.
(Замкнутая) схема называется сильно связной, если ориентированный граф, полученный путем преобразования каждого элемента в вершину, а каждого провода в дугу, является сильно связным.
Определение 3.1. Множество состояний K называется классом эквивалентности, если состояния в K образуют сильно связный подграф графа состояний. Класс эквивалентности K является ложным, если существует какой-либо переход сигнала, который всегда разрешен в K.
Я не настаиваю - я поставил - я решил. Ни кому не возбраняется ставить другие задачи и решать, если сумеет.
Полумодулярные схемы