Aritmetica Binaria, Octal Hexadecimal

2.1 Binary System Operations In this section we will discuss binary addition. We will defer binary subtraction until we introduce the two’s and one’s complements in a later section of this chapter. Binary multiplication and binary division is discussed in Chapter 10 in conjunction with shift registers. The addition of numbers in any numbering system is accomplished much the same manner as decimal addition, that is, the addition starts in the least significant position (right most position), and any carries are added in other positions to the left as it is done with the decimal system. The binary number system employs the numbers 0 and 1 only; therefore, the possible combinations of binary addition are: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 with a carry of 1

We observe that in a binary addition the largest digit in any position is 1 , just as in the decimal addition the largest digit is 9 . Furthermore, the above combinations indicate that if the number of ones to be added in any column is odd, the sum digit for that column will 1 be , and if the number of ones to be added in any column is even, then the sum digit for that column will be zero. Also, a carry occurs whenever there are two or more ones to be added in any column. Example 2.1 Add the numbers (01101101) 2 and (1110011) 2 Solution: 1111111 Carries 101101101 + 1110011 ____________________ 111100000

Check: ( 101101101) 2 = (365) 10 ( 1110011) 2 = (115) 10

Then, (111100000) 2 = (365 + 115) 10 = (480) 10

Example 2.2 Add the numbers (110110) 2 (101001) 2 (111000) 2 (10101) 2 and (100010) 2

Solution: 11 11 111111 Carries 110110 101001 111000 10101 100010 --------------1 1 001110

Check: (54) 10 (41) 10

( 110110) 2

=

( 101001) 2

=

( 111000) 2

=

(56) 10

( 10101) 2 =

(21) 10

(

100010) 2

=

(34) 10

Then, ( 11001110) 2 = (54 + 41 + 56 + 21 + 34) 10 = (206) 10

2.2 Octal System Operations The addition of octal numbers is also very similar to decimal numbers addition except that when the sum of two or more octal numbers exceeds seven, a carry occurs just as a carry occurs when the sum of two or more decimal numbers exceeds nine. Table 2.1 summarizes the octal addition. This table can also be used for octal subtraction as it will be illustrated by Example 2.4. TABLE 2.1 Table for Addition and subtraction of octal number

1

0 0 2

2

1 1 3 3

2 2 4 4

3 3 5 5

4 6 6

4 5 5 7 7

6 6 10 10

7 7 11

3 4 5 6 7

4 5 6 7 10

5 6 7 10 11

6 7 10 11 12

7 10 11 12 13

10 11 12 13 14

11 12 13 14 15

12 13 14 15 16

TABLE 2.1 Table for Addition and subtraction of octal numbers

When Table 2.1 above is used for addition, we first locate the least significant digit of the first number (augend) in the upper row of the table, and then we locate the least significant digit of the second number (addend) in the left most column of the table. The intersection of the augend with the addend gives the sum of these two numbers. We follow the same procedure for all other digits from right to left. Example 2.3 Add the numbers (3527) 8 and(4167) 8 Solution: 011 Carries 3527 + 4167 ______ 7716

Starting with the least significant digit column above, we add 7 with 7 and the table gives us 16 i.e.6 with a carry of 1. Next we add 6 and 2, with a carry of 1 , or 6 and 3, and the table gives 11 us i.e., 1 with a carry of 1 . Now we add 1, 5 and 1 (carry) and we obtain 7 with no carry. Finally, we add 4 and 3 which gives 7 and no carry. As before, we can check the sum for correctness by converting the numbers to their equivalent decimal numbers. When Table 2.1 above is used for subtraction, we first find the least significant digit of the subtrahend (the smaller number) in the first row of the table. Then, in the same column, we locate the least significant digit of the minuend (the larger number). If the least significant digit of the minuend is less than the least significant digit of the subtrahend, a borrow occurs and from the numbers 10 through 16 in the table we choose the one whose least significant digit matches the least significant digit of the minuend. We find the difference by going across to the left most column. We follow the same procedure for all other digits from right to left. Example 2.4 Subtract (415) 8 from ( 614) 8

Solution: 614 -

415

______ 177 The least significant digit of the subtrahend is 5 and we locate it in the first row of Table 2.1. Going down that column where 5 appears, we choose 14 because the least significant digit of the minuend is 4. The difference, 7 in this case with a borrow, appears across to the left most column. Next, we add the borrow to the next digit of the subtrahend, 1 in this case, so now we must subtract 2from 1. Continuing we locate 2 in the first row of the table and going down on the same column we choose 11 because the next digit of the minuend is 1 , and again from the left most column we find that the difference is 7 with another borrow. Finally, we add that borrow to 4 and now we subtract from and this difference of appears in the most significant position of the result with no borrow.

