WARNING: Summaries are generated by a large language model and may be inaccurate. We suggest that you use the synopsis, short and long summaries only as a loose guide to the topics discussed. The model may attribute to the speaker or other participants views that they do not in fact hold. It may also attribute to the speaker views expressed by other participants, or vice versa. The raw transcript (see the bottom of the page) is likely to be a more accurate representation of the seminar content, except for errors at the level of individual words during transcription.

McMillan's Theorem is used to prove that a uniquely decodable encoding exists, such that the length of each codeword is equal to the value of a function applied to the corresponding element in the set. Maxwell's Demon is an example of how particles of gas in a box can be divided using information, and junction discussed how the number of words in a codebook can be bounded by taking the nth root of the number of words. These concepts are discussed in depth in this video, with a demonstration of how to construct a unique and decodable code.

McMillan Theorem is used to prove that a uniquely decodable encoding exists, such that the length of each codeword is equal to the value of a function applied to the corresponding element in the set. A full binary tree of depth Ln is constructed, and for each element in the set, a word corresponding to a node at depth L1 is chosen. Descendants of the node are then removed, resulting in the removal of R to the power of L and minus L1 leaves from the full binary tree. This is repeated for each element in the set, resulting in a uniquely decodable code.

A prefix code is a uniquely decodable code which is constructed from a full honorary tree. To ensure that the code is uniquely decodable, the length of each codeword must be bounded by the number of leaves. This is done by ordering the leaves from L1 up to Ln and ensuring that the sum of the lengths of the codewords is less than the total number of leaves. In order to prove that the map from an integer to a word is injective, an inequality can be used to calculate the number of nodes removed at each depth. This can be used to check if there are still nodes available at the final depth.

Maxwell's demon is an example of how particles of gas in a box can be divided using information. A divider is created, splitting the box into two halves. This process is repeated, with each half being labelled as either 0 or 1, until the box is divided into multiple sections. The proportions of the box are related to the numbers that are added up, with the overall volume of the box being one. Junction discussed how the number of words in a codebook can be bounded by taking the nth root of the number of words in the codebook, and injectivity is used to ensure that each index provides a unique word.

McMillan Theorem was used to prove Channel's Source Coding Theory. X is a finite set and Sigma is also finite. Encoding is a map C from X to a set of words in Sigma and its extension, C', maps the set of words in X to a set of words in Sigma. A prefix code is an example of a uniquely decodable encoding, where no code word is a prefix of another. To show that a prefix code is uniquely decodable, it must be shown that C' is an injective map, meaning that for any atom in its image, there is a unique pre-image.

A proof is presented for the Kraft-McMillan Inequality Theorem, which states that a uniquely decodable encoding exists such that the length of each codeword is equal to the value of a function applied to the corresponding element in the set. The proof involves constructing a code using the inequality and showing that it is uniquely decodable by examining the prefixes of the codewords.

A full binary tree of depth Ln is constructed, where L1 is less than O2 and less than Ln. For each X1, a word corresponding to a node at depth L1 is chosen. Descendants of the node are then removed, resulting in the removal of R to the power of L and minus L1 leaves from the full binary tree. This procedure is then repeated for X2 to Xn, resulting in a uniquely decodable code.

A prefix code is a uniquely decodable code which can be constructed from a full honorary tree. This code is produced by selecting nodes at a depth of l_i for each x_i. This is possible because of an assumption that the sum of l_i is less than or equal to R to the Ln, where R is the number of leaves in the full honorary tree and Ln is the number of leaves at the next depth. This ensures that there are enough nodes left at the next depth for the procedure to continue.

In order to prevent deleting a node's parent, a unique decodable code must be used in which the length of each codeword is bounded by the number of leaves. This is done by ordering the leaves from L1 up to Ln, and ensuring that the sum of the lengths of the codewords is always less than the total number of leaves. If this condition is satisfied, then the code is guaranteed to be uniquely decodable.

