Digital Logic

A digital computer is an electronic machine that processes data represented in discrete form, using the binary digits 0 and 1. It accepts input, processes it according to stored instructions, and produces output, performing arithmetic and logical operations with high speed and accuracy. Personal computers and laptops are examples.

A binary number is a number written in base 2 using only the digits 0 and 1. It can be classified as:

• Integer (whole) binary number, such as $1011_2$, with no binary point.
• Fractional binary number, such as $0.101_2$, with only digits after the binary point.
• Mixed binary number, such as $101.11_2$, with digits on both sides of the point.

Binary numbers can also be unsigned (magnitude only) or signed (sign-magnitude, 1's complement or 2's complement).

The 2's complement of a binary number is obtained by inverting every bit (the 1's complement) and then adding 1 to the result. It is used to represent negative numbers and to perform subtraction by addition.

Example: for $0101_2$ (5), the 1's complement is $1010$, and adding 1 gives $1011$, which represents $-5$ in 4 bits.

A gate is universal if the NOT, AND and OR operations can all be built from it alone. NAND can do this:

• NOT: tie both inputs together, $\overline{A\cdot A}=\bar A$.
• AND: a NAND followed by a NAND used as an inverter, $\overline{\overline{A\cdot B}}=A\cdot B$.
• OR: invert each input with a NAND, then NAND the results, $\overline{\bar A\cdot\bar B}=A+B$ (De Morgan's law).

Since every Boolean function can be written with AND, OR and NOT, NAND gates alone can implement any logic circuit.

Boolean algebra is the algebra of logic in which variables take only two values, 0 and 1 (false and true). It uses the operations AND ($\cdot$), OR ($+$) and NOT ($\bar{\ }$), and it is the mathematical basis for analysing and designing digital circuits.

SOP (Sum of Products) is a form of Boolean expression in which several product (AND) terms are ORed together. For example, $F = AB + \bar A C + BC$. When every product term contains all the variables, it is the canonical SOP, written as a sum of minterms, $F=\sum m(1,3,7)$.

A PLA (Programmable Logic Array) is a programmable logic device with a programmable AND array followed by a programmable OR array. Any set of Boolean functions in SOP form can be implemented by choosing which inputs form each product term and which product terms feed each output.

A flip-flop is a basic sequential circuit with two stable states. It stores one bit of information and keeps its output until a clock or trigger pulse changes it. It is the building block of registers, counters and memory. Examples are the SR, JK, D and T flip-flops.

A register is a group of flip-flops, one per bit, used to store a binary word (an $n$-bit register needs $n$ flip-flops). Registers may be used simply for storage or, with shift capability, for shifting data left or right (shift registers).

A ripple counter is an asynchronous counter in which only the first flip-flop receives the external clock. The output of each flip-flop clocks the next one, so the change "ripples" through the stages. An $n$-bit ripple counter counts through $2^n$ states.

Octal number system. It has base 8 and uses the digits 0 to 7. Each position carries a weight that is a power of 8, so $(345)_8 = 3\times8^2+4\times8+5 = 229_{10}$. Since $8=2^3$, one octal digit equals exactly 3 binary bits, so $(101\,110)_2=(56)_8$.

Hexadecimal number system. It has base 16 and uses the digits 0 to 9 and the letters A to F (A=10, B=11, C=12, D=13, E=14, F=15). Each weight is a power of 16, so $(2F)_{16}=2\times16+15=47_{10}$. Since $16=2^4$, one hex digit equals 4 binary bits, so $(1011\,1100)_2=(BC)_{16}$.

Both systems give a compact way to write long binary numbers and are widely used in computing, for example for memory addresses and machine codes.

Basic postulates, theorems and properties of Boolean algebra:

Other useful results are $A+\bar AB=A+B$ and the consensus theorem $AB+\bar AC+BC=AB+\bar AC$.

Duality. If every AND is swapped with OR, and every 0 with 1, in a valid identity, the result is also a valid identity. This is why each law above comes as a pair.

A don't-care condition is an input combination that never occurs, or whose output does not matter, so the function value for it may be taken as either 0 or 1. It is marked X (or d) in the truth table and K-map. Each X can be treated as 1 if that gives a larger group, and as 0 otherwise, which gives a simpler expression.

Example. A BCD digit detector gives $F=1$ for the digits 5 to 9 on inputs $ABCD$. The input combinations 1010 to 1111 never occur in BCD, so they are don't-cares:

$F=\sum m(5,6,7,8,9)+d(10,11,12,13,14,15)$

Using the don't-cares in the K-map, the cells 8 to 15 form one group giving $A$, the cells 5, 7, 13, 15 give $BD$, and the cells 6, 7, 14, 15 give $BC$. Therefore

$F = A + BD + BC$

Without the don't-cares the expression would need more literals, for example $A\bar B\bar C+\bar A B D+\bar A B C$.

A full adder adds three 1-bit inputs, $A$, $B$ and the carry-in $C_{in}$, and gives a sum $S$ and a carry-out $C_{out}$.

Truth table

Expressions (from the K-maps)

$S=A\oplus B\oplus C_{in}$

$C_{out}=AB+C_{in}(A\oplus B)=AB+BC_{in}+AC_{in}$

Circuit. Two half adders and an OR gate: the first half adder adds $A$ and $B$ to give $S_1=A\oplus B$ and $C_1=AB$. The second adds $S_1$ and $C_{in}$ to give $S$ and $C_2=C_{in}(A\oplus B)$. Finally $C_{out}=C_1+C_2$.

The D (data or delay) flip-flop has a single data input $D$ and a clock input. It is made from an SR flip-flop by connecting $S=D$ and $R=\bar D$ through an inverter, which removes the invalid state. On the active clock edge, the output $Q$ takes the value of $D$.

Characteristic equation: $Q_{next}=D$.

The output follows the input one clock period later, so it is used as a delay element, for storing one bit, and in registers and data latches.

A half subtractor computes $A-B$ with two outputs, the difference $D$ and the borrow $B_{out}$:

$D = A\oplus B,\qquad B_{out}=\bar A B$

Implementation with NOR gates only. Five NOR gates are used:

1. $X=\overline{A+B}$
2. $P=\overline{A+X}=\bar A\,(A+B)=\bar AB$, which is the borrow $B_{out}$
3. $Q=\overline{B+X}=\bar B\,(A+B)=A\bar B$
4. $Y=\overline{P+Q}$
5. $D=\overline{Y+Y}=P+Q=\bar AB+A\bar B=A\oplus B$

The last gate has its two inputs tied together and acts as an inverter. Thus $D=A\oplus B$ and $B_{out}=\bar AB$ are both obtained using NOR gates alone.

(a) 305

Hexadecimal, dividing by 16:

• $305 \div 16 = 19$ remainder $1$
• $19 \div 16 = 1$ remainder $3$
• $1 \div 16 = 0$ remainder $1$

Reading the remainders upwards, $305_{10}=(131)_{16}$.

Octal, dividing by 8:

• $305 \div 8 = 38$ remainder $1$
• $38 \div 8 = 4$ remainder $6$
• $4 \div 8 = 0$ remainder $4$

So $305_{10}=(461)_8$.

(b) 225

Hexadecimal:

• $225 \div 16 = 14$ remainder $1$
• $14 \div 16 = 0$ remainder $14$ (E)

So $225_{10}=(E1)_{16}$.

Octal:

• $225 \div 8 = 28$ remainder $1$
• $28 \div 8 = 3$ remainder $4$
• $3 \div 8 = 0$ remainder $3$

So $225_{10}=(341)_8$.

Check: $3\times64+4\times8+1=225$ and $14\times16+1=225$.

A K-map (Karnaugh map) is a graphical method of simplifying Boolean functions. A three-variable map has $2^3=8$ cells, one for each minterm. It is drawn as 2 rows by 4 columns (or 4 by 2). The columns are labelled in Gray code, 00, 01, 11, 10, so that adjacent cells differ in only one variable.

Rules of grouping. Group adjacent 1s in powers of two (1, 2, 4, 8). The groups can wrap around the edges, and may overlap. Use the largest possible groups. A group of $2^k$ cells eliminates $k$ variables.

Example. $F(A,B,C)=\sum m(1,3,5,7)$.

The four 1s form one group (columns 01 and 11). In this group $A$ and $B$ change and $C=1$ stays constant, so

$F=C$

Another example is $F=\sum m(0,2,4,6)$, which gives $F=\bar C$.

Triggering is the way a clock signal makes a flip-flop change state. There are two main types.

1. Level triggering. The flip-flop responds while the clock stays at a particular level (high or low). During that time the output follows changes in the input. This can cause race-around or multiple changes within one pulse, as in a simple JK latch with $J=K=1$.

2. Edge triggering. The flip-flop changes state only at the instant of a clock transition, so the input is sampled once per pulse.

• Positive (rising) edge triggered: changes on the 0 to 1 transition.
• Negative (falling) edge triggered: changes on the 1 to 0 transition. In symbols this is shown by a bubble at the clock input.

Example. A positive edge triggered D flip-flop with $D=1$ sets $Q=1$ only at the rising edge. If $D$ changes to 0 while the clock is high, $Q$ stays 1 until the next rising edge, when it takes the new value. Master-slave flip-flops also avoid race-around.

Ripple counter. A ripple counter is an asynchronous counter in which the clock pulse is applied only to the first flip-flop. The output of each flip-flop drives the clock of the next, so the change ripples through the stages. An $n$-bit counter has $2^n$ states, and the propagation delays add up, which limits the speed.

4-bit binary (up) ripple counter.

Use four JK flip-flops with $J=K=1$ (or T flip-flops with $T=1$), so each toggles when its clock input falls (negative-edge triggered).

• The external clock goes to $FF_0$, which gives $Q_0$ (LSB).
• $Q_0$ clocks $FF_1$, $Q_1$ clocks $FF_2$, and $Q_2$ clocks $FF_3$, which gives $Q_3$ (MSB).

Each stage divides the frequency by 2, so $Q_0=f/2$, $Q_1=f/4$, $Q_2=f/8$ and $Q_3=f/16$. It is a MOD-16 counter counting from 0000 to 1111, then returning to 0000.

Count sequence and timing.

Timing diagram (each column is one clock pulse, 1 means high):

CLK : _|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|
Q0  : 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1   toggles on every clock fall
Q1  : 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1   toggles when Q0 falls
Q2  : 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1   toggles when Q1 falls
Q3  : 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1   toggles when Q2 falls

Each waveform has half the frequency of the one before it. A down counter is obtained by clocking each stage from the $\bar Q$ output of the previous stage.

Difference between sequential and combinational logic

Steps to design a combinational circuit

1. Specification. State the problem and decide the number of inputs and outputs.
2. Assign symbols to the input and output variables.
3. Truth table. Write the output for every combination of inputs.
4. Boolean expression. Write each output as a sum of minterms (or product of maxterms) from the truth table.
5. Simplify using Boolean algebra or a K-map (using don't-cares where available).
6. Draw the logic diagram with AND, OR, NOT gates, or NAND/NOR only if required.
7. Verify the circuit by checking it against the truth table.

Example. For a half adder, the inputs are $A,B$ and the outputs are $S=A\oplus B$ and $C=AB$, which are implemented with an XOR gate and an AND gate.