The Digital Digest No 1

Alright, per request of others, I've been putting together a quick tutorial/guide for some of the basics of digital logic and computer microarchitecture, and the techniques that may seem like magic to some of you. As a forewarning, I received my masters degree in electrical engineering, with a focus on computer processor architecture. That said, a lot of this seems very easy to me now, and I may miss some key points. If I go too fast, or make a leap that is intuitive only to me, speak up! My feelings won't be hurt, but it's kind of be pointless to do this if no one can follow it. Now then, I was thinking it would be nice to first have a quick how to on processor internals, but looking back, theres a fair amount of background information and I thought that it might warrant a quick description by itself. Basic computer processors are next, promise!

The Digital Digest No 1
Digital Logic, Arithmetic, and Memory

To fully understand digital logic, a deep background in electronics is not required, although an understanding of logical reasoning is indispensable. Just as one may guess, the basic digital logic gates 'AND', 'OR', and 'NOT' match the logical operations of the same name. For example:

- 'A AND B' is true when both inputs A and B are true, and false otherwise.
- 'A OR B' is true when either inputs A or B are true, and false otherwise.
- 'NOT A' is true when A is false, and false when A is true

These logical gates have symbols that are standardized by the IEEE as well (below)

These symbols are used in logical diagrams that typically represent small networks of transistors that perform those simple operations, with inputs on the left and outputs on the right. Inputs and outputs are represented by the logical values "true" and "false," by the numeric values 1 or 0, or by the raw voltage levels on the connection as high or low voltage. Thus, these symbols are connected by drawing lines from the output of one symbol to any number of inputs on other symbols. These lines represent single wires, with connections between wires represented by dots over the intersection. The only catch is that a network of wire can only be attached to one output at a time, otherwise two gates may output different voltages simultaneously, leading to an electrical short. Which of course, is as bad as it sounds.

From this, its relatively easy to form certain simple circuits to do useful things. One of the simplest is using an AND gate to mask out an input with an enable signal. Imagine that an arbitary bit (0 or 1) is sent to one input of an AND, with an enable signal to the other. When the enable is 1, the input bit is passed through. However, when the enable is 0, regardless of the input bit, the output is always 0. This effect can be reversed by passing the enable signal through a NOT gate first, effectively inverting the enable and turning it into a masking signal instead. With the inverted enable present, the AND outputs the input only when the is 0 (before it is inverted). The utility of this comes when you use a single enable signal to mask out one of two inputs to 0 depending on the value of your enable. The output of these can then be combined in an OR gate, which will effectively output only one of the two inputs. This forms the basis of a selector circuit, more commonly known as a multiplexor, which can be combined with other multiplexors to select between many inputs. While seemly simple, this is a required piece of many designs. A simple two-input multiplexor (MUX in shorthand) is shown below:

Using similar logic, we can create simple adding circuits. Given that in binary arithmetic, 1 + 1 = 10, 0 + 1 = 1 + 0 = 01, and 0 + 0 = 00, we can write simple logical expressions for the first and second output bits, the sum and carry based on two inputs, A and B. The carry is 1 whenever both inputs are 1, so the carry is simply ``A AND B.'' While the sum is 1 whenever A is 1 and B is 0, or when A is 0 and B is 1. This could be expressed as "( A AND NOT B ) OR ( NOT A AND B )", however it's more frequently expressed as XOR(exclusive or), and given its own logical symbol (similar to the OR gate with an extra line, and seen below).

Now its worth noting that although this simple circuit does generate a carry output, it cannot handle a carry input (needed for chained arithmetic). Hence, this is known as a half-adder. By chaining the sum of one half adder into another half adder, using the other input for the incoming carry, we can add three bits into a sum. The carry of both half adders can be simply combined within an OR gate to generate a carry out from the three input bits. Thus we have a full-adder, that can add two inputs, while handling an input and output carry (see below).

So, why bother with the extra carry lines? The answer is to use multiple full adders in combination to add numbers larger than one bit at a time. By laying out each full adder in a row, and connecting the appropriate carry out to the carry input of the next in the chain. Inputs for each are combined from the A inputs to form a larger bus of data, and again with the B inputs. The input carry is typically tied to '0', and the final carry out left unconnected if not needed. However, this can be extended to an adder of any size, by using enough full-adders, and connecting the carry lines, similar to snapping together toy building bricks. This carry chain can perform a number of additive carries at sequentially, leading to a sort of ripple effect through the design. This leads to the name of ripple carry adder. The design for a four-bit adder is seen below, with four copies of the above diagram represented as empty boxes having the correct input/outputs. This is a "black box" representation, useful for showing higher level connections between components without drawing each and every logic gate. Also, note that the four bit inputs for A and B are broken up into their respective bits, 3 down to 0 with 3 being the most significant digit.

Finally, the last bit of digital magic that allows us to maintain state and save information. We use a special logic gate called NAND, whose operation is effectively ``NOT( A AND B ),'' and whose symbol reflects the combined symbols of AND and NOT. With this we can create what is commonly known as a flip-flop or latch. By combining two NAND gates, fed from one another, we have a logical construct that actually has two stable states. As an exercise, imagine that the S and R inputs are both set to 1, and that Q is a value you choose (0 or 1). Depending on the current value of Q, the NAND gates maintain that value.

Now, if your brain hasn't choked on this, thats good. If not, let us consider this odd, cross-wired design in a simple way. When this construct is created, Q may not have been something we have explicitly set, or may be holding a previous value from a previous use. So, we can use the set ( S ) and reset ( R ) inputs to control the Q output. While this may seem complicated, understand that if the set line is held at 1, while reset is held at 0, regardless of the current value of Q, Q will be forced to 0. Similarly, if set is held at 0, while reset is held at 1, the output is forced to 1. Once a value is set, we leave set and reset at 1, and Q stays the same until we need to change the value again.

Note that this simple structure is known as an asynchronous circuit, meaning that it is not synchronized to anything in particular. In practice, most digital circuits are locked to a known clock signal, which is simply a "01010101" pattern, alternating at a known rate. To make use of this, flip-flops are typically connected to additional logic which latches incoming data based on a clock changing from 0 to 1 (or vice versa), toggling the appropriate set and reset lines internally. However, as that logic gets messy quickly, it will be left as an exercise to interested readers.

For the rest, it is safe to assume that the easiest flip flop to understand is what is known as a D flip-flop, which latches incoming data from a 'D' input bit, if an enable is set to 1 while the clock is transitioning from 0 to 1. More simply, they check once per clock period if the enable is set, and load the D input to the Q output. In the future, this is the sort of memory that I will be referring to, in hopes of keeping things reasonably simple.

My apologies for the length, but I'm hoping that non-technically inclined folks will be able to follow some of this. If the diagrams or anything else are unclear, lemme know. I'll try to explain as best I can.

This post has been edited by MisterGrae: 17 October 2007 - 06:32 PM