Learn › Engineering

Digital electronics

A digital circuit works with two voltage levels, 0 and 1. With them we represent numbers (in binary, signed and floating point), compute logic functions with gates and, adding memory (flip-flops), build counters and state machines. This topic follows that path with the four Digital electronics tools.

Go to the simulator

Number systems

In a positional system of base $b$ each digit is worth its value times a power of the base. Binary (base 2) uses 0 and 1; octal (8) and hexadecimal (16, digits 0–9 and A–F) are shorthands for binary, because 8 = 2³ and 16 = 2⁴:

N = i \sum d_{i} b^{i} 1011. 1_{2} = 1 \cdot 2^{3} + 0 \cdot 2^{2} + 1 \cdot 2^{1} + 1 \cdot 2^{0} + 1 \cdot 2^{- 1} = 11.5

Conversion	Method
Base $b$ → decimal	Sum of digit × $b^{position}$ (as above).
Decimal → binary, integer part	Divide by 2 over and over; the remainders, read from bottom to top, are the bits.
Decimal → binary, fractional part	Multiply by 2 over and over; the integer part of each product, read from top to bottom, is the bit.
Binary ↔ octal / hexadecimal	Group by 3 or 4 bits from the radix point toward both sides; each group is one digit.

A finite decimal fraction can be infinite in binary:

0.1 = 0.0 \overline{0011}_{2}

. That is why a computer does not store 0.1 exactly (in single precision it stores 0.100000001490116…).

Other codes: BCD writes each decimal digit with 4 bits (45 → 0100 0101) and Gray code orders numbers so that two consecutive ones differ in a single bit ( $g = b \oplus (b ≫ 1)$ ); it is used in position encoders and in Karnaugh maps.

Signed integers and overflow

With $n$ bits there are $2^{n}$ patterns. Unsigned, they represent 0 to $2^{n} - 1$ . For negatives almost every processor uses two's complement: the most significant bit is worth $- 2^{n - 1}$ instead of $+ 2^{n - 1}$ , so the range is $- 2^{n - 1}$ to $2^{n - 1} - 1$ (with 8 bits, −128 to 127).

- x \to \overline{x} + 1 = 2^{n} - x V = c_{n - 1} \oplus c_{n}

To change the sign, invert every bit and add 1. The advantage is that addition is the same for signed and unsigned numbers, and the subtraction $A - B$ is $A + \overline{B} + 1$ : a single adder does everything. What changes is how the result is read and when it is wrong:

Unsigned: the result does not fit if a carry comes out of the last bit (flag C = 1).
Signed: there is overflow (V = 1) when two numbers of the same sign give a result of the opposite sign; it is equivalent to the carry into the sign bit differing from the carry out of it.
Adding two numbers of different sign never overflows.

The 4-bit two's complement wheel: adding is turning, and going from 0111 to 1000 jumps from +7 to −8.

IEEE 754 floating point

Real numbers are stored in binary scientific notation. In single precision (32 bits) there is 1 sign bit $s$ , 8 exponent bits $E$ stored with a bias of 127 and 23 mantissa bits $m$ ; the 1 before the point is not stored (hidden bit):

x = (- 1)^{s} \cdot 1. m_{2} \cdot 2^{E - 127} 1 \leq E \leq 254

$E = 0$ is reserved for zero and denormal numbers (no hidden bit), and $E = 255$ for infinity (mantissa 0) and NaN. With 24 effective bits, the precision is about 7 decimal digits; a value that does not fit is rounded to the nearest one.

Boolean algebra and gates

A logic variable is 0 or 1. The three basic operations are AND (product, $A B$ : it is 1 only if both are 1), OR (sum, $A + B$ : it is 1 if either is 1) and NOT (complement, $\overline{A}$ ). Each one is a gate; NAND and NOR are negated AND and OR, and XOR is 1 when the inputs differ.

Gate symbols, their expression and their output for each input combination.

Law	Form with +	Form with ·
Identity and null	$A + 0 = A, A + 1 = 1$	$A \cdot 1 = A, A \cdot 0 = 0$
Complement	$A + \overline{A} = 1$	$A \overline{A} = 0$
Idempotence	$A + A = A$	$AA = A$
Absorption	$A + A B = A$	$A (A + B) = A$
Distributive	$A + BC = (A + B) (A + C)$	$A (B + C) = A B + A C$
De Morgan	$\overline{A + B} = \overline{A} \overline{B}$	$\overline{A B} = \overline{A} + \overline{B}$

De Morgan explains why NAND alone (or NOR alone) is enough for any circuit: an AND–OR sum of products becomes NAND–NAND by negating each product twice.

