Рассматриваются все возможные схемы поведение которых можно задать системой логических уравнений, как в известной комментатору Алгебре асинхронных логических схем.
Тупиковые схемы не определяются, определяются тупиковые состояния, т.е. такие, в которых выходы всех элементов устойчивы. Например, генератор из трех, соединенных в кольцо, инверторов можно доопределить так, что состояния 000 и 111 будут устойчивы и схема станет последовательной для всех состояний, хотя, конечно, и усложнится.
Во-первых не правильно противопоставляться полумодулярные и живые схемы. Схема имеющая устойчивые (тупиковые состояния) может быть вполне полумодулярной, например x=x; y=y. Во-вторых поиск изоморфных был осуществлен, как среди всех схем, так и среди таких классов, как полумодулярные и последовательные, что видно из результирующих таблиц (1 и 2). В-третьих понятие нечувствительности к задержке в проводе относится только к полумодулярным схемам и означает, что такая задержка не выводит схему из этого класса. Более того, еще Маллер показал, что все полумодулярные схемы не чувствительны к задержке в проводе исходящем из выхода элемента до первого разветвления - именно этот фокус и проделал комментатор. Скажем, в синхронной схеме он бы не прошел.
И, строго говоря, схема с добавленной задержкой не эквивалентна исходной, т.к. имеет в двое больше состояний и может быть для получения этих дополнительных состояний задержку-то и добавили.
На счет истории предмета комментатор очевидно прав. На счет ограниченности модели - замечание, скорее всего, неактуально в силу вычислительной сложности даже при введенных ограничениях. Десять элементов в схемотехнике ерунда, а различных даже замкнутых схем 2**10240. Вопрос оптимальности схем здесь, как впрочем и у Мюллера, вообще не рассматривается, т.к. он определяется выбранным элементным базисом.
К сожалению автор является (точнее являлся) специалистом именно в узкой области, где занимались созданием полумодулярных схем, обладающих некоторыми преимуществами перед синхронными и вопрос об их подсчете никогда не стоял. Оценка же их количества показала, что эта задача имеет слишком высокую вычислительную сложность, а результаты для малых количеств элементов можно оценивать просто как подарок.
Про программирование вы совершенно правы, что касается предмета исследований, то термины типа схемы не зависящие от скорости, полумодулярные или последовательные хорошо известны специалистам в области асинхронной схемотехники именно на которых и рассчитана эта статья, причем первая, попавшая на Хабр, так-то дальше песочницы меня и не пропускали. Для них, этих специалистов, это букварь и толковать эти термины лишний раз я посчитал излишним. А вот подсчетом таких схем никто не занимался, вот я и заинтересовался этой темой.
Спасибо. Наверное вы правы, но я не специалист по программированию вообще и по Питону в частности. Поэтому пишу программы только для утилитарных целей - не до красоты и лаконичности. Для меня интерес представляют схемы из логических элементов и их статистические свойства.
К сожалению при публикации этой статьи я допустил в тексте и в программе на листинге 1 ошибку - в главном цикле область изменения переменной I указана до 255, тогда как следует до 256. Соответственно полученное число ПМС из двух элементов должно быть равным 98.
Приношу извинения немногочисленным читателям, если таковые будут.
Рассматриваются все возможные схемы поведение которых можно задать системой логических уравнений, как в известной комментатору Алгебре асинхронных логических схем.
Тупиковые схемы не определяются, определяются тупиковые состояния, т.е. такие, в которых выходы всех элементов устойчивы. Например, генератор из трех, соединенных в кольцо, инверторов можно доопределить так, что состояния 000 и 111 будут устойчивы и схема станет последовательной для всех состояний, хотя, конечно, и усложнится.
Во-первых не правильно противопоставляться полумодулярные и живые схемы. Схема имеющая устойчивые (тупиковые состояния) может быть вполне полумодулярной, например x=x; y=y.
Во-вторых поиск изоморфных был осуществлен, как среди всех схем, так и среди таких классов, как полумодулярные и последовательные, что видно из результирующих таблиц (1 и 2).
В-третьих понятие нечувствительности к задержке в проводе относится только к полумодулярным схемам и означает, что такая задержка не выводит схему из этого класса.
Более того, еще Маллер показал, что все полумодулярные схемы не чувствительны к задержке в проводе исходящем из выхода элемента до первого разветвления - именно этот фокус и проделал комментатор. Скажем, в синхронной схеме он бы не прошел.
И, строго говоря, схема с добавленной задержкой не эквивалентна исходной, т.к. имеет в двое больше состояний и может быть для получения этих дополнительных состояний задержку-то и добавили.
На счет истории предмета комментатор очевидно прав. На счет ограниченности модели - замечание, скорее всего, неактуально в силу вычислительной сложности даже при введенных ограничениях. Десять элементов в схемотехнике ерунда, а различных даже замкнутых схем 2**10240. Вопрос оптимальности схем здесь, как впрочем и у Мюллера, вообще не рассматривается, т.к. он определяется выбранным элементным базисом.
К сожалению автор является (точнее являлся) специалистом именно в узкой области, где занимались созданием полумодулярных схем, обладающих некоторыми преимуществами перед синхронными и вопрос об их подсчете никогда не стоял. Оценка же их количества показала, что эта задача имеет слишком высокую вычислительную сложность, а результаты для малых количеств элементов можно оценивать просто как подарок.
Про программирование вы совершенно правы, что касается предмета исследований, то термины типа схемы не зависящие от скорости, полумодулярные или последовательные хорошо известны специалистам в области асинхронной схемотехники именно на которых и рассчитана эта статья, причем первая, попавшая на Хабр, так-то дальше песочницы меня и не пропускали. Для них, этих специалистов, это букварь и толковать эти термины лишний раз я посчитал излишним. А вот подсчетом таких схем никто не занимался, вот я и заинтересовался этой темой.
Спасибо. Наверное вы правы, но я не специалист по программированию вообще и по Питону в частности. Поэтому пишу программы только для утилитарных целей - не до красоты и лаконичности. Для меня интерес представляют схемы из логических элементов и их статистические свойства.
Статья исправлена.
К сожалению при публикации этой статьи я допустил в тексте и в программе на листинге 1 ошибку - в главном цикле область изменения переменной I указана до 255, тогда как следует до 256. Соответственно полученное число ПМС из двух элементов должно быть равным 98.
Приношу извинения немногочисленным читателям, если таковые будут.