Enlace entre lógica combinacional y lógica secuencial

2

Siempre pensé que los circuitos lógicos combinacionales solo podían resolver problemas que no requerían memoria, pero luego algo me impactó.
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 de dígitos anterior llevó a un acarreo o no). Es por eso que necesitamos dos estados, "no carry" y "carry".

Peroluegopodemosverfácilmentecómolossumadoresbinariosconportadorespuedenresolversemediantecircuitoslógicoscombinados,queaparentementenotienenmemoria.

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 el C_in del sumador actual)

Al comparar la solución de la máquina de estados finitos con el problema de la solución de lógica combinada con el problema, parece que la primera decide hacer una suma de un dígito a la vez, regulada 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 adiciones 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 cascada en serie entre los sumadores.

Al igual que podemos tener un FSM así como una versión de lógica combinada para el problema de la suma aritmética con portadores, estoy pensando si realmente podemos convertir CUALQUIER máquina de estado finito en un circuito de lógica combinada que haga el mismo trabajo, siempre que dispongamos un subcircuito para cada trabajo posible que se realiza en el FSM en un reloj (suma de un dígito en el último caso), ponemos todos esos en paralelo y, de alguna manera, codificamos la memoria en una conexión en cascada en serie.

¿Es cierto?

Esta duda surgió porque estoy intentando 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 de antemano.

    
pregunta nerdy

6 respuestas

1

Esto se debe a que 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 el resultado en lugar del resultado de una transición basada en el estado.

    
respondido por el Ignacio Vazquez-Abrams
1

No, no puede traducir un circuito (no trivial) que tenga memoria en 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 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.

    
respondido por el Wouter van Ooijen
1

Si el diseño necesita un estado, debe tener alguna forma de almacenar ese estado, eso es 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.

    
respondido por el copper.hat
0

En mi opinión, siento si un circuito combinatorio puede extraerse de un circuito secuencial dependerá de la funcionalidad del circuito. Una gran cantidad de circuitos lógicos secuenciales (pero no todos) pueden desempaquetarse e implementarse como circuitos puramente combinacionales (I creo que esto es especialmente cierto para las máquinas Moore) pero hay una gran cantidad de especificaciones de área y tiempo que serían muy difíciles de cumplir si decidiéramos implementarlas de esta manera. Además, a medida que aumenta la cantidad de estados, se vuelve poco práctico y demasiado Es costoso desarrollar 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 indicado otro póster. Tal vez sea falso en el contexto del circuito de sumador de ondulación que proporcionó, pero un sumador de N bits puede ser de hecho, se puede modelar como que atraviesa dos estados, carry-1 y carry-0, y un circuito secuencial como el que se extrae a continuación.

Una gran cantidad de circuitos secuenciales (sincronizados / sincronizados) también pueden reemplazarse por circuitos puramente combinacionales (asíncronos / sin reloj) en muchas situaciones. Estos circuitos asíncronos utilizan protocolos de datos agrupados, como el protocolo de doble fase de 4 fases. para comunicarse entre sí y esencialmente tener información de estado codificada en sus salidas.

    
respondido por el KillaKem
0

Básicamente consideramos llevar para la próxima operación (no estado) pero no importa lo que sea, 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 modelar utiliza una máquina de estados porque todo el circuito no atraviesa varios estados a diferencia de, por ejemplo, un contador

    
respondido por el vishal dharankar
0

El diagrama de estado que se muestra en la pregunta es un sumador serial . Tiene solo un sumador completo y un elemento de memoria. Y requiere N ciclos de reloj para producir el resultado de la adición de dos números de N bits.

El diagrama de bloques que se muestra en la figura es un sumador de acarreo de rizado de 4 bits que Requiere 4 bloques de sumador completos. Esto agregará dos números de 4 bits en paralelo y producirá el resultado en ningún momento (se descuidan los retrasos de propagación). La lógica aquí es puramente combinatoria 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 rizo tiene dos entradas de N bits y una salida de N + 1 bit.

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

    
respondido por el nidhin

Lea otras preguntas en las etiquetas