Canonical forms and Karnaugh maps

Every function can be written from its truth table. Each row $m$ with output 1 is a minterm, a product with every variable (the one that is 0 goes negated); the sum of the minterms is the canonical SOP form, $Σ m (\dots)$ . The rows with output 0 give maxterms (sums) and the POS form, $Π M (\dots)$ . They are correct but long: they need simplifying.

The Karnaugh map draws the truth table so that neighboring cells differ in a single bit: rows and columns go in Gray code (00, 01, 11, 10) and opposite edges are neighbors too. Two neighboring cells with a 1 merge because $A B + A \overline{B} = A$ : the variable that changes disappears.

Groups are rectangles of 1, 2, 4, 8… cells (powers of 2), and they may wrap around the edges.
Each group of $2^{k}$ cells removes $k$ variables: the ones that do not change within the group remain.
Look for the largest possible groups and the fewest groups that cover every 1; a 1 may be in several groups.
«Don't care» cells (X, combinations that never happen) are used as 1 only if they enlarge a group; they do not need to be covered.
Grouping the 0s instead of the 1s gives the minimal POS form.

With more than 4 or 5 variables the map stops being practical and the Quine–McCluskey method is used, which does the same with tables: it combines minterms that differ in one bit until it gets the prime implicants (groups that cannot grow); the essential ones (the only ones covering some 1) go in for sure, and if some 1s remain uncovered, Petrick's method picks the cheapest combination of the rest.

Combinational circuits

In a combinational circuit the output depends only on the inputs at that instant. The usual building blocks:

Block	What it does	Equations
Half adder	Adds two bits.	$S = A \oplus B, C = A B$
Full adder	Adds two bits and the incoming carry.	$S = A \oplus B \oplus C_{in}, C_{o u t} = A B + C_{in} (A \oplus B)$
4:1 multiplexer	Passes to the output the input chosen by $S_{1} S_{0}$ .	$Y = \overline{S_{1}} \overline{S_{0}} I_{0} + \overline{S_{1}} S_{0} I_{1} + S_{1} \overline{S_{0}} I_{2} + S_{1} S_{0} I_{3}$
2:4 decoder	Activates a single output, the one of the input number.	$Y_{0} = \overline{A_{1}} \overline{A_{0}}, \dots, Y_{3} = A_{1} A_{0}$

Chaining $n$ full adders, each passing its carry to the next, adds $n$ -bit numbers (a ripple-carry adder). It is simple but slow: the last bit waits for the carry to travel the whole chain.

4-bit ripple-carry adder.

Sequential circuits and flip-flops

A sequential circuit has memory: its output also depends on what happened before. The simplest memory element is the SR latch, two cross-coupled NOR gates that hold one bit. A flip-flop changes only on the rising edge of the clock (CLK), so the whole circuit advances at the same time, one step per cycle:

D flip-flop: at each rising edge (dashed) Q copies the value D has at that instant; what D does between edges does not matter.

Flip-flop	Characteristic equation	Excitation: 0→0, 0→1, 1→0, 1→1
D	$Q^{+} = D$	D = 0, 1, 0, 1
T	$Q^{+} = T \oplus Q$	T = 0, 1, 1, 0
JK	$Q^{+} = J \overline{Q} + \overline{K} Q$	JK = 0X, 1X, X1, X0
SR	$Q^{+} = S + \overline{R} Q$ (SR = 0)	SR = 0X, 10, 01, X0

The excitation table answers the design question: for the state to go from $Q$ to $Q^{+}$ , what must the inputs be? The X entries are freedoms the Karnaugh map takes advantage of.

State machines

A finite state machine describes a sequential circuit as a set of states and the transitions between them. In a Moore machine the output depends only on the state (written inside the circle); in a Mealy machine, on the state and the input (written on the arrow as input/output), and it usually needs fewer states. The design always follows the same steps:

State diagram from the problem statement: what the circuit has to remember.
State table: next state and output for each state and each input.
Code assignment: with $S$ states, $k = ⌈ lo g_{2} S ⌉$ flip-flops are needed; unused codes are «don't care».
Transition and excitation table with the chosen flip-flop.
One Karnaugh map per flip-flop input and per output, and the circuit.

Common mistakes

Reading the remainders of division by 2 from top to bottom: the first one is the least significant bit.
Grouping by 4 bits from the left when converting to hexadecimal: group from the radix point.
Confusing the carry out (C) with signed overflow (V): 100 + 50 with 8 bits has C = 0 and V = 1.
Ordering the Karnaugh map in binary (00, 01, 10, 11) instead of Gray: the groups stop being valid.
Forgetting that the map edges are neighbors, or making groups of 3 or 6 cells.
Treating the X as required 1s and covering them even when they do not help.
Writing the output of a Mealy machine inside the state, or that of a Moore machine on the arrow.

