Building Bigger

For anything more complicated than simple logic expressions, designing systems using Boolean expressions or gate-level schematics quickly becomes unbearably tedious and difficult to extend or maintain.

Consider something like binary addition. Addition is combinational -- you can write a truth table with all possible combinations of the inputs, and the outputs that should result from them -- so it is possible to write a Boolean expression for each output and/or design a gate schematic for a circuit that performs addition. But even 4-bit + 4-bit addition means there are eight inputs, so the resulting schematic would be fairly complicated, and that still only adds very small numbers. Imaging trying to design a circuit that adds 8-bit numbers, or, for that matter, 64-bit numbers like most modern processors use!

The way to solve this problem is using hierarchical design. In hierarchical design, a small system is designed -- something that performs a useful but tractable operation -- and then that system is abstracted into a functional component. The word functional points out that you (the human with limited space in your head) no longer care exactly what's inside it; you only care about what it does -- its function.

Once useful components have been designed, they can then be integrated into a larger system to perform more complicated operations. The process of abstraction and integration can be repeated with the larger systems to make even larger systems, until the desired overall functionality is complete.

Since this process resembles building a tower with blocks, the individual components are sometimes referred to as "building blocks."

Binary Adder

Addition was mentioned because it makes a good first example. When we (as humans) add two numbers, we don't add them all at once (assuming the numbers are larger than a couple digits) -- we break the problem down into smaller pieces that we then bring together for a final answer. There are, of course, many strategies for addition, but the simplest is to start at the least-significant digit and perform addition on each place value, including a carry from the previous place value when needed. So a small but useful operation would be to add single digits. The inputs to this operation would be the two single digits being added as well as a carry in from the previous place value, and the outputs would be the sum for this place value and the carry to the next place value. Since that same functionality is required for every place value, a single-digit full adder (the name given to the functionality just described) could be copied as many times as needed to create an adder of any desired size.

For binary numbers, adding single digits is particularly easy, since each digit can only be 1 or 0. In this table, inputs A and B are the digits being added, Cin is the carry in, S is the sum, and Cout is the carry out:

Inputs			Outputs
Cin	A	B	S	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

You should find it straightforward to design a circuit that implements this truth table, and at this point, the specifics of the implementation no longer matter. Instead, the functionality can be encapsulated into a box:

Usually with components like this, the inputs are on the left and/or top and the outputs are on the right and/or bottom, but the atypical orientation in this case makes sense once several of these blocks are integrated to create a multi-bit adder. Since we (as humans) typically view numbers with the more-significant places to the left, it makes sense to lay out the schematic in that way. And since lower-significance places need to provide a carry value to higher-significance places, the carry out is placed on the left of each single-bit adder so that it can be directly connected to the carry-in of the next place value.

In the context of a multi-bit adder, the least-signifcant place value will never have a carry in, so that input needs to be driven with 0. It must be driven; inputs cannot be left floating. The inputs and outputs of the overall system then need to be labeled -- in this case, this system will take in two 4-bit binary values, A_3-0 and B_3-0, and will produce the sum, S_3-0. The final carry out could be included as an output of the system or it could be left unconnected; whichever is appropriate for the system being designed.

Remember, you are the engineer. The goal of all of this is for you to learn how to design digital hardware, not to memorize specific devices. Think about why things are the way they are and how they work, not just what they are.

This is called a ripple carry adder, because the carries "ripple" across the adder from the least- to most-significant place value. This entire system can then be abstracted away into a box of its own, and, for the purposes of designing larger circuits, the inputs denoted as whatever width is needed; the internals don't matter, just the functional behavior of how the device operates on its inputs to produce its outputs.

Adder / Subtractor

In the section on arithmetic, it was shown how subtraction can be achieved using addition: instead of doing long subtraction, the subtrahend can be negated and then the two numbers added. Taking advantage of the modular nature of fixed-width numbers, negation can be achieved by (in binary) inverting each bit and then adding 1. So, since an adder has already been designed, it would be beneficial to use it to help create a subtractor. And, since there would then necessarily be an adder in the system, it makes sense to design it so that either addition or subtraction could be performed, selectable with an additional control signal.

