---
tags: Introduction to Digital System
---
# Chapter 3-Gate-Level Minimization
## The Map Method
1. Rules:
1. Draw a square and split them into several small squares.
2. Fill in minterms in each small squares.
3. Write the corresponding binary number aside the margins. Note that the binary number is from 0 and the next binary number should be only changed a bit of number.
4. Fill in the outcomes in small squares.
5. Sum the products which is 1 together. If there is a products aside, we can simplify them.
* ※Sums like below can also be merged first
* ※Terms with the least adjacent terms should be considered first.
* ※A box that 8->4->2->1 terms are adjacent should be considered in order.
6. Don't-Care Conditions: A don't-care minterm is a combination of variables whose logical value is not specified. In a k-map, it is marked "X", which can be 0 or 1.
2. Examples:
1. Two-Variable K-Map
2. Three-Variable K-Map:
3. Four-Variable K-Map:
## NAND and NOR Implementation
1. NAND Implementation
1. Introduction: AND, OR, NOT gates can be replaced by NAND gates.
2. Implementation:
1. Two Level Implementation
2. Multilevel NAND Circuits
1. Draw the SOP
2. Convert all AND gates to NAND gates with AND-invert graphic symbols.
3. Convert all OR gates to NAND gates with invert-OR graphic sympls.
4. Check all the bubbles in the diagram. For every bubble that is not compensated by another small circle along the same line, insert an inverter or complement the input literal.
2. NOR Implementation
1. Introduction
2. Implementation
1. Draw the POS
2. Convert
3. Implementation of XOR
1. Definition
1. Two Variables
1. $x\bigoplus y=x'y+xy'$
2. $(x\bigoplus y)'=xy+x'y'$
2. N Variables
2. Properties
1. $x\bigoplus0=x$
2. $x\bigoplus1=x'$
3. $x\bigoplus x=0$
4. $x\bigoplus x'=1$
5. $x\bigoplus y'=x'\bigoplus y=(x\bigoplus y)'$
6. $x\bigoplus y=y\bigoplus x$
7. $(x\bigoplus y)\bigoplus z=x\bigoplus(y\bigoplus z)$
3. Parity Generation and Checking
Take even parity for example:
$Parity\ Bit\ P=x\bigoplus y\bigoplus z...\\Parity\ Error\ Check\ C=x\bigoplus y\bigoplus z...\bigoplus P$

**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