Worked examples

Example 1From decimal to binary, octal and hexadecimal

Write 45.625 in binary, octal and hexadecimal.

Solution

Integer part, divisions by 2: 45 → 22 remainder 1, 22 → 11 remainder 0, 11 → 5 remainder 1, 5 → 2 remainder 1, 2 → 1 remainder 0, 1 → 0 remainder 1. From bottom to top: $45 = 10110 1_{2}$ .
Fractional part, multiplications by 2: 0.625 × 2 = 1.25 → 1; 0.25 × 2 = 0.5 → 0; 0.5 × 2 = 1.0 → 1, and the fraction ends (exact). From top to bottom: $0.625 = 0.10 1_{2}$ .
Octal, groups of 3 from the point: 101 101 . 101 → 55.5. Hexadecimal, groups of 4: 0010 1101 . 1010 → 2D.A.
Check: $2 \cdot 16 + 13 + 10/16 = 45.625$ .

45.625 = 101101.10 1_{2} = 55. 5_{8} = 2 D.A_{16}

Solve it in Simuveliq

In Engineering → Number systems, in Base conversion, type 45.625 with base 10.
The Result in every base card gives 10 1101.101, 55.5 and 2D.A, and Step by step shows the division table, the multiplication table and the groups of 3 and 4 bits.

Open in the simulator →

Example 2Two's complement and overflow

With 8 bits: (a) write −45 in two's complement; (b) add 100 + 50 and say whether the result is correct signed and unsigned.

Solution

(a) +45 = 0010 1101. Invert the bits: 1101 0010, and add 1: 1101 0011. Check: unsigned, that pattern is 211 = 2⁸ − 45.
(b) 0110 0100 (100) + 0011 0010 (50) = 1001 0110. The carry into the sign bit is 1 and the carry out is 0: C = 0 and V = 0 ⊕ 1 = 1.
Unsigned, 1001 0110 = 150: correct (C = 0, it fits in 0…255). Signed, the sign bit is 1 and the pattern is 150 − 256 = −106: two positives gave a negative, overflow, because 150 does not fit in −128…127.

−45 = 1101 0011; 100 + 50 = 1001 0110: 150 unsigned (correct) and −106 signed (overflow, V = 1).

Solve it in Simuveliq

In Number systems, type −45 (base 10, n = 8 bits): the representations table gives two's complement = 1101 0011, next to sign-magnitude (1010 1101), one's complement (1101 0010) and excess-128 (0101 0011), and the step by step does the inversion and the +1.
In Binary arithmetic (n bits), A = 100, B = 50 and A + B: the card shows the carry row, the flags C = 0 · V = 1 · N = 1 · Z = 0 and both readings, −106 «overflow (V = 1)» and 150 «fits».

Open in the simulator →

Example 3A number in IEEE 754

Write −6.75 in single-precision floating point and give the pattern in hexadecimal.

Solution

Sign: negative, $s = 1$ .
$6.75 = 110.1 1_{2}$ (6 = 110 and 0.75 = 0.11). Normalized: $1.101 1_{2} \times 2^{2}$ .
Stored exponent: $E = 2 + 127 = 129 = 1000000 1_{2}$ .
Mantissa: the bits after the hidden 1, 1011, padded with zeros up to 23 bits.
Pattern: 1 | 1000 0001 | 1011 000… → 1100 0000 1101 1000 0000… = 0xC0D80000. Since 6.75 is exact in binary, the stored value is exact (error 0).

−6.75 → s = 1, E = 129, mantissa 1011 0…0: 0xC0D80000.

Solve it in Simuveliq

In Number systems, in the IEEE 754 · 32 bits panel, type −6.75. The card paints the 32 bits by field, gives «hex 0xC0D80000» and the five steps (sign, binary, normalize, exponent 2 + 127 = 129, mantissa).
Try 0.1: the stored value is no longer exact and the card shows the error.

Open in the simulator →

Example 4Majority voter

Three judges vote (A, B, C = 1 if they approve). The output F is 1 if at least two approve. Find the minimal F in SOP and POS.

Solution

Truth table: F = 1 on the rows with two or three ones, 011, 101, 110 and 111, that is, $F = Σ m (3, 5, 6, 7)$ .
In the map, m7 is a neighbor of m3, m5 and m6. Three pairs that share m7 are formed: m3–m7 (A changes: $BC$ remains), m5–m7 (B changes: $A C$ ) and m6–m7 (C changes: $A B$ ). All three are essential: each is the only one covering its other 1.
$F = A B + A C + BC$ . Grouping the zeros (m0, m1, m2, m4, which form three pairs with m0) gives the POS $F = (A + B) (A + C) (B + C)$ , of the same cost.

