1) Я не знаю какой смысл в данном контексте принято вкладывать в термин fuzzy. Однако, знаю точно, что в хорошей статье каждая фраза должна быть "отполирована до блеска". Фраза "каждая clause может вмещать в себе огромное количество clauses чуть меньшего размера" противоречива.
2) В моём комментарии говорилось про MCU, в Вашем первом ответе тоже.
3) Не каждый CPU и, уж тем более, не каждый MCU имеет аппаратный MAC. Поэтому остро встаёт вопрос как реализовать его эффективно программой. Я специально увёл LLM в сторону ряда Тейлора чтобы получить ответ о техниках "приблизительного" MAC. Может быть сюда тоже можно натянуть fuzzy.
Не понял почему это fuzzy и что такое несвежий MCU, но
для элементов $\{-1, 0, 1\}$, операция умножения тривиальна (это либо инверсия знака, либо зануление, либо ничего). Основная нагрузка ложится на Accumulate.
Вот методы, которые работают по принципу «добавляй слагаемые, пока есть время/ресурс», что идейно ближе всего к ряду Тейлора:
1. Сэмплирование внешнего произведения (Outer Product Sampling)
Это самый прямой аналог «ряда» для MAC. Вы представляете произведение $AB$ как сумму $n$ матриц ранга 1:$$C = \sum_{k=1}^{n} a^{(k)} b_{(k)}^T$$ Где $a^{(k)}$ — это $k$-й столбец матрицы $A$, а $b_{(k)}^T$ — $k$-я строка матрицы $B$.
Как это работает для MAC: Вы не считаете все $n$ слагаемых. Вы выбираете $s$ случайных индексов $k$ (где много ненулевых элементов) и суммируете только их.
Сходство с Тейлором: Первые $s$ накоплений дают «приблизительный каркас», каждое последующее накопление (MAC) уточняет результат.
Метод используется в специализированных чипах (FPGA/ASIC).
Суть: Элементы $\{-1, 0, 1\}$ подаются как поток битов. Умножение превращается в простую логическую операцию (XNOR для 1/-1).
Для MAC: Аккумулятор просто считает количество «единиц» в потоке. Чем дольше вы «слушаете» поток битов (чем больше циклов MAC выполняете), тем точнее становится результат. Вы можете остановить процесс в любой момент, получив аппроксимацию.
3. Прореживание (Sparsification)
Так как элементы дискретны, вы можете заранее отфильтровать «малозначимые» операции:
Алгоритм: Игнорировать MAC-операции, где один из операндов — $0$.
Приближение: Если нужно еще быстрее, можно игнорировать те строки/столбцы, где плотность единиц (Sparsity) ниже определенного порога. Вы сначала обрабатываете «плотные» участки (главный член «ряда»), а «разреженные» оставляете на потом.
4. Метод иерархических блоков (Block-based MAC)
Разбейте матрицы на блоки (например, $8 \times 8$).
Сначала сделайте MAC для подмножества блоков (например, только по диагонали или случайно).
Это даст «пиксельную» (грубую) картину итоговой матрицы.
Добавляйте остальные блоки в аккумулятор, чтобы «повысить разрешение».
1) Я не интересовался особенностями Fuzzy-Pattern Tsetlin Machine, но если Вы запустили код на MCU, это может означать НЕ игрушечное применение. В том смысле, что есть задачи, где не требуется on-line processing, а значит не требуется параллельность.
2) Из статей 2026 на тему Tsetlin machine я бы присмотрелся вот к этой
https://arxiv.org/abs/2602.13128
3) Вот что говорит ИИ о некоторых (незрелых) альтернативах ChatGPT
Связь между KAN (Kolmogorov–Arnold Networks) и машинами Цетлина (Tsetlin Machines, TM) заключается в том, что обе архитектуры являются радикальными альтернативами господствующему подходу Deep Learning на базе многослойных перцептронов (MLP). Хотя они основаны на разных математических принципах, их объединяет стремление решить главные проблемы современных нейросетей: непрозрачность («черный ящик») и огромные вычислительные затраты. ## Сравнение KAN и машин Цетлина
| Характеристика | Сети Колмогорова–Арнольда (KAN) | Машины Цетлина (TM) | |---|---|---| | Математическая база | Теорема Колмогорова–Арнольда (непрерывные функции, сплайны). | Автоматы Цетлина (дискретная логика, обучение с подкреплением). | | Тип вычислений | Вещественные числа: сложная математика на ребрах сети. | Битовые операции: логические И, ИЛИ, НЕ (AND, OR, NOT). | | Интерпретируемость | Математическая: модель можно выразить в виде аналитической формулы. | Логическая: модель выдает набор понятных правил (IF-THEN). | | Энергоэффективность | Средняя (пока сложно оптимизировать под GPU). | Экстремально высокая: идеально для чипов без умножителей. |
## Точки соприкосновения
1. Логика вместо «черного ящика»: KAN пытается понять структуру функции через её разложение. Машина Цетлина строит логические высказывания о данных. Итог: Оба подхода позволяют человеку понять, почему ИИ принял то или иное решение, в отличие от ChatGPT. 2. Борьба с весами: В KAN классические веса заменены обучаемыми функциями. * В машинах Цетлина веса заменены на состояния автоматов (память), которые решают, включать признак в логическое правило или нет. 3. Обучение на малых данных: Обе архитектуры показывают хорошие результаты там, где данных мало для обучения гигантских трансформеров, но достаточно для извлечения четких закономерностей.
## Главное различие KAN — это инструмент для высокоточной математики, физики и инженерии, где важна непрерывность и точность аппроксимации. Машины Цетлина — это инструмент для сверхбыстрой и энергоэффективной логики, идеально подходящий для интернета вещей (IoT) и встраиваемых систем, где нужно экономить каждый микроватт энергии. ## Как они соотносятся в будущем? Сейчас ведутся исследования по созданию гибридов. Например, можно использовать логику машин Цетлина для предварительной фильтрации признаков, а KAN — для построения точных математических моделей на этих признаках.
Возращаясь к напечатанному. В 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" гласит фактически, что элементы схемы рисуют без специального входа установки в начальное состояние, но в реальном устройстве такие входы обязательно есть. А значит и состояния совсем не критические.
1) Я не знаю какой смысл в данном контексте принято вкладывать в термин fuzzy. Однако, знаю точно, что в хорошей статье каждая фраза должна быть "отполирована до блеска". Фраза "каждая clause может вмещать в себе огромное количество clauses чуть меньшего размера" противоречива.
2) В моём комментарии говорилось про MCU, в Вашем первом ответе тоже.
3) Не каждый CPU и, уж тем более, не каждый MCU имеет аппаратный MAC. Поэтому остро встаёт вопрос как реализовать его эффективно программой. Я специально увёл LLM в сторону ряда Тейлора чтобы получить ответ о техниках "приблизительного" MAC. Может быть сюда тоже можно натянуть fuzzy.
Не понял почему это fuzzy и что такое несвежий MCU, но
для элементов $\{-1, 0, 1\}$, операция умножения тривиальна (это либо инверсия знака, либо зануление, либо ничего). Основная нагрузка ложится на Accumulate.
Вот методы, которые работают по принципу «добавляй слагаемые, пока есть время/ресурс», что идейно ближе всего к ряду Тейлора:
1. Сэмплирование внешнего произведения (Outer Product Sampling)
Это самый прямой аналог «ряда» для MAC. Вы представляете произведение $AB$ как сумму $n$ матриц ранга 1:$$C = \sum_{k=1}^{n} a^{(k)} b_{(k)}^T$$ Где $a^{(k)}$ — это $k$-й столбец матрицы $A$, а $b_{(k)}^T$ — $k$-я строка матрицы $B$.
Как это работает для MAC: Вы не считаете все $n$ слагаемых. Вы выбираете $s$ случайных индексов $k$ (где много ненулевых элементов) и суммируете только их.
Сходство с Тейлором: Первые $s$ накоплений дают «приблизительный каркас», каждое последующее накопление (MAC) уточняет результат.
2. Битовый стриминг (Bit-Stream / Stochastic Computing)
Метод используется в специализированных чипах (FPGA/ASIC).
Суть: Элементы $\{-1, 0, 1\}$ подаются как поток битов. Умножение превращается в простую логическую операцию (XNOR для 1/-1).
Для MAC: Аккумулятор просто считает количество «единиц» в потоке. Чем дольше вы «слушаете» поток битов (чем больше циклов MAC выполняете), тем точнее становится результат. Вы можете остановить процесс в любой момент, получив аппроксимацию.
3. Прореживание (Sparsification)
Так как элементы дискретны, вы можете заранее отфильтровать «малозначимые» операции:
Алгоритм: Игнорировать MAC-операции, где один из операндов — $0$.
Приближение: Если нужно еще быстрее, можно игнорировать те строки/столбцы, где плотность единиц (Sparsity) ниже определенного порога. Вы сначала обрабатываете «плотные» участки (главный член «ряда»), а «разреженные» оставляете на потом.
4. Метод иерархических блоков (Block-based MAC)
Разбейте матрицы на блоки (например, $8 \times 8$).
Сначала сделайте MAC для подмножества блоков (например, только по диагонали или случайно).
Это даст «пиксельную» (грубую) картину итоговой матрицы.
Добавляйте остальные блоки в аккумулятор, чтобы «повысить разрешение».
1) Я не интересовался особенностями Fuzzy-Pattern Tsetlin Machine, но если Вы запустили код на MCU, это может означать НЕ игрушечное применение. В том смысле, что есть задачи, где не требуется on-line processing, а значит не требуется параллельность.
2) Из статей 2026 на тему Tsetlin machine я бы присмотрелся вот к этой
https://arxiv.org/abs/2602.13128
3) Вот что говорит ИИ о некоторых (незрелых) альтернативах ChatGPT
Связь между KAN (Kolmogorov–Arnold Networks) и машинами Цетлина (Tsetlin Machines, TM) заключается в том, что обе архитектуры являются радикальными альтернативами господствующему подходу Deep Learning на базе многослойных перцептронов (MLP).
Хотя они основаны на разных математических принципах, их объединяет стремление решить главные проблемы современных нейросетей: непрозрачность («черный ящик») и огромные вычислительные затраты.
## Сравнение KAN и машин Цетлина
| Характеристика | Сети Колмогорова–Арнольда (KAN) | Машины Цетлина (TM) |
|---|---|---|
| Математическая база | Теорема Колмогорова–Арнольда (непрерывные функции, сплайны). | Автоматы Цетлина (дискретная логика, обучение с подкреплением). |
| Тип вычислений | Вещественные числа: сложная математика на ребрах сети. | Битовые операции: логические И, ИЛИ, НЕ (AND, OR, NOT). |
| Интерпретируемость | Математическая: модель можно выразить в виде аналитической формулы. | Логическая: модель выдает набор понятных правил (IF-THEN). |
| Энергоэффективность | Средняя (пока сложно оптимизировать под GPU). | Экстремально высокая: идеально для чипов без умножителей. |
## Точки соприкосновения
1. Логика вместо «черного ящика»:
KAN пытается понять структуру функции через её разложение.
Машина Цетлина строит логические высказывания о данных.
Итог: Оба подхода позволяют человеку понять, почему ИИ принял то или иное решение, в отличие от ChatGPT.
2. Борьба с весами:
В KAN классические веса заменены обучаемыми функциями.
* В машинах Цетлина веса заменены на состояния автоматов (память), которые решают, включать признак в логическое правило или нет.
3. Обучение на малых данных: Обе архитектуры показывают хорошие результаты там, где данных мало для обучения гигантских трансформеров, но достаточно для извлечения четких закономерностей.
## Главное различие
KAN — это инструмент для высокоточной математики, физики и инженерии, где важна непрерывность и точность аппроксимации.
Машины Цетлина — это инструмент для сверхбыстрой и энергоэффективной логики, идеально подходящий для интернета вещей (IoT) и встраиваемых систем, где нужно экономить каждый микроватт энергии.
## Как они соотносятся в будущем?
Сейчас ведутся исследования по созданию гибридов. Например, можно использовать логику машин Цетлина для предварительной фильтрации признаков, а KAN — для построения точных математических моделей на этих признаках.
Возращаясь к напечатанному. В 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" гласит фактически, что элементы схемы рисуют без специального входа установки в начальное состояние, но в реальном устройстве такие входы обязательно есть. А значит и состояния совсем не критические.