HTSEFP: Digital logic - combinational logic

1Drawing combinational logic circuits¶

Given an expression, draw a combinational logic circuit that implements it. Optionally: use only a subset of the available logic gates.

1.1General solution¶

The logic gates appear as follows:

Type	Shape	Expression
AND		$A \cdot B$
OR		$A + B$
NOT		$\overline A$
NAND		$\overline{(A \cdot B})$
NOR		$\overline{(A + B)} = \overline A \cdot \overline B$
XOR		$A \oplus B = (A \cdot \overline B) + (\overline A \cdot B)$

Just remember what each gate looks like and you should be set. To branch a wire into two, use a black dot.

If you can only use certain gates, for example only NAND gates, then write out the truth tables for the allowed gates and think about how to use them.

1.2Examples¶

• Exercises 2, questions 1 (a) and 4

2Writing out truth tables¶

Given an expression, write out its truth table.

2.1General solution¶

Kind of like writing truth tables for propositional formulas, only with different notation for the operators (+ instead of $\lor$, $\cdot$ instead of $\land$, $\overline{A}$ instead of $\neg A$, etc).

2.2Examples¶

• Exercises 2, question 1 (b)

3Sums of products and products of sums¶

Given an expression $Y$, write it out as a sum of products and/or as a product of sums.

3.1General solution¶

3.1.1Sums of products¶

Identify the rows that result in a 1 in the truth table. Same concept as finding the disjunctive normal form in propositional logic.

3.1.2Products of sums¶

Identify the rows that result in a 0 in the truth table, and write it as $\overline{Y} = (\overline A \cdot B \cdot C) + (...)$ or whatever. Then take the negative and apply De Morgan's laws recursively until the expression is a product of sums. As an example (taken from exercises 2, question 1):

$$Y = (A \cdot B) + \overline{(A \cdot C)} \cdot \overline{B}$$

The truth table appears as follows:

The relevant rows are the third, the fifth, and the sixth, which can be written as follows:

$$\overline{Y} = (A \cdot \overline B \cdot C) + (\overline A \cdot B \cdot C) + (\overline A \cdot B \cdot \overline C)$$

We then negate both sides:

$$\begin{align}Y & = \overline{(A \cdot \overline B \cdot C) + (\overline A \cdot B \cdot C) + (\overline A \cdot B \cdot \overline C)} \\\ & = \overline{(A \cdot \overline B \cdot C)} \cdot \overline{(\overline A \cdot B \cdot C)} \cdot \overline{(\overline A \cdot B \cdot \overline C)} \\ & = (\overline A + B + \overline C) \cdot (A + \overline B + \overline C) \cdot (A + \overline B + C) \end{align}$$

and so the final line is the product-of-sums representation.

The sum-of-products representation is much easier - one step, usually. In this case, it's $(A \cdot B \cdot C) + (A \cdot B \cdot \overline C) + (A \cdot \overline B \cdot \overline C) + (\overline A \cdot \overline B \cdot C) + (\overline A \cdot \overline B \cdot \overline C)$.

3.2Examples¶

• Exercises 2, questions 1 (c) and (d), 2, 3 and 5 (a) and (b)

4Read-only memory¶

Explain how a circuit can be used as a read-only memory (ROM).

4.1General solution¶

If the inputs are ordered, then the sequence of bits representing their values (e.g. 1000 if there are four inputs and only the first one is on) can be thought of as a memory address. The sequence of bits representing the output variables - $Y_0, Y_1, Y_2$ etc - can be thought of as the value at that memory address. Since the gates are fixed, the same input bit sequence results in the same output bit sequence every time, and so this is read-only.

Note that both the input and the output variables are ordered in a ROM.

4.2Examples¶

• Exercises 2, question 5 (c)

5Drawing circuits of multiplexors¶

Given some sort of multiplexor situation and specific inputs, draw out the combinational logic circuit.

5.1General solution¶

A multiplexor is a circuit in which one or more of the input variables acts as a selector, essentially choosing which of the other input variables to allow through.

If an input is not a single bit, but rather composed of many bits (e.g. an integer greater than, well, 1) then we draw a slash through the wire and write out the number of bits used. This shouldn't really change anything.

