(IC 5.12) Finite-precision arithmetic coding - Setup

earlier we wrote down the infinite precision version of the arithmetic coding algorithm and while that was useful for building our conceptual understanding and proving certain theoretical results we're never going to actually be able to implement the infinite precision algorithm because of course we're always only going to have some finite level of precision to compute with fortunately you can implement arithmetic coding with a finite level of precision and still get very good compression performance so in this video we're going to start setting things up to describe the finite precision version of the algorithm and in the next couple of videos we'll actually write down the algorithm now one last comment i'd like to make is that normally i think it's best to work out the details of an algorithm on your own but in this case for arithmetic coding for the finite precision algorithm there are some very subtle numerical issues that pop up that have to be dealt with and it's not at all obvious even when you have a conceptual understanding of a solid conceptual understanding of how to deal with those issues so i think it's an essential part of describing the algorithm or describing arithmetic coding to go through a detailed explanation of the algorithm itself all right so let's get started so here we go we're going to first define certain quantities and let's define precision so we're going to find some constants so let's call precision the number of bits that we will use to represent numbers number of bits i'll say number of bits of okay number of bits to use to represent numbers so for example eg you know you might use sometimes people use 16. my implementation uses 32 or i've played around with different you know up to 100 even in it depends on the language that you're using so if you're you need to choose this to be large enough so that you can represent things at a good level of precision to get good compression performance and make things work but it can't be so large that you can't represent um numbers that are they're actually going to be like two to something a little bit larger than this okay so we define precision to be that and we'll define certain quantities let me define whole to be 2 to the precision and let's define half of course to be whole divided by number of two divided by two or in other words two to the precision minus one that's a two and then let's define quarter is going to be whole divided by four of course so these are going to play the role of whole is number one and we're going to use we're going to be using integers instead of real numbers so hold's going to be playing the role of number of the number one half will be playing the role of 0. 5 and quarter one quarter or you know 0. 25 so the first thing to point out is that rather than using something like floating point numbers or something like that we're going to do everything in integers and that way we'll be able to handle any rounding off that occurs explicitly so we know exactly what's going on all right and now like similar to before let's go ahead and write down let's let x be our source alphabet it's going to be some finite set we'll label it 0 to n as usual and we'll designate our end of file symbol to be 0 and we will similarly just like before we're going to have some probability mass function p on this set p0 up to pn be a pmf on x and now i'm going to put an additional requirement on p so we're going to require that the numbers p i can be represented as rationals ri over r where ri is going to be each some integer and capital r is going to be the sum of the ris i from 0 up to n now your p your given p whatever it is it might not be able to be represented as rationals but if not just round it off so that you can represent it this way so i'm going to assume that you have already rounded it off and approximated p in that way now this r along with whole is going to determine the level of precision that

you need to be able to represent in your language so you need i'll put a note up here so when you implement this you need to be able to represent integers from zero up to r times whole so this is going to restrict how large you can make precision it's going to depend on you know whatever language you're using and when i say represent r times whole i mean all of the without any rounding off you know not like approximating it you know i think represent that you know integers from zero to this number exactly certain languages allow for arbitrary arbitrarily large integers but some but many don't so you just be aware of that okay and now we need something we need a sequence to compress so let x1 up to xk be some sequence of source symbols that are non-zero and let's let xk plus one be zero so this will be some sequence that's valid with respect to our end of file condition and then and then finally we're going to define certain c and d quantities just very similar to before except now we're going to use integers instead of the real and we're going to use the r's instead of the p's to define this c and d vectors so c j will be the sum of the r's up to r j minus one note the j minus one and this is for j equals for j going from one up to n and we will similarly define d j to be cj plus rj this time not pj for all the j's from zero up to n so again like before note this is j minus 1 not j minus 1. so if you were to divide these c's and d's by capital r then you would get the same c's and d's that we had before we these were these were written in terms of p instead of r okay so i think we're all set now this is so now we have all of everything set up pre-defined and we're all ready to write down the encoder