As pessoas olham para o aninhamento de loop em circuitos booleanos?

11

Enquanto estudante de EE, participei de algumas palestras que apresentavam uma boa caracterização de circuitos booleanos em termos de quantos ciclos aninhados eles tinham. Na complexidade, os circuitos booleanos são frequentemente vistos como dags, mas em ciclos reais de hardware são comuns. Agora, modulando alguns detalhes técnicos sobre o que é um loop e o que constitui um loop aninhado, a alegação era basicamente que, para implementar no hardware um autômato, é necessário dois loops aninhados e, para implementar um processador, são necessários três loops aninhados. (Eu posso estar fora de um com essas contagens.)

Duas coisas me incomodam:

  1. Não havia nada como uma prova formal.
  2. Eu não vi isso em nenhum outro lugar.

Alguém investigou declarações precisas desse tipo?

Procurando o nome do professor, encontrei uma pequena página da web e um livro (capítulo 4) que discutem essa taxonomia.

Tipo de histórico : Caso você se pergunte por que os ciclos são úteis em hardware real, aqui está um exemplo simples. Conecte dois inversores em um ciclo. (Um inversor é um gate que calcula a função booleana NOT.) Este circuito possui dois equilíbrios estáveis ​​(e instável). Na ausência de qualquer intervenção externa, o circuito simplesmente permanecerá em um dos dois estados. No entanto, é possível forçar o circuito para um estado específico aplicando um sinal externo. A situação pode ser vista assim: enquanto o ciclo está conectado ao sinal externo "lemos a entrada", e, do contrário, simplesmente "lembramos do último valor que vimos". Então, um loop nos ajuda a lembrar de coisas.

cc.complexity-theory reference-request circuit-complexity machine-models ar.hardware-architecture Radu GRIGore
fonte
Talvez isso seja melhor visto como uma maneira de estruturar o design de um circuito digital em larga escala (assim como seria uma boa idéia usar sub-rotinas em um programa de computador em grande escala), e não como um limite inferior formal? (Capítulo 14 do livro que é ligada tem abundância de teoremas com provas, mas eles parecem assumir que você seguir certos princípios na concepção do circuito?)
Jukka Suomela
1
Jukka pode estar certo. Tomemos o exemplo de um flip-flop (um sistema de um loop) versus uma máquina de estado finito (um sistema de dois loop, como geralmente implementado). Você não pode incorporar a lógica de transição combinatória do FSM (que não possui loops) diretamente no loop do flip-flop? Obviamente, um FSM de um bit não é muito interessante. Só pode ser constante ou alternar a cada ciclo. Este último é obviamente um flip-flop em T com o terminal T conectado a um fio. Mas a mesma idéia funciona para um banco de chinelos.
Por Vognsen

Respostas:

5

Você deve dar uma olhada na tese de doutorado (posteriormente publicada como monografia) de Tomás Feder: Redes estáveis ​​e gráficos de produtos , onde ele estudou a complexidade de encontrar configurações estáveis ​​de redes , que são exatamente circuitos com "loops", como você mencionou.

Dai Le
fonte