Um circuito booleano no TCS é basicamente um DAG que consiste nos portões And, Or, Not e, pelo que se sabe, é "integridade funcional", eles podem calcular todas as funções possíveis. por exemplo, este é o princípio básico em uma ULA .
Desafio: crie um circuito para determinar se um número de 8 dígitos binários é divisível por 3 e visualize de alguma forma o resultado (ou seja, em algum tipo de figura)
O critério de julgamento para os eleitores é baseado em se o código para gerar o circuito generaliza bem para números arbitrários de tamanho e se a visualização criada por algoritmos é compacta / balanceada, mas ainda assim legível por humanos (ou seja, visualização por arranjo manual não é permitida). isto é, a visualização é apenas para n = 8, mas o código funcionará idealmente para todos os 'n'. a entrada vencedora é apenas a mais votada.
Pergunta um pouco semelhante: Construa uma máquina multiplicadora usando portas lógicas NAND
gate-golf
? essa tag é inexistente. observação para os participantes: indique qual ferramenta de idioma / visualização você está usando. se alguém quiser inserir um comentário. caso contrário, aceitará o vencedor esta noite. thx muito para os entrevistados até agora isso foi "BTE" melhor do que o esperado!Respostas:
O gráfico mantém 3 booleanos em cada nível i. Eles representam o fato de que os bits i de alta ordem do número são iguais a 0, 1 ou 2 mod 3. Em cada nível, calculamos os próximos três bits com base nos três bits anteriores e no próximo bit de entrada.
Aqui está o código python que gerou o gráfico. Basta alterar N para obter um número diferente de bits ou K para obter um módulo diferente. Execute a saída do programa python através do ponto para gerar a imagem.
fonte
Profundidade: 7 (logarítmica), 18x AND, 6x OR, 7x XOR, 31 portas (lineares)
Deixe-me calcular a soma dos dígitos na base quatro, módulo três:
circuito desenhado no Logisim
Generalização, formalmente (espero que um tanto legível):
agora em inglês:
Embora haja mais de dois bits no número, pegue dois pares de bits mais baixos e some-os no módulo 3, depois acrescente o resultado à parte de trás do número e retorne se o último par for zero no módulo 3. Se houver um número ímpar número de bits no número, adicione um zero zero extra ao topo e depois faça o polimento com propagação constante do valor.
Anexar na parte de trás em vez de na frente garante que a árvore de adição seja uma árvore equilibrada em vez de uma lista vinculada. Isso, por sua vez, garante profundidade logarítmica no número de bits: cinco portas e três níveis para cancelamento de pares e um portão extra no final.
Obviamente, se a planaridade aproximada for desejada, passe o par superior não modificado para a próxima camada em vez de envolvê-lo para a frente. Isso é mais fácil dizer do que implementado (mesmo em pseudocódigo), no entanto. Se o número de bits em um número for uma potência de dois (como é verdade em qualquer sistema de computador moderno a partir de março de 2014), nenhum par isolado ocorrerá.
Se o layouter preservar a localidade / executar a minimização do comprimento da rota, deverá manter o circuito legível.
Este código Ruby irá gerar um diagrama de circuito para qualquer número de bits (mesmo um). Para imprimir, abra no Logisim e exporte como imagem:
finalmente, quando solicitado a criar uma saída para 32 bits, meu layouter gera isso. É certo que não é muito compacto para entradas muito amplas:
fonte
2 × 24 NÃO, 2 × 10 + 5 AND, 2 × 2 + 5 OU, 2 × 2 NOR
Isso totalmente não escala. Como não. Talvez eu tente melhorar.
Eu testei isso para números de até 30 e funcionou bem.
Esses 2 grandes circuitos estão contando o número de entradas ativas:
Se a diferença desses números é
0
ou3
o número é divisível por3
. O circuito inferior direito basicamente mapeia cada combinação válida (4,4
,4,1
,3,3
,3,0
,2, 2
,1, 1
,0, 0
) em um ou.O pequeno círculo no meio é um LED que acende se o número for divisível por 3 e, caso contrário, apagado.
fonte