Digital Systems and Binary Numbe1

DIGITAL SYSTEMS 

What is Digital System?

-          Digital System: is a system in which signals have finite number of discrete values (electric impulses, decimal digits, arithmetic operations, etc.)

-          Analog System: is a system in which signals have infinite number of values (electric voltage that vary with time).

-          Synchronous: Systems where signals may change only at discrete instants.

-          Asynchronous: Systems where signals may change at any instant.

Why Are Digital Systems important?

-          It is well suited for numerical and non-numerical information processing.

-          Information processing can use a general-purpose system (computer).

-          The finite number of values in a digital signal is represented by a vector of signals with just 2 values (binary signals).

- Digital signals are quite insensitive to variations of component variable values.

-          Numerical digital systems can be made more accurate by increasing the number of digits used in the representation.

-          Complex digital systems are built as integrated circuits composed of a large number of very simple devices.

-          It is possible to select among different implementations of systems that trade off speed and amount of hardware.

When Are Digital Systems Used?

-          Digital representation and processing methods widely used

-          Extraordinary progress in digital technology and use Indispensable in modern society

-          New applications fueled by the development of computer technology

-          Knowledge about the design and use of digital systems required in a large variety of human activities

Analog and Digital Signals

-          The process of converting from analog to digital is call quantization or digitization.

Combinational and Sequential Systems

-          Digital systems are divided into 2 classes:

o   Combinational systems: the output at time t depends only on the input at t.

o   z (t) = F (x(t))

o   In this case we can say that the system has no memory b/c the output doesn’t depend on previous inputs.

o   Sequential systems: the output at time t depends on the input at time t and possibly on the input prior to t.

o z (t) = F (x(0,t))

o   where x (0,t) is the input sequence from time 0 to time t.

Binary Numbers

 -          A decimal number such as 7392 can be represented as: 7 x 103 + 3 x 102 + 9 x 101 + 2 x 100

 -          A number with a decimal point is represented by a series of coefficients as follows:

a5 a4 a3 a2 a1 a0. a-1 a-2 a-3

 -      The decimal equivalent of the binary 11010.11 is 26.75

1 x 24 + 1 x 23 + 0 x 22 + 1 x 21 + 0 x 20 + 1 x 2-1 + 1 x 2-2 = 26.75

 -          A number expressed in base-r system has coefficients multiplied by powers of r: an . rn + an-1 . rn-1 + . . . + a2 . r2 + a1 . r + a0 + a-1 . r-1 + a-2 . r-2+ . . . + a-m . r-m where r = 2,3,4... 8,9,10, ...16...

 System

Radix

Allowable Digits

Binary

2

0,1

Octal

8

0,1,2,3,4,5,6,7

Decimal

10

0,1,2,3,4,5,6,7,8,9

Hexadecimal

16

0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F

- (4021.2)5 =

4 x 53 + 0 x

4 x 125 + 0

52 + 2 x 51 + 1 x 50 + 2 x 5-1 = (511.4)10

+ 10 + 1 + 2 x (1/5)

500 + 11 +

.4

- (B65F)16 =      11 x 163 + 6 x 162 + 5 x 161 + 15 x 160 = (46687)10

11 x 4096 + 6 x 256 + 5 x 16 + 15

45056 + 1536 + 80 + 15

Augend:

101101

minuend:

101101

multiplicand: 1011

Addend:

+ 100111

subtrahend:

-100111

multiplier:   x 101

1010100                               000110                           110111

Number Base Conversions

-          A binary number can be converted to decimal by forming the sum of powers of 2 of those coefficients whose value is 1.

(1010.011) 2 = 23 + 21 + 2-2 + 2-3 = (10.375) 10

-          Similarly, a number expressed in base r can be converted to its decimal equivalent by multiplying each coefficient with the corresponding power of r and adding.

(630.4) 8 = 6 x 82 + 3 x 81 + 0 x 80 + 4 x 8-1 = (408.5) 10

-          Conversion from Decimal 41 to Binary:

Integer quotient              Remainder           Coefficient

41/2

=

20

+

½

a0 = 1

20/2

=

10

+

0

a1 = 0

10/2

=

5

+

0

a2 = 0

5/2

=

2

+

½