F = A B + A C + BC = (A + B) (A + C) (B + C)

Solve it in Simuveliq

In Engineering → Karnaugh maps, in Examples, «Load» → Majority voter (3 variables).
The map colors the three groups; Expressions gives the minimal SOP and POS, the NAND-only and NOR-only versions and the cost, and Quine–McCluskey step by step reaches the same three essential prime implicants. «Build the circuit» → AND–OR builds it in the simulator.

Open in the simulator →

Example 5Simplifying with don't cares

Simplify

F (A, B, C, D) = Σ m (1, 3, 7, 11, 15) + d (0, 2, 5)

Solution

The 1s m3, m7, m15 and m11 fill the column CD = 11: a group of 4, A and B change, $C D$ remains.
m1 is still missing. Alone, it would be $\overline{A} \overline{B} \overline{C} D$ . Taking the X at m5 as a 1, the square m1, m3, m5, m7 (rows 00 and 01, columns 01 and 11) is a group of 4: B and C change, $\overline{A} D$ remains.
The X at m0 and m2 do not help any needed group and stay as 0. Factoring, the POS is $D (\overline{A} + C)$ , cheaper still.

F = C D + \overline{A} D = D (\overline{A} + C)

Solve it in Simuveliq

«Load» → With don't cares: Σm(1,3,7,11,15) + d(0,2,5). The map shows the X and the two groups; Expressions gives the SOP $C D + \overline{A} D$ , the POS $D (\overline{A} + C)$ and the cost of each one («POS is cheaper»).
In Quine–McCluskey, the X take part in the combinations marked «(X)», but they are not columns of the implicant table: they need not be covered.

Open in the simulator →