To summarize, the desired top-level functionality is:

• Numerical inputs A and B (of arbitrary width).
• An input to control whether addition or subtraction is performed.
• A numerical 'result' output of the same width as the inputs.

Specifying behavior at a slightly lower level,

• If the add/subtract control signal is at the "add" voltage level (currently unspecified if that will be high or low), the A and B inputs should be added, which can be achieved with the adder designed earlier.
• If the add/subtract control signal is at the "subtract" level, each bit of the B input should be inverted, 1 should be added, and A and this modified version of B should be added.

Part of this functionality requires a "selectable inverter" (to invert the bits of B when subtracting). A truth table for that would be

invert?	in value	out value
0	0	0
0	1	1
1	0	1
1	1	0

which is simply XOR. So a selectable inverter for an N-bit value would look like this (keeping in mind that this is specifying four XOR gates -- one for each incoming signal -- but with all of them sharing one of the inputs):

For the "add one" functionality needed for negating B, it would be a waste to include another entire adder, because the adder designed earlier already has that capability: the carry in. Mathematically, the carry in, when 1, represents a 1 added to the least-significant place value (in other words, a '1'), so instead of driving that with a constant 0, it can be used as an input to provide the ability to add 1 when needed (i.e. when subtraction is desired). It can still be driven low when the "add one" behavior is not needed.

Conveniently, the signal that controls inverting B inverts B when it is 1, and that is also when 1 needs to be added to negate B, so those signals can be connected. When that signal is 0, B is not inverted and 1 is not added, which causes the result to be the normal addition of A and B. Thus, this signal effectively controls whether this system adds or subtracts: when 0, the result is A+B, and when 1, the result is A+/B+1, which works as A-B. An appropriate name for this control signal would be Add/Sub.

This naming scheme, where the behavior and associated logic level are described in the name, is very often used for control signals in digital systems. For example, a signal that controls reading or writing might be named W/R (typically pronounced "W R-bar" or "write not read") to indicate that "read" occurs when the signal is low and "write" occurs when it is high. A different engineer might choose to label the signal "WE" for "write enable", or RE for "active-low read enable." It just depends on the context, desired perspective, and applicable conventions.

The overall system then looks like this, which of course can be encapsulated and used as an "adder/subtractor" building block in a larger system.

Line Decoders

A common need that arises in digital systems is "there are several things, and I need to be able to select one at a time." For example, there could be eight indicator lights on some machine, but only one should be on at a time. Since only one needs to be on at a time, it would be overkill to have a control signal for each light, since that would allow for all 256 combinations of lights, most of which have multiple lights lit. Instead, it often makes more sense to use the minimal number of control signals. In this case, since there are only eight situations that need to be resolved (one for each lit light), three control signals is sufficient to represent them (since those three signals can be 000, 001, 010, etc. -- eight total combinations). However, those control signals then need to be decoded into the eight individual signals, with one being high depending on the state of the inputs.

In other words, the desired truth table would look like this:

Inputs			Outputs
A2	A1	A0	D7	D6	D5	D4	D3	D2	D1	D0
0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	1	0	0	0	0	0	0	1	0	0
0	1	1	0	0	0	0	1	0	0	0
1	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0
1	1	0	0	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	0

This device is called a line decoder, or sometimes binary decoder. Its symbol is a simple box with inputs and outputs; for example, a 2-to-4 line decoder's symbol typically looks like this:

This one also an an enable input. The most sensible behavior for the enable input (on this device!) would be to make all of the outputs low when the device is disabled. In the scenario from above, the enable could be used to turn all of the lights off.

The internals of a line decoder are surprisingly simple: each output is the relevant minterm of the inputs, so, e.g., the expression for output D5 is D5=A2·A1·A0. Including the enable would just make that D5=EN·A2·A1·A0

Priority Encoders

If the purpose of a line decoder is to take what is effectively a number and "decode" it into a single active output, then the purpose of an encoder should be the opposite: monitor many inputs and "encode" which one is active. For example, if there are eight signals, but only one will be active at a time, then that information can be encoded into only three bits (essentialy a number 0-7) representing which input is active. In other words, the desired truth table is:

Inputs								Outputs
A7	A6	A5	A4	A3	A2	A1	A0	E2	E1	E0
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	1	0	0	0	0	1	1
0	0	0	1	0	0	0	0	1	0	0
0	0	1	0	0	0	0	0	1	0	1
0	1	0	0	0	0	0	0	1	1	0
1	0	0	0	0	0	0	0	1	1	1

However, this truth table is incomplete: with eight inputs, there should be 256 rows. The problem is that although these are the only situations that fundamentally matter (based on the desired behavior of the device), it is still possible for multiple inputs to be active, and the truth table must describe what happens in those situations.

An elegant solution to this problem is to introduce a priority to the inputs. For example, you could decide that A7 has the highest priority -- that means that if A7 is active, no matter the other input values, the output will encode "7". Then, if A7 is not active, A6 could have the next-highest priority, which would mean that it would be encoded if active, regardless of A5-0. This concept can be expressed in the truth table using "don't cares":

Inputs								Outputs
A7	A6	A5	A4	A3	A2	A1	A0	E2	E1	E0
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	X	0	0	1
0	0	0	0	0	1	X	X	0	1	0
0	0	0	0	1	X	X	X	0	1	1
0	0	0	1	X	X	X	X	1	0	0
0	0	1	X	X	X	X	X	1	0	1
0	1	X	X	X	X	X	X	1	1	0
1	X	X	X	X	X	X	X	1	1	1

But there is still one combination of inputs unaccounted for: all 0s. Based on the purpose of the device, there is no good way to handle that situation. Outputting all 0s would be ambiguous with "input 0 is active." Instead, one way to handle it would be to add a new output specifically for that situation: an input that means "at least one input is active," which could be named "valid."

Inputs								Outputs
A7	A6	A5	A4	A3	A2	A1	A0	E2	E1	E0	V
0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

Now the truth table is complete.

Multiplexers and Demultiplexers

Another common need in digital systems is the ability to route information to different places. It could be that one of several sources of information needs to be routed to one destination, or one source of information needs to be routed to one of several destinations. This is where multiplexers and demultiplexers come in.

Multiplexers

A multiplexer (often shortened to "mux") selects one of several input signals and routes it to a single output line. The selection is controlled by additional input signals known as select lines. For example, a 4-to-1 multiplexer has four data inputs and two select inputs, since 2² = 4. An 8-to-1 mux would need three select lines.

The truth table for a 4-to-1 multiplexer, where the data inputs are I_3-0, the select lines are S_1-0, and the output is M, is as follows:

S1	S0	M
0	0	I0
0	1	I1
1	0	I2
1	1	I3

Note that signal names on devices like these don't have standard names. Some engineers use subscripts, some engineers use different letters, some engineers use longer or shorter names.

The schematic symbol for a multiplexer is sometimes drawn as a simple box, but often it uses a trapezoid tapering down towards the output to symbolize the idea that one of the many inputs is being "funneled down" to the output.

Demultiplexers

A demultiplexer (often shortened to "demux") performs the opposite function of a mux: it takes a single input signal and routes it to one of several output lines based on select inputs.

For instance, a 1-to-4 demultiplexer has one data input, four outputs, and two select inputs.

The truth table for a 1-to-4 demultiplexer is:

S1	S0	A0	A1	A2	A3
0	0	D	0	0	0
0	1	0	D	0	0
1	0	0	0	D	0
1	1	0	0	0	D

Note how the output in this table is defined in terms of one of the inputs (D). That still means that the output is defined for all combinations of all inputs, and so this is still a complete and valid truth table.

The schematic symbol for a demux resembles the mux, but with reversed roles for inputs and outputs.

Other Building Blocks

The concept that this text calls a "building block" does not have a strict definition -- it is simply the application of hierarchical design principles to common, general-purpose pieces of digital hardware. Other common digital devices that could be considered "building blocks" are shifters (for performing the various types of shifts discussed in a previous section), and various types of registers (which will be seen later). The reason why the ones above are included in this introductory course is because they are extremely common, and so every engineer needs to understand what they are and how they behave.