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:
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.
is
-> 1’s complement (invert all bits)
is
-> 2’s complement (plus a 1)
is
For Number with Decimal Point (IEEE single precision):
Method1 to find binary:
See the number after + sign from bottom to top.
Therefore
See the number before . sign from top to bottom.
There
Method2 to find binary:
->
To find exponent : move the dot to after the first number => count how many number moved
Sign bit: (Negative Number)
Exponent: => => => (Note the exp bias is 127)
Mantissa: 100001 ~0 (The number after .)
Then the whole stuff is :
Then change them to hex number.
Therefore the solution is
To do it backwards : (From IEEE to Decimal)
Why There is a Bias 127 in Exponent in IEEE 754 Standard Single Precision
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
Special Note:
Commutative :
Associative :
Distributive :
DeMorgan’s Theorem
Usage of basic identities and the DeMorgan’s Theorem
Lets see this example.
First, Use the Distributive approach (Draw common factor of ).
Note that .
Note that is .
Now Use DeMorgan’s Law.
Then Use the Distributive approach.
Note that , Therefore the Simpliest form is :
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( )
- A product term in which each of the n variables appears once
- (in either its complemented or normal form).
- Example : and can produce 4 minterms : ,,,
Maxterm( )
- A sum term in which each of the n variables appears once
- (in either its complemented or normal form).
- Example : and can produce 4 maxterms : ,,,
Connection Among the terms
means the sum. means the product.
Means the minterm while means the maxterm.
sum of minterms(numbers) = product of maxterms(not the numbers in minterm)
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 : Therefore . (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)
ONLINE K-MAP SOLVER (EXTREMELY USEFUL)
one of the tools to get simplest expression of a Boolean function.
- Turn a Truth Table into a Representation of Functions in the Map.
- Minimize no. of groups (circle the square groups (only 2 or 4 or 8) (Circle the 1s)
- For each group, minimize the literal cost (no. of variables in a product)
- Don’t care terms = X. You can consider the X as 0 or 1 during grouping.
- 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)