Combinational Logic

A combinational circuit has no stored state. Its outputs are Boolean functions of the present inputs only. Adders, comparators, multiplexers, demultiplexers and parity circuits are standard examples.

Binary Arithmetic

The elementary addition and subtraction rules are

Addition				Subtraction
A	B	Sum	Carry	A	B	Difference	Borrow
0	0	0	0	0	0	0	0
0	1	1	0	0	1	1	1
1	0	1	0	1	0	1	0
1	1	0	1	1	1	0	0

For unsigned $n$-bit addition, a carry beyond bit $n-1$ indicates that the exact result exceeds $2^n-1$. For two’s-complement addition, discard that carry and test signed overflow separately.

One’s- and two’s-complement subtraction

To evaluate $A-B$ with one’s complement, add $A$ to the bitwise complement of $B$. If a carry leaves the word, add it back to the least-significant bit (end-around carry). Without a carry, complement the sum and mark it negative.

Two’s complement removes the end-around step:

$$\boxed{A-B=A+\overline B+1}.$$

The operation uses the same $n$-bit adder as addition. The result is valid as an $n$-bit signed number only when it lies in $[-2^{n-1},2^{n-1}-1]$.

Note

Example — Four-bit subtraction

For $A=0101_2=5$ and $B=0011_2=3$,

$$0101+\overline{0011}+1 =0101+1100+1=1\,0010.$$

Discarding the carry gives $0010_2=2$. In unsigned subtraction the carry 1 means no borrow; borrow out is its complement.

Adders

Half adder

A half adder accepts two operand bits but no carry input:

$$\boxed{S=A\oplus B},\qquad \boxed{C=AB}.$$

Full adder

A full adder includes the incoming carry $C_{in}$:

$$\boxed{S=A\oplus B\oplus C_{in}},\qquad \boxed{C_{out}=AB+AC_{in}+BC_{in}}.$$

$A$	$B$	$C_{in}$	$S$	$C_{out}$
	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

Full-adder truth table.

Gate realization of a half adder and construction of a full adder.

Two half adders form a full adder:

$$S_1=A\oplus B,\quad C_1=AB,\quad S=S_1\oplus C_{in},\quad C_2=S_1C_{in},\quad C_{out}=C_1+C_2.$$

Multi-bit ripple-carry adder

An $n$-bit parallel adder applies all operand bits together, but each full adder waits for the carry from the next lower position:

$$S_i=A_i\oplus B_i\oplus C_i,\qquad C_{i+1}=A_iB_i+(A_i\oplus B_i)C_i.$$

Four cascaded full adders and their compact parallel-adder symbol.

The circuit is regular and economical. Its worst carry path crosses all $n$ stages, so a first estimate is

$$\boxed{t_{carry,wc}\approx nt_c}.$$

Intermediate sum bits may be temporarily wrong while the carry ripples. A carry look-ahead design instead forms generate $G_i=A_iB_i$ and propagate $P_i=A_i\oplus B_i$ terms so several carries can be evaluated in parallel; it is faster but uses more logic and routing.

Arithmetic Circuits

Half and full subtractors

For a half subtractor,

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

For a full subtractor with borrow input $B_{in}$,

$$\boxed{D=A\oplus B\oplus B_{in}},\qquad \boxed{B_{out}=\overline A B+\overline A B_{in}+BB_{in}}.$$

An ALU normally uses complement addition instead of a separate multi-bit subtractor.

Adder–subtractor

Apply mode $M$ to every $B_i$ through XOR and also set the initial carry to $C_0=M$:

$$\boxed{F=A+(B\oplus M)+M}.$$

$M$	$B_i\oplus M$	$C_0$	Operation
	$B_i$	0	$A+B$
1	$\overline B_i$	1	$A-B$

Adder–subtractor modes.

Four-bit adder–subtractor with mode-controlled complementing of $B$.

For two’s-complement arithmetic, signed overflow is

$$\boxed{V=C_{n-1}\oplus C_n}.$$

During addition, this is equivalent to equal-sign operands producing an opposite-sign result. The final carry alone is not a signed-overflow flag.

BCD addition

First add two BCD digits and the input carry as ordinary binary. If the four-bit sum exceeds 9 or produces carry $C_4$, add $0110$:

$$\boxed{K=C_4+Z_3Z_2+Z_3Z_1}, \qquad K=1\Rightarrow\text{add }0110.$$

For example, $7+8$ gives $1111$; adding $0110$ produces $1\,0101$, the BCD digits 1 and 5.

Digital Comparators

A magnitude comparator produces mutually exclusive outputs $G$ ($A>B$), $E$ ($A=B$), and $L$ ($A<B$).

One-bit comparator

$$\boxed{G=A\overline B},\qquad \boxed{E=\overline A\,\overline B+AB=\overline{A\oplus B}},\qquad \boxed{L=\overline A B}.$$

$A$	$B$	$G$	$E$	$L$
	0	0	1	0
0	1	0	0	1
1	0	1	0	0
1	1	0	1	0

Multi-bit comparator

Compare from the most-significant bit. The first unequal pair decides the result; lower bits matter only when all higher pairs are equal. For two-bit words $A_1A_0$ and $B_1B_0$, let $E_i=\overline{A_i\oplus B_i}$. Then

$$A>B=A_1\overline B_1+E_1A_0\overline B_0,$$ $$A=B=E_1E_0, \qquad A<B=\overline A_1B_1+E_1\overline A_0B_0.$$

Cascading two four-bit magnitude comparators.

Devices such as the 7485 include cascade inputs. Connect the less-significant group’s $G,E,L$ outputs to the next more-significant group so the higher group can override lower-bit decisions.

Multiplexers

A $2^n$-to-1 multiplexer (MUX) uses $n$ select lines to connect one of $2^n$ data inputs to one output.

For a four-to-one MUX,

$$\boxed{Y=\overline S_1\overline S_0D_0 +\overline S_1S_0D_1+S_1\overline S_0D_2+S_1S_0D_3}.$$

$S_1$	$S_0$	$Y$
	0	$D_0$
0	1	$D_1$
1	0	$D_2$
1	1	$D_3$

Gate-level realization of a four-to-one multiplexer.

A MUX is also a function generator. For an $n$-variable truth table, connect the variables to the select inputs and each $D_i$ to the required 0 or 1. A $2^{n-1}$-to-1 MUX can implement an $n$-variable function when each data input is chosen from $0,1,X,\overline X$ for the remaining variable $X$.

Demultiplexers

A one-to-$2^n$ demultiplexer (DEMUX) routes one data input to the output selected by $n$ address lines. Under the active-HIGH convention used here, all unselected outputs remain 0; practical devices may instead use active-LOW enables or outputs.

For a one-to-four DEMUX,

$$\begin{aligned} Y_0 & =D\overline S_1\overline S_0, & Y_1 & =D\overline S_1S_0, \\ Y_2 & =DS_1\overline S_0, & Y_3 & =DS_1S_0. \end{aligned}$$

Gate-level realization of a one-to-four demultiplexer.

A decoder with enable acts as a DEMUX when the enable is used as the data input. Check active-LOW enables and outputs on practical devices before applying the active-HIGH equations above.

Parity Generator and Checker

Parity adds one check bit so the total number of 1s is forced even or odd. For data bits $D_0,\ldots,D_{n-1}$,

$$\boxed{P_{even}=D_0\oplus D_1\oplus\cdots\oplus D_{n-1}},\qquad \boxed{P_{odd}=\overline{P_{even}}}.$$

At the receiver, XOR all received data and the parity bit:

$$S=D_0\oplus\cdots\oplus D_{n-1}\oplus P.$$

For even parity, $S=0$ means parity is consistent and $S=1$ reports an error. For odd parity the interpretation is reversed.

XOR-tree parity generation and end-to-end parity checking.

Note

Key Point — What parity can detect

Parity detects every odd number of bit errors, including any single-bit error. It cannot identify the bad bit and misses every even number of changed bits. It is an error-detection code, not an error-correction code.

Combinational Design Checks

1. Verify the Boolean expression against every truth-table row.

2. State active-HIGH and active-LOW conventions explicitly.

3. Check unused input combinations and output exclusivity where required.

4. Count logic levels on the longest path and include fan-out loading.

5. Remember that unequal gate delays can produce temporary hazards even when the final Boolean function is correct.