13
\$\begingroup\$

I'm trying to design a parallel prefix adder for a negabinary based adder. Negabinary is base \$-2\$ instead of the familiar base \$2\$ binary. Each 1 bit adder generates a sum and two (instead of one in binary) carries that go to the next adder.

To make the adder faster, I want to use a parallel prefix structure, like the Ladner-Fischer structure given below. I'm familiar with the functionality of the purple cell in the binary system, but I'm unsure how I could get the same functionality in the negabinary system.

The reason I'm doing this is just for fun, I haven't found any uses for negabinary yet.

Formulas for calculating the sum and carries:

\$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^-} \$

Ladner-fischer carry tree structure:

enter image description here

If anything is unclear, please don't hesitate to ask.

\$\endgroup\$
7
  • \$\begingroup\$ While this may be an interesting question, it doesn't seem to be an electrical question, and you may have better luck taking it to the math SE. \$\endgroup\$
    – Redja
    Commented May 23, 2017 at 12:52
  • 3
    \$\begingroup\$ I put it here because I think EE people have more experience with carry logic, designing adders etc. \$\endgroup\$
    – gilianzz
    Commented May 23, 2017 at 13:29
  • \$\begingroup\$ This is totally an EE question \$\endgroup\$
    – Voltage Spike
    Commented May 24, 2017 at 18:59
  • \$\begingroup\$ Seems like you need more than two outputs per carry. Don't you need generate and propagate for both carry and borrow? \$\endgroup\$
    – stark
    Commented May 26, 2017 at 18:35
  • \$\begingroup\$ I'm assuming you're talking about the Ladner-fischer structure. It was just an example to show off a parallel prefix tree. Each 1 bit negabinary adder outputs a sum, a positive and a negative carry. I'm unsure if we can use the concepts of generate and propagate with negabinary. \$\endgroup\$
    – gilianzz
    Commented May 26, 2017 at 20:01

1 Answer 1

1
\$\begingroup\$

I have probably spent more time on this question than I should've, but here are my findings.

I cannot find any example of a "pure" parallel prefix adder for negabinary numbers. I also think it's an open problem, as I haven't seen any proof that it isn't possible.

The closest I can get you is by using a two-step negative negabinary addition (commonly abbreviated n.n.b.a. in literature). It is based on the following property:

Let \$f(x) = \overline{x_{n-1}}x_{n-2}...\overline{x_1}x_0\$ and \$g(x) = x_{n-1}\overline{x_{n-2}}...x_1\overline{x_0}\$. These are basically an XOR-operation with 0xAA...AA and 0x55...55 respectively. You can then prove that

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

Where the left side is the negabinary sum \$+_{nb}\$, while the \$+\$ on the right side is a normal binary sum.

The negative sum can then simply be inverted using the same property but with a zero operand:

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

So in order to find the sum using parallel prefix adders, you can:

  1. Compute \$f(a)\$ and \$f(b)\$, ie. by inverting every odd bit of the negabinary numbers
  2. Compute the regular binary sum while setting the carry bit for the LSB (the \$+1\$), leading to a first intermediary sum \$s_1\$.
  3. Invert all bits of \$s_1\$ (this is \$f(g(s_1))\$). This is the finish of the first sum, while also starting the inversion.
  4. Increment the result by 0xAA...AB (\$=f(0)+1\$) using a parallel prefix adder, yielding the second intermediary sum \$s_2\$
  5. Compute \$g(s_2)\$ (inverting each even bit) to find the final negabinary sum.

I have actually tried to find a "pure" parallel prefix adder, but I considered it too complex for the time I was willing to spend on it. Here's why:

The whole point of parallel prefix adders is to find some operation of \$\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n\$ that allows you to easily calculate the (in this case 2) carries from these bits. As an added constraint, the operation needs to be associative to be computed in parallel. For example, this basically excludes any NOT operator (that is not part of a double negation). For example: \$a \circ b=a\cdot \bar b\$ is not an associative operator, because

$$\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}$$

Note that the boolean operator for the carries in your question includes the mixed terms \$c_i^+\overline{c_i^-}\$ and \$c_i^-\overline{c_i^+}\$, making it impossible to use it as-is. For a single carry in normal binary addition, it became quite obvious how to construct this operator when thinking about it in terms of generation and propagation, but it seems to be not so obvious for negabinary carries.

\$\endgroup\$
2
  • \$\begingroup\$ My current understanding is that it is in fact impossible to construct this "pure" parallel prefix adder. It would seem that a parallel prefix adder can get an efficiency of O(log(N)), whereas a negabinary equivalent seems to always have complexity O(2*log(N)) (2x n.n.b.a). \$\endgroup\$
    – gilianzz
    Commented Jun 15, 2018 at 21:11
  • \$\begingroup\$ I didn't find any literature proving or stating that it was impossible. I'd be happy to be proven wrong either way though. But the 2-step n.n.b.a. does seem to be the standard currently for negabinary addition as far as I can tell. \$\endgroup\$
    – Sven B
    Commented Jun 16, 2018 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.