Design of Digital Circuits Reading: Binary Numbers

Design of Digital Circuits Reading: Binary Numbers

Required Reading for Week 1 23-24 February 2017 Spring 2017

Carnegie Mellon

Binary Numbers Design of Digital Circuits 2016 Srdjan Capkun Frank K. Gürkaynak http://www.syssec.ethz.ch/education/Digitaltechnik_16

Adapted from Digital Design and Computer Architecture, David Money Harris & Sarah L. Harris ©2007 Elsevier

2

Carnegie Mellon

In This Lecture 

How to express numbers using only 1s and 0s

Using hexadecimal numbers to express binary numbers

Different systems to express negative numbers

Adding and subtracting with binary numbers

3

Carnegie Mellon

Number Systems 1's column 10's column 100's column 1000's column

Binary Numbers 

Decimal Numbers 

537410 =

1's column 2's column 4's column 8's column

11012 =

4

Carnegie Mellon

Number Systems 

Decimal Numbers 1's column 10's column 100's column 1000's column

537410 = 5 × 103 + 3 × 102 + 7 × 101 + 4 × 100 five thousands

three hundreds

seven tens

four ones

Binary Numbers 1's column 2's column 4's column 8's column

11012 = 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 = 1310 one eight

one four

no two

one one

5

Carnegie Mellon

Powers of two 20

=

28

=

21

=

29

=

22

=

210

=

23

=

211

=

24

=

212

=

25

=

213

=

26

=

214

=

27

=

215

=

6

Carnegie Mellon

Powers of two 20

=

1

28

=

256

21

=

2

29

=

512

22

=

4

210

=

1024

23

=

8

211

=

2048

24

=

16

212

=

4096

25

=

32

213

=

8192

26

=

64

214

=

16384

27

=

128

215

=

32768

Handy to memorize up to 215 7

Carnegie Mellon

Binary to Decimal Conversion 

Convert 100112 to decimal

8

Carnegie Mellon

Binary to Decimal Conversion 

Convert 100112 to decimal

24

× 1 + 23 × 0 + 22 × 0 + 21 × 1 + 20 × 1 =

9

Carnegie Mellon

Binary to Decimal Conversion 

Convert 100112 to decimal

24

× 1 + 23 × 0 + 22 × 0 + 21 × 1 + 20 × 1 =

16 × 1 + 8 × 0 + 4 × 0 + 2 × 1 + 1 × 1 = 16

+ 0

+ 0

+ 2

+ 1

= 1910

10

Carnegie Mellon

Decimal to Binary Conversion 

Convert 4710 to binary

11

Carnegie Mellon

Decimal to Binary Conversion 

Convert 4710 to binary  Start with 26 = 64  Now 25 = 32

is 64 ≤ 47 ?

no

do nothing

12

Carnegie Mellon

Decimal to Binary Conversion 

Convert 4710 to binary       

Start with 26 = 64 Now 25 = 32 Now 24= 16 Now 23= 8 Now 22= 4 Now 21= 2 Now 20= 1

is 64 ≤ 47 ? is 32 ≤ 47 ? is 16 ≤ 15 ? is 8 ≤ 15 ? is 4 ≤ 7 ? is 2 ≤ 3 ? is 1 ≤ 1 ?

no yes no yes yes yes yes

do nothing subtract 47 – 32 =15 do nothing subtract 15 – 8 = 7 subtract 7-4 = 3 subtract 3-2 =1 we are done

13

Carnegie Mellon

Decimal to binary conversion 

Convert 4710 to binary       

Start with 26 = 64 Now 25 = 32 Now 24= 16 Now 23= 8 Now 22= 4 Now 21= 2 Now 20= 1

is 64 ≤ 47 ? is 32 ≤ 47 ? is 16 ≤ 15 ? is 8 ≤ 15 ? is 4 ≤ 7 ? is 2 ≤ 3 ? is 1 ≤ 1 ?

no yes no yes yes yes yes

0 1 0 1 1 1 1

