4. Obtain an optimal prefix code for the message “MISSION SUCCESSFUL”. Indicate the code
for the message.
in Other Math Topics by

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.

1 Answer

 

We make a list of the letters and their frequencies in the message MISSION SUCCESSFUL, including the space. S=5; I=U=C=2; M=O=N=space=E=F=L=1. The number after the equals sign gives the "weight", the frequency of the letter(s). The next step is to make a tree with the highest frequency letters near the top of the tree and the lowest at the bottom. These are the leaves. The idea is to find an optimal binary code that is shortest for the highest frequency letter and longest for the lowest. The branches of the tree bifurcate to two "child" branches we call left and right. Left is denoted on the code by a zero and right by a 1. We start at the base of the tree with all the letters with a frequency of 1. We group them into pairs. Since there are seven we take three pairs: FL, spE, ON and join each pair to a "node", which is simply a point where each letter branches off to the left or right. We give the node the combined weight of the letters that branch off from it. So for ON, spE and FL the combined weight is 2. So we have three nodes. We take a pair of these (spE node and FL node) and create another node that joins them. What we can do now is create another node that joins the spare ON node and the spare letter M.

We end up with a type of family tree where at each node including the topmost, we have exactly two children at every node. In this tree there is only one "parent" per pair of "children", a sort of monogenesis. Each child can only parent two children. At the end of the generation chain are the letters, the leaves of the tree.

To find out which unique code each letter is associated with we use the digit 1 when we branch to the right and 0 if we branch to the left. Here are the codes I came up with.

S=0, C=110, I=1110, U=1111, M=1000, F=10010, L=10011, space=10100, E=10101, O=10110, N=10111. The message is these codes following one another in sequence, so it goes:

1000|1110|0|0|1110|10110|10111|10100|0|1111|110|110|10101|0|0|10010|1111|10011

The vertical bar has been inserted for legibility; it isn't part of the code. This is not the only way the message can be encoded, and the decoding depends on the receiver possessing the tree from which the codes are derived.

by Top Rated User (1.1m points)
edited by

Related questions

1 answer
asked Oct 8, 2014 in Other Math Topics by simran | 642 views
1 answer
asked May 16, 2013 in Geometry Answers by anonymous | 686 views
1 answer
asked Oct 8, 2014 in Other Math Topics by simran | 593 views
1 answer
1 answer
asked Sep 7, 2017 in Algebra 1 Answers by Devon | 612 views
2 answers
asked Mar 2, 2014 in Algebra 1 Answers by Vidya Rianti | 698 views
1 answer
0 answers
asked Aug 8, 2012 in Word Problem Answers by anonymous | 1.5k views
0 answers
asked Nov 14, 2011 in Statistics Answers by anonymous | 1.1k views
1 answer
asked Jul 3, 2016 in Other Math Topics by myomcy | 571 views
1 answer
asked Jul 3, 2016 in Other Math Topics by myomcy | 874 views
1 answer
asked Mar 31, 2016 in Word Problem Answers by Godizlove | 564 views
1 answer
asked Aug 11, 2013 in Geometry Answers by rahul | 526 views
Welcome to MathHomeworkAnswers.org, where students, teachers and math enthusiasts can ask and answer any math question. Get help and answers to any math problem including algebra, trigonometry, geometry, calculus, trigonometry, fractions, solving expression, simplifying expressions and more. Get answers to math questions. Help is always 100% free!
87,542 questions
99,768 answers
2,417 comments
504,297 users