Example 6Cyclic function (Petrick's method)

Simplify

F (A, B, C) = Σ m (0, 1, 2, 5, 6, 7)

Solution

The six 1s form a ring of pairs and there are six 2-cell prime implicants: $\overline{B} C$ (1, 5), $B \overline{C}$ (2, 6), $\overline{A} \overline{C}$ (0, 2, which wraps around the edges), $\overline{A} \overline{B}$ (0, 1), $A C$ (5, 7) and $A B$ (6, 7).
Each 1 is in two of them, so none is essential: the map does not say where to start.
Petrick: for each minterm, the sum of the implicants that cover it, and the product is required to be 1: $(P_{3} + P_{4}) (P_{1} + P_{4}) (P_{2} + P_{3}) (P_{1} + P_{5}) (P_{2} + P_{6}) (P_{5} + P_{6})$ . The cheapest products have 3 terms: $P_{1} P_{3} P_{6}$ and $P_{2} P_{4} P_{5}$ .

Two minimal solutions:

F = \overline{A} \overline{C} + \overline{B} C + A B

F = \overline{A} \overline{B} + B \overline{C} + A C

Solve it in Simuveliq

«Load» → Cyclic function (Petrick). Quine–McCluskey says «There are no essential implicants (cyclic function)», writes Petrick's product and picks P3, P1, P6: $\overline{A} \overline{C} + \overline{B} C + A B$ , the groups on the map.

Open in the simulator →

Example 7Full adder

Design a circuit that adds three bits A, B and

C_{in}

and gives the sum S and the carry

C_{o u t}

Solution

Truth table: the sum of three bits goes from 0 to 3 = 11₂. S is the low bit and is 1 when there is an odd number of ones: $S = Σ m (1, 2, 4, 7) = A \oplus B \oplus C_{in}$ (the map of S is a checkerboard, with no pairs: XOR).
$C_{o u t}$ is 1 with two or three ones: it is the majority voter of example 4, $C_{o u t} = A B + A C_{in} + B C_{in}$ .
To reuse the XOR of A and B, write $C_{o u t} = A B + C_{in} (A \oplus B)$ : if A and B are 1 there is a carry; if only one is 1, there is a carry when $C_{in}$ arrives. That is 5 gates: two XOR, two AND and one OR.
Check: 1 + 1 + 0 = 2 = 10₂, so S = 0 and $C_{o u t}$ = 1; and 1 + 1 + 1 = 3 = 11₂, S = 1 and $C_{o u t}$ = 1.

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

and

C_{o u t} = A B + C_{in} (A \oplus B)

Solve it in Simuveliq

In Engineering → Digital circuits, «Load example» → Full adder. Click the switches A, B and Cin and watch the LEDs S and Cout.
The truth table the simulator gets from the circuit gives S = 0, 1, 1, 0, 1, 0, 0, 1 and Cout = 0, 0, 0, 1, 0, 1, 1, 1 for rows 000 to 111, with the expressions (A ⊕ B) ⊕ Cin and (A ⊕ B)Cin + AB.

Open in the simulator →

Example 8Detector of the sequence 101

A bit X arrives every clock cycle. Design a Mealy machine with D flip-flops whose output Z is 1 on receiving the last 1 of each 101, allowing overlap (10101 gives two detections).

Solution

States according to how much of the sequence has been seen: S0 = nothing, S1 = «1», S2 = «10». From S2, a 1 completes 101 (Z = 1) and that 1 is already the start of another: go to S1 (overlap). A 0 in S2 gives «100», which is useless: back to S0.
Three states → $k = ⌈ lo g_{2} 3 ⌉ = 2$ flip-flops: S0 = 00, S1 = 01, S2 = 10; code 11 is unused (X).
With D flip-flops, $D = Q^{+}$ : $Q_{1}^{+} = 1$ only when going to S2 (from S1 with X = 0), and $Q_{0}^{+} = 1$ when going to S1, which happens with every X = 1. With the X of code 11, the maps give $D_{1} = Q_{0} \overline{X}$ , $D_{0} = X$ and $Z = Q_{1} X$ .
Check with X = 1 0 1 0 1: states S0 → S1 → S2 → S1 → S2 → S1 and Z = 0 0 1 0 1, two detections.

D_{1} = Q_{0} \overline{X}

D_{0} = X

Z = Q_{1} X

Solve it in Simuveliq

In Engineering → State machines, in Examples, «Load» → 101 detector (Mealy, overlapping).
You see the State diagram, the Transition and excitation table · D (with «With 3 states, k = ⌈log₂ 3⌉ = 2 flip-flops are needed») and the Minimal equations with their map: D1 = Q0X̄, D0 = X, Z = Q1X. «Build the circuit in the simulator» builds it with its clock so you can test it.

Open in the simulator →

Example 9Modulo-5 counter with T flip-flops

Design a counter that runs through 0, 1, 2, 3, 4, 0… with T flip-flops, whose output Z is 1 at 4.

Solution

Five states → 3 flip-flops ( $Q_{2} Q_{1} Q_{0}$ , from 000 to 100); codes 101, 110 and 111 never appear: X.
With T, $T = Q \oplus Q^{+}$ : a flip-flop is toggled when its bit has to change. From 011 to 100 all three change ( $T_{2} T_{1} T_{0} = 111$ ) and from 100 to 000 only $Q_{2}$ (100).
Excitation table for 000, 001, 010, 011, 100: $T_{2}$ = 0, 0, 0, 1, 1; $T_{1}$ = 0, 1, 0, 1, 0; $T_{0}$ = 1, 1, 1, 1, 0.
Maps with the X: $T_{2} = Q_{2} + Q_{1} Q_{0}$ , $T_{1} = Q_{0}$ , $T_{0} = \overline{Q_{2}}$ , and the Moore output $Z = Q_{2}$ .

T_{2} = Q_{2} + Q_{1} Q_{0}

T_{1} = Q_{0}

T_{0} = \overline{Q_{2}}

Z = Q_{2}

Solve it in Simuveliq

«Load» → Modulo-5 counter (T). The excitation table says «The 3 unused codes are don't-cares (X)» and the Minimal equations give T2 = Q2 + Q1Q0, T1 = Q0, T0 = Q̄2 and Z = Q2.
Change the flip-flops to D or JK in Implementation to compare how many gates each one needs.

Open in the simulator →

Digital electronics

Number systems

Signed integers and overflow

IEEE 754 floating point

Boolean algebra and gates

Canonical forms and Karnaugh maps

Combinational circuits

Sequential circuits and flip-flops

State machines

Common mistakes

Worked examples

Example 1From decimal to binary, octal and hexadecimal

Solution

Solve it in Simuveliq

Example 2Two's complement and overflow

Solution

Solve it in Simuveliq

Example 3A number in IEEE 754

Solution

Solve it in Simuveliq

Example 4Majority voter

Solution

Solve it in Simuveliq

Example 5Simplifying with don't cares

Solution

Solve it in Simuveliq

Example 6Cyclic function (Petrick's method)

Solution

Solve it in Simuveliq

Example 7Full adder

Solution

Solve it in Simuveliq

Example 8Detector of the sequence 101

Solution

Solve it in Simuveliq

Example 9Modulo-5 counter with T flip-flops

Solution

Solve it in Simuveliq

Related topics