do nothing subtract 47 – 32 =15 do nothing subtract 15 – 8 = 7 subtract 7-4 = 3 subtract 3-2 =1 we are done

Result is 01011112

14

Carnegie Mellon

Binary Values and Range 

N-digit decimal number  How many values?  Range?  Example: 3-digit decimal number  

10N [0, 10N - 1]

103 = 1000 possible values Range: [0, 999]

N-bit binary number  How many values?  Range:  Example: 3-digit binary number 

2N [0, 2N - 1]

23 = 8 possible values Range: [0, 7] = [0002 to 1112] 15

Carnegie Mellon

Binary

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

16

Carnegie Mellon

Binary

0

0

0000

1

1

0001

2

2

0010

3

3

0011

4

4

0100

5

5

0101

6

6

0110

7

7

0111

8

8

1000

9

9

1001

10

A

1010

11

B

1011

12

C

1100

13

D

1101

14

E

1110

15

F

1111

17

Carnegie Mellon

Binary numbers can be pretty long.

A neat trick is to use base 16

How many binary digits represent a hexadecimal digit? 4 (since 24 = 16)

Example 32 bit number: 0101 1101 0111 0001 1001 1111 1010 0110

18

Carnegie Mellon

Binary numbers can be pretty long.

A neat trick is to use base 16

How many binary digits represent a hexadecimal digit? 4 (since 24 = 16)

Example 32 bit number: 0101 1101 0111 0001 1001 1111 1010 0110 5 D 7 1 9 F A 6

19

Carnegie Mellon

Binary numbers can be pretty long.

A neat trick is to use base 16

How many binary digits represent a hexadecimal digit? 4 (since 24 = 16)

Example 32 bit number: 0101 1101 0111 0001 1001 1111 1010 0110 5 D 7 1 9 F A 6

The other way is just as simple C

E

2

8

3

5

4

B 20

Carnegie Mellon

Binary numbers can be pretty long.

A neat trick is to use base 16

How many binary digits represent a hexadecimal digit? 4 (since 24 = 16)

Example 32 bit number: 0101 1101 0111 0001 1001 1111 1010 0110 5 D 7 1 9 F A 6

The other way is just as simple C E 2 8 3 5 4 B 1100 1110 0010 1000 0011 0101 0100 1011

21

Carnegie Mellon

Convert 4AF16 (or 0x4AF) to decimal

22

Carnegie Mellon

Convert 4AF16 (or 0x4AF) to decimal

162

× 4 + 161

×A

256

× 4 + 16

× 10 + 1

1024

+ 160

+ 160 × F

+ 15

=

× 15 = = 119910

23

Carnegie Mellon

Bits, Bytes, Nibbles… 10010110 most significant bit

least significant bit

byte

10010110 nibble

least significant byte

24

Carnegie Mellon

Powers of Two 

210 = 1 kilo

1000

220 = 1 mega

1 million (1,048,576)

230 = 1 giga

1 billion (1,073,741,824)

(1024)

25

Carnegie Mellon

Powers of Two (SI Compatible) 

210 = 1 kibi

1000

220 = 1 mebi

1 million (1,048,576)

230 = 1 gibi

1 billion (1,073,741,824)

(1024)

26

Carnegie Mellon

Estimating Powers of Two 

What is the value of 224?

How many values can a 32-bit variable represent?

27

Carnegie Mellon

Estimating Powers of Two 

What is the value of 224?

24 × 220 ≈ 16 million

How many values can a 32-bit variable represent? 22 × 230 ≈ 4 billion 28

Carnegie Mellon

Decimal

Binary

11 3734 + 5168 8902

carries

11 1011 + 0011 1110

carries

29

Carnegie Mellon

1001 + 0101

1011 + 0110

30

Carnegie Mellon

1 1001 + 0101 1110

111 1011 + 0110 10001 OVERFLOW !

31

Carnegie Mellon

Overflow 

Digital systems operate on a fixed number of bits

