Inspirado pela popularidade recente de nandgame na TNB e meu próprio desafio anterior .
fundo
O decimal densamente compactado (DPD) é uma maneira de armazenar com eficiência dígitos decimais em binário. Ele armazena três dígitos decimais (000 a 999) em 10 bits, o que é muito mais eficiente que o BCD ingênuo (que armazena um dígito em 4 bits).
Tabela de conversão
O DPD foi projetado para converter facilmente entre os bits e os dígitos, através de um simples padrão de correspondência de cima para baixo. Cada padrão de bits define quantos dígitos altos (8-9) o número possui, onde estão e como mover os bits para formar a representação decimal.
A seguir, a tabela de conversão de 10 bits do DPD para três dígitos decimais. Cada dígito decimal é representado como binário de 4 bits (BCD). Ambos os lados são escritos da esquerda para a direita, do dígito mais significativo para o mínimo.
Bits => Decimal (Digit range)
a b c d e f 0 g h i => 0abc 0def 0ghi (0-7) (0-7) (0-7)
a b c d e f 1 0 0 i => 0abc 0def 100i (0–7) (0–7) (8–9)
a b c g h f 1 0 1 i => 0abc 100f 0ghi (0–7) (8–9) (0–7)
g h c d e f 1 1 0 i => 100c 0def 0ghi (8–9) (0–7) (0–7)
g h c 0 0 f 1 1 1 i => 100c 100f 0ghi (8–9) (8–9) (0–7)
d e c 0 1 f 1 1 1 i => 100c 0def 100i (8–9) (0–7) (8–9)
a b c 1 0 f 1 1 1 i => 0abc 100f 100i (0–7) (8–9) (8–9)
x x c 1 1 f 1 1 1 i => 100c 100f 100i (8–9) (8–9) (8–9)
Notações
- As letras minúsculas
a
parai
são os bits que são copiados para a representação decimal. 0
e1
são os bits exatos nos padrões de bits de entrada ou saída.x
bits são ignorados na conversão.
Tarefa
Construa um circuito lógico usando portas NAND de duas entradas para converter 10 bits de DPD em 12 bits de BCD.
Exemplos
Bits enfatizados são os bits de correspondência de padrão.
DPD Decimal BCD
0 0 0 0 0 0 0 1 0 1 005 0000 0000 0101
^
0 0 0 1 1 0 0 0 1 1 063 0000 0110 0011
^
0 0 0 1 1 1 1 0 0 1 079 0000 0111 1001
^ ^ ^
0 0 0 0 0 1 1 0 1 0 090 0000 1001 0000
^ ^ ^
0 0 0 1 0 1 1 1 1 0 098 0000 1001 1000
^ ^ ^ ^ ^
1 0 1 0 1 1 1 0 1 0 592 0101 1001 0010
^ ^ ^
0 0 1 1 0 0 1 1 0 1 941 1001 0100 0001
^ ^ ^
1 1 0 0 1 1 1 1 1 1 879 1000 0111 1001
^ ^ ^ ^ ^
1 1 1 0 0 0 1 1 1 0 986 1001 1000 0110
^ ^ ^ ^ ^
0 0 1 1 1 1 1 1 1 1 999 1001 1001 1001
^ ^ ^ ^ ^
1 1 1 1 1 1 1 1 1 1 999 1001 1001 1001
^ ^ ^ ^ ^
Critério de pontuação e vitória
A pontuação é o número de portas NAND de duas entradas usadas em seu circuito. A pontuação mais baixa vence.
Você pode definir pequenos componentes em termos de portas NAND de duas entradas e usá-los em sua construção final. Se um componente X
incluir N
portas NAND de duas entradas, cada uso será X
adicionado N
à sua pontuação. Para portas lógicas básicas, isso significa:
- NÃO: +1
- 2 entradas AND: +2
- 2 entradas OU: +3
- 2 entradas XOR: +4
fonte
a
ai
média e o processo de conversão. Siga as etapas, em vez de apenas mostrar exemplos e esperar que entendamos disso.Respostas:
45 NANDs (ou 43)
45 parece ser o mínimo absoluto, mas é possível alcançar 43 NANDs com um truque: supondo que os maiores números sejam codificados corretamente.
888, 889, 898, 899, 988, 989, 998, 999 devem ser codificados com os 2 MSB como 00, exigindo apenas 43 NANDs para decodificação.
No entanto, na especificação para decodificação, eles são especificados para serem ignorados, o que significa que podem ser qualquer coisa. É razoável supor que essa especificação mais livre possa exigir menos portais, mas o oposto é verdadeiro. São necessários 45 portões para isso. Essa economia pode trazer benefícios reais para circuitos reais.
Também encontrei circuitos que eram significativamente mais eficientes e mais rápidos, contendo mais alguns portões.
Desta vez, nenhuma imagem desenhada a lápis do circuito. Talvez mais tarde.
O circuito é apresentado em código Verilog óbvio, pronto para ser executado com o teste incluído.
Código Verilog:
fonte
65 62 6058 NANDsTomando as entradas como
i0
parai9
e as saídas comoo0
ao9, oa, ob
que temosEstrutura de teste Python para validar a correção da construção.
fonte