Vínculo entre Lógica Combinacional y Lógica Secuencial

Siempre pensé que los circuitos lógicos combinacionales solo podían resolver problemas que no requerían memoria, pero algo me llamó la atención.
Siempre que estamos modelando un sumador binario con una máquina de estados finitos, lo consideramos como un problema que requiere memoria (necesitamos saber si la suma del dígito anterior condujo a un acarreo o no). Por eso necesitamos dos estados, "no carry" y "carry".

ingrese la descripción de la imagen aquí

Pero luego podemos ver fácilmente cómo los sumadores binarios con portadores pueden resolverse mediante circuitos lógicos combinacionales, que aparentemente no tienen memoria.

ingrese la descripción de la imagen aquí

Me parece que la memoria está codificada de alguna manera en la forma en que colocamos los sumadores individuales en serie (C_out del último sumador entra en C_in del sumador actual)

Comparando la solución de la máquina de estados finitos al problema con la solución de la lógica combinacional al problema, parece que la primera decide hacer sumas de un dígito a la vez, reguladas por un reloj y es por eso que la memoria debe estar en forma de estados. Y parece que este último decide hacer todas las sumas de dígitos al mismo tiempo, por lo que no hay necesidad de relojes y, de alguna manera, la memoria para los operadores anteriores se implementa a través de una conexión en serie en cascada entre los sumadores.

Al igual que podemos tener una FSM, así como una versión Lógica Combinacional para el problema de la suma aritmética con portadores, estoy pensando si podemos convertir CUALQUIER máquina de estados finitos en un Circuito Lógico Combinacional que haga el mismo trabajo, siempre que organicemos un subcircuito para cada trabajo posible que se realiza en el FSM en un reloj (adición de un dígito en el último caso), poner todos en paralelo y de alguna manera codificar la memoria en una conexión en serie en cascada.

Es verdad ?

Esta duda surgió porque estoy tratando de vincular todos los conceptos que aprendí recientemente en Teoría de la Computación (Autómatas, Máquinas de Turing, Complejidad Computacional: Complejidad del Tiempo y Complejidad del Espacio) con circuitos lógicos combinacionales.

Muchas gracias por adelantado.

Respuestas (6)

No, no puede traducir un circuito (no trivial) que tiene memoria a un circuito combinatorio (sin retroalimentación).

Las salidas de un circuito combinatorio son, por definición, una función de sus entradas (y nada más).

Tome el circuito no combinatorio más simple: la celda de memoria Set-Rest (dos pares cruzados NANDS o NORS). Cuando las entradas tienen el valor 'recordar', las salidas son una función del pasado. Esto simplemente no es posible con ningún circuito combinatorio.

Si el diseño necesita un estado, entonces debe tener alguna forma de almacenar ese estado, es decir, la memoria.

La salida de un sumador (o multiplicador, etc.) está completamente determinada por las entradas, por lo que puede implementarse completamente en lógica combinatoria.

Una memoria de un solo bit no se puede implementar en lógica combinatoria, de lo contrario no sería memoria.

Eso es porque modelar el sumador como un FSM es conveniente, pero en última instancia es falso. No hay estados; lo que se muestra como un "estado" es simplemente la salida y no el resultado de una transición basada en el estado.

Esto parece profundo y realmente quiero comprenderlo, pero no pude entender completamente. ¿Existe algún tipo de método o sugerencia para obtener un FSM y verificar si es un FSM real o no, es decir, verificar si los estados son realmente salidas o si realmente representan el resultado de una transición basada en el estado? ? ¿Me podrías recomendar algún material para leer? muchas gracias
Un FSM requiere algún tipo de memoria para almacenar el estado actual, así como algún tipo de reloj para determinar cuándo se deben realizar las transiciones (es decir, solo puede existir para la lógica secuencial). Un sumador (siendo una lógica puramente combinacional) no tiene ninguno de los dos.
Lo que decía @IgnacioVazquez-Abrams, si hay memoria (y reloj) entonces hay estados. Puede crear estados falsos de "caída" o temporales, simplemente nombrando nodos intermedios como estados, pero eso es solo una conveniencia para el diseñador. Otra pista de que tiene estados es que (generalmente) necesita hacer algo especial al encender el "circuito". La ROM puede parecer una excepción, pero hizo "algo especial" cuando la programó, después de programar, la ROM se comporta como una lógica combinatoria. En el contexto más amplio, el "estado" no tiene que ser cero o uno, podría ser analógico.

El diagrama de estado que se muestra en la pregunta es un sumador en serie . Solo tiene un sumador completo y un elemento de memoria. Y requiere N ciclos de reloj para producir el resultado de la suma de dos números de N bits.

El diagrama de bloques que se muestra en la figura es un sumador de acarreo de ondulación de 4 bits que requiere 4 bloques de sumadores completos. Esto agregará dos números de 4 bits en paralelo y producirá el resultado en poco tiempo (se ignoran los retrasos de propagación). La lógica aquí es puramente combinacional y no tiene memoria.

En resumen, el diagrama de estado dado no corresponde al diagrama de bloques dado. Son dos sistemas digitales diferentes. El sumador en serie tiene dos entradas de un solo bit y una salida de un bit. Mientras que un sumador de acarreo de ondas tiene dos entradas de N bits y una salida de N+1 bits.

Las máquinas secuenciales no se pueden reemplazar con lógica combinacional. Pero los circuitos combinacionales se pueden reemplazar con circuitos secuenciales. Por lo general, se hace para reducir la complejidad del hardware. Lo que vimos en su pregunta es un ejemplo de eso. Los circuitos como contadores, registros de desplazamiento, etc. nunca se pueden reemplazar con lógica combinacional.

En términos de complejidad computacional, el sumador serial separa los pasos del cómputo en el tiempo, reutilizando el hardware. El sumador ondulado separa los pasos en el espacio, usando copias separadas del hardware para hacer los pasos separados.

En mi opinión, creo que si un circuito combinacional se puede extraer de un circuito secuencial dependerá de la funcionalidad del circuito. Muchos (pero no todos) los circuitos lógicos secuenciales se pueden desempaquetar e implementar como circuitos puramente combinacionales (Creo que esto es especialmente cierto para las máquinas Moore), pero hay muchas especificaciones de tiempo y área que serían muy difíciles de cumplir si decidiéramos implementarlas de esta manera. un sistema de esta manera.

No estoy seguro de estar de acuerdo con la postura de que representar un sumador con el diagrama que proporcionó es necesariamente falso como lo ha dicho otro cartel. Tal vez sea falso en el contexto del circuito del sumador de ondulación que proporcionó, pero un sumador de N bit puede ser modelado como si pasara por dos estados, carry-1 y carry-0, y se extrajo un circuito secuencial como el siguiente.

sumador secuencial

Muchos circuitos secuenciales (sincrónicos/con reloj) también se pueden reemplazar por circuitos puramente combinacionales (asincrónicos/sin reloj) en muchas situaciones. entre sí y esencialmente tienen información de estado codificada en sus salidas.

Básicamente, consideramos el acarreo para la próxima operación (no el estado), pero no importa cuál será, puede ser 1 o 0 y la salida final se decidirá por el valor y la combinación de toda la lógica, no podemos modelarlo usando el estado máquina porque todo el circuito no pasa por múltiples estados a diferencia de, por ejemplo, un contador

Vínculo entre Lógica Combinacional y Lógica Secuencial
RespuestasAquíPolítica de privacidad1y, 1v