a3 = 1

2/2

=

1

+

0

a4 = 0

1/2

=

0

+

½

a5 = 1

-          The conversion from decimal integers to any base-r system is similar to the example, except that division is done by r instead of 2.

-          Conversion from Decimal 153 to Octal:

153

19 1

2  3

0 2 = (231) 8

-          Conversion from Decimal fraction (0.6875) 10 to Binary:

Integer

Fraction

Coefficient

0.6875 x 2 =

1

+

0.3750

a-1 = 1

0.3750 x 2 =

0

+

0.7500

a-2 = 0

0.7500 x 2 =

1

+

0.5000

a-3 = 1

0.5000 x 2 =

1

+

0.0000

a-4 = 1

-          The conversion from decimal fraction to any base-r system is similar to the example. Multiplication is by r instead of 2, and the coefficients found from the integers may range in value from 0 to r-1 instead of 0 and 1.

-          Conversion from Decimal fraction (0.513) 10 to Octal:

0.513 x 8 = 4.104

0.104 x 8 = 0.832

0.832 x 8 = 6.656

0.656 x 8 = 5.248

0.248 x 8 = 1.984

0.984 x 8 = 7.872

(0.513) 10 = (0.406517…) 8

-          The conversion of decimal numbers with both integers and fraction parts is done by converting the integer and fraction separately and then combining the two answers.

Octal and Hexadecimal Numbers

-          The conversion from and to binary, octal and hexadecimal plays an important part in digital computers. Since 23 = 8 and 24 = 16, each octal digit corresponds to three binary digits and each hexadecimal digit corresponds to four binary digits.

-          Conversion from binary to Octal:

(10 110 001 101 011. 111 100 000 110) 2 = (26153.7406) 8

-          Conversion from binary to Hexadecimal:

(10 1100 0110 1011. 1111 0000 0110) 2 = (2C6B.F06) 16

-          Conversion from Octal to binary:

(673.124) 8 = (110 111 011. 001 010 100) 2

-          Conversion from Hexadecimal to binary: (306.D) 16 = (0011 0000 0110. 1101) 2

-          Conversion from Hexadecimal to Decimal:

(37B) 16

3 x 162 + 7 x 161 + 11 x 160

= 3 x 256 + 7 x 16 + 11 x 1

= 768 + 112 +11

= (891) 10

Complements

-          Are used to simplify the subtraction operation and for logical manipulation.

Diminished Radix Complement

-          Given a number N in base r having n digits, the (r – 1)’s complement of N is defined as (r – 1) – N. For decimal numbers, r = 10 and r – 1 = 9, so the ninth complement of N is (10n – 1) – N. Now, 10n represents a number that consists of a single 1 followed by n 0’s. 10n – 1 is a number represented by n 9’s.

- If n = 4 è 104 = 10,000 and 104 – 1= 9999.

- The 9’s complement of 546700 is 999999 – 546700

=

453299

- The 9’s complement of 012398 is 999999 – 012398

=

987601

-          For binary numbers, r = 2 and r – 1 = 1, so the 1’s complement of N is (2n – 1) – N. 2n is represented by a binary number that consists of a 1 followed by n 0’s.

- If n = 4 è 24 = (10000) 2 and 24 – 1= (1111) 2.

-          The 1’s complement of a binary number is formed by changing 1’s to 0’s and 0’s to 1’s.

The 1’s complement of 1011000 is 0100111 The 1’s complement of 0101101 is 1010010

Radix Complement

-          The r’s complement of n-digit number N in base r is defined as rn – N for N ≠ 0 and 0 for N = 0. Comparing with the (r – 1)’s complement, the r’s complement is obtained by adding 1 to the (r – 1)’s complement since rn – N = [(rn – 1) –N] + 1.

- The 10’s complement of decimal

2389 = (104 –1) – 2389 + 1

= 7611.

- The 2’s complement of binary

101100 = (26 –1) – 101100 + 1

= 010100.

- The 10’s complement of decimal

012389 = (106 –1) – 012389 + 1

= 987602.

- The 10’s complement of decimal

246700 = (106 –1) – 246700 + 1

= 753300.

