CS3350B Computer Organization Chapter 2: Synchronous Circuits Prelude
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Monday February 1, 2021
Alex Brandt
Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 1 / 12
Outline
1 Everything on a Computer is a Number
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 2 / 12
Radix Representations
Radix is the base number in some numbering system.
In a radix 𝑟 representation digits (𝑑𝑖) are from the set {0, 1, . . . , 𝑟 − 1}
𝑥=𝑑𝑛1 ×𝑟𝑛1 +𝑑𝑛2 ×𝑟𝑛2 +⋅⋅⋅+𝑑1 ×𝑟1 +𝑑0 ×𝑟0
𝑟 = 10 ⇒ decimal, {0,1,2,3,4,5,6,7,8,9}
𝑟=2 ⇒ binary,{0,1}
𝑟 = 8 ⇒ octal, {0,1,2,3,4,5,6,7}
𝑟 = 16 ⇒ hexadecimal, {0,1,2,3,4,5,6,7,8,9,𝑎,𝑏,𝑐,𝑑,𝑒,𝑓}
Refresh: Decimal to Binary
(13)10 =(1×101)+(3×100)
(1101)2 =(1×23)+(1×22)+(0×21)+(1×20)=8+4+0+1=(13)10
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 3 / 12
Unsigned Binary Integers
Unsigned Integers ⇒ the normal representation An 𝑛-bit number:
𝑥 = 𝑥𝑛12𝑛1 + 𝑥𝑛22𝑛2 + ⋯ + 𝑥121 + 𝑥020
Has a factor up to 2𝑛1. Has a range: 0 to (2𝑛 −1) Example
0000 0000 0000 0000 0000 0000 0000 10112 = 0+⋯+1×23 +0×22 +1×21 +1×20
= 0+⋯+8+0+2+1=1110
Using 32 bits: 0 to +4,294,967,295
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 4 / 12
Signed Binary Integers (1/2)
How to encode a negative sign?
One’s Compliment: Invert unsigned representation to get negative. Get value by inverting all bits then multiply by −1.
Leading bit decides if negative or not.
All positive numbers have the same representation as unsigned.
In one’s compliment:
(0101)2 = (0101)2 = 5
(1101)2 = −1 × (0010)2 = −2 (0000)2 = (0000)2 = 0
(1111)2 = −1 × (0000)2 = −0 ????
One’s compliment is rarely used: Signed zero.
Weird borrowing required in arithmetic.
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 5 / 12
Signed Binary Integers (2/2)
How to encode a negative sign?
Two’s Compliment: Invert all the bits with respect to 2𝑛
Same as treating leading bit as negative in expansion.
Leading bit decides if negative or not.
All positive numbers have the same representation as unsigned.
In two’s compliment:
(0101)2 = (0101)2 = 5
(1101)2 = −1×23 +(0101)2 = −8+5 = -3 (0000)2 = (0000)2 = 0
(1111)2 = −1 × 23 + (0111)2 = −1
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 6 / 12
Two’s Compliment
Advantages:
Arithmetic is the same whether positive or negative:
(0101)2 = 5 + (1101)2 = −3
(0010)2 = 2 (Throw away carry bit)
No signed 0.
One extra value represented with same number of bits.
For an 𝑛-bit number:
Range of values is −2𝑛1 to 2𝑛1 − 1
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 7 / 12
Same Bits Different Numbers
It is important to realize that the same bit pattern can represent different numbers.
(1001 1010)2 ⇒ (154)10 interpretted as unsigned
⇒ (−102)10 interpretted as two’s compliment
Can be disastrous in programming!
unsigned int a = (1 << 31); // a = 2147483648
int b = a; // b = -2147483648
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 8 / 12
Signed Negation
In two’s compliment, bit-wise complement then add 1. 6=(0110)2 =(0×23)+(1×22)+(1×21)+(0×20)
⇓ compliment
(1001)2 =(−1×23)+(0×22)+(0×21)+(1×20)=−8+1
⇓ add one
(1001)2 +(0001)2 =(1010)2 =−8+0+2+0=−6
Also works in reverse! (from negative to positive) ë Still, compliment then add 1.
ë −6=(1010)2 ⇒(0101)2 +1⇒(0110)2 =6
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 9 / 12
Signed Extension
Signed Extension:
Represent a number using more bits but keep numerical value. Very easy in two’s compliment!
Copy the signed bit to the left until desired number of bits.
Examples: 8-bit to 16-bit
2: 0000 0010 ⇒ 0000 0000 0000 0010 -2: 1111 1110 ⇒ 1111 1111 1111 1110 -10: 1111 0110 ⇒ 1111 1111 1111 0110
Note: Truncation (representing a number using less bits) is tricky and you must know what you’re doing.
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 10 / 12
Logical Shift
Logical Shift:
Shift the bits left or right a specified number of times. Fills the vacancies with 0s on shift left and shift right. Throw away any bits that flow out.
<< (shift left) and >> (shift right) in C (unsigned).
Examples (in 8 bits):
2 << 3 = (0000 0010) << 3 = (0001 0000) = 16.
8 >> 2 = (0000 1000) >> 2 = (0000 0010) = 2.
-4 >> 1 = (1111 1100) >> 1 = (0111 1110) = 126.
ë This last one is ambiguous if it is logical or arithmetic shift. In high-level programming languages the right shift operator is usually an arithmetic shift…
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 11 / 12
Arithmetic Shift
Arithmetic Shift:
Shift the bits left or right a specified number of times.
Fills the vacancies with 0s on shift left.
Fills the vacancies with 1s on shift right if number is negative. Fills the vacancies with 0s on shift right if number is positive. Throw away any bits that flow out.
<< (shift left) and >> (shift right) in C (signed).
Examples (in 8 bits):
2 << 3 = (0000 0010) << 3 = (0001 0000) = 16. 8 >> 2 = (0000 1000) >> 2 = (0000 0010) = 2. -4 >> 1 = (1111 1100) >> 1 = (1111 1110) = -2.
Alex Brandt Chapter 2: Synchronous Circuits, Prelude Monday February 1, 2021 12 / 12