Inspirado por la reciente popularidad de nandgame en TNB y mi propio desafío anterior .
Antecedentes
El decimal denso (DPD) es una forma de almacenar eficientemente dígitos decimales en binario. Almacena tres dígitos decimales (000 a 999) en 10 bits, que es mucho más eficiente que el BCD ingenuo (que almacena un dígito en 4 bits).
Tabla de conversión
DPD está diseñado para convertir fácilmente entre los bits y los dígitos mediante una simple coincidencia de patrones de arriba a abajo. Cada patrón de bits define cuántos dígitos altos (8-9) tiene el número, dónde están y cómo mover los bits para formar la representación decimal.
La siguiente es la tabla de conversión de 10 bits de DPD a tres dígitos decimales. Cada dígito decimal se representa como binario de 4 bits (BCD). Ambos lados se escriben de izquierda a derecha desde el dígito más significativo hasta el menos.
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)Anotaciones
- Las letras minúsculas
aaison los bits que se copian en la representación decimal. 0y1son los bits exactos en los patrones de bits de entrada o salida.xlos bits se ignoran en la conversión.
Tarea
Construya un circuito lógico utilizando puertas NAND de dos entradas para convertir 10 bits de DPD a 12 bits de BCD.
Ejemplos
Los bits enfatizados son los bits de coincidencia de patrones.
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
^ ^ ^ ^ ^Criterio de puntuación y ganador
El puntaje es el número de compuertas NAND de dos entradas utilizadas en su circuito. El puntaje más bajo gana.
Puede definir componentes pequeños en términos de compuertas NAND de dos entradas y luego usarlas en su construcción final. Si un componente Xincluye Ncompuertas NAND de dos entradas, cada uso de Xagrega Na su puntaje. Para puertas lógicas básicas, esto significa:
- NO: +1
- 2 entradas Y: +2
- 2 entradas O: +3
- XOR de 2 entradas: +4
fuente
aqueisignifican las letras y el proceso de conversión. Siga los pasos, en lugar de solo mostrar ejemplos y esperar que entendamos a partir de eso.Respuestas:
45 NAND (o 43)
45 parece ser el mínimo absoluto, pero es posible alcanzar 43 NAND mediante un truco: suponiendo que los números más grandes están codificados correctamente.
888, 889, 898, 899, 988, 989, 998, 999 deben codificarse con 2 MSB como 00, lo que requiere solo 43 NAND para la decodificación.
Sin embargo, en la especificación de decodificación, se especifica que se ignoran, lo que significa que pueden ser cualquier cosa. Es una suposición razonable que esta especificación más libre podría requerir incluso menos puertas, pero lo contrario es cierto. Se requieren 45 puertas para esto. Este ahorro podría dar beneficios reales para circuitos reales.
También encontré circuitos que eran significativamente más eficientes y rápidos, que contenían algunas puertas más.
No hay imagen dibujada a lápiz del circuito esta vez. Quizás mas tarde.
El circuito se presenta en código Verilog obvio, listo para ejecutarse con prueba incluida.
Código Verilog:
fuente
65 62 6058 NANDTomando como las entradas
i0ai9y las salidas comoo0parao9, oa, obque tenemosMarco de prueba de Python para validar la corrección de la construcción.
fuente