Zainspirowany niedawną popularnością nandgame na TNB i moim własnym poprzednim wyzwaniem .
tło
Gęsto upakowany ułamek dziesiętny (DPD) to sposób na skuteczne przechowywanie cyfr dziesiętnych w formacie binarnym. Przechowuje trzy cyfry dziesiętne (od 000 do 999) w 10 bitach, co jest znacznie wydajniejsze niż naiwny BCD (który przechowuje jedną cyfrę w 4 bitach).
Tabela konwersji
DPD jest zaprojektowany do łatwej konwersji między bitami a cyframi poprzez proste dopasowanie wzoru od góry do dołu. Każdy wzorzec bitów określa, ile wysokich cyfr (8–9) ma liczba, gdzie się znajdują i jak przesuwać bity, aby utworzyć reprezentację dziesiętną.
Poniżej znajduje się tabela konwersji z 10 bitów DPD na trzy cyfry dziesiętne. Każda cyfra dziesiętna jest reprezentowana jako 4-bitowy układ binarny (BCD). Obie strony są pisane od lewej do prawej, od najbardziej znaczącej cyfry do najmniejszej.
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)
Notacje
- Małe litery
a
toi
są bity, które są kopiowane do reprezentacji dziesiętnej. 0
i1
są dokładnymi bitami we wzorcach bitów wejściowych lub wyjściowych.x
bity są ignorowane podczas konwersji.
Zadanie
Zbuduj obwód logiczny za pomocą dwuwejściowych bramek NAND do konwersji 10 bitów DPD na 12 bitów BCD.
Przykłady
Bity podkreślone to bity pasujące do wzorca.
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
^ ^ ^ ^ ^
Kryterium punktacji i wygranej
Wynik to liczba dwuwejściowych bramek NAND używanych w twoim obwodzie. Najniższy wynik wygrywa.
Możesz zdefiniować małe elementy w kategoriach bramek NAND z dwoma wejściami, a następnie użyć ich w swojej ostatecznej konstrukcji. Jeśli komponent X
zawiera N
bramki NAND z dwoma wejściami, każde użycie X
dodaje N
do wyniku. W przypadku podstawowych bramek logicznych oznacza to:
- NIE: +1
- 2-wejściowe ORAZ: +2
- 2-wejściowe OR: +3
- 2-wejściowy XOR: +4
źródło
a
nai
myśli i proces przekształcania. Wykonaj kolejne kroki, zamiast tylko pokazywać przykłady i mieć nadzieję, że to zrozumiemy.Odpowiedzi:
45 NAND (lub 43)
45 wydaje się być absolutnym minimum, ale możliwe jest osiągnięcie 43 NAND za pomocą sztuczki: Zakładając, że największe liczby są poprawnie zakodowane.
888, 889, 898, 899, 988, 989, 998, 999 należy zakodować za pomocą 2 MSB jako 00, co wymaga jedynie 43 NAND do dekodowania.
Jednak w specyfikacji dekodowania są one ignorowane, co oznacza, że mogą być dowolne. Jest rozsądnym założeniem, że ta bardziej swobodna specyfikacja może wymagać jeszcze mniejszej liczby bramek, ale jest odwrotnie. Wymagane jest do tego 45 bramek. Ta oszczędność może dać realne korzyści dla prawdziwych obwodów.
Znalazłem również obwody, które były znacznie wydajniejsze i szybsze, zawierające kilka dodatkowych bramek.
Tym razem nie rysowano ołówkiem obrazu obwodu. Może później.
Obwód jest przedstawiony w oczywistym kodzie Verilog, gotowy do uruchomienia z dołączonym testem.
Kod Verilog:
źródło
65 62 6058 NANDBiorąc jak wejść
i0
doi9
i wyjść jako0
doo9, oa, ob
mamyFramework testowy Pythona do sprawdzania poprawności konstrukcji.
źródło