-          The 2’s complement can be formed by leaving the least significant 0’s and the first 1 unchanged, and the replacing 1’s with 0’s and 0’s with 1’s in the other four most- significant digits.

The 2’s complement of binary  1101100   is 0010100.

-          The 2’s complement of the following number is obtained by leaving the least significant 1 unchanged, and complementing all other digits.

The 2’s complement of binary  0110111   is 1001001.

Summary

-          The radix complement and diminished radix complement are defined as:

(N) r   = an n-digit number N in base r

[N] r   = the r’s complement of (N)r

[N] r-1 = the (r-1)’s complement of (N)r

[N] r   = rn - (N)r (Eq.1) [N] r-1 = [N]r - 1                (Eq.2)

From Eq.1 and Eq.2, we can also derive the following equations: [N] r       = [N]r-1 + 1     (Eq.3)

[N] r-1 = (rn - 1) - (N)r (Eq.4)

In the decimal system, r=10, we have 10’s complement and 9’s complement. In the octal system, r=8, we have 8’s complement and 7’s complement. In the binary system, r=2, we have 2’s complement and 1’s complement.

System

Radix Complement

Diminished Radix Complement

Decimal

10's complement

9's complement

Octal

8's complement

7's complement

Binary

2's complement

1's complement

To find the radix complement representation of a number, it is more convenient to first derive the diminished radix complement. The radix complement is then obtained by adding 1 to the diminished radix complement.

The 9's complement of a decimal number is obtained by subtracting each digit from 9. The 7's complement of an octal number is obtained by subtracting each digit from 7. The 1's complement of a binary integer is obtained by subtracting each digit from 1.

Examples:

-          Find the 10's complement and the 9's complement of (546700) 10

(453299)10  9's complement

(453300)10  10's complement       (add 1 to the 9’s complement)

-          Find the 8's complement and the 7's complement of (526071) 8

(251706)8  7's complement

(251707)8  8's complement           (add 1 to the 7’s complement)

-          Find the 2's complement and the 1's complement of (00011010) 2

(11100101)2  1's complement

(11100110)2  2's complement       (add 1 to the 1’s complement)

Subtraction with Complements

Example (1):

Using 10’s complement, subtract 72532 – 3250

M     – N

M

=

72532

10’s complement of N

= +

96750 (99999 – 03250) + 1

Sum

=

169282

Discard end carry 105

= -

100000

Answer

=

69282

Example (2):

Using 10’s complement, subtract 3250 – 72532

M     –      N

M

=

03250

10’s complement of N

=

+

27468 (99999 – 72532) + 1

Sum

=

30718

No end carry.

Answer - (10’s complement of 30718)  =      - 69282

Example (3):

Using 2’s complement, subtract 1010100 – 1000011

X             –      Y

X

=

1010100

2’s complement of Y

=

+

0111101

Sum

=

10010001

Discard end carry 27

=

-

10000000

Answer: X - Y

=

0010001

Example (4):

Using 2’s complement, subtract 1000011 – 1010100

Y             –      X

Y

=

1000011

2’s complement of X

=

+

0101100

Sum

=

1101111

No end carry.

Answer: Y – X - (2’s complement of 1101111) =       -0010001

Example (5): Using 1’s complement, subtract X – Y = 1010100 – 1000011

X     =        1010100

1’s complement of Y        = +    0111100 (+1 End-around carry)

Sum =      10010000

+ 1

Answer: X - Y                    =        0010001

Example (6): Using 1’s complement, subtract Y – X 1000011 – 1010100

Y     =        1000011

1’s complement of X        = +   0101011

Sum            =        1101110

No end carry.

Answer: Y – X - (1’s complement of 1101110) =       -0010001

Signed Binary Numbers

-          It is customary to represent the sign with a bit placed in the leftmost position of the number and to make it 0 for positive and 1 for negative.

-          Consider the number 9 represented in binary with 8 bits. +9 is represented with sign bit 0 in the leftmost position followed by the binary equivalent of 9 to give 00001001.

00001001

Signed magnitude     à    10001001

Signed-1’s complementà    11110110

Signed-2’s complementà    11110111

Arithmetic Addition

-          The addition of 2 numbers in the signed-magnitude system follows the rules of ordinary arithmetic.

-          If the signs are the same, we add the two magnitudes and give the sum the common sign.

