Friday, June 18, 2010

Digital Logic in Reason: 8-bit Full Adder

On the Propellerhead's Users Forum, user fieldframe likened my 16-bit counter to a calculator that some clever person had implemented in the successful PS3 game "LittleBIGPlanet":

It was a very generous comparison - I'm sure that person spent a lot longer than I did on their amazing creation. I'm not going to go to such extraordinary lengths to do anything like this in Reason. Well, not for a little while anyway, but it did give me the idea to implement a simple 8-bit adder.
This article contains some introductory explanations of digital logic - you may already know some or all of this, but if you don't then I hope you find this informative.

An 8-bit adder takes two 8-bit binary numbers, and adds them together to give a result. For example, 85 (01010101b in binary) summed with 60 (00111100b) gives 145 (10010001b). I'm only concerned with unsigned numbers in this article.

The heart of the classical digital adder is the 1-bit full adder - a relatively simple device that takes three digital inputs and produces two digital outputs:
  • A and B are single bit inputs representing the two 1-bit numbers to be summed ("addends")
  • input Cin is a single bit input that is usually tied to zero but can accept a carry overflow from a previous adder unit when multiple adders are chained together.
  • output S is a single bit output that is the binary sum of A and B.
  • output Cout is a single bit output that is high if the sum resulted in a carry.
This image is used under the Creative Commons Attribution ShareAlive 3.0 license.

This device is combinational rather than sequential or synchronous because it makes no use of internal state - there are no flipflops or clock signals. Everything happens as soon as the inputs change. A counter is (usually) a sequential circuit - it has internal state (the current count) and that only changes when the clock rises. Generally, sequential circuits are much more interesting than combinational circuits, but you need working combinational circuits to create interesting sequential circuits, so for this project I'm concentrating on creating a robust combinational device.

Quick aside: A OR B (inclusive OR) means (A or B) or (A and B), whereas A XOR B (eXclusive OR) means (A or B) but not (A and B). i.e. one or the other but not both.

A 1-bit Full Adder outputs:
  • S as high if A and B are different and Cin is low, or A and B are the same and Cin is high. i.e. (A XOR B) XOR Cin.
  • Cout as high if either A & B are both high, or (A XOR B) and Cin are both high.
The schematic for this circuit can be drawn as:

By placing multiple Full Adders together side-by-side with their Carry inputs and outputs connected it is possible to create a wider Full Adder, such as this 8-bit one:

This image is derived from this source and distributed under the same Creative Commons Attribution ShareAlike 3.0 license.

Each bit of addend A (A7..A0) goes into a separate 1-bit Full Adder along with its counterpart from the other addend B (B7...B0). The result is simply the collection of outputs S (S7...So). However, in the event that this eight bit result overflows, the last carry Cout will be set, so the result is essentially a nine-bit number Cout + S (CoutS7...So).

This is essentially the way I've constructed my 8-bit adder, which you can play with here.

For the purposes of my demonstration, to set the 8-bit inputs A and B the following section in the rack is used:

Each input has two combinators associated, with buttons labeled 0 to 7. These represent the bits within the 8-bit input number. Each bit in an unsigned binary number has a weight dependent on its position. Button 0 is the least significant bit with a weight of 1, and 7 is the most significant bit, with a weight of 128. The value of a binary number is the sum of the weights for positions where a 1 appears and these eight buttons can be used to set this. Therefore the buttons represent the ones and zeros in an 8-bit unsigned binary number.

For example, the following represents a digital 0 input:

00000000b = 0*128 + 0*64 + 0*32 + 0*16 + 0*8 + 0*4 + 0*2 + 0*1 = 0

Whereas this represents 71:

01000111b = 0*128 + 1*64 + 0*32 + 0*16 + 0*8 + 1*4 + 1*2 + 1*1 = 71

And of course this represents 255:

11111111b = 1*128 + 1*64 + 1*32 + 1*16 + 1*8 + 1*4 + 1*2 + 1*1 = 255

By setting up A and B, you'll see the sum on the "A + B" Vocoder near the bottom. This example shows 85 + 60 = 145:

01010101b + 00111100b = 10010001b

This example (255 + 1 = 256) shows what happens when the eight bit sum overflows into the final carry output, and becomes nine bits:

11111111b + 00000001b = 100000000b

So how did I construct a 1-bit Full Adder? Look at the schematic diagram again:

You'll notice that the device is made up from two XOR gates, two AND gates and an OR gate. I already have these from my 16-bit counter project, so I can simply wire them up here (after fixing a minor bug in the AND gate):

Because I was able to implement two XOR gates and two AND gates in a single Thor instance, I only need three Thor devices (XOR2, AND2, OR2) to implement this adder. Cool. But what's that fourth Thor for?

It turns out that in Reason, CV signals are not limited to the operational range 0-127. It appears that, with Thor at least, it is possible to go beyond these limits to some degree. As the value gets bigger it eventually reaches a point where the Thor "mod scaling" fails if it uses this value. Normally an input signal of zero scaled by a CV value of 127 gives zero, but if the scaling factor is high enough it seems that Thor's multiplication goes a bit nuts and zero times a large CV value is some other large CV value. This causes the AND gate to fail - you get: (low AND high) gives "high", which is wrong.

In this application, there are four upstream logic gates (Thor instances) that contribute to the Cout signal and this seems to push the CV value too high when all the inputs are high. So the final Thor is used to hard-limit the final Cout output to the range 0-127, using the hard-clip mode of Thor's shaper with minimum drive. Therefore the nasty large CV value is squashed back into the expected 0-127 range and everything downstream works properly again.

The shaper buffer.

For a bit of fun, this is what part of the back of the rack looks like once everything is wired up:


After all that, what use is this adder? Well, for one it helps validate my logic gates - the more things like this that work, the more confidence I have that my designs are working properly. Secondly, with a few changes, this will be the basis for a subtractor, which will then allow me to differentiate a CV signal, which is a measurement of the signal's slope at a point in time. This opens the door to CV integration, where CV signals can be integrated over time by simply keeping a running sum. This is essentially the same as measuring the area under the curve. Integrators and differentiators are an important part of many circuits, including feedback systems, so perhaps I can find some musical use for this yet.

Of course, if you have any good ideas, please let me know or feel free to try building something yourself with the files and ideas I've shared.

For reference, I include my combinational logic gate test-bench (version 0.0.4) - bipolar NOT, XOR, AND and OR gates for your use. Enjoy.

Files in this post:

The examples in this article require Reason 4 or newer.

No comments:

Post a Comment