Связь между комбинационной логикой и последовательной логикой

Я всегда думал, что комбинационные логические схемы могут решать только задачи, не требующие памяти, но тут меня что-то осенило.
Всякий раз, когда мы моделируем двоичный сумматор с помощью конечного автомата, мы рассматриваем его как проблему, требующую памяти (нам нужно знать, привело ли сложение предыдущей цифры к переносу или нет). Вот почему нам нужны два состояния: «без переноса» и «перенос».

введите описание изображения здесь

Но тогда мы можем легко увидеть, как двоичные сумматоры с несущими могут быть решены комбинационными логическими схемами, которые, казалось бы, не имеют памяти.

введите описание изображения здесь

Мне кажется, что память как-то закодирована в том, как мы ставим отдельные сумматоры последовательно (C_out последнего сумматора переходит в C_in текущего сумматора)

Сравнивая решение задачи с помощью конечного автомата с решением задачи с помощью комбинационной логики, кажется, что первый решает складывать по одной цифре за раз, регулируемый часами, и поэтому память должна быть в форме состояний. И похоже, что последний решает делать все сложения цифр одновременно, поэтому нет необходимости в часах и как-то память для предыдущих носителей реализована через последовательное каскадное соединение между сумматорами.

Точно так же, как мы можем иметь конечный автомат, а также версию комбинационной логики для задачи арифметического сложения с носителями, я думаю, можем ли мы на самом деле преобразовать ЛЮБОЙ конечный автомат в комбинационную логическую схему, которая выполняет ту же работу, при условии, что мы организуем одна подсхема для каждой возможной работы, которая выполняется в FSM за один такт (добавление одной цифры в последнем случае), поместить все это параллельно и каким-то образом закодировать память в последовательном каскадном соединении.

Это правда ?

Это сомнение возникло, потому что я пытаюсь связать все понятия, которые я недавно изучил в теории вычислений (автоматы, машины Тьюринга, вычислительная сложность: временная сложность и пространственная сложность) с комбинационными логическими схемами.

Заранее большое спасибо.

Ответы (6)

Нет, вы не можете преобразовать (нетривиальную) схему с памятью в комбинаторную (без обратной связи) схему.

Выходы комбинаторной схемы по определению являются функцией ее входов (и ничем иным).

Возьмем простейшую некомбинаторную схему: ячейку памяти Set-Rest (две кросс-пары NAND или NORS). Когда входные данные имеют значение «запомнить», выходные данные являются функцией прошлого. Это просто невозможно с любой комбинаторной схемой.

Если проекту требуется состояние, то он должен иметь какой-то способ хранения этого состояния, то есть память.

Выход сумматора (или умножителя и т. Д.) Полностью определяется входами, поэтому его можно полностью реализовать в комбинаторной логике.

Однобитовая память не может быть реализована в комбинаторной логике, иначе это не была бы память.

Это потому, что моделирование сумматора как конечного автомата удобно, но в конечном счете неверно. Нет состояний; то, что показано как «состояние», является просто выходом, а не результатом перехода на основе состояния.

Это кажется глубоким, и я действительно хочу понять это, но я не мог полностью понять. Есть ли какой-то метод или подсказка, чтобы получить FSM и проверить, является ли он истинным FSM или нет, то есть проверить, действительно ли его состояния являются выходными данными или они действительно представляют результат перехода на основе состояния. ? Не могли бы вы порекомендовать мне какой-либо материал для чтения? Большое спасибо
FSM требует некоторой памяти для хранения текущего состояния, а также некоторого вида часов, чтобы определить, когда должны выполняться переходы (т. е. они могут существовать только для последовательной логики). Сумматор (представляющий собой чисто комбинационную логику) не имеет ни того, ни другого.
Что сказал @IgnacioVazquez-Abrams, если есть память (и часы), то есть состояния. Вы можете создавать фальшивые «провалы» или временные состояния, просто называя промежуточные узлы состояниями, но это просто удобство для дизайнера. Еще одна подсказка, которая у вас есть, заключается в том, что вам (обычно) нужно сделать что-то особенное при включении «схемы». ПЗУ может показаться исключением, но вы сделали «что-то особенное», когда программировали его, после программирования ПЗУ ведет себя как комбинаторная логика. В более широком контексте «состояние» не обязательно должно быть нулем или единицей, оно может быть аналоговым.

Диаграмма состояний, показанная в вопросе, представляет собой последовательный сумматор . В нем всего один полный сумматор и элемент памяти. И для получения результата сложения двух N-битных чисел требуется N тактов.

Блок-схема, показанная на рисунке, представляет собой 4-битный сумматор с неравномерным переносом , для которого требуется 4 полных блока сумматора. Это добавит два 4-битных числа параллельно и даст результат в кратчайшие сроки (задержками распространения пренебрегают). Логика здесь чисто комбинационная и в ней нет памяти.

Короче говоря, данная диаграмма состояний не соответствует данной блок-схеме. Это две разные цифровые системы. Последовательный сумматор имеет два однобитовых входа и один битовый выход. В то время как сумматор с пульсирующим переносом имеет два N-битных входа и один N+1-битный выход.

Последовательные машины нельзя заменить комбинационной логикой. Но комбинационные схемы можно заменить последовательными схемами. Обычно это делается для уменьшения аппаратной сложности. То, что мы видели в вашем вопросе, является примером этого. Схемы, такие как счетчики, сдвиговые регистры и т. д., никогда не могут быть заменены комбинационной логикой.

С точки зрения вычислительной сложности последовательный сумматор разделяет этапы вычислений во времени, повторно используя аппаратное обеспечение. Сумматор пульсаций разделяет шаги в пространстве, используя отдельные копии оборудования для выполнения отдельных шагов.

На мой взгляд, я чувствую, что возможность извлечения комбинационной схемы из последовательной схемы будет зависеть от функциональности схемы. Многие (но не все) последовательные логические схемы могут быть распакованы и реализованы как чисто комбинационные схемы (я чувствую, что это особенно верно для машин Мура), но есть много спецификаций времени и площади, которые было бы очень трудно выполнить, если бы мы решили реализовать их таким образом. система таким образом.

Я не уверен, что согласен с позицией, согласно которой представление сумматора с предоставленной вами диаграммой обязательно ложно, как заявил другой автор. моделируется как прохождение через два состояния: перенос-1 и перенос-0, а также последовательная схема, такая как показанная ниже.

Последовательный сумматор

Многие последовательные (синхронные/синхронизированные) схемы также могут быть заменены чисто комбинационными (асинхронными/безтактовыми) схемами во многих ситуациях. друг друга и, по сути, имеют информацию о состоянии, закодированную в их выходах.

В основном мы рассматриваем перенос для следующей операции (не состояния), но не важно, что это будет, это может быть 1 или 0, а окончательный вывод будет определяться значением и комбинацией всей логики, мы не можем смоделировать его с помощью состояния машина, потому что вся схема не проходит через несколько состояний, в отличие, например, от счетчика

Связь между комбинационной логикой и последовательной логикой
СпросиСетьПолитика конфиденциальности1y, 0v