-          If the signs are different, we subtract the smaller magnitudes from the larger and give the result the sign of the larger magnitude.

+6

00000110

-6

11111010

+13

00001101

+13

00001101

00010011

00000111

+6

00000110

-6

11111010

-13

11110011

-13

11110011

11111001

11101101

-          Negative numbers must be in 2’s complement and that the sum obtained after the addition if negative is in 2’s-complement form.

Arithmetic Subtraction

-          Take the 2’s complement of the subtrahend (including the sign bit) and add it to the minuend (including the sign bit). A carry out of the sign-bit position is discarded.

(± A) – (+B) = (± A) + (-B)

(± A) – (-B) = (± A) + (+B)

Binary Codes

-          Binary codes play an important role in digital computers. A bit is a binary digit. It is equal to 0 or 1.

-          Although the minimum number of bits required to code 2n quantities is n, there is no

maximum number of bits that may be used for a binary code.

Decimal Codes

-          BCD (binary-code decimal) is a straight assignment of the binary equivalent. Check Table 1-2 page 18.

Error Detection Code

-          Binary information can be transmitted from one location to another. External noise may change some of the bits from 0 to 1 and vice versa. To achieve error-detection we use a parity bit.

-          A parity bit is an extra bit included with a message to the total number of 1’s transmitted either odd or even. See Table 1-3 Page 20.

-          Two methods are implemented:

o   Even Parity: the P bit is chosen so that the total number of 1’s in the five bits is even.

o   Odd Parity: the P bit is chosen so that the total number of 1’s in the five bits is odd.

Gray Code

-          Gray code is used to represent the digital data when it is converted from analog data. See Table 1 – 4 Page 21.

-          The advantage of the Gray code over binary numbers is that only one bit in the code group changes when going from one number to the next.

-          In Gray to go from      7 to 8: 0100 è 1100 In Binary to from:                         7 to 8: 0111 è 1000

ASCII Character Code

-          The standard binary code for representation of alphanumeric characters is ASCII (American Standard Code for Information Interchange). It uses 7 bits to code 128 characters. See Table 1-5 Page 23.

Binary Storage & Registers

Registers

-          A register is a group of binary cells. Each cell stores one bit of information. The state of a register is an n—tuple of 1’s and 0’s, with each bit designating the state of one cell in the register.

-          The content of a register is a function of the interpretation given to the information stored in it. See page 25.

Binary Logic

-          Deals with variables that take on two discrete values and with operations that assume logical meaning.

-          The 2 values may be called by different names (e.g. true/false, yes/no, 0/1)

-          It is suited for the analysis and design of digital systems.

Definition of Binary Logic

-          Consists of binary variables and logical operations.

o   Variables: A, B, C, x, y, z, etc., with each variables having two values 1 and 0

o   Logical Operations:

§  AND: is represented by a dot or an absence of an operator.

·         EX: x . y = z or xy = z or is read as “x AND y is equal to z.”

·         It means z = 1 iff x = 1 and y = 1; otherwise, z = 0.

§  OR: is represented by + sign.

·         EX: x + y = z or is read as “x OR y is equal to z.”

·         It means z = 1 if x = 1 or if y = 1 or if x = 1 and y =1. if both x = 0

and y= 0, then z = 0.

§  NOT: is represented by ‘ or -.

·         EX: x’ = z (or 0 = z) is read, “not x is equal to z,” meaning that z is what x is not. In other words, if x = 1, then z = 0; but if x = 0, then z

= 1.

§  For each combination of values x and y, there is a value z specified by the definition of the logical operation. The definition is listed in compact form using truth tables.

Truth Table of Logical Operations

AND                                   OR                                      NOT

x

y

x . y

x

y

x + y

x

x’

0

0

0

0

0

0

0

1

0

1

0

0

1

1

1

0

1

0

0

1

0

1

1

1

1

1

1

1

Logic Gates

-          Electronic digital circuits are called logic circuits because, with the proper input, they establish logical manipulation paths. See Fig. 1 – 6 Page 31.

z= x.y                                                  z= x+y

x                                                  x

y                                                  y

x                        x’

Two-input AND gate                    Two-input OR gate           Not gate or inverter