Design of combinational circuits

Combinational behavior and specifications

Definition. A combinational circuit produces outputs determined only by the present input values. It has no stored state and no feedback path that preserves information from an earlier input. A complete design starts by naming inputs and outputs, writing a truth table, deriving equations, simplifying them, and selecting gates.

Example. A two-input alarm output that is 1 exactly when both sensors report danger is $F=AB$.

Exam point. If an output depends on the previous cycle, the circuit is sequential, even if its gates look combinational.

Truth tables and output equations

Definition. A truth table lists every input combination and the corresponding output. For $n$ binary inputs it has $2^n$ rows. Each output may be converted independently into SOP from its 1 rows or POS from its 0 rows.

Example. A three-input majority output is 1 when at least two inputs are 1.

Exam point. Confirm that all input rows occur exactly once and that output labels match the stated condition.

Solved design. Design the majority function for $A,B,C$.

1. Enumerate inputs 000 through 111.
2. Rows with at least two ones are 011, 101, 110, and 111.
3. The canonical SOP is $A'BC+AB'C+ABC'+ABC$.
4. Grouping or reasoning by pairs gives $F=AB+AC+BC$.

$A$	$B$	$C$	$F$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Answer. $F=AB+AC+BC$.

Deriving a circuit from a verbal condition

Definition. Translate each part of a specification into a Boolean condition, then combine conditions using AND, OR, or complement. “Only if” creates a necessary condition; “either” may mean inclusive OR unless exclusivity is stated. The truth table resolves ambiguity before simplification.

Example. A lamp turns on if switch $A$ is on or both $B$ and $C$ are on: $F=A+BC$.

Exam point. Inclusive OR allows both alternatives to hold at once.

Solved design. A controller asserts output $Y$ when request $R$ is active and either permission $P$ is active or override $O$ is active, but a lock $L$ must be absent.

1. The request is required: include factor $R$.
2. Permission OR override is $(P+O)$.
3. “Lock absent” means $L'$.
4. Combine the requirements: $Y=R(P+O)L'$.
5. For a check, if $R=1,P=0,O=1,L=0$, then $Y=1$; if $L=1$, it is 0. Answer. $Y=R(P+O)L'$.

Half adder

Definition. A half adder adds two one-bit operands without a carry input. Its sum is XOR, and its carry is AND. It is a combinational building block; it does not store the carry output for a later operation.

Example. $1+1$ produces sum 0 and carry 1.

Exam point. Sum and carry are separate outputs; do not confuse the carry bit with the sum bit.

Solved design. Derive the half-adder equations.

1. Inputs are $A,B$; the binary sum is 0 for 00 and 11, and 1 for 01 and 10.
2. Therefore $S=A\oplus B$.
3. Carry is 1 only when both bits are 1, so $C=AB$.
4. Check all four rows.

$A$	$B$	$S$	$C$
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Answer. $S=A\oplus B$, $C=AB$.

Full adder

Definition. A full adder adds bits $A,B$ and carry-in $C_{in}$. The two outputs are sum $S$ and carry-out $C_{out}$. Their equations are $S=A\oplus B\oplus C_{in}$ and $C_{out}=AB+AC_{in}+BC_{in}$.

Example. Inputs 1,1,1 represent decimal 3, so the output pair is 11.

Exam point. Carry-out is the majority function of the three input bits.

Solved design. Construct a full adder from two half adders and one OR gate.

1. First half adder adds $A,B$: $S_1=A\oplus B$, $C_1=AB$.
2. Second half adder adds $S_1,C_{in}$: $S=S_1\oplus C_{in}$ and $C_2=S_1C_{in}$.
3. Combine carry outputs: $C_{out}=C_1+C_2$.
4. Substitute: $C_{out}=AB+(A\oplus B)C_{in}$.
5. Expanding XOR gives $AB+A'BC_{in}+AB'C_{in}$, which simplifies to $AB+AC_{in}+BC_{in}$. Answer. Two half adders and one OR gate implement a full adder.

Ripple-carry addition

Definition. A ripple-carry adder connects the carry output of bit position $i$ to the carry input of position $i+1$. It computes multi-bit binary addition with one full-adder stage per bit, plus handling for the least significant bit. Carry propagation creates a delay that grows with word length.

Example. Adding 0110 and 0011 begins at the least significant bit and propagates carries left.

Exam point. Read carry direction from low significance to high significance.

Solved calculation. Add $1011_2+0110_2$ using four bit positions.

