`AExE0201` Digital logic¶

Number systems and positional value¶

For radix \(r\), a number

\[ (d_nd_{n-1}\dots d_0.d_{-1}d_{-2}\dots)_r =\sum_k d_k r^k. \]

Common bases:

Base	Symbols	Recognition cue
Decimal	0-9	everyday arithmetic
Binary	0, 1	digital hardware state representation
Octal	0-7	groups of 3 binary bits
Hexadecimal	0-9, A-F	groups of 4 binary bits

Fast conversions:

binary to octal: group bits in 3 from the binary point outward;
binary to hex: group bits in 4;
hex digit to binary: replace each digit by its 4-bit equivalent;
decimal to binary integer: repeated division by 2;
decimal fraction to binary: repeated multiplication by 2.

Decimal-code recognition:

Code	Classification	Decisive cue
8421 BCD	weighted	the four bit weights are 8, 4, 2, and 1
2421	weighted	each position has a stated weight
Excess-3	non-weighted	add 3 to a decimal digit, then encode it in 4-bit binary

Octal is a positional number system, not normally grouped with decimal digit codes such as BCD, 2421, and Excess-3. In the assigned comparison, Excess-3 is the unambiguous non-weighted code.

Signed representations and complements¶

Method	Positive range in \(n\) bits	Negative handling	Key trap
Unsigned	\(0\) to \(2^n-1\)	not represented	no sign bit
Sign-magnitude	\(0\) to \(2^{n-1}-1\)	MSB is sign	two zeros exist
1's complement	\(0\) to \(2^{n-1}-1\)	bitwise inversion	two zeros exist
2's complement	\(0\) to \(2^{n-1}-1\)	invert and add 1	standard signed arithmetic

For \(n\)-bit 2's complement, range is

\[ -2^{n-1} \text{ to } 2^{n-1}-1. \]

Recognition cues:

2's complement overflow in addition occurs when two same-sign operands produce a result with opposite sign.
Carry-out from the MSB is not by itself the signed-overflow test.
Subtraction is commonly performed as \(A-B=A+(2\text{'s complement of }B)\).

Logic levels and basic gates¶

Digital logic abstracts voltage ranges into logic states.

HIGH and LOW are voltage ranges, not universal exact voltages; thresholds depend on the logic family and supply voltage.
Positive logic maps HIGH to 1 and LOW to 0. Negative logic reverses that assignment.

Gate	Boolean form	Output is 1 when
NOT	\(Y=\overline{A}\)	input is 0
AND	\(Y=AB\)	all inputs are 1
OR	\(Y=A+B\)	any input is 1
NAND	\(Y=\overline{AB}\)	not all inputs are 1
NOR	\(Y=\overline{A+B}\)	all inputs are 0
XOR	\(Y=A\oplus B\)	inputs differ
XNOR	\(Y=\overline{A\oplus B}\)	inputs are equal

Universal gates:

NAND alone can realize any Boolean function.
NOR alone can also realize any Boolean function.

Boolean algebra essentials¶

Core laws used in simplification:

Law	Identity
Identity	\(A+0=A\), \(A\cdot1=A\)
Null	\(A+1=1\), \(A\cdot0=0\)
Idempotent	\(A+A=A\), \(A\cdot A=A\)
Complement	\(A+\overline{A}=1\), \(A\overline{A}=0\)
Commutative	\(A+B=B+A\), \(AB=BA\)
Associative	\((A+B)+C=A+(B+C)\)
Distributive	\(A(B+C)=AB+AC\)
Absorption	\(A+AB=A\), \(A(A+B)=A\)
De Morgan	\(\overline{AB}=\overline{A}+\overline{B}\), \(\overline{A+B}=\overline{A}\,\overline{B}\)

Recognition trap: Boolean addition is OR, not arithmetic addition.

SOP, POS, minterms, maxterms¶

Form	Structure	Canonical unit	Built from truth table rows
SOP	OR of product terms	minterms	rows where output is 1
POS	AND of sum terms	maxterms	rows where output is 0

A minterm contains every variable once, either complemented or uncomplemented.
A maxterm also contains every variable once.
Canonical SOP is convenient for direct implementation from 1-rows.
Canonical POS is convenient from 0-rows.

Example for variables \(A,B\):

\(A\)	\(B\)	Minterm
0	0	\(\overline{A}\overline{B}\)
0	1	\(\overline{A}B\)
1	0	\(A\overline{B}\)
1	1	\(AB\)

Truth table to Karnaugh map¶

K-map purpose: minimize Boolean expressions by visually grouping adjacent 1s or 0s.

Rules:

adjacent cells differ by one variable only;
use Gray-code ordering;
groups must be powers of two: 1, 2, 4, 8, ...;
larger groups remove more literals;
edge wrapping is allowed; corners may be adjacent;
use don't-care terms if they help simplification.