(IC 5.13) Finite-precision arithmetic coding - Encoder

in the previous video we set everything up for the finite Precision version of the arithmetic coding algorithm and in this video we're going to write down the encoder now fortunately we've done all of the hard work for the finite Precision encoder when we modified the infinite Precision encoder to integrate those rescaling operations into the process of finding the interval from A to B so the finite Precision encoder is going to look very similar to that modified INF Precision encoder except there will be some additional modifications to account for the fact that we're going to be using integers instead of real numbers so here we go the finite Precision encoder and it takes as input of course the sequence to be encoded X1 up to XK terminated by the end of file symbol zero and we're also going to take in as before these C and D vectors to determine the probabilities you could also take in P but let's take in the C's and D's since they're already in or you could take in R but let's just take in C and D like before and let's also take in this capital r you could determine that from C but let's go ahead and make that an input argument and now as before in the infinite Precision case we have some the same sort of initializations a is initialized to zero and B is now initialized instead of to one we initialize it to whole so whole is playing the role of the number one and everything just to I'm going to say this over and over probably we're doing everything in integers so B is whole and we also like before we initialize this counter this s counter for the number of middle splits that we're going to do all right and now similarly to before we're going to have this for loop as I goes from one up to k + 1 we're going to Loop over the input symbols and in each iteration of this for Loop we'll do something very similar to before we will set W to be the difference of b and a and whoops keep a there now and we're going to update A and B just as before except that so it's going to be I'll write it this way a plus round w dxi ided r so let me write the Second Step here the a update and then I'll explain what I mean by this notation here round W cxi / R now remember that in the infinite Precision algorithm we at this step we had B became a plus uh what was it d w dxi and a became a + W cxi but now remember that D is the unnormalized version D the D's and C's are defined in terms of R and we have to divide by this capital r which is the sum of all the RS in order to get the same thing as before and it in order to get the probabilities so that's what the division by R is doing and what do I mean by this round thing here what's going on with this so let me explain what I mean here so we're doing everything in integer let me write that down that is that's important so everything in everything is in integers so at no point in this algorithm are we going to have anything represented as a floating Point number so what do I mean by this operation right here so let me explain this so in this expression so look at just inside this inside the parenthesis here W dxi divided R these are all integers W is an integer it's the difference of these two integers a and b are always going to be integers dxi is an integer because it's the sum of these you know some C's and R RS are all the RS are all integers remember RS are all integ integers and this capital r is also an integer because it's the sum of all the little RS so but when we divide by capital r this as a mathematical expression this is not necessarily an integer but we want to keep everything in integer so what I mean by this round this thing here is some language specific operation so this is a language specific it's going to depend on whatever language programming

language you have happen to be using and this is meant what I mean by this is choose the integer that is as close as possible to this mathematical quantity so you know mathematically speaking that's you know you take this and then you round it but you might not actually uh execute this operation you're not actually going to execute this operation inside the parentheses when you do this because that would be you know not necessarily an integer and everything is in integers remember so for example let me just give you how I did it I implemented this in Python and in Python if you have integers if W dxi and R are integers and you do this operation right here asteris asterisk is multiply then this in indeed returns an integer and what it does is it Returns the largest integer that's less than or equal to this quantity in other words it rounds down so you know when I put round here you don't actually have to get exactly the closest integer maybe you round up maybe you round down but you want to closely approximate this mathematical quantity which is not necessarily an integer so and I think uh C works the same way in this way so in another language I don't know you might have to use something like division with remainder in order to get that integer something like that but you don't you're not going to use uh floating point so not floating point it might work with floating point but it's best to do everything in integers so you can control exactly the rounding that's occurring okay so that's that and now so now we continue and we have as in our modified version of the algorithm we have the following Loops so while B is less than half or a is greater than half we're going to do the following one of the following two things and note here instead of 1/2 instead of 0 five I'm using our predefined half quantity which is some large integer so if we're in the first case b less than half which we've called case Zero then we'll do the following emit 0 one a bunch of ones we're going to Emit s1's and do the rescaling operations set a equal to 2 * a actually let me put that on the next line let me make it a little more space here s is going to be reset to zero a 2 Aus half and B B minus oops that's not what I wanted to say that's the next line Sorry a is two actually I could just go ahead and that's small enough let me just put it up here so a becomes 2 A and B becomes 2 b all right otherwise if a is greater than half we're in this case which we've called case one then we'll do the following we do the symmetric thing emit one and a bunch of zeros and we will emit s Zer reset s to zero and now let me put it down here because it's going to be a little longer a becomes 2 A minus half we subtracting half instead of 0. five this time and B becomes 2 B minus half that's supposed to say s oops s Zer make that a little more clear s Zer so this is exactly the same as before except that we're doing everything in integers so we use half instead of2 and now we have the other loop of this sort so now we have this other while loop so while a is so now we're in case s the middle sort of thing while a is greater than quarter and B is less than three quarters or I'll just put 3times quarter then we increment s so this is just like

