Abstraction & Digital Logic: From Transistors to Gates
D Flip Flop
CSE12 Winter 2021 2
D FF positive edge wave
CSE12 Winter 2021
3
D FF negative edge triggered
CSE12 Winter 2021
4
D FF negative edge triggered waveform?
Option 2
Option 1
CSE12 Winter 2021
Option 3
5
A peak inside the DFF
Negative D latch
Positive D latch
CSE12 Winter 2021
6
Positive D latch
Positive edge triggered DFF
Negative D latch
Negative edge triggered DFF
Data Representation
Using binary numbers to represent information
Data Representation
■ Goal: Store numbers, characters, sets, database records in the computer.
■ What we got: Circuit that stores 2 voltages, one for logic 0 (0 volts) and one for logic 1 (ex: 3.3 volts).
CSE12 Winter 2021
8
Storing Information
Value Representation Value Representation H 0 False 0
T 1 True 1
• Use more bits for more items
• Three bits can represent 8 things: 000,001,…,111 • N bits can represent 2N things
N bits
8
16
32
64
Can represent
256
65,536
4,294,967,296
1.8446…x1019
Which is approximately
256
65 thousand (64K where K=1024)
4 billion
20 billion billion
CSE12 Winter 2021
9
Storing Information
Byte is a unit of information. Remember 1 byte = 8 bits
Most computers today use:
Type
Character Integers Addresses
# of bits
8-16 32-64 32-64
CSE12 Winter 2021
10
Character Representation
■ ASCII (American Standard Code for Information Interchange)
■ Defines what character is represented by each sequence of 7 bits.
■ Examples:
0100 0001 is 0x41 (hex) or 65 (decimal). It
represents “A”.
0100 0010 is 0x42 (hex) or 66 (decimal). It represents “B”.
■ Different bit patterns are used for each different character that needs to be represented.
CSE12 Winter 2021
11
ASCII Properties
ASCII has some nice properties.
• If the bit patterns are compared, (pretending they represent integers), then
“A” < “B”
65 < 66
• This is good because it helps with sorting things into
alphabetical order. • But...:
• ‘a’ (61 hex) is different than ‘A’ (41 hex) • ‘8’ (38 hex) is different than the integer 8 • ‘0’ is 30 (hex) or 48 (decimal)
• ‘9’ is 39 (hex) or 57 (decimal)
CSE12 Winter 2021
12
7-bit ASCII table
NO CSE12 Winter 2021
NEED to memorize this
13
Integer Representation
Usual answers:
1. Represent0andconsecutivepositiveintegers • Unsigned integers
2. Representpositiveandnegativeintegers • Signed magnitude
• One’s complement
• Two’s complement
Unsigned and two’s complement the most common CSE12 Winter 2021
15
Unsigned Integers
• Integer represented is binary value of bits:
0000 -> 0, 0001 -> 1, 0010 -> 2, …
• Encodes only positive values and zero •Range: 0 to 2n –1, for n bits
CSE12 Winter 2021
16
Unsigned Integers
If we have 4 bit numbers:
To find range make n = 4. Thus 24–1 is 15 Thus the values possible are 0 to 15 [0:15] = 16 different numbers
7 would be 0111
17 not represent-able -3 not represent-able
For 32 bits:
Range is 0 to 232 – 1 = [0: 4,294,967,295] Which is 4,294,967,296 different numbers
CSE12 Winter 2021
17
Signed Magnitude Integers
• A human readable way of getting both positive and negative integers.
CSE12 Winter 2021
18
Signed Magnitude Integers
Representation:
■ Use 1 bit of integer to represent the sign of the integer
◆ Signbitismsb:0is“+”,1is”–”
■ Rest of the integer is a magnitude, with same
encoding as unsigned integers.
■ To get the additive inverse of a number, just flip (invert, complement) the sign bit.
■ Range: -(2n-1 – 1) to 2n-1 -1 CSE12 Winter 2021
19
Signed Magnitude – Example
If 4 bits then range is: -23 +1to23 –1
which is -7 to +7
Given only 4 bits to represent signed magnitude, what integer the following binary numbers represent:
•0101is 0101=+5 •-3is? 1011=1011
•+12 is ? •Not possible range is -7 …. +7
• [-7,…, -1, 0, +1,…,+7] = 7 + 1 + 7 = 15 < 16 =
• What problems does this cause? CSE12 Winter 2021
20
Signed Magnitude - Example
If 4 bits then range is: -23 +1to23 –1
which is -7 to +7
Questions:
•0101is0 101=+5
• -3 is ? is 1 011 = 1011
• +12 is ? Not possible range is -7 .... +7
• [-7,..., -1, 0, +1,...,+7] = 7 + 1 + 7 = 15 < 16 =
• What problems does this cause?
0 = 1 000 (negative zero)
0 = 0 000 (positive zero)
You are wasting two unique binary numbers (1000
and 0000) in representing the same integer value! CSE12 Winter 2021
21
One’s Complement
• Historically important (in other words, not used today!!!)
• Early computers built by Semour Cray (while at CDC)
were based on 1’s complement integers.
• Positive integers use the same representation as unsigned.
• 0000 is 0
• 0111 is 7, etc
• Negation is done by taking a bitwise complement of the positive representation.
• Complement = Invert = Not = Flip = {0 -> 1, 1 -> 0}
• A logical operation done on a single bit • Top bit is sign bit
CSE12 Winter 2021
22
One’s Complement Representation
To get 1’s complement of –1
• Take +1: 0001 •Complementeachbit: 1110
• Don’t add or take away any bits.
Another example:
• 1100 ->flip 0011 3 -> -3
• This must be a negative number. To find out which,
find the inverse!
• 0011 is +3
• 1100 in 1’s Complement must be?
Properties of 1’s complement:
• Any negative number will have a 1 in the MSB •Whatis0000? 0
• What is 1111? -0
CSE12 Winter 2021
23
Two’s Complement
• Variation on 1’s complement that does not have 2 representations for 0.
• This makes the hardware that does arithmetic simpler and faster than the other representations.
• The negative values are all “slid” by one, eliminating the –0 case.
• How to get 2’s complement representation:
• Positive: just as if unsigned binary • Negative:
• Take the positive value
• Take the 1’s complement of it • Add 1
CSE12 Winter 2021
24
Two’s Complement
Example, what is -5 in 2SC?
1. What is 5? 0101
2. Invert all the bits: 1010 (basically find the 1SC) 3.Addone: 1010+1=1011whichis-5in2SC
To get the additive inverse of a 2’s complement integer
1. Take the 1’s complement 2. Add 1
CSE12 Winter 2021
25
What value is my negative number?
■ Assume 4-bit number…
◆ 1100 is negative, but what number is it? ◆ Take 2SC again using same method!
★ Invert all bits ★ Add 1
1100 > 0011 + 0001 0100
CSE12 Winter 2021
26
Visualizing Signed Numbers
■ Signed Magnitude
■ One’s Complement
■ And… Two’s Complement
000
001
010
011
100
101
110
111
0
1
2
3
4
5
6
7
signed magnitude
0
1
2
3
-0
-1
-2
-3
1’s Compleme nt
0
1
2
3
-3
-2
-1
-0
2’s Compleme nt
0
1
2
3
-4
-3
-2
-1
CSE12 Winter 2021
unsigned
27
Two’s Complement
Number of integers representable is -2n-1 to 2n-1-1
So if 4 bits:
[-8,…,-1,0,+1,…,+7] = 8 + 1 + 7 = 16 = 24 numbers
CSE12 Winter 2021
28
Interesting observation about 2SC representation
Assume you use n bits to represent your 2SC number
The integer 0 is always represented as 0….0 (n times)
The integer -1 is always represented as 11…..111 (n times)
CSE12 Winter 2021
29
Sign Extension
How to change a number with a smaller number of bits into the same number (same representation) with a larger number of bits?
This must be done frequently by arithmetic units
0010 = 2 (4 bits)
0000 0010 = 2 (8 bits)
CSE12 Winter 2021
35
Sign Extension – unsigned
Unsigned representation:
Copy the original integer into the LSBs, and put 0’s elsewhere.
Thus for 5 bits to 8 bits: xxxxx -> 000xxxxx
CSE12 Winter 2021
36
Sign Extension – signed magnitude
Signed magnitude:
Copy the original integer’s magnitude into the LSBs & put the original sign into the MSB, put 0’s elsewhere.
Thus for 6 bits to 8 bits sxxxxx -> s00xxxxx
CSE12 Winter 2021
37
Sign Extension – 1SC and 2SC
1’s and 2’s complement:
1. Copytheoriginaln-1bitsintotheLSBs
2. TaketheMSBoftheoriginalandcopyitelsewhere
Thus for 6 bits to 8 bits: sxxxxx -> sssxxxxx
CSE12 Winter 2021
38
Sign Extension
What is -12 in 8-bit 2’s complement form 12
0000 1100 -> Binary
1111 0011 -> flip
1111 0100 -> +1
CSE12 Winter 2021
39