Digital and Computer System [1] - Fundamentals

Fundamentals

Reference Book:

M. Morris Mano and Charles R. Kime, Logic and Computer Design Fundamentals, 4th Edition, Prentice Hall, 2008

Number Systems

Decimal numbers

A digit is a single place that can hold numerical values between 0 and 9.

Binary numbers

Only two values in a binary digit: 0 and 1.

Example:

$(11010)_{2} = 1\times2^{4}+1\times2^3+0\times2^2+1\times2^1+0\times2^0 = 26$

Conversion from Decimal

Method 1: Use Calculator

Method 2:

Complements

• Radix-1 complement: each digital of the number is subtracted from the radix
• Radix complement: add a 1 to the radix-1 complement of the number.

Complements Example – 1 and 2’s complement in a binary system. (to represent -ve number in a computer)

• 1’s complement: invert each bit of a number from 0 to 1 or from 1 to 0.
• 2’s complement: add a 1 to the 1’s complement

In computer, byte instead of bit is used as the minimum unit for data storage and retrieval.

Common Data Types

Fixed-Point Number

For Postive Number:

For Negative Number:

Lets say we want to represent -5.

$(5)_{10}$ is $(0,000, 0101)_{b}$

-> 1’s complement (invert all bits)

$(-5)_{10}$ is $(1,111, 1010)_{b}$

-> 2’s complement (plus a 1)

$(-5)_{10}$ is $(1,111,1011)_b$

For Number with Decimal Point (IEEE single precision):

Method1 to find binary:

$12 = 6\times2 + 0$

$6 = 3\times2+0$

$3 = 1\times2+1$

$1 = 0\times2 + 1$

See the number after + sign from bottom to top.

Therefore $12 = 1100_b$

$0.125\times2 = 0.25$

$0.25\times2 = 0.5$

$0.5 \times 2 = 1$

See the number before . sign from top to bottom.

There $0.125 = 001_b$

Method2 to find binary:

$12 = 1\times2^3+1\times2^2+0\times2^1+0\times2^0 = 1100_b$

$0.125 = 0\times2^{-1} + 0\times2^{-2} + 1\times2^{-3} = 001_b$

-> $-12.0125 = -1100.001_b$

To find exponent : move the dot to after the first number => count how many number moved

$-1100.001_b => -1.100001_b$

Sign bit: $S = 1$ (Negative Number)

Exponent: $E = 3$ => $127+3$ => $130$ => $10000010_2$ (Note the exp bias is 127)

Mantissa: 100001 ~0 (The number after .)

Then the whole stuff is : $1\space1000001\space0100001\space0_b$

Then change them to hex number.

$11000001 = C1$

$01000010 = 42$

$00000000 = 00$

$00000000 = 00$

Therefore the solution is $C1420000_H$

---

To do it backwards : (From IEEE to Decimal)

Why There is a Bias 127 in Exponent in IEEE 754 Standard Single Precision

---

ASCII code

BCD code (Binary-Coded Decimal code)

• Only 0-9 are represented in binary

• For decimal Arithmetic operations in computer

---

From Boolean algebra to Computer

How a computer thinks

Boolean algebra can be realized with tiny electronic components called logic gates.

Any logical operation can be composed with the 3 basic logical operations.

Basic logical operations:

• NOT(!) - Notice the bubble o

• AND(*) - Looks Like a D

• OR(+)

Any logical operation can be composed in either of 2 forms

Sum of Product (Notice the gate!)

Product of Sum (Notice the gate!)

Read Here to understand the concept of SOP and POS

Basic Identities of Boolean Algebra

$X + 0 = X$

$X + 1 = 1$

$\overline{\overline{X}} = X$

$X\cdot1 = X$

$X\cdot 0=0$

---

Special Note:

$X + X = X$

$X + \overline{X} = 1$

$X\cdot X=X$

$X\cdot \overline{X}=0$

---

Commutative :

$X+Y = Y+X$

$XY = YX$

Associative :

$X + (Y+Z) = (X+Y)+Z$

$X(YZ)=(XY)Z$

Distributive :

$X(Y+Z) = XY+XZ$

$X + YZ = (X+Y)(X+Z)$

DeMorgan’s Theorem

Usage of basic identities and the DeMorgan’s Theorem

Lets see this example.

$Z = \bar{X}\cdot\bar{Y} + \bar{X}\cdot Y + X.\bar{Y}$

First, Use the Distributive approach (Draw common factor of $\bar{X}$).

$Z = \bar{X}\cdot (\bar{Y}+Y)+X\cdot\bar{Y}$

Note that $\bar{Y} + Y = 1$.

$Z = \bar{X}\cdot 1 + X \cdot \bar{Y}$

Note that $\bar{X}\cdot 1$ is $\bar{X}$.

$Z = \bar{X} + X\cdot\bar{Y}$

Now Use DeMorgan’s Law.

$Z = \overline{(X\cdot(\bar{X}+Y))}$

Then Use the Distributive approach.

$Z = \overline{(X\cdot\overline{X}+X\cdot Y)}$

Note that $\bar{X}\cdot X=0$, Therefore the Simpliest form is :

$Z = \overline{X\cdot Y}$

---

Boolean Function

• well defined with its corresponding truth table

Canonical Forms

to specify Boolean functions in a form that allows comparison for equality.

• Sum of Minterms (SOM)
• Product of Maxterms (POM)

What is meant by Minterm and Maxterm?

口號：Min乘Max加

Minterm( $\cdot$ )

• A product term in which each of the n variables appears once
• (in either its complemented or normal form).
• Example : $A$ and $G$ can produce 4 minterms : $AG$,$A\bar{G}$,$\bar{A}\bar{G}$,$\bar{A}G$

Maxterm( $+$ )

• A sum term in which each of the n variables appears once
• (in either its complemented or normal form).
• Example : $A$ and $G$ can produce 4 maxterms : $A+G$,$A+\bar{G}$,$\bar{A}+G$,$\bar{A}+\bar{G}$

Connection Among the terms

$\sum$ means the sum. $\prod$ means the product.

$m$ Means the minterm while $M$ means the maxterm.

sum of minterms(numbers) = product of maxterms(not the numbers in minterm)

$$\sum m(0,3,4,6,7) = \prod M(1,2,5)$$

Boolean Function Optimization

Literal Cost

Literal

• a variable or it complement

Literal Cost

• the number of literal appearances in a Boolean expression
• It is Better to have a lower literal cost.
• Example : $F = BD + \bar{A}BC + ACD;$ Therefore $L = 8$ . (2+3+3)

Gate Input Cost

• the number of inputs to the gates (G – inverters not counted)
• It is Better to have a lower Gate Input cost.
• Example :

![](

---

Kmap (Karnaugh Map) (Very Important)

More Details

ONLINE K-MAP SOLVER (EXTREMELY USEFUL)

one of the tools to get simplest expression of a Boolean function.

1. Turn a Truth Table into a Representation of Functions in the Map.
2. Minimize no. of groups (circle the square groups (only 2 or 4 or 8) (Circle the 1s)
3. For each group, minimize the literal cost (no. of variables in a product)
4. Don’t care terms = X. You can consider the X as 0 or 1 during grouping.
5. Plot all the circled numbers out (ABCD). Cross out if there exist both 1 and 0.

Some Exercise/Examples Here:

Tricks

To derive minimal boolean function of any circuit, you can use the 3 approach :

Approach 1 : Use Truth Table

Approach 2 : Use K-map to simplify (Recommend)

Approach 3 : Directly derive it from the circuit (You may get wrong easily)