Formula Sheets: Number System | Digital Logic - Computer Science Engineering (CSE) PDF Download

 Page 1


Num b er System F orm ula Sheet
Num b er System Basics
• Definition : System for represen ting n um b ers using digits and a base (radix).
• Common Bases : Binary (base-2), Octal (base-8), Dec imal (base-10), Hexadecimal (base-16).
• Num b er Represen tation : N =
?
m-1
i=-k
d
i
·b
i
, whereb is base,d
i
is digit,m is in teger part digits,
k is fractional part digits.
• Num b er of Digits : N
digits
=?log
b
X?+1 , for in teger X in base b .
• Base Con v ersion (In teger) :
– T o base b : Divide b y b , collect remainders, e.g., 13
10
= 1101
2
.
– F rom base b : N
10
=
?
d
i
·b
i
, e.g., 1011
2
= 1·2
3
+0·2
2
+1·2
1
+1·2
0
= 11
10
.
• Base Con v ersion (F raction) :
– T o base b : Multiply fractional part b y b , collect in teger parts, e.g., 0.625
10
= 0.101
2
.
– F rom base b : F
10
=
?
d
i
·b
-i
, e.g., 0.11
2
= 1·2
-1
+1·2
-2
= 0.75
10
.
In teger Represen tation
• Unsigned In teger :
– Range: 0 to 2
w
-1 , where w is w ord size (bits), e.g., 32-bit: 0 to 4,294,967,295 .
– Bits Required: w =?log
2
(N +1)? , for n um b er N .
• Signed In teger (2’s Complemen t) :
– Range: -2
w-1
to 2
w-1
-1 , e.g., 32-bit: -2,147,483,648 to 2,147,483,647 .
– Negation: -X = 2
w
-X =X +1 , where X is bit wise complemen t.
– Sign Bit: MSB = 0 (p ositiv e), 1 (negativ e).
• 1’s Complemen t :
– Range: -(2
w-1
-1) to 2
w-1
-1 , e.g., 4-bit: -7 to +7 .
– Negation: -X =X .
– Dra wbac k: T w o zeros (+0 , -0 ), less common.
• Sign-Magnitude :
– Range: -(2
w-1
-1) to 2
w-1
-1 , e.g., 4-bit: -7 to +7 .
– Represen tation: MSB for sign, remaining w-1 bits for magnitude.
– Dra wbac k: T w o zeros, complex arithmetic.
• Ov erflo w Detection (2’s Complemen t) :
Floating-P oin t Num b er Represen tation
– IEEE 754 Standard : V alue = (-1)
s
·M·2
E
, wheres is sign bit,M is man tissa (significand),
E is exp onen t.
– F ormats :
* Single Precision (32-bit): 1 sign, 8 exp onen t, 23 man tissa bits.
* Double Precision (64-bit): 1 sign, 1 1 exp onen t, 52 man tissa bits.
– Normalized F orm : M = 1.f , where f is fraction (23 or 52 bits), implied leading 1 .
– Exp onen t Bias : E
biased
= E + bias, bias = 2
e-1
-1 , e.g., 127 (single), 1023 (double), e is
exp onen t bits.
1
Page 2