A map from an integer from 1 to n to a word in tX is injective and can be proved by showing that if two words are not equal, then the extension of the map is also not equal. The length of such a word is given by m times LMax, where LMax is the largest number on the l, and ql is the number of words in the set. To check if there are enough available nodes at each step, an inequality can be used to calculate the number of nodes removed at each depth. This can be used to check if there are still nodes available at the final depth.

Junction discussed how the number of words in a codebook can be bounded by taking the nth root of the number of words in a codebook. This is done by taking the maximum length of the words in the codebook, L, and the number of symbols used, R, and calculating the number of words as R to the power of L. This number is then bounded by taking the nth root of the maximum number of words, which converges to one as n increases. This means that the number of words in the codebook must be less than or equal to one. Injectivity is used to ensure that each index provides a unique word.

Maxwell's demon is an example of how particles of gas in a box can be divided using information. A divider is created, and the box is split into two halves. The left half is then further subdivided, with one half being labelled as 0 and the other being labelled as 1. This process is repeated, with the box being split into halves at each step, until the box is divided into multiple sections. The proportions of the box are related to the numbers that are added up, with the overall volume of the box being one.

okay so today I'm going to talk about this crafted McMillan theorem which we used last in last talk to prove that Channel's Source coding Theory now I just give a recap of this notation first so at X ba finite set yeah like in lots of loss of talk the X has a distribution but now we for the four Prison face crafting McMillan Theory we don't have that at the moment I think so X is a finite set and we also take a sigma Sigma is also fine I said then definition this is a recap from last time and encoding is a map C let me call it C from X to this set of words in Sigma yeah and including is a inject is an injecting map and we also notice that given such an encoding we we know it there exists a map called the record extension of the map denoted by C Prime is is the map is the obvious map you can Define out of C from the set of words in X to this set of words in Sigma so the idea is you take a words in x the image will be a will be a words in Sigma defined by this expression so that's encoding so let's look at a a special encoding which is called foreign encoding so encoding is called uniquely decodable if it's extension is injected so this means that if you have a code word which is a which is the image of this I almost in the image of C Prime then you can determine it's pre-image uniquely let's look at one example which is called prefix code so a preface code a code encoding C for X2 Sigma star is a prefix previous prefix encoding if if the following holds so for all let me call X 1.xn so for all code words for all such words foreign C s i is not a prefix of c x j so this is saying no code words is a prefix of the other code word and we are we're seeing this is example of this uniquely decodable encoding so why why why is this it's because so to show it is let me move let me ask a bit of a silly question so yeah uh when we say an encoding I guess we mean it Maps X to non-empty words in Sigma red um but that's not stated but like C Prime well we'll have the empty string as part of its output because you can feed in the empty string and I guess the meaning of prefix with the empty string is also a little on a clear um so maybe it's by encoding we mean I guess we take as a hypothesis that c of X is non-empty red yes yes cool yeah foreign right let's see why this preface code is uniquely the decodable so if I have a previous code for x 2 Sigma star so to show it is uniquely indicatable I want to show this extension is inject map so for any atoms in image I have a unique pretty image so if I take a take

elements in the image of this C Prime so I take a code word keep using S we wanted we want to show like there is a unique we want to show that if we have a such a codeword in the image we can we can find this unique it's a pretty image is unique so by this by the definition of extension we know this this words is given by this this is actually this now let's look at each of these terms so if we just write C X1 the image of X1 to be say t one dot t l one and I use one to Index this we do this for each of these cxi say T1 t l m n n so we read this code from the beginning if if as we move on if we stop it here we'll observe this this part this part coming from a another c x j then then we know this say XJ will be a prefix for c will be a prefix for say X Y so it's a x y so this this cannot happen because our code is prefix code so so we can move until here then we can read X1 but if you what happens if we move if we move Beyond this point if we move Beyond this point if we can't determine we can decode this part to be another CX okay again then this will control the density X1 will be a prefix of cxj but our code is preface code so this cannot happen so we can so when we read this code at this stage we can surely see this coming from x y and we do the same thing for each of these terms we know this one is a unique thing sits inside the pre-image of this codeword yeah or something yeah so we can see this prefix code is a uniquely decodable code now we are able to State this craft technique theorem so they call away fixes to finite set at the beginning and let's write there are an elements in x and our elements in Sigma now consider a function on consider a function on x so that l b a function on X valued in positive integer so because X is finite this is the same as a tuple so this is the same as we have a tuple in this set now the theorem says that there exists a uniquely decodable encoding C such that each each length of this cxi is equal to l i l i I mean l applied to x i o l x i and we denote this by hello I if and only if all of our this tube of numbers satisfy this inequality so so this is say the seven and now we are going to prove it foreign thank you yeah you find it only yeah yeah I guess just okay then yeah this is the statement let's look at the proof let's do this Direction first so if we have this inequality we can construct let me put it this way we want to shoot this thing if we have this inequality then we can construct a a uniquely decodable code satisfy that property so