2.3 Hexadecimal System Operations

Hexadecimal addition and subtraction is accomplished similarly to that of addition and subtraction with octal numbers except that we use Table 2.2. When Table 2.2 below is used for addition, we first locate the least significant digit of the first number (augend) in the upper row of the table, and then we locate the least significant digit of the second number (addend) in the left most column of the table. The intersection of the augend with the addend gives the sum of these two numbers. We follow the same procedure for all other digits from right to left. TABLE 2.2 Table for Addition and subtraction of hexadecimal numbers 0 C 1 D 2 E 3 10 4 10 5 11 6 12 7 13 8 14 9

1 D 2 E 3 F 4 11 5 11 6 12 7 13 8 14 9 15 A

2 E 3 F 4 10 5 12 6 12 7 13 8 14 9 15 A 16 B

3 F 4 10 5 11 6 7 13 8 14 9 15 A 16 B 17 C

4

5

6

7

5

6

7

8

6

7

8

9

7

8

9

8

9

9

A

A

8 9

C

B C

B

B

A

A B

A

9

D

C D

D

A

B

B

C

C

D

E

F

E

F

E

F

10 11

A

B

C

D

E

F

10

B

C

D

E

F

10

11

12

C

D

E

F

10

11

12

13

D

E

F

10

11

12

13

14

15 A 16 B 17 C 18 D 19 E 1A F 1B

16 B 17 C 18 D 19 E 1A F 1B 10 1C

17 C 18 D 19 E 1A F 1B 10 1C 11 1D

18 D 19 E 1A F 1B 10 1C 11 1D 12 1E

E

F

10

11

12

13

14

15

F

10

11

12

13

14

15

16

10

11

12

13

14

15

16

17

11

12

13

14

15

16

17

18

12

13

14

15

16

17

18

19

13

14

15

16

17

18

19

1A

Example 2.5 Add the numbers (F347) 16 and (E916) 16 Solution:

F347 + E916 1DC5D

Starting with the least significant digit column above, we add with and the table gives us D with no carry. Next, we add 4 and 1 and we obtain 5 with no carry. Now, we add 9 and and 3 we C obtain with no carry. Finally, we add F and E and that gives 1D . As before, we can check the sum for correctness by converting the numbers to their equivalent decimal numbers. Example 2.6 Subtract (A9F8) 16 from (D5C7) 16 Solution: D5C7 -

A9F8 2BCF

The subtraction begins by locating the least significant digit of the subtrahend, in this case, in the first row of Table 2.2, and going down the same column we find 17 on the last row of the table. Going across to the left most column we find that the difference is F with a borrow. Next, because of the borrow, we reduce the digit C of the minuend to B and from it we subtract. The difference is found by locating F in the first row, going down the same column we find 1B , and going across to the left most column we find that the difference is C with a borrow. Now, because of the previous borrow, we reduce 5 to 4 and subtracting 9 from it we find that the difference is B with another borrow. Finally, because of the previous borrow, we reduce D to C and we subtract A from it. The difference is 2 with no borrow.

2.4 Complements of Numbers

The subtraction operation is simplified by the use of the complements of numbers. For each base−b system there are two useful types of complements, the b’s−complement And the (b−1)’s−complement. Accordingly, for the base−10 system we have the tens − complements and the nines − complements, for the base−2 we have the twos − complements and ones − complements, for the base−8 we have the eights − complements and sevens − complements, and for the base−16 we have the sixteens − complements and the fifteens - complements.

2.4.1Tens − Complement

The tens − complement of a number can be found by subtracting the first non − zero least significant digit and all zeros to the right of it from 10; then, we subtract all other digits from 9. Example 2.7 Find the tens _complement of 23567 Solution: We first subtract 7 (lsd) from 10 and we obtain 3 . This is the lsd of the tens − complement. For the remainder part of the tens complement, we subtract 6,5,3 , and 2 from 9 and we obtain 3, 4,6 , and respectively. Therefore, the tens - complement of 23567 is 76433 Example 2.8 Find the tens − complement of 0.8642 Solution: We first subtract 2 (lsd) from 10 and all other digits from 9. Therefore, the tens − complement of 0.8642 is 0.1358 Example 2.9 Find the tens _ complement of 37.562 Solution: We first subtract 2(lsd) from 10 and all other digits from 9. Therefore, the tens − complement of 37.562 is 62.438.

2.4.2Nines− Complement The nines− complement of a number can be found by subtracting every digit (lsd) of that number from 9. Example 2.10 Find the nines_complement of 23567