Addition overflows when the result is too big to fit in the available number of bits

See previous example of 11 + 6

32

Carnegie Mellon

Overflow (Is It a Problem?) 

Possible faults

Security issues

33

Carnegie Mellon

Binary Values and Range 

N-digit decimal number  How many values?  Range?  Example: 3-digit decimal number  

10N [0, 10N - 1]

103 = 1000 possible values Range: [0, 999]

N-bit binary number  How many values?  Range:  Example: 3-digit binary number 

2N [0, 2N - 1]

23 = 8 possible values Range: [0, 7] = [0002 to 1112] 34

Carnegie Mellon

Signed Binary Numbers 

Sign/Magnitude Numbers

One’s Complement Numbers

Two’s Complement Numbers

35

Carnegie Mellon

Sign/Magnitude Numbers 

1 sign bit, N-1 magnitude bits

Sign bit is the most significant (left-most) bit  Positive number: sign bit = 0  Negative number: sign bit = 1

A : aN 1 , aN 2 ,

a2 , a1 , a0 

n 2

A  ( 1)an 1  ai 2i i 0

Example, 4-bit sign/mag representations of ± 6: +6 = -6=

Range of an N-bit sign/magnitude number: 36

Carnegie Mellon

Sign/Magnitude Numbers 

1 sign bit, N-1 magnitude bits

Sign bit is the most significant (left-most) bit  Positive number: sign bit = 0  Negative number: sign bit = 1

A : aN 1 , aN 2 ,

a2 , a1 , a0 

n 2

A  ( 1)an 1  ai 2i i 0

Example, 4-bit sign/mag representations of ± 6: +6 = 0110 - 6 = 1110

Range of an N-bit sign/magnitude number: [-(2N-1-1), 2N-1-1] 37

Carnegie Mellon

Problems of Sign/Magnitude Numbers 

Addition doesn’t work, for example -6 + 6: 1110 + 0110 10100 wrong!

Two representations of 0 (± 0): 1000 0000

Introduces complexity in the processor design (Was still used by some early IBM computers) 38

Carnegie Mellon

One’s Complement 

A negative number is formed by reversing the bits of the positive number (MSB still indicates the sign of the integer): One’s Complement

27

26

25

24

23

22

21

20

0

0

0

0

0

0

0

0

=

+0

0

0

0

0

0

0

0

0

1

=

1

1

0

0

0

0

0

0

1

0

=

2

2

0

1

1

1

1

1

1

1

=

127

127

1

0

0

0

0

0

0

0

=

-127

128

1

0

0

0

0

0

0

1

=

-126

129

1

1

1

1

1

1

0

1

=

-2

253

1

1

1

1

1

1

1

0

=

-1

254

1

1

1

1

1

1

1

1

=

-0

255

Unsigned

39

Carnegie Mellon

One’s Complement 

A negative number is formed by reversing the bits of the positive number (MSB still indicates the sign of the integer): One’s Complement

27

26

25

24

23

22

21

20

0

0

0

0

0

0

0

0

=

+0

0

0

0

0

0

0

0

0

1

=

1

1

0

0

0

0

0

0

1

0

=

2

2

0

1

1

1

1

1

1

1

=

127

127

1

0

0

0

0

0

0

0

=

-127

128

1

0

0

0

0

0

0

1

=

-126

129

1

1

1

1

1

1

0

1

=

-2

253

1

1

1

1

1

1

1

0

=

-1

254

1

1

1

1

1

1

1

1

=

-0

255

Unsigned

40

Carnegie Mellon

One’s Complement 

The range of n-bit one’s complement numbers is: [-2n-1-1, 2n-1-1] 8 bits: [-127,127]

Addition: Addition of signed numbers in one's complement is performed using binary addition with end-around carry. If there is a carry out of the most significant bit of the sum, this bit must be added to the least significant bit of the sum:

Example: 17 + (-8) in 8-bit one’s complement +

0001 0001

(17)

1111 0111

(-8)

1 0000 1000 +