In any case, draw a box for the decoder (drawing the entire diagram shouldn't be required, but if it is, that section is below), and draw some input and some output wires for it. If there are $n$ input variables, then the decoder should have $n$ output wires and $\log_2 n$ input wires (e.g. 1-to-2, 2-to-4, 3-to-8, 4-to-16, etc). Each of the wires from the decoder should be ANDed with one of the input variables, with a 1 for wire ANDed with the selected variable and a 0 for all the others. Then, all the AND gates should be ORed. The final output should be the same as that of the selected variable. This is quite straightforward; see the examples below.

5.2Examples¶

• Exercises 2, questions 6 and 9

6Labeling wires in a circuit¶

Given an adder/subtractor circuit diagram and the input numbers, label all the wires or fill in some truth table about the circuit.

6.1General solution¶

6.1.1Carrying out addition with a circuit¶

First, a bit of a background. We can figure out the type of circuit needed to perform addition by drawing the truth table for the first sum and carry bit:

From the truth table, it's clear that $S_0$ can be produced using an XOR gate, and $C_0$ can be produced using an AND gate. This circuit (known as a half adder) looks something like this:

We can then compute the truth table for the $i$th sum and $i+1$th carry bit, with $A_i$, $B_i$, and the previous carry bit given as input, as follows:

The $i$th sum bit can be represented by:

$$S_i = (A_i \cdot B_i \cdot C_i) + (A_i \cdot \overline B_i \cdot \overline C_i) + (\overline A_i \cdot B_i \cdot \overline C_i) + (\overline A_i \cdot \overline B_i \cdot C_i)$$

and the $i+1$th carry bit can be represented by:

$$C_i = (A_i \cdot B_i \cdot C_i) + (A_i \cdot B_i \cdot \overline C_i) + (A_i \cdot \overline B_i \cdot C_i) + (\overline A_i \cdot B_i \cdot C_i)$$

The combinational circuitry (known as the full adder) for representing the above truth table might look like this:

We then connect the $C_{i+1}$ output to the full adder for the next $i$, resulting in a ripple adder¹ (as diagrammed in the lecture notes for lecture 4).

(We can represent the above circuit diagram as a big box with + written inside it and the necessary inputs and outputs, since it's too complex to have to draw multiple times for every ripple adder.)

6.1.2Subtraction and circuits¶

Instead of building a whole other circuit for subtraction, we use the fact that $A-B = A + (-B)$ and simply add $A$ and the negative of $B$. To add the negative of B, we take its two's complement, which can be done mechanically by flipping all the bits and adding one (by setting the initial carry bit to 1). To flip all the bits and set the initial carry bit to 1, we use a variable called Binvert², which specifies whether we're doing addition or subtraction and selects accordingly. (If it's 1, we're subtracting; if it's 0, we're adding.)

6.1.3Labeling an adder/subtractor circuit¶

Write the numbers A and B in binary, using twos complement. For each bit, figure out the sum and the carry bit. If it's a subtraction, set Binvert to 1 and allow the required bit-flipping and initial carry to propagate.

6.1.4Truth tables and adder/subtractor circuits¶

Same idea as labeling, only write it in a table. For example, in exercises 2, question 7, we get the following truth table for the entire operation:

So the sum of 98 and 25 is 1111011_two, which is 123 in decimal, exactly as it should be.

Note that this could be computed simply by converting the numbers to signed binary (same number of bits) and adding them, since that is what an adder circuit purports to do anyway.

6.1.5Overflow and adder circuits¶

We can mechanically determine the situations in which overflows happen by first constructing a truth table for this. Overflows can only happen when A and B are the same sign and the sum is the opposite sign. We can then draw a 16-line truth table in 4 variables (Binvert, $A_{n-1}$, $A_{n-1}$, and $S_{n-1}$) with the output variable being overflow detection (1 if there is an overflow, 0 if there is not.) The solution for question 11 in exercises 2 explains this pretty well.

6.2Examples¶

• Exercises 2, questions 7, 8 and 11

7Encoder truth tables¶

Given the situation for an encoder, draw the truth table.

7.1General solution¶

Easy enough. Just figure out the mapping from each input to each output and construct the truth table from that. See the example below. (Note that in the example, 9 can be drawn in two ways: with $L_3$, and without. Both should be correct.)

7.2Examples¶

• Exercises 2, question 10

8Decoder circuit diagrams¶

Given the truth table for a decoder, draw the circuit diagram.

8.1General solution¶

For each output variable $Y_i$, find the logic gate (or series of logic gates) best suited to represent that variable from the input parameters. This is pretty simple - the trick is to treat each output variable separately. For example, for the 1-to-2 decoder mentioned in the notes for lecture 4, we have the following truth table:

and so we can easily see that $Y_1 = \overline A$ and $Y_2 = A$, resulting in the following circuit diagram:

For the 2-to-4 decoder mentioned on the same page of the lecture notes, we have the following truth table:

$Y_1$ can be produced using a NOR gate, $Y_2$ with $(\overline A \cdot B)$, $Y_3$ with $(A \cdot \overline B)$, and $Y_4$ with an AND gate, resulting in the following circuit diagram:

8.2Examples¶

• Just the lecture notes