Solution: We subtract every digit of the given number from and we find that the nines−complement of 23567 is 76432. We observe that this complement is one less than which, as we found in Example 2.7, is the tens − complement of 23567. This is always the case, that is, the nines − complement is always one less than the tens − complement. Alternately, we can add 1 to the nines − complement to obtain the tens − complement. Example 2.11 Find the nines − complement of 37.562 Solution: We subtract every digit of the given number from 9 and we find that the nines − complement of 23567 is 76432 .Therefore, the nines − complement of 37.562 is 62.437.

2.4.3Twos− Complement The twos −complement of a number can be found by leaving all the least significant zeros and the least significant one unchanged and then replacing all zeros with ones and all ones with zeros in all the other digits. Example 2.12 Find the twos − complement of 1101100 Solution: Starting from the right side of the given number we leave 100 unchanged and then for the remaining digits, i.e, 1101 we replace the ones with zeros and the zero with one. Therefore, the twos − complement of 1101100 is 0010100. Example 2.13 Find the twos− complement of 0.1011 Solution: We leave the lsd (last 1 ) unchanged and we replace the ones with zeros and the zero with one. Therefore, the twos - complement of 0.1011 is 0.0101. The leading 0 to the left of the binary point that separates the integer and fractional parts remains unchanged.

Example 2.14 Find the twos − complement of 1101100.1011 Solution: We leave the lsd (last 1 ) unchanged and we replace the ones with zeros and the zeros with ones. Therefore, the twos - complement of 1101100.1011 is 0010011.0101

2.4.4Ones−Complement The ones − complement of a number can be found by replacing all zeros with ones and all ones with zeros. Example 2.15 Find the ones− complement of 1101100 Solution: Replacing all ones with zeros and all zeros with ones we find that the ones− complement 1101100 of 0010011 is . We observe that this complement is one less than 0010100 which, as we found in Example 2.12, is the twos − complement of 1101100. This is always the case, that is, the ones − complement is always one less than the twos − complement. Alternately, we can add 1to the ones – complement to obtain the twos- complement. Example 2.16 Find the ones− complement of 0.1011 Solution: Replacing all ones with zeros and all zeros with ones we find that the ones− complement of 0.1011 is 0.100 . The leading 0 to the left of the binary point that separates the integer and fractional parts remains unchanged. Example 2.17 Find the ones− complement of 1101100.1011 Solution: Replacing all ones with zeros and all zeros with ones we find that the ones− complement of 1101100.1011 is 0010011.0100

2.5 Subtraction with Tens_ and Twos_Complements

We will assume that the numbers for the subtraction operation are both positive numbers. The subtraction operation using tenscomplement or twos-complements is performed as follows: 1. Take the tens −complement or twos-complement of the subtrahend and add it to the minuend which remains unchanged. 2. Check the result (sum), and a. if an end carry occurs, discard it. b. if an end carry does not occur, take the tens − complement or twos− complement of the result (sum) and place a minus ( − ) sign in front of it. Example 2.18 Perform the subtraction tens − complement method.

(61435

–

02798)

using

the

Solution: Minuend = 61435 stays unchanged 61435 Subtrahend 02798 take tens - complement 97202 Discard end carry 158637

Therefore,

(61435 – 02798) 10

=

(58637) 10

Example 2.19 Perform the subtraction using the tens− complement method. Solution: Minuend = 02798 stays unchanged Subtrahend 61435 take tens – complement 38565

02798

No end carry

41363

Since there is no end carry, we take the tens − complement of the sum 41363 and we place a minus (−) sign in front of it resulting in -58637. Therefore, (02798 – 61435) 10 = (−58637) 10 Example 2.20 Perform the subtraction twos− complement method.

(1101100

–

1011011)

Solution: Minuend = 1101100 stays unchanged 1101100

2

using

the

Subtrahend = 1011011 take twos - complement 0100101 Discard end carry

10010001

Therefore, ( 1101100

–

1011011) 2

=

(0010001) 2

Example 2.21 Perform the subtraction twos − complement method.

(1011011

–

1101100) 2

using

the

Solution: Minuend = 1011011 stays unchanged 1011011 Subtrahend 1101100 take twos complement + 0010100 No end carry

1101100

Since there is no end carry, we take the twos− complement of the sum and we place a minus (−) sign in front of it resulting in -0010001. Therefore, ( 1011011 – 1101100) 2 = (–0010001) 2

.

2.6 Subtraction with Nines− and Ones− Complements We will assume that the numbers for the subtraction operation are both positive numbers. The subtraction operation using nines− complement or ones− complements is performed as follows: 1. Take the nines− complement or ones −complement of the subtrahend and add it to the minuend which remains unchanged. 2. Check the result (sum), and a. if an end carry occurs, add 1 − referred to as end around carry − to the lsd of the result (sum). b. if an end carry does not occur, take the nines− complement or ones− complement of the result (sum) and place a minus ( − ) sign in front of it. Example 2.22 Perform the subtraction (61435 – 02798) 10 using the nines− complement method. Solution: Minuend = 61435 stays unchanged 61435 Subtrahend 02798 take nines complement + 97201 Make end carry an end around carry 158636 +