1 0000 1001 =

(9) 41

Carnegie Mellon

Two’s Complement Numbers 

Don’t have same problems as sign/magnitude numbers:  Addition works  Single representation for 0

Has advantages over one’s complement:  Has a single zero representation  Eliminates the end-around carry operation required in one's complement addition

42

Carnegie Mellon

Two’s Complement Numbers 

A negative number is formed by reversing the bits of the positive number (MSB still indicates the sign of the integer) and adding 1: Two’s Complement

27

26

25

24

23

22

21

20

0

0

0

0

0

0

0

0

=

0

0

0

0

0

0

0

0

0

1

=

1

1

0

0

0

0

0

0

1

0

=

2

2

0

1

1

1

1

1

1

1

=

127

127

1

0

0

0

0

0

0

0

=

-255

128

1

0

0

0

0

0

0

1

=

-254

129

1

1

1

1

1

1

0

1

=

-3

253

1

1

1

1

1

1

1

0

=

-2

254

1

1

1

1

1

1

1

1

=

-1

255

Unsigned

43

Carnegie Mellon

Two’s Complement Numbers 

A negative number is formed by reversing the bits of the positive number (MSB still indicates the sign of the integer) and adding 1: Two’s Complement

27

26

25

24

23

22

21

20

0

0

0

0

0

0

0

0

=

0

0

0

0

0

0

0

0

0

1

=

1

1

0

0

0

0

0

0

1

0

=

2

2

0

1

1

1

1

1

1

1

=

127

127

1

0

0

0

0

0

0

0

=

-128

128

1

0

0

0

0

0

0

1

=

-127

129

1

1

1

1

1

1

0

1

=

-3

253

1

1

1

1

1

1

1

0

=

-2

254

1

1

1

1

1

1

1

1

=

-1

255

Unsigned

44

Carnegie Mellon

Two’s Complement Numbers 

Same as unsigned binary, but the most significant bit (msb) has value of -2N-1 i=n-2

I=

∑ bi2i – bn-12n-1

i=0

 Most positive 4-bit number:  Most negative 4-bit number: 

The most significant bit still indicates the sign (1 = negative, 0 = positive)

Range of an N-bit two’s comp number:

45

Carnegie Mellon

Two’s Complement Numbers 

Same as unsigned binary, but the most significant bit (msb) has value of -2N-1 i=n-2

I=

∑ bi2i – bn-12n-1

i=0

 Most positive 4-bit number:  Most negative 4-bit number:

0111 1000

The most significant bit still indicates the sign (1 = negative, 0 = positive)

Range of an N-bit two’s comp number: [-2N-1, 2N-1-1] 8 bits: [-128,127] 46

Carnegie Mellon

“Taking the Two’s Complement” 

How to flip the sign of a two’s complement number:  Invert the bits  Add one

Example: Flip the sign of 310

=

00112

47

Carnegie Mellon

“Taking the Two’s Complement” 

How to flip the sign of a two’s complement number:  Invert the bits  Add one

Example: Flip the sign of 310  Invert the bits

=

00112 11002

48

Carnegie Mellon

“Taking the Two’s Complement” 

How to flip the sign of a two’s complement number:  Invert the bits  Add one

Example: Flip the sign of 310  Invert the bits  Add one

=

00112 11002 11012

49

Carnegie Mellon

“Taking the Two’s Complement” 

How to flip the sign of a two’s complement number:  Invert the bits  Add one

Example: Flip the sign of 310

=

00112 11002 11012

=

110002

 Invert the bits  Add one 

Example: Flip the sign of -810

50

Carnegie Mellon

“Taking the Two’s Complement” 

How to flip the sign of a two’s complement number:  Invert the bits  Add one

Example: Flip the sign of 310

=

00112 11002 11012

=

110002 001112 010002

 Invert the bits  Add one 

Example: Flip the sign of -810  Invert the bits  Add one

51

Carnegie Mellon

Add 6 + (-6) using two’s complement numbers 0110 + 1010