before increment s and a becomes that's an A becomes 2 A minus quarter remember quarter is whole divided by 4 B is 2 B minus quarter so this is just like before except that we're using our integer uh value quantities instead of our real valued quantities and let me indicate the nesting structure just to be clear I'm using sort of once again I'm using python sort of notation so this if else if a is greater than half then do all of these things here this while loop contains this stuff and the four Loop the for Loop contains all of this and that is the end of that for Loop just like before in our modified infinite Precision algorithm and now once again just like in our modified infinite Precision algorithm we increment S one more time and we have our our final sequence that we emit so if a is less or equal to quarter then we're in the sort of this the sort of Q case that we called it way back when and we emit zero and a bunch of ones and the number of ones we emit is s otherwise we're in the 3 Q case the 34 the third quarter case so we emit one and a bunch of zeros in particular s zeros zeros and then we are done that's it so the output of the algorithm is the sequence that the sequence of zeros and ones that was emitted so let me just I'll denote that by beta 1 up to Beta M it's the sequence binary sequence I binary sequence emitted during the operation of the algorithm all right so this is all just exactly the same as our modified infinite precision algorithm where we integrated these while Loops here we integrated these rescaling operations into the process of narrowing down A and B and by doing that by doing this by integrating these in here this is the key to making the finite Precision algorithm work so we saw before that these operations guaranteed that this quantity this W here the difference between b and a was guaranteed to be at least quarter it was one quarter before and now it's going to be at least quarter which is fantastic because that allows us to know that we're not going to lose Precision so when this is big enough then these quantities here this rounding off operation that occurs is going to be at a good it's going to be a good approximation and that's what we want it to be as good in approximation as possible in order to get good compression performance the worse the this rounding is the worse our compression performance is and in fact and of course you know in order for the finite Precision algorithm to work at all this rescaling is absolutely critical because otherwise eventually A and B are going to be the same so thanks to our hard work of you know modifying the infinite Precision version of the algorithm to integrate these rescaling operations we were able to just basically with very minor modifications to handle this integer valued representation with very minor modifications obtain our finite Precision encoder and one thing to note here that perhaps I should point out is that the final A and B that you get it should be clear that they're not going to be the same as in the infinite Precision algorithm I mean of course well we're doing using integers so that's different but even if you were to rescale back down they're going to be different because we're rounding things off and so you'll have some degradation of your compression performance depending on how good that rounding is you know because the compression performance depended on the final U the width of the final interval being equal to the product of the probabilities you know px1 px2 up to pxk time p 0 and it's not going to be exactly that anymore so there will be a slight

degradation of compression performance but as you can imagine I mean if you have a pretty good level of precision I mean if you know whatever um if whole is a pretty big number if the if Precision the number of bits you're using is pretty large then you're going to be able to approximate P very well in this way with these RIS divided by R and so this and this rounding that occurs since the difference between b and a this W is always going to be at least quarter this rounding is not going to be very significant so you'll still you're still um going to get very good compression performance it it's a you know you suffer on the order of you know a few bits or tens of bits or this order of magnitude of degradation of compression performance when you're using a reasonable amount of um of precision I mean of course that I'm just saying that to give you rough order of magnitude it all depends on how large the file that your encoding is and and how you know maybe some of the PS are very small and so it's hard to approximate them it all depends on all these things but just to give you a rough order of magnitude it it's pretty good the approximation is pretty good all right so that's the finite Precision encoder and next we'll look at the finite Precision decoder we'll write down the algorithm for that and as you can imagine we're going to have to make some pretty significant modifications to our infinite Precision decoder because we need to integrate these rescaling operations into it you know uh as you might imagine this rounding it's going to play um it's going to affect how we need to do the decoding and what a key part of the decoder is doing these rescaling operations at exactly the same points in the decoding process as when they were done during the encoding process so that whatever rounding occurs is done in exactly the same way and that is crucial I can't stress that enough it's crucial that these be done at exactly the same points and the rounding be done in exactly the same way so for that reason that the decoder is quite subtle it is tricky to get your decoder to work but we are going to look at in the next video how to handle