> TVS%`0Lbjbjٕ 5.L lllllll$LA
F4)4OA$BhDsAl
sAll
A
jl
l
ll
$|Ej;dA0AEFEEl<
sAsA
A
llllllKFUPM-EE DEPT.
EE430: Information Theory and Coding
Problem Set # 2 Dr. Ali Muqaibel
1. Consider a sequence of letters of the English alphabet with their probabilities of occurrence as given here:
LetterailmnopyProbability0.10.10.20.10.10.20.10.1Compute two different Huffman codes for this alphabet. In one case, move a combined symbol in the coding procedure as high as possible, and in the second case, move it as low as possible. Hence, for each of the two codes, find the average code-word length and the variance of the average code-word length over the ensemble of letters.
2. A discrete memoryless source has an alphabet of seven symbols whose probabilities of occurrence are as described here:
Symbols0s1s2s3s4s5s6Probability0.250.250.1250.1250.1250.06250.0625Compute the Huffman code for this source, moving a "combined" symbol as high as possible. Explain why the computed source code has an efficiency of 100 percent.
3. Consider a discrete memoryless source with alphabet {s0, s1, s2} and statistics {0.7, 0.15, 0.15} for its output.
(a) Apply the Huffman algorithm to this source. Hence, show that the average code-word length of the Huffman code equals 1.3 bits/symbol.
(b) Let the source be extended to order two. Apply the Huffman algorithm to the resulting extended source, and show that the average code-word length of the new code equals 1.1975 bits/symbol.
(c) Compare the average code-word length calculated in part (b) with the entropy of the original source.
4. Consider the following binary sequence
11101001100010110100...
Use the Lempel-Ziv algorithm to encode this sequence. Assume that the binary symbols 0 and 1 are already in the codebook.
5. A discrete memoryless source with A = { a, b, c } emits the following string.
bccacbcccccccccccaccca
Using the Lempel-Ziv algorithm, encode this sequence and find the code dictionary and the transmitted sequence.
6. A source with A = {a, b, c} is encoded using the Lempel-Ziv algorithm. The transmitted code word sequence is 2,3,3,1,3,4,5,10,11,6,10.
Construct the dictionary and decode this sequence.
Note: not all answers will be posted. Questions are selected from different text books (Wells, Haykin).
Practice is something we do before and not during exams! Best regards, Dr. Ali Muqaibel
34BC 9
~sdVsJh6CJH*]aJh%#h6CJ]aJhh6CJH*]aJh6CJ]aJhCJaJhhCJaJh%#h%#h%#h%#6CJ]aJh%#CJaJh%#CJaJh%#h%#CJaJh%#h%#5CJ\aJh%#hCJaJho3h5CJ\aJhcmHsHhmHsHho3h4 zVVV#$d$1$A$If^`a$gdlۥ"$d$1$A$If^`gdlۥd<1$^`gdo3&$d%d&d'dNOPQgdc&$$d%d&d'dNOPQa$ L $ ( , llll#$d$1$A$If^`a$gdl#$d$1$A$If^`a$gdl"$d$1$A$If^`gdlFf#$d$1$A$If^`a$gdlۥ, 0 4 8 9
[[#$d$1$A$If^`a$gd3lۥ"$d$1$A$If^`gd3lۥ$d<1$^`a$gdc^`gd%#$d<1$^a$gdo3FfB#$d$1$A$If^`a$gdl
!X23478:;<=>NQno$ȽwwlddddhCJaJhhCJaJh6CJH*]aJhh6CJH*]aJhh6CJ]aJhhCJaJho3h5CJ\aJhhhCJaJhCJaJhc6CJ]aJh6CJH*]aJh6CJ]aJh%#h6CJ]aJ' #$d$1$A$If^`a$gd3lۥ !kd@$$Iflִ7
0)|PSSSSSSS
t06 44
laS!-27=CIPW#$d$1$A$If^`a$gd3l#$d$1$A$If^`a$gd3l"$d$1$A$If^`gd3lWXkd$$Iflִ7
0)|PSSSSSSS
t06 44
laSXop
$Ohi~~l$d<1$^a$gdc$
1dT1$a$gd$d1$a$gd$8dx1$^8`a$gdc$7d1$^7`a$gd7d1$^7`gdd1$^`gd ^`dx1$^gdc$&'
4K*4MN*+KŷŷŷůŷŷůŧŧŢ}qeYhA]hA]5CJaJhA]hA]CJ\aJhA]hcCJ\aJhchA]CJ\aJhchA]6CJ\]aJ hc5 h6 h5hcCJaJho3CJaJho3ho36CJ]aJho3ho3CJaJho3ho35CJaJhhCJaJhhCJaJho3h5CJ\aJ"4KNLx$dN^`gdA]x^`gdA]$d31$^a$gdcd1$^`gdcd<1$^gdc
d1$`gdo3 d1$gdo3KLhA]hcCJ\aJ30&P P. A!"0#$%$$IfS!v h5P55555555 #vP#v :Vl
t6, 5P5 aSkd$$Ifl 7 K_P
t06$$$$44
laS$$IfS!v h5P55555555 #vP#v :Vl
t6, 5P5 aSkd$$Ifl 7 K_P
t06$$$$44
laS$$IfS!vh5P5S5S5S5S5S5S5S#vP#vS:Vl
t6,5P5SaS$$IfS!vh5P5S5S5S5S5S5S5S#vP#vS:Vl
t6,5P5SaSH@HNormal5$7$8$9DH$_HmH sH tH DADDefault Paragraph FontVi@VTable Normal :V44
la(k(No List@B@@ Body TextB*CJaJphx@x%#
Table Grid7:V0$A$L .4 $(,0489 !-27=CIPWXop$Ohi4KNN 0H0H0H0H0H0H0H0H0H0H0H0H0H00H0H0H0H0H0H0H0H0H0$A$C$EƀH0H0H0H0H0H0H0H0H0H0H0dij.mWINWORD.EXEhp LaserJet 1320 PCL 6 (Copy 1XC 4dXXA4DINU"4$]'$IUPH dA4 [none] [none]Arial4P d?CSS<Automatic>dij.mWINWORD.EXENL p@UnknownGz Times New Roman5Symbol3&z Arial"Ah5ccxx24H H 2QHX(?%#2Z1. Consider a long random sequence of 0's and 1's that are independent and equally likely.Dr. Maan KousaITCOh+'0(4@P \h
\1. Consider a long random sequence of 0's and 1's that are independent and equally likely.Dr. Maan KousaNormalITC2Microsoft Office Word@@ż@賀$|@賀$|c՜.+,0Lhp
+EE.Dept.H '[1. Consider a long random sequence of 0's and 1's that are independent and equally likely.Title
!"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJLMNOPQRURoot Entry F$|WData
1Table EWordDocument5.SummaryInformation(CDocumentSummaryInformation8KCompObjq
FMicrosoft Office Word Document
MSWordDocWord.Document.89q