Digital Logic and Binary Binary Numbers Binary Coded ...

[Pages:5]Digital Logic and Binary Numbers

These are lecture notes originally made to accompany chapter 3 of the book SPARC Architecture, Assembly

Language Programming, and C, by Richard P. Paul, 2nd edition, 2000. Some examples or text may be found in that book. These slides were later revised for the Java

Virtual Machine.

By Michael Weeks

1

? With 2 bits, 4 states are possible (22 = 4)

Bit1 Bit0 State 00 1 01 2 10 3 11 4

Bit2 Bit1 Bit0 000 001 010 011 100 101 110 111

State 1 2 3 4 5 6 7 8

? With 3 bits, 8 states are possible (23 = 8) ? With n bits, 2n states are possible

3

Binary

? A computer is a "bistable" device ? A bistable device:

? Easy to design and build ? Has 2 states: 0 and 1

? One Binary digit (bit) represents 2 possible states (0, 1)

2

Binary Coded Decimal (BCD)

? Why not use 4 bits to represent decimal?

? Let 0000 represent 0 ? Let 0001 represent 1 ? Let 0010 represent 2 ? Let 0011 represent 3, etc.

? This is called BCD ? Only uses 10 of the 16 possibilities

4

Binary Number System

? From left to right, the position of the digit indicates its magnitude (in decreasing order)

? E.g. in decimal, 123 is less than 321 ? In binary, 011 is less than 100

? A subscript indicates the number's base

? E.g. is 100 decimal or binary? We don't know! ? But 1410 = 11102 is clear

5

Bytes

? A group of 8 bits is a byte ? A byte can represent 28 = 256 possible states ? Registers are usually a multiple of bytes ? Java Virtual Machine uses local variables in

place of registers ? JVM local variables have 32 bits (4 bytes) ? 232 = 4,294,967,296

6

Memory Addresses

? Memory addresses are in binary

? often 32 bits ? if each memory address maps to 1 byte:

? 232 bytes = 4 GB

? K = kilo = thousand, ? but 1KB actually means 1024 bytes ? 1MB = 1024 x 1024 bytes ? 1GB = 1024 x 1024 x 1024 bytes

7

Hexadecimal

? With 4 bits, there are 16 possibilities

? Use 0, 1, 2, 3, ...9 for the first 10 symbols

? Use a, b, c, d, e, and f for the last 6

Bit3 Bit2 Bit1 Bit0 Symbol 0 0 00 0 0 0 01 1 0 0 10 2 0 0 11 3 0 1 00 4 0 1 01 5 0 1 10 6 0 1 11 7 1 0 00 8 1 0 01 9 1 0 10 a 1 0 11 b 1 1 00 c 1 1 01 d 1 1 10 e 1 1 11 f

9

Hexadecimal to Binary

? f0e516 = ? in binary ? Translate each into a group of 4 bits:

f16 => 11112, 016 => 00002, e16 => 11102, 516 => 01012

So this is 11110000111001012

11

Octal and Hexadecimal

? It is difficult for a human to work with long strings of 0's and 1's

? Octal and Hexadecimal are ways to group bits together

? Octal: base 8 ? Hexadecimal: base 16

8

Binary to Hexadecimal

? 01010110101100112 = ? in hex ? Group into 4 bits, from the right: ? 0101, 0110, 1011, 00112 ? Now translate each (see previous table):

01012 => 5, 01102 => 6, 10112 => b, 00112 => 3 So this is 56b316 ? What if there are not enough bits?

? Pad with 0's on the left 10

Decimal to Any Number Base

? Take the decimal number, and divide by the new number base

? Keep track of the quotient and remainder ? Repeat until quotient = 0 ? Read number from the bottom to the top

12

Decimal to Binary

? Binary is base 2

? Example: convert 35 (decimal) to binary

Quotient Remainder

35 / 2 = 17 1

17 / 2 = 8 1

8 / 2 = 4

0

4 / 2 = 2

0

2 / 2 = 1

0

1 / 2 = 0

1

? So 3510 = 1000112

13

Any Number Base to Decimal

? From right to left, multiply the digit of the number-to-convert by its baseposition

? Sum all results

14

Binary to Decimal

? Binary is base 2 ? Example: convert 10110 (binary) to decimal

101102 = 1x24 + 0x23 + 1x22 + 1x21 + 0x20 = 1x16 + 0x8 + 1x4 + 1x2 + 0x1 = 16 + 0 + 4 + 2 + 0 = 22

? So 101102 = 2210

15

ASCII

? American Standard Code for Information Interchange

? Use byte values to represent characters ? The assembler allows double-quotes

bipush 77 istore_3

; Push capital M on stack ; Pop stack to local var 3

17

Hexadecimal to Decimal

? Hexadecimal is base 16 ? Example: convert 16 (hex) to decimal

1616 = 1x161 + 6x160 = 1x16 + 6x1 = 16 + 6 = 22

? So 1616 = 2210 ? Not surprising, since 1616 = 0001, 01102

? If one of the hex digits had been > 9, say c, then we would have used 12 in its place.

16

ASCII chart

18

Bitwise Logical Operations

? There are several binary operations:

? NOT ? AND ? OR ? XOR ? NAND ? NOR

19

AND

? The AND operation uses 2 binary values

? a and b

a b a and b 000 010 100 111

21

XOR

? The XOR (exclusive-or) operation uses 2 binary values

? True when only one input is true.

? a xor b a b a xor b

000 011 101 110

23

NOT

? The NOT operation simply complements a binary value

? not (a) ? a'

a not(a) 01 10

20

OR

? The OR operation uses 2 binary values

? a or b

a b a or b 000 011 101 111

22

NAND

? The NAND (Not-AND) operation uses 2 binary values

? Take the AND function, and complement it.

? a nand b a b a nand b

001 011 101 110

24

NOR

? The NOR (Not-OR) operation uses 2 binary values ? Take the OR function, and complement it. ? NAND and NOR are easy to make on a chip.

a b a nor b 001 010 100 110

25

Logic Operations

A 0011 Logical B 0101 0 0000 false 1 0001 a and b 2 0010 a and (not b) 3 0011 a 4 0100 b and (not a) 5 0101 b 6 0110 a xor b 7 0111 a or b 8 1000 a nor b 9 1001 a xor (not b) A 1010 not b B 1011 a or (not b) C 1100 not a D 1101 b or (not a) E 1110 a nand b F 1111 true

JVM iand, land

ixor, lxor ior, lor

i for integer l for long

27

Logic Instruction Examples

bipush 0x21 bipush 0x3c

20

iand

bipush 0x21

bipush 0x3c

3d

ior

bipush 0x47 bipush 0xca

42

iand

bipush 0x47

bipush 0xca

cf

ior

bipush 0x55

69

bipush 0x3c

ixor

bipush 0x55

aa

bipush 0xff

ixor

The cf and aa results are only the last byte 29

Possible Logic Functions

? Suppose you have 2 binary digits: a, b ? Imagine that some function operates on them to

create c. ? What could this function be?

? There are only 16 possibilities ? And some of these are not useful!

a

some

c

b

function

26

Bitwise

? Each of these logic functions is a bitwise operation, meaning that the result is independent of the bits to the left or right

e.g. 1 0 1 or 0 1 1 1 1 1

? compare this with addition

28

NOT?

There is no NOT operation We can use xor for this e.g. 55 xor ff aa

30

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download