Serial Data and Binary Addition

Serial Data and Binary Addition

Okay, so we have now created a notion of a standardized grid on which our circuits will be built.  The next step involved a crucial design decision, one which will affect the design of every circuit in the computer.   The question is, what format will the data be in?  There are two big options:

  1. Parallel: A byte of data will be represented as one electron on each of eight separate wires.  The wires must be synchronized with each other.
  2. Series: A byte of data will be represented as eight electrons on a single wire, carefully timed to indicate where the word begins and ends.

Real-world processors of course use parallel data, but they also don’t need to worry much about timings (race conditions are real issues, but they are caused by entirely different reasons).  For example, if you are connecting 64 wires from one chip to another, and the outer wire is 5% longer than the inner wire, it doesn’t matter.  In cellular automata, the exact distances matter a lot.  If we want a 16-bit processor, that’s 16 bulky wires we would have to work around every corner (each of which will either flip their order or put them all out of sync).  We would also have to expend additional effort to flip the order of bits or adjust the spacing between wires in order to get the data buses to connect to our circuits.  The advantage of parallel data is processor speed (maybe?), the ability to stick with a more traditional architecture, and the ease of creating memory (maybe).

A corner for parallel data, drawn in Logisim.

Serial data has the advantage that a change in word size requires a lot less redesign of the hardware.  The only important factor is the distance between electrons, which matters for all circuits anyways.  Serial-based circuits are also much smaller, since there is simply 1 wire per input stream.  The downside is that serial data can sometimes be more clumsy to work with, since, by definition, circuits don’t see the entire word at once.  Without a special counter, the circuits can’t tell where words begin or end.  Performing “backwards” bitshifts is easy (with delay wire), but performing “forwards” bitshifts is hard (either using diagonal wiring to cut corners, or delaying everything else relative to the selected data).

We chose serial data for our project, primarily due to the vastly increased simplicity of wiring.  Our decision was made in part by the difficulty of constructing a binary adder.

The Binary Adder

In order to get a better idea of how the computer will end up looking/working, I decided to build something larger and more complex, something that I didn’t know ahead of time how it would work.  I chose to build a binary adder.  Part of the reason I chose an adder was that the process of binary addition involves “carry over” between bits, which requires interaction between the bits of a number.  Most of the other basic operations, like bitwise logic, are significantly simpler to implement.

The core of a binary adder is the full adder, which takes in three bits (A, B, and Carry-in) and outputs two bits (Sum and Carry-out).  Below is a circuit diagram, but keep in mind that the order of inputs doesn’t matter.

Logic diagram of a full adder.

The carry-in represents the “overflow” from the previous pair of bits, and carry-out represents the overflow from the current pair of bits.  For parallel data, a set of full adders is used, with the C_out of one adder hooked up as an input to the next.  Here is how a parallel adder would probably look for our computer, drawn with

Parallel binary adder. An implementation would require a substantial amount of delay wire. Sometimes, a carry-in wire is connected to the first full adder to allow for 1’s complement subtraction. Without a carry-in wire, the first full adder could be replaced by a half adder.

The idea behind a serial adder is much simpler: take a single full adder and loop the carry-out back around to carry-in.  In real electronics, this would require a flip-flop to temporarily hold/delay the carry bit, but in our circuits the delay is simply given by the loop of wire.  Serial adders, importantly, can only handle little-endian data, meaning that the least significant bit comes first.  This means that the binary number 011 refers to the decimal number 6 (rather than a 3 with a leading zero).

The creation of a series adder took a reasonable amount of effort, but here was our second working prototype (after a string of failures).  The first version was significantly larger.   You can see the red corners of the 3×5 tile bounding box.

Serial adder, with 101 (5) in the top input and 10111 (29) in the left input.

Below is an image showing the flow of information around this adder design. The carry loop is the length-22 loop in the bottom-right of the adder which rotates counter-clockwise, and this loop is packed with an AND, OR, and wire splitter.  As information flows into the adder, both inputs are split, with one pair going to an XOR and the other pair going to an AND.   The output of the XOR is split, with one half travelling straight to be XORed with the current carry value, resulting in the output value.  The other half is ANDed with the carry, which is then ORed with the output of the first AND gate to produce the next value of the carry loop.

Serial adder with arrows indicating data flow.

After an intense round of golfing, the following 2×3 tile design is probably final.  It has the exact same connectivity, but the wires have been shortened.  Since both designs are “lagless” and “linear,” this more compact version is superior in literally every way.

Current best binary serial adder design, shown with inputs of 11 (3) and 011 (6).
Data flow of compressed adder.

What Did We Learn?

We learned a couple things about how our computer will end up functioning:

  1. It will use serial data (a sequence of electrons on a single wire to represent a word).
  2. The spacing between electrons (well, the places where an electron could be) will be 22 ticks.  I do have some potential worries about 22-tick technology, though, since it might lead to the creation of a lot more of multi-tile components whenever data needs to flow in a 22-tick loop.  Some technology (graphics, global clock, etc.) might still use 11-tick technology.
  3. We will probably use 2’s complement, since it does not require us to preset the carry-in of an adder.  This might mean, however, that subtraction would be broken down into two steps: negation and addition.  We would have a 2’s complement converter/command.

Leave a Reply

Your email address will not be published. Required fields are marked *