the the idea is that we first we construct the code then it shows it's uniquely decodable so this is the direction we want to prove so suppose we have this now let's proceed this proof so I will write the general argument on the left hand side and we will do examples simultaneous on the right hand side foreign yes so we can also assume we reorder these two posts so we can assume a y is less than O2 lesson Ln in this left hand side my example will be r equal to 2 and a equal to maybe it's not good just up so I is the size of Sigma equal to 2 and a is the size of x equal to 5. now assume we first we assume L1 less than O2 less than Ln so let's take example here say two three three three so the first step is we construct this full honorary tree so that's a be a full very true of steps Ln so in this in this case we will have a binary tray full binary tray of steps three now if we have this for Android tray of depth and we notice that every word of lens l less than Ln corresponds to a note in this graph in this trade at depths l so the depth is sort of one more one less than the number of rows right yes yes so there's that's three so I guess the the root node is the empty string is that how you think about it yes yeah yes now so yeah this is his observation now let's construct this code this encoding we have this tree now now for each step one for each foreign first so step one we take X1 for x one we Define C X1 to be a word corresponds to corresponding to a be a word corresponding to a note V1 of a at depth L1 so here we know the L1 in this example the L1 is 2. then we Define c X1 to be any nodes in the in-depth two so and in for let me just choose the first one this is the first step now the second let's move on to the second step yeah that should be a bad ride uh maybe just walk a little bit further uh yeah too far yeah you kind of want to come back come back to around here yeah yep that's it yeah okay and I'll keep my okay oh now the second step is so we already pick a words for X1 the second oh so the second step is I remove or descendants of V1 so our picture is here and we Peak we want to be this one now we remove this this subgraph so by doing this we notice that was a problem I can't even I can't erase this green thing here yeah so there's a bit of a bug let me try anyway I would just use black too right foreign by doing this we remove R to the power of L and minus L1 leaves of the full on the way tree right yeah then we repeat this procedure for X2 x n

so there is a problem that we have to we have to make sure that because at each each step we remove some descendants which means we will remove some leaves and we have to make sure the number of leaves leaves we remove is smaller than the leaves we have for this full honorary tray but this is given by our assumption note that we have this inequality maybe not that way uh after after this procedure we remove this many leaves and by our assumption we know or assumption we have this smaller than one times r l n foreign so in the end any back to this example say for each X2 I choose this because because the Tuple actually is two three three three so in the rest of the words I choose vertex um depth string so I'll just choose this this forward so in the end I get a code in this example the code is given by I take X1 goes to B1 which is 0 0 as 2 goes to V2 which is zero zero zero one zero zero one zero here and X3 goes to zero one one and X4 goes to one zero zero and x five goes to one zero one and notice in this example this code is previous pre is a prefix code so it's uniquely decodable this holds this is true in general sorry G letters results in this example in this example right so if you go in this trade if you go left you get zero and if you go right you get one one okay yeah awesome thank you yeah so this this procedure produces us a so hope can move so we obtain a prefix code which is uniquely decodable C from X to Sigma star and by our construction we know that c x i equal to l i for all I equal y to a so this gives gives us one direction of the serum okay happy with this proof wait I think I missed the inductive step there somewhere so so that sum is less than or equal to R to the Ln but this is so what uh why why why put R to the L in there oh yes this is a number of leaves we have for this this full honorary trait right right but don't I also need to know that I can she has one at the right the number of leaves at that depth but then I also need to know that when I go to the next step there's enough leaves left there's enough nodes left at the right depth for me to pick did you prove that I mean x i you choose a node at depth Li right yeah yes I mean if if all the ills are small couldn't they have run out why don't I run out yeah because we have this this assumption this assumption basically there's inequality right so yeah we have assumptions that that sum is less than equal to one we multiply our R to L and on both sides we get this inequality and this is telling

it's this is the leaves number of Leaves we removed yes and this this is the total leaves we have yeah yeah okay and our assumption guarantee that we we have enough leaves so the number of leaves that we remove is always smaller than the number of Leaves we have okay I see so the reason we order them from L1 up to Ln is that I mean you can't do this choosing deeper nodes first because you might later somehow remove its parent so you have you do those first yes and then okay and you're saying that uh yeah all right I see cool yeah yeah so yeah actually we'll present the ordering yeah make sure that yeah after we we removed the the we we first deal with the world's ways lower depths then we do this then we won't delete the they they they loads of um further divs so that won't be a problem yeah it seems quite relevant to and in total the leaves yeah the fact that you can just sum up the number you remove and that is sufficient also hinges on the order of this removal somehow right so you can't run out of nodes at depth two because if you did then there's no there's no deeper things somehow right uh wait so I'm maybe I'm still not clear on so I have a bunch of twos in a row in my list of L's [Music] um so suppose L1 L2 and L3 are all two so then I've got R to the Ln minus 2 plus r to the Ln minus 2 plus r to the Ln minus 2 and 2 is small so that's a large power of r Now isn't it yeah you say I kind of run out of those if you have three two there yeah if you have like three two there you can see that because there's more than their inverse that's R to the minus l i will be big then that bound would tell you you say in this case if you have this uh let me move to this side here if you have two here you will see this will be R minus 2 plus minus 2 plus r minus two which will be straight three and four then you can only have when these things are smaller than the number of n has to be small as well [Music] so yeah the remaining thing you can what you can do is yeah you can only have one more two otherwise otherwise it's a big set bound yeah okay foreign cool um so that's the end of the proof right well you did One Direction Let's Stay One Direction um all right let's move to the second set of boards if you're ready it's over here yeah okay foreign so the other direction is if we we have a uniquely decodable code satisfy that condition on the length of each codeword then this inequality holds so we let see be is encoding ah okay sorry interrupt but I yeah I I think I understand so this this final

inequality road is true but I feel like actually it's a special case of the check that you want to do at each step and in each step to check there's an available node at that depth you have to do the same calculation but it's sort of like the common factor is not R to the Ln so you can count at each stage how many nodes at a given depth are removed and that's a power of R and then using the same inequality you can check that there are always enough available at each step and this this is kind of like at the end also this check is a similar thing it means that kind of at the final depth there's still anything available but yeah okay I get it yeah yes yeah that's fine yeah so let's say being encoding such that this extension is injective and [Music] each cxi has the right lens now let's consider this number P now let's M yeah natural number let's consider the power of n then we can rewrite this as we just spell out this this power we have this now we claim this map the map from this by this I mean the integer from 1 to n this map given by if I take a tupo and map it to this word in t X not s X one extra is injective and this can be say can be proved in the following way suppose you're supposed to have two these two they're not equal and since this is is uniquely codeable this extension is injected implies these two words are equal and this tells you this this we also note that the less of such a word sorry what did I miss about this claim why is this not obvious or is that what you're saying yeah yeah it's obvious okay okay good that's it you're probably not say private objective but does it seem to be interactive timelines yeah it's it's obviously yeah okay that's okay cool so way awesome notes that the lens of this world will just be the sum of this number now we by change the way of counting recall we have this will equal to I equal I one equal to one hand foreign each of this power will give us a a words in t coming from a words of length m in X so we change the way of counting we know this equal to this q a l r minus l will F from 1 to we know the the Mac the maximum length of such a word will given by m times L Max where L Max is the the largest number on this l and this ql so L Max equal to this and ql is the number of words in this set by S to power m i mean all the words of length N in N in x no in x oh yes l did this step clear yep I think so [Music] yeah you probably want to stand about where I am now yeah that's good now we notice that for each l

there are at most R to the power of L Word so ql will less than R to the power of L so our this number will be bounded by this which is equal to n L Max then we take the M's root so we know p is less than equal to this and remember our n is any natural number and we also we also know this converge to one as M goes to Infinity then this tells us P has to be less than equal to one that is so for each end yeah that's yeah the movies not hard but how they start this how how to get this idea I have no clue well it has a bit of a similarity to the last part of the source coding theorem where you're talking about blocks Maybe I'm not sure if that's where the idea for taking the nth power came from um but yeah that's that's very neat hmm so where where exactly does the injectivity come in it's in the part where we yeah one way right yeah yeah for this for this this chain this right change of counting I think yeah yeah so each of these index provides you a word uniquely that's pretty satisfying low Tech but uh nice yes so that's it right yeah that's it they also there is also a proof which for this direction but for the special case when the code you have is a prefix code but I guess this General case is good enough yeah or do you want to see that special case yeah I think I think that's a good place to leave the proof I wondered if it might be useful to if you don't mind I'll just translate your example over to the board here and draw it as nested boxes because that's a also a kind of convenient way to think about so let me redraw your diagram first yep first of all thanks Junction that was a great talk yeah does anybody have questions for junction while I'm I'll just I'll just draw for a bit and then maybe make a comment but feel free to ignore me until then I think it looks really good I have a dumb question um but why is the absolute value of C Prime equal to this one will be ally along my own on the second hotspot circular sport this one right here yeah yeah yeah like because this thing is equal to this right by our definition this extension is given by this and this will just be concatenation of each of this this code word and each of these will have length l i one and when you concaten it then the lens will add add together we will add this lens together right it doesn't work yeah yeah like you have a b and you have a then a b a will have less two plus one three yeah awesome thank you all right any other questions for Junction okay well uh if not I'll try and translate this to

so maybe the uh very original way to think about the meaning of codings in the sense we've just described in connection with entropy is to go right back to Maxwell's demon right the way you're talking about particles of gas in a box and a bit of information is the knowledge of whether a given particle is on the left hand side or the right hand side of some divider right in here this is my divider so then you would read the left hand because it was a demon sorry it was a damage these examples why is it always a demon why not why not an angel well angels angels Don't cause your whole field to have a headache for a hundred years so I guess it should be a deal directions so that so this division here corresponds to either going to the left or going to the right and then we're going to further split the left hand box into another half and then so uh and then the one of them doesn't divide anymore so that's kind of let's call it zero zero right that's here here so maybe I'll draw a line and then the other one gets subdivided further in half right so maybe I'll do it the other way around so this is uh zero one zero I guess if I read it how did you read it from right to left or left to right John 10 like down the tree like zero one zero let zero one one yeah like that oh yeah yes okay yeah yeah and then I've got the one remaining one which is uh doesn't yeah I guess you're not using these so I guess it's probably not that you subdivide the right hand side at this node and that node you just do it once perhaps be like this well okay I don't actually know how to relate you kind of want to relate the volumes of these pieces to these numbers that you're adding up there should be proportions of the box right so I guess I need to divide the Box in half at every step in order for that to work out right so do you read these bottom up sorry do you read this from the node up to the stream uh I'm reading them from the top down what is your I don't know if you write it sorry that's the third one rather that should be like zero one one um it's oh zero one one yeah zero one one okay I mean we could do it either way I guess man okay so uh so one zero and then half again so this is one zero zero and one zero one yeah I realize I'm reading it in the opposite direction you would usually read a string but uh okay now what are the volumes of those boxes well if the overall so the volume of the square is one then this is 2 to the minus two this is 2 to the minus three to the minus three two to the minus three two