5
\$\begingroup\$

You can use cascaded full adders to add any two binary numbers together. Is there a circuit for when I only want to add 1 (incrementing the value)? Is there a similar circuit for subtracting (i.e. adding 0b1111 1110)? I'm working with 8 bit numbers, but this applies for all word lengths.

\$\endgroup\$
  • 2
    \$\begingroup\$ A circuit besides a full adder? You could just use one where one set of inputs is static, either 00...01 (++) or FF...FF (--) You could optimize/eliminate some of the input gates with the knowledge of constant inputs. \$\endgroup\$ – Nick T Dec 14 '10 at 15:45
  • \$\begingroup\$ @Nick T, I was thinking of doing this but wasn't certain how to approach it. \$\endgroup\$ – Thomas O Dec 14 '10 at 15:53
  • \$\begingroup\$ You could feed the carry-in line, but I suspect you don't have access to silicon... \$\endgroup\$ – tyblu Dec 14 '10 at 22:50
4
\$\begingroup\$

Let's see. In a simple ripple carry adder, sum,carry-out = a + b + carry-in

c[0] = carry-in
for i in n
    sum[i] = a[i] ^ b[i] ^ c[i]
    c[i+1] = (a[i]&b[i]) | (a[i]&c[i]) | (b[i]&c[i])
carry-out = c[n]

Now if we want to compute sum,carry-out = a + 0 + 1, set b[] = all 0 and simplify:

c[0] = 1
for i in n
    sum[i] = a[i] ^ c[i]
    c[i+1] = a[i] & c[i]
carry-out = c[n]

which is simpler. Subtraction by 1 can be similarly simplified (exercise for reader: what is b[] and carry-in in that case?)

Happy hacking!

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

If you're talking about discrete logic, like 7400 series logic, then the chip you're looking for is called a counter. Two 74191 (4-bit up/down synchronous counter) chips cascaded will give you what you want, and there are other chips that do a similar function.

If you want the most compact way to add '1', then you could use half-adders for each bit instead of full adders. Not too sure about subtraction though.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks. I'm considering building a transistor computer so whereever I can save transistors it is good. \$\endgroup\$ – Thomas O Dec 14 '10 at 15:53
  • 4
    \$\begingroup\$ Transistor computers are easy to make when you're building the transistors on a single silicon wafer :) \$\endgroup\$ – W5VO Dec 14 '10 at 16:07
  • \$\begingroup\$ Food for thought, if you're talking about making a discrete transistor CPU: The Intel 4004 (4 bit CPU) has 2300 transistors (excluding main ROM/RAM, and I/O. \$\endgroup\$ – W5VO Dec 14 '10 at 17:01
  • \$\begingroup\$ @Thomas: I don't want to discourage you, but even the most simple CPU needs a few thousand transistors and the more components the greater the chance that something is wrong somewhere. I wouldn't want to debug it anyway. Why don't you build one with standard 74HCxx logic? This may increase your chances considerably, and it should be a serious challenge too. \$\endgroup\$ – stevenvh Dec 14 '10 at 17:14
  • 1
    \$\begingroup\$ @stevenvh Actually I should have written relay computer and it's been done before (web.cecs.pdx.edu/~harry/Relay/.) I doubt I'd actually build it, but it would be a design project to do in my spare time. \$\endgroup\$ – Thomas O Dec 14 '10 at 17:29
1
\$\begingroup\$

What you are looking for is a edge triggered T-triggers. Input = output of previous stage AND count clock.

Here is schematics for transistor-based T-trigger:

http://forum.cxem.net/index.php?app=core&module=attach&section=attach&attach_rel_module=post&attach_id=45908

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

In the diagrams, lines to the right are outputs and all others (from the top, bottom or left) are inputs.

next                 b0                     b1                   b2     
number   B0 ─ XOR ─┬──┘        B1 ─ XOR ─┬──┘        B2 ─ XOR ─┬──┘    
counter     ┌──┘   └─ NOT ─┐      ┌──┘   └─ NOT ─┐      ┌──┘   └─ NOT ─┐    
         1 ─┴──────────── AND ─c1─┴──────────── AND ─c2─┴──────────── AND ──  ...


c[0] = 1                 | Note: sum[i] =              c[ i ]      + B[i]
for i in n               |              =            2*c[i+1]      + b[i]
  b[ i ] =  B[i] ^ c[i]  |              =              c[i+1] <<1  + b[i]
  c[i+1] = ~b[i] & c[i]  |              = (~b[i]      & c[i]) <<1  + b[i]
carry-out = c[n+1]       |              =                        (B[i] ^ c[i]) +
                         |            (~(B[i] ^ c[i]) & c[i]) <<1  

If a half adder must be used:

                                                                    b[i]
B ────┬── XOR ────      to use a half   B[i] ──┬───────┬───── XOR ────┘     
    ┌──────┘   half     adder without          │   ┌─ XOR ─────┘
    │ └────┐   adder    circuit trace         XOR ─┤               
C ──┴──── AND ────      crossings you          │   └─ XOR ─────┐
                        can use this:   C[i] ──┴───────┴───── AND ─ c[i+1] ── ...

A simple decrement is a complemented negation: D-1 = ~-D.
Negation is 2's complement which is an incremented complement: -D = ~D +1.

Thus, D-1 = ~(~D +1), so a bit-wise combinational (parallel) complementation before and after a sequential incrementation suffices.

However, https://en.wikipedia.org/wiki/Half_subtractor the sequential decrement circuit is even simpler:

 previous                  d0                 d1                 d2     
  count       D0 ── XOR ─┬──┘    D1 ── XOR ─┬──┘    D2 ── XOR ─┬──┘    
(decrement)       ┌──┘   └──┐        ┌──┘   └──┐        ┌──┘   └──┐    
               1 ─┴─────── AND ─ b1 ─┴─────── AND ─ b2 ─┴─────── AND ──  ...

b[0] = 1                  
for i in n              
  d[ i ] =  D[i] ^ b[i]  
  b[i+1] =  d[i] & b[i]  
borrow-out = b[n+1]          
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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