Wednesday, September 22, 2010

Numbers with Different Base (Number System)

Decimal

(base 10)

Binary

(base 2)

Octal

(base 8)

Hexadecimal

(base 16)

00

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

00

01

02

03

04

05

06

07

10

11

12

13

14

15

16

17

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

Complements

Complements are used in digital computers for simplifying the subtraction operation and for logical manipulations. There are two types of complements for each base-r system: (1) the r’s complement and (2) the (r-1)’s complement. When the value of the base is substituted, the two types receive the names 2’s and 1’s complement for binary numbers, or 10’s and 9’s complement for decimal numbers:

The r’s Complement:

Given a positive number N in base r with an integer part of n digits, the r’s complement of N is defined as rn-N for N≠0 and 0 for N=0. The following numerical example will help clarify the definition.

The 10’s complement of (52520)10 is 105 – 52520 = 47480.

The number of digits in the number is n = 5.

The 10’s complement of (0.3267)10 is 1 – 0.3267 = 0.6733.

No integer part, so 10n = 100 = 1.

The 10’s complement of (25.639)10 is 102 – 25.639 = 74.361.

The 2’s complement of (101100)2 is (26)10 – (101100)2 = (1000000 – 101100)2 = 010100.

The 2’s complement of (0.0110)2 is (1 – 0.0110)2 = 0.1010.

The (r – 1)’s Complement:

Given a positive number N in base r with an integer part of n digits and a fraction part of m digits, the (r – 1)’s complement of N is defined as rn – r-m – N. Some numerical examples follow:

The 9’s complement of (52520)10 is (105 – 1 – 52520) = 99999 – 52520 = 47479.

No fraction part, so 10-m = 100 = 1.

The 9’s complement of (0.3267)10 is (1 – 10-4 – 0.3267) = 0.9999 – 0.3267 = 0.6732.

No integer part, so 10n = 100 = 1.

The 9’s complement of (25.639)10 is (102 – 10-3 – 25.639) = 99.999 – 25.639 = 74.360.

The 1’s complement of (101100)2 is (26 – 1)10 – (101100)2 = (111111 – 101100)2 = 010011.

The 1’s complement of (0.0110)2 is (1 – 2-4)10 – (0.0110)2 = (0.1111 – 0.0110)2 = 0.1001.

Postulates and Theorems of Boolean Algebra

Postulate 2

Postulate 5

Theorem 1

Theorem 2

Theorem 3, involution

Postulate 3, commutative

Theorem 4, associative

Postulate 4, distributive

Theorem 5, DeMorgan

Theorem 6, absorption

x + 0 = x

x + x’ = 1

x + x = x

x + 1 = 1

(x’)’ = x

x + y = y + x

x + (y + z) = (x + y) + z

x (y + z) = xy + xz

(x + y)’ = x’y’

x + xy = x

x . 1 = x

x . x’ = 0

x . x = x

x . 0 = 0

xy =yx

x(yz) = (xy)z

x + yz = (x + y)(x + z)

(xy)’ = x’ + y’

x(x + y) = x

Minterms and Maxterms for three Binary Variables

Minterms

Maxterms

x y z

Term

Designation

Term

Designation

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

x’ y’ z’

x’ y’ z

x’ y z’

x’ y z

x y’ z’

x y’ z

x y z’

x y z

m0

m1

m2

m3

m4

m5

m6

m7

x + y + z

x + y + z’

x + y’+ z

x + y’+ z’

x’+ y + z

x’+ y + z’

x’+ y’+ z

x’+ y’+ z’

M0

M1

M2

M3

M4

M5

M6

M7

Karnaugh Map (K Map)

The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem.

The values inside the squares are copied from the output column of the truth table, therefore there is one square in the map for every row in the truth table. Around the edge of the Karnaugh map are the values of the two input variable. A is along the top and B is down the left hand side. The diagram below explains this:

The values around the edge of the map can be thought of as coordinates. So as an example, the square on the top right hand corner of the map in the above diagram has coordinates A=1 and B=0. This square corresponds to the row in the truth table where A=1 and B=0 and F=1. Note that the value in the F column represents a particular function to which the Karnaugh map corresponds.

Universal Gate

Universal Gates:

A universal gate is a gate which can implement any Boolean function without need to use any other gate type.

The NAND and NOR gates are universal gates.

In practice, this is advantageous since NAND and NOR gates are economical and easier to fabricate and are the basic gates used in all IC digital logic families.

In fact, an AND gate is typically implemented as a NAND gate followed by an inverter not the other way around.

Likewise, an OR gate is typically implemented as a NOR gate followed by an inverter not the other way around.

NAND Gate is a Universal Gate:

To prove that any Boolean function can be implemented using only NAND gates, we will show that the AND, OR, and NOT operations can be performed using only these gates.

NOR Gate is a Universal Gate:

To prove that any Boolean function can be implemented using only NOR gates, we will show that the AND, OR, and NOT operations can be performed using only these gates.