Inspiriert von der jüngsten Beliebtheit von Nandgame auf TNB und meiner eigenen vorherigen Herausforderung .
Hintergrund
Dicht gepackte Dezimalstellen (DPD) sind eine Möglichkeit, Dezimalstellen in Binärform effizient zu speichern. Es speichert drei Dezimalstellen (000 bis 999) in 10 Bit, was viel effizienter ist als naives BCD (das eine Stelle in 4 Bit speichert).
Umrechnungstabelle
DPD ist so konzipiert, dass eine einfache Umwandlung zwischen den Bits und den Ziffern durch einfachen Musterabgleich von oben nach unten möglich ist. Jedes Bitmuster definiert, wie viele hohe Stellen (8-9) die Zahl hat, wo sie sich befindet und wie die Bits verschoben werden, um die Dezimaldarstellung zu bilden.
Das Folgende ist die Umwandlungstabelle von 10 Bit DPD in drei Dezimalstellen. Jede Dezimalstelle wird als 4-Bit-Binärzahl (BCD) dargestellt. Beide Seiten werden von links nach rechts von der höchstwertigen bis zur niedrigsten Stelle geschrieben.
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)Notizen
- Die Kleinbuchstaben
abisisind die Bits, die in die Dezimaldarstellung kopiert werden. 0und1sind die genauen Bits in den Eingabe- oder Ausgabebitmustern.xBits werden bei der Konvertierung ignoriert.
Aufgabe
Erstellen Sie eine logische Schaltung, indem Sie NAND-Gatter mit zwei Eingängen verwenden , um 10 Bit DPD in 12 Bit BCD zu konvertieren.
Beispiele
Hervorgehobene Bits sind die Mustervergleichsbits.
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
^ ^ ^ ^ ^Bewertungs & Gewinnkriterium
Die Punktzahl ist die Anzahl der NAND-Gatter mit zwei Eingängen, die in Ihrer Schaltung verwendet werden. Die niedrigste Punktzahl gewinnt.
Sie können kleine Komponenten in Form von NAND-Gattern mit zwei Eingängen definieren und diese dann in Ihrer endgültigen Konstruktion verwenden. Wenn eine Komponente Xenthält Nzwei Eingang - NAND - Gatter, jede Verwendung von Xfügt , Num Ihre Gäste. Für grundlegende Logikgatter bedeutet dies:
- NICHT: +1
- AND mit 2 Eingängen: +2
- ODER mit 2 Eingängen: +3
- XOR mit 2 Eingängen: +4
quelle
aiAntworten:
45 NANDs (oder 43)
45 scheint das absolute Minimum zu sein, aber es ist möglich, 43 NANDs durch einen Trick zu erreichen: Unter der Annahme, dass die größten Zahlen korrekt codiert sind.
888, 889, 898, 899, 988, 989, 998, 999 sollen mit 2 MSB als 00 codiert werden, was nur 43 NANDs zum Decodieren erfordert.
In der Dekodierungsspezifikation sind sie jedoch so festgelegt, dass sie ignoriert werden. Dies bedeutet, dass sie alles Mögliche sein können. Es ist eine vernünftige Annahme, dass diese freiere Spezifikation noch weniger Gatter erfordern könnte, aber das Gegenteil ist der Fall. Hierfür sind 45 Tore erforderlich. Diese Einsparung könnte echte Vorteile für echte Schaltungen bringen.
Ich fand auch Schaltungen, die wesentlich effizienter und schneller waren und ein paar weitere Gates enthielten.
Diesmal ist kein vom Bleistift gezeichnetes Bild der Schaltung zu sehen. Vielleicht später.
Die Schaltung wird in offensichtlichem Verilog-Code dargestellt und ist mit eingeschlossenem Test zum Laufen bereit.
Verilog-Code:
quelle
65 62 6058 NANDsNimmt man die Eingaben wie
i0aufi9und die Ausgänge wieo0zuo9, oa, obhaben wirPython-Test-Framework zur Überprüfung der Korrektheit der Konstruktion.
quelle