Question

1. If you stored the following binary number (-0.000000100101) as a binary floating point number, what value would be STORED in the exponent section? Also convert A7.11 Hex value to floating point.

2. Number of bits saved using Huffman encoding. From the following characters used in a message with their associated frequency, use Huffman Coding as a compression technique. How many bits will be saved in the message? (Keep in mind that one character is one byte which consists of 8 bits). Draw the associated Huffman Tree to help calculate your answer. Show all your work. (15 points)

Character                                                                                            Frequency

A	6
B	11
C	13
D	14
E	19
F	47

Answer 1

1)

Finding exponent :

First we normalize 0.000000100101. We keep shifting decimal place to the right until there is one non-zero to the left of decimal.

0.000000100101 * 2⁰

00.00000100101 * 2^-1

000.0000100101 * 2^-2

...........

1.00101 * 2^-7

Exponent of 2 is -7. But there is a bias 127, hence (-7 + 127 = 120) is our exponent.

(120)₁₀ = (01111000)₂

Hence 120 / 01111000 will be stored in the exponent part of the floating point representation.

Converting A7.11 to floating point :

A7.11 is first converted to binary.

Since A = 10 = 1010, 7 = 0111, 1 = 0001

(A7.11)₁₆ = (10100111.00010001)₂

We will normalize this by shifting decimal to left.

10100111.00010001 * 2⁰

1010011.100010001 * 2¹

101001.1100010001 * 2²

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

1.010011100010001 * 2⁷

sign is positive = 0

exponent is 7 = 127 + 7 = 134 = 10000110

mantissa = 010011100010001 (trailing zeroes are added because mantissa's length is 23 bits)

2)

The huffman tree is as generated :

The minimum freq is of A and B and hence they combine to give Node of 17 (11+6)

Now the minimum freq is of C and D and hence they combine to give Node of 27 (13+14)

Now minimum freq is of E and Node of 17, which combine to give Node of 36 (19 + 17)

Now minimum freq is of Node of 36 and Node of 27, which combine to give Node of 63 (36 + 27)

Now minimum freq is of Node of 63 and F, which combine to give Node of 110 (63 + 47). Final tree is :

Huffman Codes of the characters -

A - 0000

B - 0001

C - 010

D - 011

E - 001

F - 1

Total number of bits in Huffman encoded message = ∑ ( frequency_i x code length_i )

= { (6*4) + (11*4) + (13*3) + (14*3) + (19*3) + (47*1) }

= { 24 + 44 + 39 + 42 + 57 + 47 }

= { 253 }

if we dont use huffman then,

each character takes 8 bits so for A = 8*6 = 48

for B = 11*8 = 88

for C = 13*8 = 104

for D = 14*8 = 112

for E = 19*8 = 152

for F = 47*8 = 376

total = 880 bits

bits saved = 880 - 253 = 627 bits

Hope this helped.