Num b er System F orm ula Sheet
Num b er System Basics
• Definition : System for represen ting n um b ers using digits and a base (radix).
• Common Bases : Binary (base-2), Octal (base-8), Dec imal (base-10), Hexadecimal (base-16).
• Num b er Represen tation : N =
?
m-1
i=-k
d
i
·b
i
, whereb is base,d
i
is digit,m is in teger part digits,
k is fractional part digits.
• Num b er of Digits : N
digits
=?log
b
X?+1 , for in teger X in base b .
• Base Con v ersion (In teger) :
– T o base b : Divide b y b , collect remainders, e.g., 13
10
= 1101
2
.
– F rom base b : N
10
=
?
d
i
·b
i
, e.g., 1011
2
= 1·2
3
+0·2
2
+1·2
1
+1·2
0
= 11
10
.
• Base Con v ersion (F raction) :
– T o base b : Multiply fractional part b y b , collect in teger parts, e.g., 0.625
10
= 0.101
2
.
– F rom base b : F
10
=
?
d
i
·b
-i
, e.g., 0.11
2
= 1·2
-1
+1·2
-2
= 0.75
10
.
In teger Represen tation
• Unsigned In teger :
– Range: 0 to 2
w
-1 , where w is w ord size (bits), e.g., 32-bit: 0 to 4,294,967,295 .
– Bits Required: w =?log
2
(N +1)? , for n um b er N .
• Signed In teger (2’s Complemen t) :
– Range: -2
w-1
to 2
w-1
-1 , e.g., 32-bit: -2,147,483,648 to 2,147,483,647 .
– Negation: -X = 2
w
-X =X +1 , where X is bit wise complemen t.
– Sign Bit: MSB = 0 (p ositiv e), 1 (negativ e).
• 1’s Complemen t :
– Range: -(2
w-1
-1) to 2
w-1
-1 , e.g., 4-bit: -7 to +7 .
– Negation: -X =X .
– Dra wbac k: T w o zeros (+0 , -0 ), less common.
• Sign-Magnitude :
– Range: -(2
w-1
-1) to 2
w-1
-1 , e.g., 4-bit: -7 to +7 .
– Represen tation: MSB for sign, remaining w-1 bits for magnitude.
– Dra wbac k: T w o zeros, complex arithmetic.
• Ov erflo w Detection (2’s Complemen t) :
Floating-P oin t Num b er Represen tation
– IEEE 754 Standard : V alue = (-1)
s
·M·2
E
, wheres is sign bit,M is man tissa (significand),
E is exp onen t.
– F ormats :
* Single Precision (32-bit): 1 sign, 8 exp onen t, 23 man tissa bits.
* Double Precision (64-bit): 1 sign, 1 1 exp onen t, 52 man tissa bits.
– Normalized F orm : M = 1.f , where f is fraction (23 or 52 bits), implied leading 1 .
– Exp onen t Bias : E
biased
= E + bias, bias = 2
e-1
-1 , e.g., 127 (single), 1023 (double), e is
exp onen t bits.
1
– Range (Single Precision) :
* Exp onen t: -126 to +127 (biased 1 to 254), normalized.
* V alue: ˜±2
-126
to ±2
127
·(2-2
-23
) .
– Precision : P ˜ 2
-f
, where f is fraction bits, e.g., 2
-23
˜ 1.19×10
-7
(single).
– Sp ecial V alues :
* Zero: s = 0/1 , E = 0 , M = 0 .
* Infinit y: E = 255 (single), M = 0 .
* NaN: E = 255 , M ?= 0 .
– Denormalized Num b ers : M = 0.f , E = -126 (single), for small v alues, V alue = (-1)
s
·
M ·2
-126
.
– Rounding Error : ?˜
1
2
·2
-f
, impacts arithmetic accuracy .
Data Represen tation
– Bit : Smallest unit, 0 or 1.
– Byte : 8 bits, 2
8
= 256 v alues.
– W ord : w bits, t ypically 16, 32, or 64, 2
w
v alues (unsigned).
– BCD (Binary-Co ded Decimal) : 4 bits p er decimal digit, e.g., 123
10
= 000100100011
BCD
.
* Bits Required: N
bits
= 4·N
digits
, less e?icien t than binary .
* Con v ersion Time: T
BCD
=O(N
digits
) .
– Gra y Co de : A djacen t n um b ers differ b y 1 bit, e.g., 3-bit: 000, 001, 011, 010, 110, 111, 101,
100.
* Binary to Gra y: G
i
=B
i
?B
i+1
, B
n-1
is MSB.
* Gra y to Binary: B
i
=G
i
?B
i+1
?···?G
n-1
.
* Gate Coun t: N
gates
˜n-1 X OR gates for n -bit con v ersion.
– Error Detection Co des :
* P arit y Bit: Ev en/Odd, 1 bit, detects single- bit errors.
* Hamming Distance: d
min
, n um b er of bit differences, d
min
= 2 for single-error detection.
P erformance Metrics
– Con v ersion Time : T
con v ert
= O(logN) for in teger base con v ersion, O(k) for fractional (k
digits).
– Arithmetic Dela y (In teger) : T
add
˜O(logw) (CLA), T
m ul
˜O(w) for w -bit n um b ers.
– Arithmetic Dela y (Floating-P oin t) : T
add-FP
˜ T
align
+T
add
+T
normalize
, t ypically 3-5
cycles.
– Storage E?iciency : E
storage
=
log
2
N
w
, higher for binary vs. BCD.
– Represen tation Error (Floating-P oin t) : ?
rel
˜
|X-X appro x|
|X|
= 2
-f
, where f is fraction
bits.
– Circuit Complexit y : C
circuit
=N
gates
·T
gate
, e.g., Gra y co de con v ersionC ˜ (n-1)·T
X OR
.
Applications and Concepts
– Num b er Systems : Binary for digital circ uits, hexadecimal for compact represen tation.
– In teger Represen tation : 2’s complemen t for arithmetic, T
neg
˜T
add
in ALUs.
– Floating-P oin t : Used in scien tific c omputing, GPUs, P ? 2
-f
critical for precision.
– BCD : Displa ys, financial systems, N
bits
= 4·N
digits
for readabilit y .
– Gra y Co de : Re duces errors in coun ters, enco ders, d
min
= 1 p er transition.
– Data Represen tation : Impacts memory usage, S
mem
=w·N
w ords
, and p e rformance.
2