¿Observan las personas el nido de bucles en los circuitos booleanos?

11

Mientras era estudiante de EE asistí a algunas conferencias que presentaban una buena caracterización de los circuitos booleanos en términos de cuántos bucles anidados tienen. En complejidad, los circuitos booleanos a menudo se consideran dags, pero en los ciclos reales de hardware son comunes. Ahora, modulo algunos tecnicismos con respecto a qué es un bucle y qué constituye un bucle anidado, la afirmación era básicamente que para implementar en hardware un autómata se necesitan dos bucles anidados, y para implementar un procesador se necesitan tres bucles anidados. (Podría estar fuera de uno con estos recuentos).

Dos cosas me molestan:

  1. No había nada como una prueba formal.
  2. No vi esto en ningún otro lado.

¿Alguien investigó declaraciones precisas de este tipo?

Al buscar el nombre del profesor, encontré una pequeña página web y un libro (Capítulo 4) que analizan esta taxonomía.

Tipo de antecedentes : en caso de que se pregunte por qué los ciclos son útiles en el hardware real, aquí hay un ejemplo simple. Conecte dos inversores en un ciclo. (Un inversor es una puerta que calcula la función booleana NO). Este circuito tiene dos equilibrios estables (y uno inestable). En ausencia de cualquier intervención externa, el circuito simplemente permanecerá en uno de los dos estados. Sin embargo, es posible forzar el circuito a un estado particular aplicando una señal externa. La situación puede verse así: mientras el ciclo está conectado a la señal externa "leemos la entrada", y de lo contrario simplemente "recordamos el último valor que vimos". Entonces, un bucle nos ayuda a recordar cosas.

Radu GRIGore
fuente
Quizás esto se vea mejor como una forma de estructurar el diseño de un circuito digital a gran escala (al igual que sería una buena idea usar subrutinas en un programa informático a gran escala), y no realmente como un límite inferior formal. (El Capítulo 14 del libro que vinculó tiene muchos Teoremas con Pruebas, pero parecen suponer que sigue ciertos principios en el diseño del circuito?)
Jukka Suomela
1
Jukka puede tener razón. Tomemos el ejemplo de un flip-flop (un sistema de un bucle) versus una máquina de estados finitos (un sistema de dos bucles como se implementa generalmente). ¿No puede alinear la lógica de transición combinacional del FSM (que no tiene bucles) directamente en el bucle del flip-flop? Por supuesto, un FSM de un bit no es muy interesante. Solo puede ser constante o alternativo en cada ciclo. Este último es, por supuesto, un flip-flop T con el terminal T conectado a un cable 1. Pero la misma idea funciona para un banco de chanclas.
Por Vognsen

Respuestas:

5

Debería echar un vistazo a la tesis doctoral (más tarde publicada como una monografía) de Tomás Feder: Redes estables y gráficos de productos , donde estudió la complejidad de encontrar configuraciones estables de redes , que son exactamente circuitos con "bucles" como usted mencionó.

Dai Le
fuente