In a quiz on computer organization, we were asked the following question:
Design an arithmetic circuit that has two selection variables ( $\mathrm{S}_0$ and $\mathrm{S}_1$ ), and two 3-bit inputs ($A$ and $B$ registers). The circuit generates four operations as shown in the table below. Draw the logic diagram of the circuit (3 stages ( three stages mean only do three bits –)).
$S_1$ $S_0$ O/P 0 0 1ドル-A$ 0 1 $B-1$ 1 0 2ドルB+A$ 1 1 $-B-1$
I was unsure how to implement this because each full adder only takes two inputs and a carry-in, but the operations seem to require three inputs in some cases (e.g., 2ドルB + A$).
I tried using two full adders per bit, but I got confused about how to handle the carry bits of the first FA of every bit.
Some of my classmates mentioned that this can be done using only one full adder per bit, but I couldn't figure out how.
-
$\begingroup$ This isn't optimal, but a half adder allows you to compute the xor and the and of two inputs. xor can be used to compute the negation of an input. So you can create a nand gate with adders. Hence, you can create any logic circuit with just half adders. $\endgroup$Alan Abraham– Alan Abraham2025年04月19日 22:15:11 +00:00Commented Apr 19 at 22:15
-
$\begingroup$ @AlanAbraham Could you please show me how you did it? I’d really appreciate a step-by-step explanation if you have time. Thanks! $\endgroup$user163790– user1637902025年04月20日 07:34:03 +00:00Commented Apr 20 at 7:34
-
$\begingroup$ Tackle the problem from the other side (possibly complementing this question in the process): What is a level; what would be each level in a solution? $\endgroup$greybeard– greybeard2025年04月21日 05:31:34 +00:00Commented Apr 21 at 5:31
-
$\begingroup$ @greybeard three level mean only do three bits $\endgroup$user163790– user1637902025年04月21日 08:26:56 +00:00Commented Apr 21 at 8:26
-
2$\begingroup$ For 2ドルB+A$ you can first multiply $B$ by 2ドル$ (by doing a left shift) and then adding that with $A$. It's a major pain to draw out logic circuits and then also submit the image on this website, I doubt you're going to get much help on that side. $\endgroup$Alan Abraham– Alan Abraham2025年04月21日 13:51:16 +00:00Commented Apr 21 at 13:51
1 Answer 1
There is exacly one operation calling for a full addition: 2ドルB+A$ -
let the last level be an adder.
Operation 1ドル-A$ can be implemented as 2ドル+\neg A$, $B-1$ as $B+\neg 0$, and $-B-1$ simply as $\neg B+0$ -
the middle level could use a 4:1 selector for the first adder input, and a true/complement/zero/one element, or just another 4:1 selector for the second one.
The first level would comprise one ($\neg B$) or two ($\neg A$, too) complementors/bunches of inverters.
Overflow detection or saturation arithmetic would require additional effort.
-
$\begingroup$ "Operation 1ドル-A$ can be implemented as 2ドル+\neg A,ドル $B-1$ as $B+\neg 0,ドル and $-B-1$ simply as $\neg B+0$ - " can you elaborate on how you arrived at this $\endgroup$user163790– user1637902025年04月22日 20:58:51 +00:00Commented Apr 22 at 20:58
-
$\begingroup$ Not really, I'm afraid: each was immediate/obvious to me. Beginning with 2ドルB$ not needing an adder at all, but "shifting to the left"/routing to the next adder bit, $−B−1$ being the one's complement, ... $\endgroup$greybeard– greybeard2025年04月22日 21:59:05 +00:00Commented Apr 22 at 21:59
-
1$\begingroup$ @ppp In two's complement representation, -A = (NOT A) + 1, so (-B - 1) = NOT B, etc. As greybeard points out, computation of 2B does not need any actual work, just proper routing to the inputs of the MUX (multiplexer); this is known as a "wire shift" in technical jargon. $\endgroup$njuffa– njuffa2025年04月23日 04:59:18 +00:00Commented Apr 23 at 4:59