---
tags: Introduction to Digital System
---
# Chapter 4-Combinational Logic
## Introduction
1. Combinational Logic Circuits
Combinational logic circuits are composed of logic gates with no feedback paths or memory elements.
2. Sequential Logic Circuits
Sequential logic circuits are composed of storage elements and logic gates with its output function of the inputs and the state of storage elements.
## Analysis Procedure
1. Make sure that the given circuit is a combinational circuit.
The circuit has logic gates, no feedback, and no memory elements
2. Obtain the boolean functions or the truth table
## Design Procedure
1. State the problem.
2. Determine the inputs and outputs.
3. Derive the truth table.
4. Derive the simplified boolean functions of each inputs.
5. Draw the logic diagram and verify the correctness.
## Examples
1. Adder
1. Circuits and Truth Tables
1. Half Adder
2. Full Adder
* ※A full adder = 2 half adders + 1 OR gate
3. Adder with Lots of Bits
* A 4-bit Binary Adder
* ※$C_4$ and $C_3$ output the wrong value at the beginning because of the behavior of hardward circuit. But $C_4$ becomes correct as soon as $C_3$ is correct + a little delay. $C_3$ becomes correct as soon as $C_2$ is correct + a little delay and so on ... .
2. Carry Propagation
1. Introduction
The circled logic gates have more propagation delays.
2. Time
1. $2$ gate levels for each full adder
2. $2n$ gate levels for an n-bit binary ripple-carry adder
* We can employ faster gates to reduce delays or carry lookahead scheme.
* Lookahead Scheme
$\begin{cases}C_1=G_0+P_0"C_0"\\C_2=G_1+P_1"C_1"=G_1+P_1G_0+P_1P_0"C_0"\\C_3=G_2+P_2"C_2"=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0"C_0"\\\vdots\end{cases}$
2. Adder/Subtractor
* An addition/subtraction of two n-digit numbers needs a sum of (n-1) digits.
* ※Overflow
3. Decimal Adder
1. If the binary sum is bigger than $9$, BCD sum is equal to the binary sum.
2. If the binary sum is smaller than $9$, BCD sum is equal to the binary sum plus $6$.
4. Binary Multiplier
1. Two Bits
2. 4 Bits
5. Magnitude Comparator
* Design Approach
Let $\begin{cases}A=A_3A_2A_1A_0\\B=B_3B_2B_1B_0\end{cases}$
1. If $A=B$
$\begin{cases}A_3=B_3\\A_2=B_2\\A_1=B_1\\A_0=B_0\end{cases}\\Let\ x_i=exclusive\ or=A_iB_i+A_i'B_i'\\\Rightarrow (A=B)=x_3x_2x_1x_0$
2. If $A>B$
$A_3B_3'+x_3A_2B_2'+x_3x_2A_1B_1'+x_3x_2x_1A_0B_0'$
3. If $A<B$
$A_3'B_3+x_3A_2'B_2+x_3x_2A_1'B_1+x_3x_2x_1A_0'B_0$
6. Decoders
1. $n$ to $2^n$ Decoders
Take $n=3$ for example
2. Decoders with Enable Input
Take $n=2$ for example
3. Combine 2 $n$ to $2^n$ into a $n+1$ to $2^{n+1}$
For example
4. Decoder Implementation of
Because each outputs of a decoder are minterms, we can implement any Boolean function of n input variables with a decoder and an external OR gate.
* ※Example: Full Adder
7. Encoders
1. $2^n$ to $n$ Decoders
Take an 8-to-3 encoder for example
2. Priority Encoder
Take a 4 bits inputs encoder for example
8. Multiplexers
1. $2^n$ Inputs Multplexers
2. Quadruple Two-to-One-Line Multiplexers
3. Three-States and Multiplexers
1. Three-States Buffer
2. Bus
3. Multiplexer

**Reference**
NCKUCSIE 1101_Introduction to Digital System
Digital Design With an Introduction to The Verilog HDL, VHDL and System Verilog 6/e by M.Morris Mano Michael D. Ciletti