Równoległe komórki sumujące przedrostek w Negabinary

Usiłuję zaprojektować równoległy sumator prefiksów dla sumatora opartego na negabinary. Negabinary to podstawa zamiast znanego binarnego base . Każdy 1-bitowy sumator generuje sumę i dwa (zamiast jednego w formacie binarnym) przeniesienia przechodzą do następnego sumatora. $-2$ $2$

Aby przyspieszyć dodawanie, chcę użyć równoległej struktury przedrostka, takiej jak podana poniżej struktura Ladnera-Fischera. Znam funkcjonalność fioletowej komórki w systemie binarnym, ale nie jestem pewien, jak mógłbym uzyskać tę samą funkcjonalność w systemie negabinarnym.

Powodem, dla którego to robię, jest po prostu dla zabawy, nie znalazłem jeszcze żadnych zastosowań dla negabary.

Wzory do obliczania sumy i przenosi:

$s_i = a_i \oplus b_i \oplus (c_i^+ + c_i^-)$

$c_{i+1}^+ = \overline{a_i}\overline{b_i}\overline{c_i^+}c_i^-$

$c_{i+1}^- = a_ib_i\overline{c_i^-}+a_i c_i^+ \overline{c_i^-}+b_i c_i^+ \overline{c_i^-}$

Struktura drzewa Ladner-Fischera:

Jeśli coś jest niejasne, nie wahaj się zapytać.

digital-logic adder

— gilianzz
źródło

Chociaż może to być interesujące pytanie, nie wydaje się to pytaniem elektrycznym i lepiej mieć szczęście, biorąc je na matematykę SE.

— Redja

Umieściłem to tutaj, ponieważ uważam, że ludzie z EE mają większe doświadczenie w logice przenoszenia, projektowaniu dodatków itp.

— gilianzz

To jest całkowicie pytanie EE

— skok napięcia

Wygląda na to, że potrzebujesz więcej niż dwóch wyników na przeniesienie. Czy nie potrzebujesz generować i propagować zarówno dla noszenia, jak i pożyczania?

— surowy

Zakładam, że mówisz o strukturze Ladnera-Fischera. To był tylko przykład pokazania równoległego drzewa prefiksów. Każdy 1-bitowy sumator ujemny generuje sumę, przeniesienie dodatnie i ujemne. Nie jestem pewien, czy możemy użyć koncepcji generowania i propagowania z negabinary.

— gilianzz

Prawdopodobnie spędziłem więcej czasu na tym pytaniu niż powinienem, ale oto moje ustalenia.

Nie mogę znaleźć żadnego przykładu „czystego” równoległego sumatora przedrostków dla liczb ujemnych. Myślę też, że to otwarty problem, ponieważ nie widziałem żadnego dowodu, że nie jest to możliwe.

Najbliżej, jak mogę cię zdobyć, jest zastosowanie dwuetapowego negatywnego dodatku negabinarnego (często w literaturze skróconego nnba). Opiera się na następującej właściwości:

Niech i . Są to w zasadzie operacje XOR z odpowiednio i . Następnie możesz to udowodnić $f(x) = \overline{x_{n-1}}x_{n-2}...\overline{x_1}x_0$ $g(x) = x_{n-1}\overline{x_{n-2}}...x_1\overline{x_0}$ 0xAA...AA0x55...55

- (a +_{n b} b) = g (f (a) + f (b) + 1)

$-(a +_{nb} b) = g\left(f(a) + f(b) + 1\right)$

Gdzie lewa strona jest sumą ujemną , podczas gdy po prawej stronie jest normalną sumą binarną. $+_{nb}$ $+$

Suma ujemna może być po prostu odwrócona przy użyciu tej samej właściwości, ale z operandem zerowym:

- x = g (f (x) + f (0) + 1)

$-x = g\left(f(x) + f(0) + 1\right)$

Aby więc znaleźć sumę przy użyciu równoległych sumatorów prefiksów, możesz:

Oblicz i , tj. odwracając każdy nieparzysty kawałek liczb ujemnych $f(a)$ $f(b)$
Oblicz regularną sumę binarną, ustawiając bit przenoszenia dla LSB ( ), prowadząc do pierwszej sumy pośredniej . $+1$ $s_1$
Odwróć wszystkie bity (to jest ). To jest koniec pierwszej sumy, a zarazem rozpoczęcie inwersji. $s_1$ $f(g(s_1))$
Zwiększ wynik o 0xAA...AB( ) przy użyciu sumatora równoległego prefiksu, uzyskując drugą sumę pośrednią $=f(0)+1$ $s_2$
Oblicz (odwracając każdy parzysty bit), aby znaleźć ostateczną sumę negabinarną. $g(s_2)$

W rzeczywistości próbowałem znaleźć „czysty” równoległy sumator prefiksów, ale uznałem, że jest to zbyt skomplikowane na czas, jaki chciałem na to poświęcić. Dlatego:

Cały punkt dodawania równoległych prefiksów polega na znalezieniu operacji która pozwala łatwo obliczyć (w tym przypadku 2) przenosi z tych bitów. Jako dodatkowe ograniczenie operacja musi być asocjacyjna, aby mogła być obliczana równolegle. Na przykład, w zasadzie wyklucza to dowolny operator NOT (który nie jest częścią podwójnej negacji). Na przykład: nie jest operatorem asocjacyjnym, ponieważ $\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ $a \circ b=a\cdot \bar b$

\begin{aligned} (a \circ b) \circ c & = a \cdot \bar{b} \cdot \bar{c} \\ a \circ (b \circ c) & = a \cdot \bar{b \cdot \bar{c}} \end{aligned}

$\begin{align} (a\circ b)\circ c &= a\cdot \bar b \cdot \bar c\\ a\circ (b \circ c) &= a\cdot \overline{b \cdot \bar c} \end{align}$

Zauważ, że operator logiczny dla przeniesień w twoim pytaniu zawiera mieszane terminy i , co uniemożliwia użycie go takim, jakim jest. W przypadku pojedynczego przeniesienia w normalnym dodatku binarnym stało się całkiem oczywiste, jak skonstruować tego operatora, gdy myśli się o nim w kategoriach generowania i propagacji , ale wydaje się, że nie jest to takie oczywiste w przypadku przeniesień ujemnych. $c_i^+\overline{c_i^-}$ $c_i^-\overline{c_i^+}$

— Sven B.
źródło

Moje obecne rozumienie jest takie, że w rzeczywistości niemożliwe jest zbudowanie tego „czystego” równoległego sumatora przedrostka. Wydawałoby się, że równoległy sumator prefiksów może uzyskać wydajność O (log (N)), podczas gdy równoważnik negabinaryjny zawsze wydaje się mieć złożoność O (2 * log (N)) (2x nnba).

— gilianzz

Nie znalazłem żadnej literatury dowodzącej lub stwierdzającej, że jest to niemożliwe . Byłbym szczęśliwy, gdyby okazało się, że i tak się mylę. Ale o ile mi wiadomo, 2-etapowa nnba wydaje się być standardem dla dodawania negabinarnego.

— Sven B,