1) (20 points) Construct a Huffiman code for the following data (show all the st
ID: 3733203 • Letter: 1
Question
1) (20 points) Construct a Huffiman code for the following data (show all the steps): Frequeney of SytmbosTest Symbol Sequence A B CD E 021 0.35 016 0.08 0.20 BEAAEDDEBB 0.34 0.12 0.07 0.37 0.10 AADADDECCD 040 020 0.21 0.09 0.10 ACAAECEAEB Student Name Leon Andersom Uiiwal Baskota Albert Boateng Nissi Campbell Samuel A. Dagne James Daniel Zakeia Davis Justin Epps Amanuel E. Gebre Melrondarius Groom Yoseph Hailemariam Antonie Hobson 0.15 0.24 0.14 0.27 0.20 AEBBADCBEE 0.50 02 0.1 0.05 0.15 ACBDAABDAC 045 0.18 0.19 007 0.11 BEBAAABCBA 0.29 0.07 0.10 0.20 0.34 EEAEAEDEEE 0.20 0.30 0.15 0.25 0.I0 ABBCBAACBD 0.35 0.30 012 020 0.03 AADADBCABB 0.10 0.16 054 0.12 0.08 BCCADCCCco 0.44 0.22 0.11 0.04 0.19 AAABBEABEA 028 027 0.15 0.14 0.16 ACEDDCBACA 0.10 0.29 0.21 0.32 0.08 BBDBBADDDC 025 0.36 0.12 018 009 BBAEBACBBA 021 0.14 0.15 0.40 0.10 DDACEBADDA 0.50 0:05 0.02 10.16 027 AAABAHECDA 0.09 0.08 025 040 8 DDABCCEADD 017 019 036 012 016 CADECCDEABC Portia Junius Justin McGuffee Ryun Moore Keara Rogers Timothy Stewart Nebiyou Tadesse Phat Tran (a) Determine the average number of bits per symbol ) Determine the generic compression ratio compared to fixed-length encoding (c) Encode the given text symbol sequence using the Huffman code that you determined compression ratio achieved for this text compared to fixed-length encoding. Compute theExplanation / Answer
Calculation of Huffman Code:
changing frequency for 100 sysmbols for Simplification of Calculation:
Leon Anderson
A B C D E
21 35 16 8 20
Let Smallest be X and Second Smallest be Y
We will add the value Smallest and Second Smallest and write as follows
XY value(X+Y)
A B DC E
21 35 24 20
We will do this until we have only One Column is left
EA B DC
41 35 24
EA DCB
41 59
EADCB
100
Now we will divide from bottom to top in Binary Tree
0 /
EA DCB
0/ 1 0/
E A DC B
0/
D C
Huffman encoding
Symbol Encoding
B 11
A 10
E 00
C 101
D 100
a. For average number of bits per symbol
frequency of element* character used to represent / frequency of elements
35*2+21*2+20*2+16*3+8*3/100=2.24
b. for fix length encoding for n symbols we need UB(log2(n)), UB()=UPPER BOUND()
here we needUB(log2(5))=3
we need 3*100=300 bits to represent
Generic comression Ratio=bits in huffmann coding/bits in fixed length coding
224/300=0.7466
c. BEAAEDDEBB
Encoded string is:
1110000010100101111
Now for other questions we will directly make table and then we will solve:
Ujjwal Baskota:
Huffman encoding
Symbol Encoding
D 1
A 00
B 011
E 0100
C 0101
a. For average number of bits per symbol
frequency of element* character used to represent / frequency of elements
34*2+12*3+7*4+37×1+10*4/100=2.09
b. for fix length encoding for n symbols we need UB(log2(n)), UB()=UPPER BOUND()
here we needUB(log2(5))=3
we need 3*100=300 bits to represent
Generic comression Ratio=bits in huffmann coding/bits in fixed length coding
209/300=0.6967
c. AADADDECCD
Encoded string is:
000010011010001011
Albert Boateng
Huffman encoding
Symbol Encoding
A 1
C 01
B 000
E 0010
D 0011
a. For average number of bits per symbol
frequency of element* character used to represent / frequency of elements
40×1+20×3+21×2+9×4+10×4/100=2.18
b. for fix length encoding for n symbols we need UB(log2(n)), UB()=UPPER BOUND()
here we needUB(log2(5))=3
we need 3*100=300 bits to represent
Generic comression Ratio=bits in huffmann coding/bits in fixed length coding
218/300=0.7267
c. ACAAECEAEB
Encoded string is:
10111001001001010010000
Nissi Campbell
Huffman encoding
Symbol Encoding
C 00
A 10
B 11
D 010
E 011
a. For average number of bits per symbol
frequency of element* character used to represent / frequency of elements
25×2+20×2+28×2+15+3+12×3/100=2.39
b. for fix length encoding for n symbols we need UB(log2(n)), UB()=UPPER BOUND()
here we needUB(log2(5))=3
we need 3*100=300 bits to represent
Generic comression Ratio=bits in huffmann coding/bits in fixed length coding
239/300=0.7967
c. BADBCDECBD
Encoded string is:
111001011000100110011010
PS: Rest questions can be solved in similar manner.
If you want any specific part do let me know.
Give it a Thumbs Up. Thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.