¿Es realmente necesaria la lógica secuencial para resolver algunos tipos de problemas? [cerrado]

El tamaño de un circuito combinatorio es una función de su entrada. Cuanta más entrada pueda usar un circuito para calcular su salida, más grande debe ser el circuito. Supongamos, por ejemplo, que uno necesitaba diseñar un circuito que determinaría si una entrada tenía un número par o impar de bordes ascendentes en el último segundo, si se garantizase que cada tiempo alto y bajo fuera de al menos 100 ms. Uno podría usar una cadena de búferes puramente combinatorios con un tiempo de propagación de 91 ms para generar doce entradas a un circuito que luego podría contar el número de secuencias "01" dentro del flujo de bits. Tal circuito sería bastante grande, pero no imposible.

Si uno quisiera hacer un circuito que pudiera decir si la entrada había pulsado alto un número par o impar en el último minuto, se podría usar el mismo principio, pero el resultado sería bastante difícil de manejar. Si uno tiene alguna señal de reloj disponible que puede ayudar a estabilizar los tiempos e impedir que el circuito se vuelva tan totalmente impráctico (*), incluso sin retroalimentación (tenga en cuenta que los circuitos combinatorios pueden usar señales de reloj, pero no pueden generarlas). Las optimizaciones facilitadas por el reloj pueden ayudar a evitar que un circuito se vuelva totalmente inviable, pero aún así sería grande. Incrementar el tiempo en cuestión a un día, año, década o siglo también haría crecer la máquina. Si uno no necesitaba que la máquina durara más de 100 años, en teoría se podría construir una máquina puramente combinatoria para informar si el número de pulsos en los últimos 100 años era par o impar, y luego usarlo para hasta 100 Años, pero hacerlo sería monstruosamente poco práctico.

Por el contrario, utilizando una lógica secuencial, la tarea se podría realizar utilizando un solo flip-flop D con una salida invertida. A pesar de que en el transcurso de un año, el dispositivo aceptaría millones de segundos de "entrada", eso no sería un problema ya que un solo flip flop será suficiente para mantener el estado derivado de una cantidad ilimitada de entrada.

(*) Es posible construir un flop D sin usar retroalimentación si se puede garantizar que el tiempo entre los pulsos de reloj no exceda algún límite, aunque desafortunadamente este simulador no puede manejar MOSFETs monolíticos.

^{simular este circuito : esquema creado usando CircuitLab}

Los "resistores" son en realidad modos de agotamiento en VDD, y los MOSFET son monolíticos, con sus bases vinculadas a VSS en lugar de a la fuente. Mientras PHI1 es alto, todo lo que esté en IN se transferirá a la puerta de M2, y su inverso aparecerá en el drenaje de M2. Cuando el PHI1 es bajo, lo que haya en la puerta y el drenaje de M2 permanecerá allí, al menos por un tiempo, debido a la capacidad de la puerta de M2. Cuando PHI2 es alto, todo lo que esté en el drenaje de M2 se transferirá a la compuerta de M4, y su inverso aparecerá en el drenaje de M4. Cuando el PHI2 está bajo, lo que haya en la puerta y el drenaje de M4 permanecerá allí por un tiempo debido a la capacidad de la puerta de M4. Siempre que PHI1 y PHI2 no se superpongan y sean lo suficientemente rápidos para volver a cargar los condensadores antes de que la fuga altere sus valores, este circuito se puede usar de manera confiable como un D-flop. De hecho, los circuitos de este tipo eran muy comunes en la lógica LSI de los años 70.

Además, incluso si uno ve este estilo de circuito como "trampa", es posible usar el reloj para estabilizar los retrasos de propagación de lógica puramente secuencial haciendo que un reloj seleccione entre rutas lógicas con tiempos de propagación más cortos o más largos.

