Jak implementuje się sprzętowo całkowitą liczbę całkowitą bez znaku?

10

Pracuję nad projektem, który wymaga wielu maksymalnych funkcji (i maksymalnych funkcji jako argumentów dla innych maksymalnych funkcji).

Starając się uprościć projektowanie sprzętu, zastanawiałem się, w jaki sposób max jest implementowany w sprzęcie?

Matematycznie Max (a, b) można przedstawić jako [(a + b) + abs (b - a)] / 2.

Czy tak to jest zaimplementowane w sprzęcie? (tzn. etapami; dodawanie, podział przesunięcia bitów itp.)

Jeśli tak, w jaki sposób oblicza się wartość bezwzględną różnicy?

digital-logic James
źródło

10

Bardzo prostym podejściem byłoby wdrożenie (a> b)? A: b. a> b można zaimplementować, zaczynając od lewej i sprawdzając każdą parę bitów (a, b):

oba 0 lub oba 1: przejdź do następnej niższej pary
a wynosi 1: a jest najwyższy; b wynosi 1: b jest najwyższy

Kiedy wiesz, który z nich jest najwyższy, możesz go wybrać za pomocą multipleksera 2N-> N.

Przy pewnym sprytnym trikowaniu sprawdzanie par bitów można połączyć z multiplekserem dla tej samej pary bitów.

Wouter van Ooijen
źródło

2

Spójrzmy na algorytm w pytaniu:

[(a + b) + abs(b - a)]/2

Ma to etapy dodawania i odejmowania, które następnie wprowadza się do dodawania drugiego etapu. Podział na 2 jest trywialny pod względem sprzętowym, można tego dokonać poprzez usunięcie LSB. Jednak dwustopniowy pełny sumator / odejmator jest dość powolny i wymaga dużej ilości bramek, szczególnie jeśli kaskadujesz wiele znaków tak jak ty.

Opierając się na odpowiedzi Woutera van Ooijena, uogólniona struktura jest cyfrowym komparatorem zasilającym wybrany sygnał multipleksera:

schematyczny

^{symulacja tego obwodu - Schemat utworzony przy użyciu CircuitLab}

Powyższy schemat dotyczy:

(A > B) ? A : B

zauważ jednak, że można go łatwo zmienić w celu dowolnego porównania między dwoma wejściami, tworząc różne logiczne połączenia między wyjściami komparatora a wyborem multipleksera.

Jeśli więc wiemy, jak sformułować trzy wyjścia z komparatora, możemy zaimplementować dowolne porównanie sprzętowe. Logika komparatora jest tutaj dobrze opisana . Aby zoptymalizować sprzęt, po prostu usunę logikę napędzającą nieużywane wyjścia komparatora.

Ale ostatecznie, jeśli chodzi o sprzęt, musi przejść syntezę. Dlatego nie powinieneś mieć obsesji na punkcie tego, który schemat poziomu bramki jest optymalny. Zamiast tego zoptymalizuj kod i algorytmy, aby przynajmniej nie zmuszać syntezatora do uzyskania nieefektywnego wyniku. „Przy odrobinie sprytnego trikowania sprawdzanie par bitów można połączyć z multiplekserem dla tej samej pary bitów”, a najłatwiejszym sposobem przeprowadzenia tej optymalizacji jest synteza.

Travisbartley
źródło

1

Jeśli naprawdę chcesz zbudować specjalistyczny obwód do obliczenia maksimum, możesz zacząć od podstawowego bloku z następującymi równaniami:

\begin{array}{rcl} E_{i, o u t} & \leftarrow & E_{i, i n} \land \neg (a_{i} \oplus b_{i}) \\ L_{i, o u t} & \leftarrow & (\neg E_{i, i n} \land L_{i, i n}) \lor (E_{i, i n} \land a_{i} \land \neg b_{i}) \\ r_{i} & \leftarrow & (\neg E_{i, i n} \land ((L_{i, i n} \land a_{i}) \lor (\neg L_{i, i n} \land b_{i}))) \lor (E_{i, i n} \land (a_{i} \lor b_{i})) \end{array}

$\begin{eqnarray} E_{i,out} &\leftarrow& E_{i,in} \wedge \neg (a_i \oplus b_i) \\ L_{i,out} &\leftarrow& (\neg E_{i,in} \wedge L_{i,in})\vee (E_{i,in} \wedge a_i \wedge \neg b_i)\\ r_i &\leftarrow& (\neg E_{i,in} \wedge ((L_{i,in} \wedge a_i) \vee (\neg L_{i,in} \wedge b_i))) \vee (E_{i,in} \wedge (a_i \vee b_i)) \end{eqnarray}$

a następnie połącz je z najbardziej znaczącą cyfrą podającą następną. Część krytyczna przechodzi z MSB do LSB, podczas gdy obwód oparty na odejmowaniu będzie miał co najwyżej krytyczną ścieżkę prowadzącą z LSB do MSB, a następnie z powrotem do LSB.

Jest to odpowiednik sumatora tętnienia do noszenia. Jeśli jesteś zainteresowany, możesz zbudować ekwiwalent dla adderów carry-save lub carry-select.

$E$ $L$ $\neg E$ $a$

AProgrammer
źródło

Jak implementuje się sprzętowo całkowitą liczbę całkowitą bez znaku?

Odpowiedzi: