Entropy & Data Compression: Shannon's Source Coding & Symbol Codes

[00:00:04]thank you all for coming let me recap what we did last time we've started talking about Source coding also known as data compression we've been looking at toy examples one example of a redundant file for us to compress is something that's mainly zeros with just a few ones scattered at random so we call that the bent coin how should we compress a file like that well when we're thinking about compression the claims we're examining are Shannon's assertions that if you take log base 2 of one over the probability of an outcome that tells you how much information content that outcome has got and it's how long the message ought to be associated with that outcome in bits as well it's the ideal message length the entropy which is the average of the Shannon information content is claimed to be the right way to measure average information content and the third assertion that we've got and that we have sort of proved last time is the source coding theorem which says that if you get a very long string of outcomes from uh a random Source identically distributed then those outcomes can be compressed into roughly n times the entropy bits so we sort of proved that last time we U did this proof by counting the typical set we didn't actually do a general proof that's in the book but what we did was we looked at a special case of the bent coin where you toss it n times and get mainly zeros and a few ones and there we all know what the typical set is you expect to get roughly if it was a bent coin with a bias of 10% you expect 10% ones and the typical set of strings is all the strings that have roughly 10% ones so in general what the typical set means and this is a a defined concept is uh if you get a string of n independent out comes from a source that string is very likely to be in a typical set the typical set elements all have roughly the same probability as each other and there are 2 to the n * the entropy of them so the rough proof of the source coding theorem is then well just give a name to each of these guys the number of names um you'll need is 2 to the end time the entropy so the length of all the names will be n * the entropy and they've incidentally all got roughly the same probability as each other which must therefore be 2 Theus n times the entropy so that's the uh very rough outline of the proof of the source coding theorem for a general source and we did it for the bent coin um looking at a long string of n outcomes and the way we found our ourselves at the proof was we imagine iMed playing the bcoin lottery we wanted to win the lottery for the mafia boss how much of his money did we need to spend which tickets would we buy well we found this big sack full of tickets and then we imagined writing a a new name for each ticket on the reverse of the ticket we counted the number of tickets in the bag and we found we had 2 to the end times the entropy so that's what we did last time that was our proof of the source coding theorem at least for the bent coin when I said the number of tickets in the bag is 2 to the n * the entropy it's 2 to the 2 to the n * the entropy plus a little bit and that little bit is to do with the fluctuations around the the mean of the the typical number of of ones those fluctuations go a square root of n where n is the length of the the string so they get relatively small compared to this the main term nh2 and here's just a picture reminding you what a gan distribution looks like and you can get the probability um down um as small as you like the probability of failure as small as you like just by adding a few extra square root of n's a few extra standard deviations to your typical set all right so that was a ridiculous way to do compression it involved a very large bin bag full of tickets that you wrote things on the two sides of that was our compression and uncompression algorithm now for the next two lectures we're going to discuss practical data compression how would we compress a bent coin practically well that's actually a homework exercise I set for you so I'd like you to work on that but we'll carry on working on other approaches to related problems and I'm going to talk today about a method of doing data compression called symbol codes and the idea of a symbol code is it's something you could apply for example to English or to any language that involves an alphabet of characters where some characters are more probable than others and to make life especially simple to start with I'm going to pretend that the probability distribution for every character is the same every time and that we know that distribution and we'll usually assume that it's non-uniform so here is what that distribution could look like here's an alphabet of 26 characters plus space so 27 in all and a probability distribution over those and you can see space is the most probable character and then we've got e t a o i n h r s HDL all that that sort of stuff so it's a this is like an English language distribution and the task now is to give a code word to each of these symbols in the alphabet to each to each of these elements of the alphabet and here's an example of what those code words could look like we're going to encode into binary and we've given a the code word four zeros and we've given Zed the code word 1 1 0 1 01 and space has got 01 so that's an example of a code and the way you use a symbol code is you take the source file and you replace it by the corresponding code words in order concatenated with no punctuation at all so the receiver won't be able to see where the boundaries between the code words are okay so a symbol code is going to be a map from each symbol X in your alphabet to we'll call it C of X and C of X is a binary string and as you can see here it can be of of any length and the way we write that in set notation is 01 is the set with zero and one in it and 01 set with a plus means the set of all strings of any length um made up of zeros and ones um that may be familiar to those of you who hang out with computer scientists um let me give you another example 01 to the power two is the same as the set of string 0 0 0 1 1 0 and 1 one okay so that's just a little bit of notation a symbol code is a map from symbols to Binary strings and then the way a symbol code works is we encode the string of outcomes X1 X2 X3 up to xn by concatenating without punctuation the code word for X1 and the code word for X2 the code word for X3 and the code word for xn so I'll just give you an example if we gave a the code word one B the code word 0 and0 and c1011 then the file containing cabb would get encoded as 1 0 1 1 1 0 1 0 0 1 Z okay so that's a fairly simple idea but now we need to get our head round these symbol codes understand them theoretically and understand them practically and these are quite important codes they're quite widely used especially in in history so the questions we want to ask today are the theoretical question how well might a symbol code perform and what we're anticipating here is maybe the answer will have something to do with the entropy and Shannon information content and that sort of thing and that would again reinforce the claims we've been asserting and then the Practical question is hey stuff Theory I just want to know how to make a good one how do we make good symbol codes and when we say good or optimal we need to Define what we mean by optimal so let's do that so what do we mean by Optimal well we're after compression so we want a short expected length don't we so we'll use that as our main objective function so there may be others so we'll Define the expected length of a code C for an ensemble X on The Ensemble being the alphabet with all its probabilities we'll Define it to be L of c and x is sum over all your elements in your alphabet and multiply the probability of that outcome by the length that you have assigned where Li I is the length in bits of the code that you've assigned to the I element okay nothing profound going on here I'm just defining the expected length and it's probably a good idea to immediately use an example so let's give ourselves an alpha alphabet and the alphabet is going to be a b c d and let's have a probability distribution half quter 1/8 1/8 so this is a toy probability distribution with uneven probabilities one thing we might want to know about this Ensemble is what is its entropy and the answer is well it's a half * 1 plus a A4 * 2 + an e * 3 + an e * 3 these 1 2 3 and three being respectively the logs base two of this this this and this and that is 1 and 3/4 bits so let's um give ourselves a symbol code and then try and make it better and we need to pin down what the rules of the game are actually going going to be here um so what do we want uh let's let's define the the rules first and then look at some examples first rule is it had better work when someone encodes with this and then someone else decodes they better get back what we first put in so what comes out must be what comes in um we want it to decode correctly and we want it to guarantee to decode correctly not just to have a 99.9% chance of working which was already quite good in our slightly silly approach of last time we want it to always decode correctly um so let let's justify our other rules and then I'll say a bit more precisely what we what we mean by by this ideally we'd like it to be easy to decode as well so we don't want to have the recipient having to spend hours staring at the code book trying to figure out where the punctuation where the missing punctuation marks go in the in this received string so easy to decode would be nice to have but it's not essential if if we can get a big win on this final objective which is small expected length small L CX okay let's just be precise about what we mean by it's got to decode right we want the code to be uniquely decodable so when you receive an encoded string there should be no ambiguity about what was sent so for any string X and any other string y such that X is not the same as y we want the encoding of x to not equal the encoding of Y so that's the definition of unique decodability okay and just to check my notation is clear C of AI is the way we encode a particular element of the alphabet and then if we have C of a string like X that's just the concatenation of X1 X2 okay so I'm overloading in the symbol C to mean either the way that you encode a single symbol or it could be the encoding of an entire string all right okay we've got ourselves an ensemble let's define some symbol codes and have a think about these objectives what does it mean to say it's got to be uniquely decodable what does what does that imply how do we get a small expected length is this a good start for English um could it be made better is it uniquely decodable let's look at a a simple example let's define a code called C1 and its code words are going to be one and three zeros 0 1 0 0 0 0 1 0 and three zeros and a one and I've deliberately made them all four characters long because now we know the recipient will be able to put the punctuation marks in the right place because they're all four characters long what's the expected length of this well all code words are four bits long so the expected length is also four right um can we improve on this is this uh is this the best possible uh code for this Ensemble any suggestions it's got rather a lot of Z zeros in it hasn't it should we get rid of some of the zeros would that work oh you're being shy today yes geter get rid of the trailing zeros brilliant thank you okay so if we remove all the trailing zeros then the recipient will still be able to figure out where the punctuation marks ought to be because they can just look for the ones and they know that the one comes at the end of any code word all right so this is still still self- punctuating and it's easy to decode because they just read along till they head a one and then they can spit out okay it must have been a c or whatever whatever they have got to so what's the expected length of this well I've worked it out for you in advance it's 1.875 or 1 and 78 okay that's a nice idea um [Music] um can we get the expected length any shorter how how about how about this one how about that code what's the expected length of this one expected length is one okay is it uniquely decodable maybe not because even very short strings may have the same encodings as each other okay so this is not uniquely decodable okay so the goal is to get the expected length very short um uh so can we do any better than than this one well uh how about this we need to have have a bit more length they've got to be a bit code words must be different from each other okay that's one of the rules so a deduction from rule is all code words must be different and that's a consequence of unique decodability all right so let's make them different okay uh how about this 1 0 0 0 1 0 and 1 0 okay the expected length of this this is 1 and 58 how do you out the expected okay the expected length is there's a chance of a half of this happening a quarter of this and an eighth for this and an eighth for this so the question was where does the expected length come from expected length is there's a half chance of getting a length of one there's a quarter chance of a length of two plus a 1/8 chance of three plus a 1/8 chance of two and then I added those up all right so it's just the average length of a word given that the lengths are going to be the lengths are 1 2 3 and two okay any other questions so what do you think of this guy let's let's use him to encode something it's the it's got a shorter expected length than examples we've looked at so far let me encode something with it c a a b encoded with is code number three code four when we encode C a b we get 010 1 o oh so is C4 easy to decode is it uniquely decodable what we're trying trying to do here is sort of sail close to the wind we want to make all the code words as short as possible because that's good news but we don't want to sail too close and have problems of unique decodability so is this uniquely decodable we could stare hard at this and and try and figure out is there some other interpretation so we read along 01 how could we get 01 oh it has to be a c doesn't it soorry s of think hard and say okay that's a c then we look at this bit and one one zero what could be this I were thinking hard looking at the code book and we say well maybe oh look there's another zero here it could be an A and an a um and then a b but it could have been uh maybe it was a an a here and a one and a zero maybe that was a d here and then there was a zero from somewhere and so it's difficult to decode because I'm I'm not quite sure especially if we haven't reached the end yet it's not clear what's going on can anyone give us a proof that it's actually not uniquely decodable a proof would mean that you find two strings that have exactly the same DC okay so if you encode DC that gives you 0 1 0 sorry DC gives you 1 0 0 1 Z okay and it have you got another string that also encodes as a b d is 1 0 0 one Z well done okay so if we call this X and this y they're different but they've got the same encoding so it's not uniquely decodable okay so this is useless not uniquely decodable so what's going on let's give ourselves one more example C5 here's C5 0 0 0 1 1 0 1 1 okay expected length of this is two because they're all length two so that's not as good as this one um actually I want to give you a few more has anyone got any further ideas any ways we can improve yeah the C2 mhm last symb aha so you're suggesting take C2 and tweak the last word so we got C6 using 1 0 1 01 but you're saying you don't actually need that final punctuation character because once you've seen three zeros if you're using C2 you know a one is coming next so you can get rid of it all right great okay so the lengths are 1 2 3 and three which incidentally are the same as the Shannon information contents let's call those hi one bit 2 bits three bits and three bits so the expected length which is the average of the length is going to be the same as the average of the Shannon information contents which is the ENT Y which we've already worked out so that's 1 and 3/4 which is the entropy right so that's a fun idea we've got a symbol code whose expected length is the entropy if we encode c a a b with this then we get 0 0 1 1 1 01 now an interesting thing to notice that this set of code words here has lots of zeros in it and only a few ones do you think you can make it any better is it uniquely decodable can anyone give an argument why it must be uniquely decodable we've sort of already said it haven't we okay you're being shy I'll I'll help out the receiver can read along and look in the code code book and once they reach the end of a valid word that's in the code book nothing else will have happened you can't reach you can't get through an a different code word on the way to the code word you're actually thinking of no code word is a prefix of any other code word so this code this is a prefix code is the name we give to this no code word is a prefix of any other we don't have to use prefix codes but it makes them easy to decode another property of a prefix code is you can arrange the code words in a tree where the branches in the tree are the decision is the next character going to be a zero or a one and at each step in the tree you either keep going or you stop because you found a code word so in this one you go down the one branch and you stop and you found the code word for a which is one you go this way get zero and one if you have zero followed by one then you've got B which is encoded with 01 the characters that we the the symbols we saw as we went along those branches we keep going down here zero and one this is C this is D all right I'm going to give you just one more code unfortunately I ran out of board let's put it way over here let me Define another code C7 it's going to look like this 1 1 0 1 0 0 0 0 0 I've deliberately chosen this one because it's not a prefix code it has the property that the code word for a is a prefix of the code word for B and for C all right so it's not a prefix code which means it may be a bit of a headache to decode if you receive a one and you know some more stuff is coming and you receive a zero what what was going on could have been an a could be we start a d you get another zero you still don't know you get some more zeros you you still don't know what's going on you wait and you get lots and lots of zeros and you still don't know and maybe when a one comes along then maybe you can figure out whether the first symbol was an a a b or a c okay so we don't like this uh because it's not easy to decode but is it actually uniquely decodable yes why okay so if you reverse first these four code words they are the same as the code words of C6 which is uniquely decodable if this one were not uniquely decodable that would mean it has got two code Words which are two sorry two strings X and Y whose encodings are identical to each other you could then reverse the two of those and you would have found yourself a pair of strings that have the same code word over here for this code and we know that's impossible because that one's uniquely to code so this one is uniquely decodable but we don't like it because it's not a prefix code so this is uniquely decodable right so one of the ideas we're floating now is easy to decode could mean for example that we'd like a prefix code please but we really do want small expected length okay let me suggest an idea now about how we get small expected length we've found a code here which we're speculating could be the best you can do for this Ensemble with the symbol code because it happens to have reached the entrepre and we've already heard some theorems about not being able to do better than the entropy um and it has the property here's the key intuition about symbol codes and is of all of data compression it has the key property you give short code words to the probable outcomes and longer code words to the less probable ones okay that's what it's all about and that's a possible guess about how we might get the smallest possible expected length we could say oh you give me a list of probabilities I'll sort them and I'll give the shortest possible code word to the most probable one and the and steadily longer code words as we go down the list have a chat to your neighbor and see what you think of of that idea okay so I've suggested an idea here it's got the right spirit it's giving short code words to the probable outcomes and long ones to the less probable ones is that going to work or can anyone criticize that for us if you've got a huge number of symbols then what it might not be good it's definitely not good probably not good okay I might agree with you let me give you uh some backup for your intuition there we've found a case where this proposed algorithm is getting us to the entropy so we can't be too critical of it but maybe we can find a counter example where it doesn't it doesn't work and it doesn't need to be a monster example we can give them all a probability of a quarter except just to make life interesting We'll add Epsilon to one of them and add Epsilon over two to one and subtract Epsilon over two from this one and subtract Epsilon from that one where Epsilon is a billionth okay so they're all essentially they all have a probability of a quarter all right and now we apply this suggested algorithm and what code do we end up with end up with C6 all right so this is a new probability distribution when you use code six which is proposed by this algorithm here you get an expected length that is well the lengths are 1 2 3 and three is the last one in the list and the average of those since they're all equ probable give or take Epsilon is 9 over 4 which is 2 and A4 bits is that the optimal symol code can we do better how anyone C use C5 and the expected length will be two okay QED so but the length of c5x will be 2 right so we can't just use that simple rule though it's got the right Spirit we need to identify some sort of trade off of when do you give short code words to the the most probable guy recognizing that there seems to be some sort of trade-off that when we decide to not give them all length two words if one of them gets a length one then some others sort of get longer it's a bit like when you've got a glove full of water plastic glove full of water and you squeeze a few of the fingers and the other ones have to get bigger there's some sort of conserved quantity lurking in there and that cons conserve quantity is to do with unique decodability if we allowed ourselves to shorten some of the words and didn't make the others longer it looks like we lose uniquely unique decodability I've lost board as well I've run out of board let's wipe this I think the time has come for me to reveal how this rubber glove Works how the the constraint of unique decodability works so let's rattle through a way of thinking about about this if I only use code words of a particular length how many of them can I have well if all my code words have length to um L2 then I can have four of them if all my code words have length three I can have eight if all my code words have length one I can only have zero and one so I can have two and in general I can have two to the L of them so there I was changing the size of the alphabet and noticing that if I have long words I can have more of them exponentially more of them and here is the idea that wraps this up and is consistent with everything we've seen so far the idea is you can think of each code word of some length L has a cost let's call it of 2us L and what we're doing is going to the symbol coding Supermarket here are the different aisles of the supermarket you can go you make making a symbol code you can pick any code words you want so here's the entire set of all conceivable code words but you can't have any choice because it might not be uniquely decodable and I've arranged them in aisles where each aisle has words of the same length and you can wander through the supermarket make some choices and the size of the package for each code word is indicating how much it'll cost you so you've got a budget of one which is the entire height of this Supermarket you can buy these two code words if you want the and the one and then you're done you can't add any more code words of any length because they'd be confused with the zero and the one or you can have these four or you can have these eight or we've seen a bunch of things you can also have you could pick those four that was code number one and you haven't exceeded your budget and that's uniquely decodable the fact that you haven't exceeded your budget doesn't guarantee that it's uniquely decodable but uh definitely if you go over your budget of one then it won't be uniquely decodable so what we've got is the following assertion let's write it here having identified code one if a code is uniquely decodable then the cost of all the code words has to be less than your budget sum of 2us L I must be less than or equal to one these are the costs of your code words that's your budget okay okay and this is called the craft inequality and it's true and we haven't proved it I've just told you it and the proof is in the book so if you're interested in a a proof it's in the textbook okay so this is what unique decodability implies you've got to stay within your budget so there was code one and we had some other ideas here was code number five that was the selection that we made with code where was it uh two two that's code two which doesn't go over budget but it didn't quite use up the whole budget and so on noticed we could make a change instead of buying the 001 code word right at the top we could Lop off the final one and buy the 0000 next door instead and that made the expected length shorter which is good and then we looked at this guy H that was my silly idea sorry about that 1 0 0 1 Z One Z okay and that went over the budget all right and it was a great Labor to find a proof that it went that it didn't work we had to think about strings but now we've got the craft inequality we could have known straight away oh no point even trying this thing it's violated the craft inequality so it can't be uniquely decodable all right um in blue there we have the optimal code and here is um C7 which I wiped off which is where we reversed all of them so this is also uniquely decodable and you can see the difference between the prefix code in blue which is sort of sensible it walks through the supermarket from one side to the other buying code words that you won't confuse with each other whereas the silly um back to front one C6 uh bought one 1 0 1 0 0 which are prefixes of each other and they're on the same um y coordinate in this in this picture all right so that's the craft inequality and a code that gets right up to the budget that uses the full budget we will call a complete code a complete code is one that has sum of 2us l i equal to 1 if you haven't chosen yourself a complete code the advice is you can probably go back to the supermarket make some switches and get yourself a shorter code so it's a bit silly not to use a complete code all right and as we've observed easy to decode codes are prefix codes so let's now address the Practical question or no the theoretical question Theory first practice next let's do five minutes on each the theoretical question is how well can we do with symbol codes so if I give you any ensemble X and if you come up with the best symbol code by whatever method how small can the expected length be okay so the definition of the expected length is Su over i p i l i and we're now going to show that whatever you do with a symbol code you can't beat the entropy and we'll also identify what you need to do in order to get close to the or all the way to the entropy and it's all about figuring out what these expected lengths should be let me give us a clue I'm going to define the ideal length for a code word to be log base 2 one over the probability for that code word so I'm going to introduce a definition namely the Chan information content so I say let's assume the symbol code ought to be using those I'm I'm not assuming it I'm I'm just making a definition and then we'll end up with a proof okay so that's that's the ideal lengths now if you rearrange this and if you imagine that someone has picked some length Li that may or may not be the ideal lengths you can use those similarly to Define some implicit probabilities for which those chosen lengths would be the ideal lengths Okay so we've defined a relationship between lengths and probabilities in this way and I'm going to call the implicit probabilities q and the implicit probability q that you can get from whatever lengths you have come up with will be 2us I except you maybe didn't choose a complete code so maybe the sum of all of these isn't one which would mean it's not a probability distribution so I'm going to divide by the appropriate normal normalizing constant Zed where Z is sum of 2us l i which will be one if it is a complete code so it's one if you've made a sensible uh trip to the supermarket but it could be smaller than one so note Zed will be less than or equal to one for any uniquely decodable code and Z equals 1 for a complete code right what does that then mean well it means Li I the lengths that you've chosen are log base 2 1 over Qi minus log base 2 Z and now I can plug this into l so L is Su i p i we've got log base 2 1 on Qi minus log base 2 of Zed sorry my board hygiene isn't very good [Music] today okay wouldn't it be great if this said sum of P log 1/ P so let's do that sum over i p log base 2 1/ p except that's not true anymore so we need to uh add on the appropriate thing so that it is true sum of P log p over q and then we still have minus log Z lurking at the end sum of Pi is one so we can suck the log Zed out of the summation right we've got somewhere if you pick any symbol code at all then its expected length will equal the entropy plus something plus something else let's give this a name we'll call this the coolback lia Divergence between p and Q and here's a little theorem sum of P log P / Q for any two distributions p and Q is greater than or equal to zero this is called Gibbs inequality and it's one of the most important inequalities of information Theory with equality only if Q is equal to p and log Zed we already know is less sorry Zed is all is less than or equal to one so log Z is less than or equal to Z and minus log Z is greater than or equal to Z with equality only if the code is complete so it's greater than or equal to zero if the code is uniquely decodable with equality only if it's complete so this is true for any code for any symbol code and so what we have just proved is that the expected length is greater than or equal to the entropy not only that so we've shown that the best you can possibly do with the entropy we've shown what you need to do in order to get to the entropy you need your P to equal your Q so you should be using implicit probabilities that are equal to the true probabilities so your length should be the information contents okay so you get equality if and only if the lengths you're using are the channel information contents and you've got a complete code which will happen for free when you do that okay so what have we done we've sort of proved a source coding theorem for symbol codes we've shown that you should be using the Shannon information code contents to set your code word lengths if you want to get to the entropy and then you will get to the entropy and you can't get any further okay that was the theoretical bottom line for symbol codes so the ideal code lengths are the Shannon information contents but in practice if I give you some probabilities like the probabilities we had for English a moment ago you take log base two of them and you're not going to get an integer out are you so in practice for any real probability distribution you typically can't actually get exactly to the entropy so there's a a missing um result which is how close can you get and here's the answer to that let's start again on the left hand side and I'm not going to prove this but it's in the textbook if these ideal lengths l i star which are the channel information contents are not integers how close can you get answer well you can still always get within one bit of the entropy so there exists an optimal symbol code for which this is true so you can get within one bit which sounds pretty good come back next week to hear whether this is good enough or whether in fact we still want to do better the answer is going to be we want to do better because this isn't going to be good enough all right so that's Theory what about practice wouldn't it be great to be able to just take a probability distribution and work out an optimal symbol code for that probability distribution let me tell you how to do it how to make optimal symbol codes I'm not going to prove it you can read the book to figure out a proof the method for making optimal symbol codes that I will show you is called the Huffman algorithm and it's very elegant and it's not completely obvious why it should actually be optimal and why it should get you any near the optimal the ideal Shannon information cont content uh code lengths so here's a summary of how it works remember how prefix code could be related to a binary tree what we're going to do is build that binary tree starting from the leaves we're going to start from the smallest most remote leaves so build a binary tree starting from the furthest leaves of the tree and that's essentially the algorithm let you let me show you what I mean I'll show you with an example that's usually the easiest way let me inventor probability distribution okay here is a six element probability vector and here's the statement of the algorithm combine the two symbols with smallest probability into a new single symbol and repeat that's the algorithm okay so we look at our list of probabilities and we say these are the two smallest so we will combine them and we've defined a little bit of a binary tree here we combine them we add up their probabilities and we get 0.21 and now we repeat on the set of five probabilities that we have have here the two smallest ones are these two we add them up we get 0.25 and now we look at these four probabilities plop plop plop plop we find the two smallest which are4 and 21 we combine them we get 0 3 5 okay that was the first iteration that was the second iteration that was the third iteration and then we've got 25 and 35 which are smaller than 40 so we combine them we get 0.6 and the fourth step and then we combine these we get one and we're done and that was the fifth step and now we've made a binary tree and so we have made a prefix code because we can just slap label 0 1 01 anywhere you like 0 1 0 1 01 and that defines your code words reading from the root back out to the leaves just as an example 1 0 0 so the code word you'll give to this one is one 0 0 and you can fill in the others that's the Huffman algorithm and it's optimal cool hey so let me SU summarize what we've said we've used Gibbs inequality we've talked about unique decodability we've introduced the idea of prefix codes and binary trees and symbol codes are really all about building nice binary trees whenever you get a code that does achieve the entropy the code lengths are equal to the information contents that's the ideal code lengths and with a symbol code you can always get within one bit of the entropy and you can do that with the Huffman algorithm here are the results we've stated without proof the book has proofs of those results I've got a few more slides just to keep things moving um with some things you can be doing for next time I al already encouraged you to do a project namely invent a compressor and an compressor for a source file of 10,000 bits from a bent coin whose probability of one is 01 Implement them and or estimate how well it works and the screen has got some other recommended exercises and recommended reading thanks very much for coming see you next week [Applause]