Add -2 + 3 using two’s complement numbers 1110 + 0011

52

Carnegie Mellon

Add 6 + (-6) using two’s complement numbers 111 0110 + 1010 10000

Add -2 + 3 using two’s complement numbers

111 1110 + 0011 10001 Correct results if overflow bit is ignored 53

Carnegie Mellon

Increasing Bit Width 

A value can be extended from N bits to M bits (where M > N) by using:  Sign-extension  Zero-extension

54

Carnegie Mellon

Sign-Extension 

Sign bit is copied into most significant bits

Number value remains the same

Give correct result for two’s complement numbers

Example 1:  4-bit representation of 3 =  8-bit sign-extended value:

0011 00000011

Example 2:  4-bit representation of -5 =  8-bit sign-extended value:

1011 11111011 55

Carnegie Mellon

Zero-Extension 

Zeros are copied into most significant bits

Value will change for negative numbers

Example 1:  4-bit value = 00112 = 310  8-bit zero-extended value: 000000112 = 310

Example 2:  4-bit value = 10112 = -510  8-bit zero-extended value: 000010112 = 1110

56

Carnegie Mellon

Number System Comparison Number System

Range

Unsigned

[0, 2N-1]

Sign/Magnitude

[-(2N-1-1), 2N-1-1]

Two’s Complement

[-2N-1, 2N-1-1]

For example, 4-bit representation: -8

-7

-6

-5

-4

-3

-2

-1

Unsigned

0

1

2

3

4

5

6

7

9

10

11

12

13

14

15

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111

1111 1110 1101 1100 1011 1010 1001

8

0000 1000

0001 0010 0011 0100 0101 0110 0111

Two's Complement Sign/Magnitude

57

Carnegie Mellon

Lessons Learned 

How to express decimal numbers using only 1s and 0s

How to simplify writing binary numbers in hexadecimal

Methods to express negative numbers  Sign Magnitude  One’s complement  Two’s complement (the one commonly used)

58

Design of Digital Circuits Reading: Binary Numbers

Design of Digital Circuits Reading: Binary Numbers Required Reading for Week 1 23-24 February 2017 Spring 2017 Carnegie Mellon Binary Numbers Desi...

Recommend Documents

Digital Logic Design Unit-I Digital system and binary numbers
ECS-301 : Digital Logic Design. Unit-I. Digital system and binary numbers: : Signed binary numbers, binary codes, cyclic

Digital Systems and Binary Numbers
Digital Systems. â« Binary Numbers. â« Number-Base Conversions. â« Octal and Hexadecimal Numbers. â« Complements. â

Digital Systems and Binary Numbers
[PDF]Digital Systems and Binary Numbershttp://eclass.duth.gr/.../Pages%20from%20DIGITAL%20SYSTEM%20DESIGN%20...CachedTh

CS 226: Digital Logic Design - Lecture 2: Binary Numbers
The following number-systems are important for this course. 1. Decimal System with decimal-digits = {0, 1, 2, 3, 4, 5, 6

Symbols : Cool Ece Digital System Design Negative Binary Numbers
Symbols : Cool Ece Digital System Design Negative Binary Numbers Converter Signedbinarynumbersforann Number 2s Complemen

Digital System And Binary Numbers - Unacademy
This course would contain basics of the digital system starting from number system, conversion from one form to another

Digital Data and Binary Numbers - web.pdx.edu
1. Digital Data and Binary Numbers. 1.Digital Data. 2. Binary numbers. 3. How digital data is displayed on the monitor.

Two State Devices | Binary Numbers | Digital Electronics
Digital electronic systems are based on devices that can be set to two different states (like a switch (i.e. it can be o

CSCI 2150 -- Digital Signals and Binary Numbers
Digital Signals and Binary Numbers. Digital waveforms. Last period, we covered the differences between a real-world anal

Binary Numbers
Binary numbers. A rudimentary knowledge of how binary numbers work is required in order to understand the mechanism of d