^{simular este circuito} A diferencia del circuito MOSFET, el de arriba simulará. Cada búfer tiene un tiempo de propagación de 700 ns, y cada salida de mux cambiará en el flanco ascendente del reloj y no habrá otro tiempo, siempre que los flancos ascendentes del reloj ocurran entre 700 ns y 1400 ns después de un cambio de entrada, y los bordes descendentes no ocurran hasta que al menos 1400ns después de un cambio de entrada. El circuito anterior cumple inicialmente las restricciones de tiempo, pero como el reloj y los datos no son desviaciones de múltiplos exactos para violarlo, muestra el comportamiento consecuente.

Si tiene algún conjunto de entradas booleanas S , y alguna función f que asigna S a un conjunto de salidas booleanas R , entonces sí: cualquier f puede representarse con lógica combinacional pura , y puede derivar qué lógica necesita del mapa de Karnaugh, etc. El proceso de completar el mapa de Karnaugh puede ser difícil: está pre-computando manualmente todas las respuestas.

Esto tiene dos grandes limitaciones:

1. Todas las entradas deben estar disponibles al mismo tiempo
2. Debe haber un número máximo finito definido de entradas

No puedes usar lógica combinacional pura para, por ejemplo, La máquina de estados del controlador de elevación clásico, porque no puede registrar si un botón ha sido presionado o no. No puede usarlo para procesar la señal porque necesita registrar valores previos de la señal. También hace que la implementación sea incómoda y costosa: si desea encontrar cuál de los mil millones de registros coincide con una entrada particular, debe tener mil millones de comparadores.

Creo que esto también se desvía hacia el territorio de Turing-completitud. La función que genera 1 si una cinta de Turing se detiene y 0 si no lo hace, no es teóricamente computable por ningún tipo de lógica .

La lógica secuencial se desarrolló a partir de una necesidad para poder predecir con precisión cuándo un determinado valor o conjunto de valores se encontraba en un lugar determinado, de modo que otra lógica podría decidir hacer algo con esa información. Muchos problemas lógicos se pueden resolver utilizando solo la lógica combinatoria, pero surge un problema cuando se necesita usar la salida de una función como entrada para otra función. Para crear hardware de propósito general, es necesario poder copiar y redireccionar valores binarios a voluntad en todo el sistema para que se puedan realizar diferentes funciones en un orden arbitrario. Sin esta capacidad, tenemos que agregar lógica para cada orden de operaciones posible que pueda suceder en cualquier lugar, lo que no es posible.

Además, si puede construir un multiplexor en funcionamiento sin un solo flip-flop, realmente necesita presentar una patente, como ahora.

Todos los problemas digitales que son intrínsecamente combinatorios se pueden resolver utilizando la lógica combinatoria. Por ejemplo, el cifrado AES normalmente se haría usando lógica secuencial, pero teóricamente se podría hacer de manera combinatoria, siempre que tuviera todas las entradas disponibles listas simultáneamente, y se desenrollaran todos los bucles duplicando la lógica. Por supuesto, sería horriblemente ineficiente con todos esos bloques lógicos duplicados, pero aún así es posible.

Sin embargo, algunos problemas están inherentemente basados en el tiempo. Si la descripción de su problema contiene algún tipo de "haga esto, luego haga eso", deberá utilizar la lógica secuencial.

Cualquier sistema en tiempo real que utilice filtros o controladores digitales requerirá necesariamente elementos de memoria que cumplan con los requisitos de retardo de las ecuaciones de diferencia de tiempo discreto. Los datos de lote que teóricamente podrían proporcionar todos los datos de entrada relevantes, no están disponibles en sistemas en tiempo real. En un sistema de control, por lo general, al menos se requiere un Integrador que requiera una memoria en una implementación digital.

Los ejemplos incluyen: procesamiento de audio en tiempo real, ADC y DAC de Sigma-Delta, sistemas de control en tiempo real.

Además, cualquier máquina de estado requiere elementos de memoria para representar los estados.