End around carry 1 58637

Therefore, ( 61435 – 02798) 10 = (58637) 10

Example 2.23 Perform the subtraction (02798 – 61435) 10 using the nines −complement method. Solution: Minuend = 02798 stays unchanged 02798 Subtrahend 61435 take nines complement + 38564 No end carry 41362

Since there is no end carry, we take the nines − complement of the sum 41362 and we place a minus (−) sign in front of it resulting in -58637. Therefore, . Example 2.24

( 02798 – 61435) 10 = (–58637) 1

Perform the subtraction (1101100 – 1011011) using the ones− complement method. Solution: Minuend = 1101100 stays unchanged 1101100 Subtrahend 1011011 take ones complement + 0100100 Make end carry an end around carry

10010000 0010000 End around carry + 1 0010001

Therefore, ( 1101100 – 1011011) 2 = (0010001) 2

Example 2.25 Perform the subtraction (1011011 – 1101100) 2 using the ones− complement method. Solution: Minuend = 1011011 stays unchanged

1011011

Subtrahend = 1101100 take ones complement

+ 0010011

No end carry

1101110

Since there is no end carry, we take the ones − complement of the sum 1101110 and we place a minus (−) sign in front of it resulting in – 0010001

Therefore, (1011011 – 1101100) 2 = (–0010001) 2.

Fundamentals of Boolean Algebra

T

his chapter begins with the basic logic operations and continues

with the fundamentals of Boolean algebra and the basic postulates and theorems as applied to electronic logic circuits. truth tables are defined and examples are given to illustrate how they can be used to prove Boolean algebra theorems or equivalent expressions.

5.1 Basic Logic Operations The following three logic operations constitute the three basic logic operations performed by a digital computer. 1. Conjunction (or logical product) commonly referred to as the AND operation and denoted with the dot (.) symbol between variables. 2. Disjunction (or logical sum) commonly called the OR operation and denoted with the plus (+) symbol between variables

3. Negation (or complementation or inversion) commonly called NOT operation and denoted with the bar (−) symbol above the variable.

5.2 Fundamentals of Boolean Algebra This section introduces the basics of Boolean algebra. We need to know these to understand Chapter 6 and all subsequent chapters in this text.

5.2.1 Postulates Postulates (or axioms) are propositions taken as facts; no proof is required. A well − known axiom states that the shortest distance between two points is a straight line. 1. Let X be a variable. Then,X=0 or X=1 . If ,X=0 then X’= 1, and vice− versa. 2.0 .0 = 0 3.0.1= 1.0= 0 4.1.1.= 1 5.0+0= 0 6.0+1 = 1 + 0 = 1 7.1+1 = 1

5.2.2 Theorems 1. Commutative laws a. A . B = B . A b.A + B = B + A 2. Associative laws a. ( A . B) . C = A . ( B . C) b. A + B) + C = A + (B + C) 3. Distributive laws a. A . ( B + C) = A . B + A . C b. A . (B + C) = (A + B) . ( A + C) 4. Identity laws a. A . A = A

b. A + A = A

5. Negation laws a. A’ = A’ b. (A)’’

= A’’ = A

6. Redundancy laws a. A . ( A + B) = A b. A + (A . B) = A

7. a. 0 . A = 0 b. 1 . A = A

c. 0 + A = A d. 1 + A = 1

8. a. A . A’ = 0 b. A + A’ = 1

9. a. A . ( A + B) = A . B b. A + (A . B) = A + B

10. DeMorgan’s theorems a.( A . B)’ = A’ + B’ b. (A + B)’ = A’ . B’

5.3 Truth Tables A truth table provides a listing of every possible combination of inputs and lists the output of a logic circuit which results from each input combination. A truth table can be used to prove that one logical expression is equal to another or to prove theorems. When a proof is accomplished by the use of the truth table it is called proof by perfect induction. Example 5.1

Simplify the Boolean expression C = A’ . B + A . B + A’ . B Solution: From Theorem 3.a, A . B + A . C = A . ( B + C) and for this example, A . B + A . B = (A + A)B and from Theorem 8.b, A + A = 1 . Then, the given expression reduces to C = 1 . B + A’ . B’

Next, from Theorem 7.b, 1 . B = B and thus C = B + A’ .

B’

Finally, from Theorem 9.b, A + (A’ . B) = A + B or B + (B’ . A) = A + B. Therefore, C= A’ + B