## 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. 