Microsoft PowerPoint – SN-2017-Sec02.pptx
2. Binary Codes
Transmitting binary: wires
• To manipulate binary representations in real devices need to connect components.
– In electronic devices this is done by wires.
– Each wire can represent one bit at a time (as a high or low voltage between wire & ground).
• A bit (H or L) is forced onto one end of wire by a line driver (output) in the sending
component…
• …and detected by a line receiver (input) in the receiving component
• Multiple bits can be sent in sequence over the same wire, but one at a time:
– A bit must be kept steady on the wire for a minimum bit time to be properly detected be receiver.
– bit time varies according to the technology.
• To carry n-bits, can use one wire (serial transmission) taking n bit times, or n wires running
in parallel (parallel transmission) taking 1 bit time. This arrangement is called an n-bit bus.
Computer Systems Binary Codes 2
Place H or L on wire
Detect H or L
is often denoted
4
Basic Components
• A 1-bit memory (build into n-bit registers to store binary code words)
• Devices to perform useful operations on bits and on code words. Examples:
– Inverter (or NOT gate)
• One wire in, one wire out, flips input bit (H L, L H)
– n-bit adder (see later)
• Takes in two n-bit code words, treats them as numbers and generates code word of the sum.
Computer Systems Binary Codes 3
1 0 0 1 1 0 1 0 8-bit register: needs input and output wires (not shown)
Computer Systems Binary Codes 4
Unsigned Number Representation
• Unsigned binary code is positional like the decimal system used in ordinary
arithmetic.
– Each digit carries a weight depending on its position in the code word;
– In decimal allowed digits are 0, 1,.., 9; in binary only 1s and 0s allowed.
• Can generate positional codes with any number as base. Position of a digit is
weighted using powers of the base.
• Lowest weighted digit is least significant; highest is most significant.
• Decimal positional code. E.g. 205310
= 2103 + 0102 + 5101 + 3100 = 200+0+50+3
• Binary positional code E.g. 10012
= 123 + 022 + 021 + 120 = 8 + 0 + 0 + 1 = 910
• Subscript removes ambiguity with different number bases. 100110 ≠ 10012 !
Computer Systems Binary Codes 5
The Powers of 2
It’s useful to know the value of each bit position for binary
numbers!
value 27 26 25 24 23 22 21 20
= 128 64 32 16 8 4 2 1
Don’t memorize this table! Construct it when you need it.
Computer Systems Binary Codes 6
Decimal to Binary Conversion
Problem: find the k-bit binary representation of an integer x
– Write k columns containing the powers of 2
– Starting from the left, put a 1 if x is at least as large as the column
value (and subtract that from x)
– Stop at the rightmost column (The remaining value must be 0)
• Example: Convert 20310 to 8-bit binary.
– First note that largest power of 2 in 8-bit positional number is 128
– Check the result by converting 110010112 back to decimal!
128 64 32 16 8 4 2 1
1 1 0 0 1 0 1 1
Computer Systems Binary Codes 7
Unsigned binary addition
• Adding 2 binary values works just like mechanical decimal arithmetic.
– Start adding from units column (conventionally the rightmost). Progress to the “2s”
column then to the “4s” etc.
– Every column generates a sum bit, S and a carry bit, C. The carry bit must be added
into the next column
C 1 1 1 0
x 1 0 1 0
y 1 1 1 1
S 1 1 0 0 1
• Example: Add the two 4-bit numbers
• x = 1010 and y = 1111
• What decimal numbers are these?
• Solution: Examine the table (right)
• Result is 110012 = ?10
• Note that the sum is too big to be a 4-bit
number.
• This is always true if the carry from the
most significant column is 1.
Overflow
• If we add two n-bit unsigned numbers and the sum is too big to be an n-bit number, the
sum cannot be represented in the n-bit code.
• This is called an (unsigned) overflow.
• A necessary and sufficient condition for unsigned overflow is that the carry from the
most significant bit (MSB) position is 1.
• An n-bit unsigned adder is a device which takes in two n-bit unsigned binary code
words and outputs an n-bit number representing the sum.
• If there is an overflow, the number representing the sum is wrong.
• A practical adder should signal when there is an overflow. This can be done using the
carry from the MSB position. This is often referred to as the adder’s carry out (C).
Computer Systems Binary Codes 8
n
n
n
C
1
Computer Systems Binary Codes 9
Hexadecimal
• Binary codewords can be very long and difficult for humans to
work with.
• A common way to shorten binary strings is to convert them to a
base 16 number representation (called hexadecimal).
• Hex has 16 digits: 0, 1, …, 9, a, b, c, d, e, f
• Because 16 = 24, it is easy to convert between binary and hex.
– Every group of 4 bits can be directly represented as a single hex digit.
• Don’t worry about hex arithmetic – we use hex just to make the
notation for bits easier to read
Computer Systems Binary Codes 10
Hexadecimal Digits
Digit 0 1 2 3 4 5 6 7
Binary 0000 0001 0010 0011 0100 0101 0110 0111
Digit 8 9 a b c d e f
Bits 1000 1001 1010 1011 1100 1101 1110 1111
Computer Systems Binary Codes 11
Just replace each hex digit with its 4-bit binary equivalent. Don’t use
commas; put a space between the 4-bit groups
3 a 6 e
0011 1010 0110 1110
Binary to hex conversions are equally easy. Remember to pad the binary
number out to the left with 0s until the number of bits is a multiple of 4.
Hex to Binary
Computer Systems Binary Codes 12
Representing signed numbers
• Here numbers can be negative or positive
• Recall: a k-bit word has 2k distinct values.
• Instead of choosing all our code words as being positive
(as with unsigned binary), we choose half of them to
represent negative numbers
• This can be done in more than one way. E.g. in sign &
magnitude the most significant bit is the sign (1 means a
negative number) and the other bits the magnitude:
– +1 in 8-bit sign and mag code is 0000 0001
– -1 in 8-bit sign and mag code is 1000 0001
Two’s complement
• The commonest code for signed numbers is two’s complement.
• Take an 8-bit two’s complement code as an example.
– The code word 0000 0000 represents 0.
– Code words with MSB=0 represent +ve numbers. Largest positive value is 0111 11112 = +127
– To find the code word for –x simply subtract x from 28 =256 and convert the answer to binary
in the usual way.
• Example: Find the two’s complement code word for -1.
– Find the code word for 256 – 1 = 255. This is 1111 11112.
• NOTE that the code word 1111 11112 represents 255 in an unsigned 8-bit code but
-1 in an 8-bit two’s complement code
– It is vital to remember which code you are working in.
Computer Systems Binary Codes 13
Computer Systems Binary Codes 14
Properties of 2’s complement
• In the 8-bit two’s complement code the numbers represented are as follows:
• An 8-bit two’s comp code cannot represent numbers greater than +127
• Note that the MSB indicates the sign
• The inverse of an 8-bit two’s complement number can be found by flipping all the bits and
adding 0000 0001 to the result. This process is called negation.
• If the two’s complement codes for a number and its inverse are input to an 8-bit unsigned
adder, and the carry out is ignored, the answer is 0 (try it!)
Number Code Number Code
0 0000 0000 -1 1111 1111
1 0000 0001 -2 1111 1110
2 0000 0010 -3 1111 1101
… … …. ….
127 0111 1111 -128 1000 0000
Computer Systems Binary Codes 15
Characters
• We write characters as geometric shapes (“character graphics”), but inside a
computer a character is represented as a word (“character code”)
• A character code is a table giving the bit value that represents each character.
• ASCII (American Standard Code for Information Interchange) is an older
standard code (1960), still in common use: uses 7-bit or 8-bit code words.
• Unicode (two-byte code, 16 bits) is the current standard and includes many
additional characters. Can be extended to 32-bits.
• When you declare a character string in older languages (C, C++, …), it is
represented as
– a sequence of bytes
– where each byte contains the ASCII code of one character
• A String in Java is a sequence of Unicode characters
Questions
1. Bit times are just as important on buses as on single wires. Why?
2. A register will need some inputs and outputs other than for the data
stored or read. Why?
3. Convert 224 to binary.
4. Convert 111101012 to hexadecimal.
5. Convert FE16 to decimal.
6. The 8-bit 2’s complement code can represent all numbers between –
128 and +127. An 8-bit unsigned adder will add numbers in this range
correctly unless the code overflows. Find two examples to show that
2’s complement code overflows do not occur when unsigned code
overflows do (one example) and vice versa (another example)
7. Challenge. Can you find a condition for two’s complement overflow
in an 8-bit code (Hint it involves the carries into and out of the MSB)
Computer Systems Binary Codes 16