1. Bit 0: $1+0=1$, carry 0.
2. Bit 1: $1+1+0=10_2$, write 0, carry 1.
3. Bit 2: $0+1+1=10_2$, write 0, carry 1.
4. Bit 3: $1+0+1=10_2$, write 0, carry 1 beyond the word.
5. Reading the carry and written bits gives $10001_2$. Answer. $1011_2+0110_2=10001_2$.

Carry generate and propagate

Definition. For bit $i$, define generate $G_i=A_iB_i$ and propagate $P_i=A_i\oplus B_i$ (some conventions use $A_i+B_i$ for carry propagation). Then $C_{i+1}=G_i+P_iC_i$ and $S_i=P_i\oplus C_i$. State the convention used when comparing formulas.

Example. If $A_i=B_i=1$, then $G_i=1$ and the output carry is 1 regardless of input carry.

Exam point. XOR-propagate and OR-propagate differ as signals, though both can be used in the carry equation under appropriate definitions.

Solved calculation. Compute the carry into bit 2 for two low-order bit pairs with $A_0B_0=10$, $A_1B_1=11$, and $C_0=1$.

1. At bit 0, $G_0=0$, $P_0=1$, so $C_1=0+1\cdot1=1$.
2. At bit 1, $G_1=1$, $P_1=0$, so $C_2=1+0\cdot1=1$.
3. The second bit generates carry itself. Answer. $C_2=1$.

Comparator circuits

Definition. A magnitude comparator reports whether binary words are equal, less than, or greater than. Equality is the AND of bitwise XNOR results. For unsigned words, comparison is decided by the first differing bit when scanning from most significant to least significant.

Example. $1010_2>1001_2$ because the first differing bit from the left is 1 versus 0.

Exam point. Compare from the most significant bit; lower bits matter only after all higher bits tie.

Solved calculation. Compare $A=11010$ and $B=11100$ as unsigned values.

1. Bits 4 and 3 match: 1 and 1, then 1 and 1.
2. At bit 2, $A_2=0$ and $B_2=1$.
3. The first difference determines the comparison; lower bits are irrelevant.
4. Thus $A<B$. Answer. $A<B$; equality output is 0.

Multiplexers

Definition. A $2^k$-to-1 multiplexer selects one of its data inputs using $k$ select bits. The output equals the selected data value. For a 2-to-1 mux with select $S$, $Y=S'D_0+SD_1$.

Example. With $S=1$, a 2-to-1 mux outputs $D_1$.

Exam point. Map select-bit values to data inputs in the order stated; reversed labels change the function.

Solved design. Implement $F(A,B,C)=\Sigma m(1,2,6,7)$ using a 4-to-1 mux with $A,B$ as selects and $C$ as the remaining data variable.

1. Group minterms by select pair $AB$.
2. For $AB=00$, rows 0 and 1 give output 0 when $C=0$, 1 when $C=1$; set $D_0=C$.
3. For $AB=01$, rows 2 and 3 give 1,0; set $D_1=C'$.
4. For $AB=10$, rows 4 and 5 give 0,0; set $D_2=0$.
5. For $AB=11$, rows 6 and 7 give 1,1; set $D_3=1$. Answer. Selects $A,B$ with $D_0=C,D_1=C',D_2=0,D_3=1$.

Implementing a function with a multiplexer

Definition. A Boolean function with $n$ inputs can be implemented by a mux using some inputs as selects and the remaining inputs to form data values. Each data input is obtained by fixing the select assignment and simplifying the residual function. Constants and complemented literals are valid mux data inputs.

Example. $F(A,B)=A'B$ can use a 2-to-1 mux with select $A$, data $D_0=B,D_1=0$.

Exam point. Derive every data input from the truth table; do not guess the wiring from the expression's visual order.

Solved design. Use a 4-to-1 mux to implement $F(A,B,C)=AB+C$ with $A,B$ as select inputs.

1. For $AB=00$, $F=C$, so $D_0=C$.
2. For $AB=01$, $F=C$, so $D_1=C$.
3. For $AB=10$, $F=C$, so $D_2=C$.
4. For $AB=11$, $F=1+C=1$, so $D_3=1$.
5. Connect the select lines in the specified order and use the four data functions. Answer. $D_0=D_1=D_2=C$, $D_3=1$.

Decoders

Definition. An $n$-to-$2^n$ decoder activates one output for each $n$-bit input combination, assuming an active-high one-hot decoder. Each output is a minterm. Enable inputs may force all outputs inactive when the decoder is disabled; active-low devices reverse the output polarity.

Example. A 2-to-4 decoder output $Y_2$ is 1 for input 10, so $Y_2=AB'$ when $A$ is most significant.

Exam point. Check whether outputs and enable are active-high or active-low.