Возращаясь к напечатанному. В Workcraft можно построить и верифицировать диаграмму переходов Мамрукова, где два пучка стрелок. Соответствующая модель называется FSM. Интересно то, что обратимая FSM означает, что начальная разметка достижима из любой достижимой разметки.
Очевидно, что представленная здесь теория не позволяет задать вот такую, аналоговую, а значит практическую схему
Рис. 5
Она взята из статьи Behzad Razavi, A Fifty Applications of the CMOS Inverter—Part 2
Он пишет: Схема на рис. 5(а) предпочитает защелкиваться и устанавливаться в «вырожденные» условия A=B=0 и X=Y=Vdd (или наоборот). Однако, мы знаем, что перекрестно связанные инверторы помогают избегать вырожденных условий, это показано на рис. 5(b).
По сути, два инвертора в кольце образуют ячейку памяти. Однако, будучи частью внешнего контура, эта ячейка постоянно переключается. Получается "кто кого перетянет".
Диаграмму Мамрукова натянуть на куб нельзя уже только потому, что переходы из вершины 000 в вершину 111 для последовательных схем запрещены. Кроме того, у Мамрукова из вершин 000 и 111 выходит пять стрелочек, у Вас - три. Тем не менее, диаграмма Мамрукова полумодулярна (я надеюсь). Признаю, я не обратил внимания, что все стрелочки направлены из нерабочего цикла в рабочий. Т.е. переключения между циклами быть не может, я ошибся. Хотя, никто не проверял можно ли обратить обратить одну или несколько из этих пяти стрелочек так, чтобы схема осталась прежней.
Что же касается симуляций, я, конечно, задавал начальные условия 000 и 111 - схема сразу же сваливается в рабочий цикл. Вашу фразу "не параметры на начало среза, а актуальные..." я не понимаю. Симуляция такого генератора - это так или иначе симуляция перезарядки конденсаторов. В отличии от практики, индуктивности нет. На каждом шаге симуляции, в его начале напряжения на конденсаторах актуальные. Идеальную линию задержки, без затухания, без индуктивности, без емкости и без сопротивления я также устанавливал. Не помогает.
Интересно было бы всё-таки перевести осциллятор из рабочего цикла в нерабочий. Сколько я не пытался сделать это в SPICE-симуляторе, мне это не удалось. И стр. 43 в диссертации Мамрукова отвечает на вопрос "почему не удалось?" Потому что попадание в нерабочий цикл 000-111 никак не мешает выходу из него. Более того, такое попадание непредсказуемо - один раз за тысячу периодов или за миллион - иди лови.
Ю. В. Мамруков. Анализ апериодических схем и асинхронных процессов. Диссертация к.т.н. ЛЭТИ, 1984.
На уровне философии Ваш подход страдает тем же недостатком, что и асимпотические оценки в дискретной математике, только наоборот. В том смысле, что математики любят устремить n к бесконечности и показать, что в таком то базисе (например 2И-НЕ плюс 2ИЛИ-НЕ) такая-то схема (например n-разрядный сумматор) имеет такую-то сложность, которая меньше предыдущей. Инженера интересует n в диапазоне от 4 до 1024. Вы фактически устремили n не к бесконечности, а к нулю и получили такой же бесполезный результат. Именно эта задача была поставлена и поэтому признаю - она решена. Композицию в статье "Последовательные схемы" я не видел, поэтому повторю вопрос - можно ли взять несколько последовательных схем одной размерности, выполнить их композицию и получить дистрибутивную схему той же размерности?
Пересчёт подразумевает, что на вход анализатора поступают схемы от первой до последней (с астрономическим номером при n>3). Насколько я понял, поступают они последовательно. Здесь напрашивается конвейер. Возможно, JIT-компилятор Numba и сделает подобие конвейера, но это будет жалкое подобие. Нужно изначально писать под конвейер. Но это требует досконального знания архитектуры процессора. А в случае, если будет принято правильное решение, - то архитектуры GPU. Можно, конечно, написать на Verilog, но для этого нужно иметь отладочную плату с мощной FPGA. Насколько мне известно, бесплатного online доступа к таким платам нет, в отличии от GPU.
Что же касается композиции и декомпозиции, то в качестве легкого утреннего упражнения можно взять n=2 и синтезировать из последовательных схем дистрибутивные или наоборот разложить каждую дистрибутивную на последовательные. Благо, инструмент для этого у Вас (да и у всего прогрессивного человечества) уже есть, называется "Алгебра асинхронных схем". Она изложена в той Книге 1986, на которую Вы ссылаесь.
Тогда напрашивается не сужение класса схем (от полумодулярных к дистрибутивным, а затем к последовательным), а наобот - композиция последовательных в дистрибутивные и их обоих в полумодулярные. Для заданного n на первом этапе и с повышением n на втором.
Вы привели пример неоживляемых схем, поэтому уточню вопрос. Может ли неудачный выбор начальных состояний перевести схему из класса полумодулярных в класс дистрибутивных?
Ни в одной статье цикла ничего не сказано про начальные условия, это специально? Или для схем, заданных на всех 2^n состояниях, начальные условия могут быть произвольными?
А всё потому, что автор настаивает на своей постановке задачи. А ведь есть возможность увеличить 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.
Ю. В. Мамруков. Анализ апериодических схем и асинхронных процессов. Диссертация к.т.н. ЛЭТИ, 1984.
1. Предложены формулы для определения множеств конфликтных состояний и решения задач обратной и прямой достижимости. На основе этих формул разработаны методы полного анализа и анализа рабочего множества, ориентированные на формульное представление множеств состояний.
2. Предложены алгоритмы полного анализа и анализа рабочего множества, ориентированные на табличное представление множеств состояний, отличающиеся высокой скоростью.
3. Введено понятие редукции схемы по самонезависимой переменной и исследованы ее свойства. Предложен метод сокращения трудоемкости анализа за счет снижения их размерности, основанный на использовании редукции.
Ещё раз попробую угадать название следующей статьи - уж не параллельно-последовательные схемы ли это? Книга 1986 на стр. 258 гласит: В параллельно-последовательных схемах каждая переменная возбуждается только после того, как в результате изменения своих значений станут устойчивыми все ранее возбужденные переменные. Класс параллельно-последовательных схем является подклассом дистрибутивных и образует расширение класса последовательных схем.
Хорошо, выходит за рамки, но "критические" состояния есть не только в последовательных схемах, но также в дистрибутивных и в полумодулярных. Такие схемы с критическими состояниями можно было посчитать и дать несколько примеров в развернутом виде. Я не утвеждал, что минимизация влияет на поведение схемы, я утвеждал, что результат минимизации может быть одинаков для схемы, которая выходит из критических состояний и для схемы, где эти состояния игнорируются. Это можно было бы проверить на примерах. Но Вы не хотите их приводить.
По первому способу - точно не всегда, поскольку устойчивые состояния - это не don't care. Более того, этот способ не выводит схему из тупика. Мой вопрос был по второму способу - всегда ли переход в соседнее состояние или по цепочке эквивалентен don't care? Наверняка не всегда и даже не известно "лучше" он или "хуже" первого. В том смысле, что даёт большее количество эквивалентов после минимизации.
Тогда вопрос - всегда ли можно выйти из критических состояний так что чтобы результирующая схема была такой же, как в случае игнорирования оных? А в начальной установке ничего сложного нет. Её обычно делают одним транзистором, перетягивая выход либо вверх, либо вниз.
Да, это оно. В конце статьи "Последовательные схемы ч.4" приведены формулы для маллеровского пайплайна, который в русской традиции называют распределителем импульсов и делают на простых элементах, типа 2И-НЕ. И то как этот пайплайн превращается в кольцо инверторов показано. Но это "правильный" способ. Я говорю про "неправильный", игнорировать 000 и 111, что даёт то же самое кольцо. Отсюда вывод - в этом, частном, случае правильный способ "равен" неправильному. Переформулирую ранее заданный вопрос - можно ли считать кольцо из инверторов распределителем? Вы вообще вычеркнули его из последовательных схем. По поводу названия "критические состояния" - какое-то оно слишком истеричное. Да, возможно, в космосе от Солнца может прилететь поток протонов с высокой энергией, который выведет схему из рабочего цикла в эти состояния, откуда нет выхода. Но самое последнее предложение в "ч.4" гласит фактически, что элементы схемы рисуют без специального входа установки в начальное состояние, но в реальном устройстве такие входы обязательно есть. А значит и состояния совсем не критические.
Здесь как в научной байке: Докладчик только начал выступление, - "Есть целый ряд проблем...", как сразу получил вопрос, - "Какой ряд Вы называете целым"? Что такое ненадёжное функционирование? Вы говорите про последовательные схемы, которые могут быть реализованы без нарушения полумодулярности на 2И(ИЛИ)-НЕ с нагрузочной способностью два. Реализация такого элемента - это четыре транзистора. Монструозность, вернее неприемлимая задержка и увеличенное энергопотребление появляются, если количество входов превышает пять. Для элементов, реализующих (анти)монотонные функции пяти и менее входов (давно) найдены минимальные транзисторные схемы. Однако, вернёмся к счётчикам в коде Грея. Если взять n=3 и гамильтонов цикл, известный как coil-in-the-box, то Ваш метод даст маллеровский пайплайн из трёх С-элементов. Однако, если игнорировать устойчивые состояния 000 и 111 (don't care), то мы получим просто кольцо из трёх инверторов. И кто из них счётчик Грея?
Мешает отсутствие элементной базы чтобы собрать такие счётчики. Там даже при n=3 вылазят монстры. Их декомпозиция означает добавление сигнала. Это, в свою очередь, означает доопределение таблицы истинности определенным Вами образом. Это доопределение делает из добавленного элемента монстра. Замкнутый круг. Во всех смыслах.
На всякий случай скажу, что гамильтоновы циклы - это коды Грея и количество их разновидностей - это экспоненциальная функция от n. Соответственно, интересно было бы узнать как возрастает число разных счётчиков в коде Грея. Возможно, там есть пропуски из-за Вашего определения изоморфности.
Возращаясь к напечатанному. В Workcraft можно построить и верифицировать диаграмму переходов Мамрукова, где два пучка стрелок. Соответствующая модель называется FSM. Интересно то, что обратимая FSM означает, что начальная разметка достижима из любой достижимой разметки.
Очевидно, что представленная здесь теория не позволяет задать вот такую, аналоговую, а значит практическую схему
Она взята из статьи Behzad Razavi, A Fifty Applications of the CMOS Inverter—Part 2
Он пишет: Схема на рис. 5(а) предпочитает защелкиваться и устанавливаться в «вырожденные» условия A=B=0 и X=Y=Vdd (или наоборот). Однако, мы знаем, что перекрестно связанные инверторы помогают избегать вырожденных условий, это показано на рис. 5(b).
По сути, два инвертора в кольце образуют ячейку памяти. Однако, будучи частью внешнего контура, эта ячейка постоянно переключается. Получается "кто кого перетянет".
Диаграмму Мамрукова натянуть на куб нельзя уже только потому, что переходы из вершины 000 в вершину 111 для последовательных схем запрещены. Кроме того, у Мамрукова из вершин 000 и 111 выходит пять стрелочек, у Вас - три. Тем не менее, диаграмма Мамрукова полумодулярна (я надеюсь). Признаю, я не обратил внимания, что все стрелочки направлены из нерабочего цикла в рабочий. Т.е. переключения между циклами быть не может, я ошибся. Хотя, никто не проверял можно ли обратить обратить одну или несколько из этих пяти стрелочек так, чтобы схема осталась прежней.
Что же касается симуляций, я, конечно, задавал начальные условия 000 и 111 - схема сразу же сваливается в рабочий цикл. Вашу фразу "не параметры на начало среза, а актуальные..." я не понимаю. Симуляция такого генератора - это так или иначе симуляция перезарядки конденсаторов. В отличии от практики, индуктивности нет. На каждом шаге симуляции, в его начале напряжения на конденсаторах актуальные. Идеальную линию задержки, без затухания, без индуктивности, без емкости и без сопротивления я также устанавливал. Не помогает.
Интересно было бы всё-таки перевести осциллятор из рабочего цикла в нерабочий. Сколько я не пытался сделать это в SPICE-симуляторе, мне это не удалось. И стр. 43 в диссертации Мамрукова отвечает на вопрос "почему не удалось?" Потому что попадание в нерабочий цикл 000-111 никак не мешает выходу из него. Более того, такое попадание непредсказуемо - один раз за тысячу периодов или за миллион - иди лови.
Ю. В. Мамруков. Анализ апериодических схем и асинхронных процессов. Диссертация к.т.н. ЛЭТИ, 1984.
На уровне философии Ваш подход страдает тем же недостатком, что и асимпотические оценки в дискретной математике, только наоборот. В том смысле, что математики любят устремить n к бесконечности и показать, что в таком то базисе (например 2И-НЕ плюс 2ИЛИ-НЕ) такая-то схема (например n-разрядный сумматор) имеет такую-то сложность, которая меньше предыдущей. Инженера интересует n в диапазоне от 4 до 1024. Вы фактически устремили n не к бесконечности, а к нулю и получили такой же бесполезный результат. Именно эта задача была поставлена и поэтому признаю - она решена. Композицию в статье "Последовательные схемы" я не видел, поэтому повторю вопрос - можно ли взять несколько последовательных схем одной размерности, выполнить их композицию и получить дистрибутивную схему той же размерности?
Пересчёт подразумевает, что на вход анализатора поступают схемы от первой до последней (с астрономическим номером при n>3). Насколько я понял, поступают они последовательно. Здесь напрашивается конвейер. Возможно, JIT-компилятор Numba и сделает подобие конвейера, но это будет жалкое подобие. Нужно изначально писать под конвейер. Но это требует досконального знания архитектуры процессора. А в случае, если будет принято правильное решение, - то архитектуры GPU. Можно, конечно, написать на Verilog, но для этого нужно иметь отладочную плату с мощной FPGA. Насколько мне известно, бесплатного online доступа к таким платам нет, в отличии от GPU.
Что же касается композиции и декомпозиции, то в качестве легкого утреннего упражнения можно взять n=2 и синтезировать из последовательных схем дистрибутивные или наоборот разложить каждую дистрибутивную на последовательные. Благо, инструмент для этого у Вас (да и у всего прогрессивного человечества) уже есть, называется "Алгебра асинхронных схем". Она изложена в той Книге 1986, на которую Вы ссылаесь.
Тогда напрашивается не сужение класса схем (от полумодулярных к дистрибутивным, а затем к последовательным), а наобот - композиция последовательных в дистрибутивные и их обоих в полумодулярные. Для заданного n на первом этапе и с повышением n на втором.
Вы привели пример неоживляемых схем, поэтому уточню вопрос. Может ли неудачный выбор начальных состояний перевести схему из класса полумодулярных в класс дистрибутивных?
Ни в одной статье цикла ничего не сказано про начальные условия, это специально? Или для схем, заданных на всех 2^n состояниях, начальные условия могут быть произвольными?
А всё потому, что автор настаивает на своей постановке задачи. А ведь есть возможность увеличить 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.
На всякий случай нужно сказать, что в работе
Ю. В. Мамруков. Анализ апериодических схем и асинхронных процессов. Диссертация к.т.н. ЛЭТИ, 1984.
1. Предложены формулы для определения множеств конфликтных состояний и решения задач обратной и прямой достижимости. На основе этих формул разработаны методы полного анализа и анализа рабочего множества, ориентированные на формульное представление множеств состояний.
2. Предложены алгоритмы полного анализа и анализа рабочего множества, ориентированные на табличное представление множеств состояний, отличающиеся высокой скоростью.
3. Введено понятие редукции схемы по самонезависимой переменной и исследованы ее свойства. Предложен метод сокращения трудоемкости анализа за счет снижения их размерности, основанный на использовании редукции.
На всякий случай нужно сказать, что параллельно-последовательные схемы, а также бесповторные и беспетлевые впервые введены в оборот в диссертации
М. А. Кишиневский. Реализация и анализ апериодических схем. ЛЭТИ, 1982.
Ещё раз попробую угадать название следующей статьи - уж не параллельно-последовательные схемы ли это? Книга 1986 на стр. 258 гласит: В параллельно-последовательных схемах каждая переменная возбуждается только после того, как в результате изменения своих значений станут устойчивыми все ранее возбужденные переменные. Класс параллельно-последовательных схем является подклассом дистрибутивных и образует расширение класса последовательных схем.
Хорошо, выходит за рамки, но "критические" состояния есть не только в последовательных схемах, но также в дистрибутивных и в полумодулярных. Такие схемы с критическими состояниями можно было посчитать и дать несколько примеров в развернутом виде. Я не утвеждал, что минимизация влияет на поведение схемы, я утвеждал, что результат минимизации может быть одинаков для схемы, которая выходит из критических состояний и для схемы, где эти состояния игнорируются. Это можно было бы проверить на примерах. Но Вы не хотите их приводить.
По первому способу - точно не всегда, поскольку устойчивые состояния - это не don't care. Более того, этот способ не выводит схему из тупика. Мой вопрос был по второму способу - всегда ли переход в соседнее состояние или по цепочке эквивалентен don't care? Наверняка не всегда и даже не известно "лучше" он или "хуже" первого. В том смысле, что даёт большее количество эквивалентов после минимизации.
Тогда вопрос - всегда ли можно выйти из критических состояний так что чтобы результирующая схема была такой же, как в случае игнорирования оных? А в начальной установке ничего сложного нет. Её обычно делают одним транзистором, перетягивая выход либо вверх, либо вниз.
Да, это оно. В конце статьи "Последовательные схемы ч.4" приведены формулы для маллеровского пайплайна, который в русской традиции называют распределителем импульсов и делают на простых элементах, типа 2И-НЕ. И то как этот пайплайн превращается в кольцо инверторов показано. Но это "правильный" способ. Я говорю про "неправильный", игнорировать 000 и 111, что даёт то же самое кольцо. Отсюда вывод - в этом, частном, случае правильный способ "равен" неправильному. Переформулирую ранее заданный вопрос - можно ли считать кольцо из инверторов распределителем? Вы вообще вычеркнули его из последовательных схем. По поводу названия "критические состояния" - какое-то оно слишком истеричное. Да, возможно, в космосе от Солнца может прилететь поток протонов с высокой энергией, который выведет схему из рабочего цикла в эти состояния, откуда нет выхода. Но самое последнее предложение в "ч.4" гласит фактически, что элементы схемы рисуют без специального входа установки в начальное состояние, но в реальном устройстве такие входы обязательно есть. А значит и состояния совсем не критические.
Здесь как в научной байке: Докладчик только начал выступление, - "Есть целый ряд проблем...", как сразу получил вопрос, - "Какой ряд Вы называете целым"? Что такое ненадёжное функционирование? Вы говорите про последовательные схемы, которые могут быть реализованы без нарушения полумодулярности на 2И(ИЛИ)-НЕ с нагрузочной способностью два. Реализация такого элемента - это четыре транзистора. Монструозность, вернее неприемлимая задержка и увеличенное энергопотребление появляются, если количество входов превышает пять. Для элементов, реализующих (анти)монотонные функции пяти и менее входов (давно) найдены минимальные транзисторные схемы. Однако, вернёмся к счётчикам в коде Грея. Если взять n=3 и гамильтонов цикл, известный как coil-in-the-box, то Ваш метод даст маллеровский пайплайн из трёх С-элементов. Однако, если игнорировать устойчивые состояния 000 и 111 (don't care), то мы получим просто кольцо из трёх инверторов. И кто из них счётчик Грея?
Мешает отсутствие элементной базы чтобы собрать такие счётчики. Там даже при n=3 вылазят монстры. Их декомпозиция означает добавление сигнала. Это, в свою очередь, означает доопределение таблицы истинности определенным Вами образом. Это доопределение делает из добавленного элемента монстра. Замкнутый круг. Во всех смыслах.
На всякий случай скажу, что гамильтоновы циклы - это коды Грея и количество их разновидностей - это экспоненциальная функция от n. Соответственно, интересно было бы узнать как возрастает число разных счётчиков в коде Грея. Возможно, там есть пропуски из-за Вашего определения изоморфности.