MACM-96 is by Mahesh Naik , published here 6-14-96

contact at: kiran@giasbm01.vsnl.net.in or BOMAAB04@giasbm01.vsnl.net.in

MACM related resources on this page:

Mr. Naik's original source code

the original Virtual Queue Skew Coder :

VQSC source code

VQSC postscript paper

Summary of the MACM method ( with VQSC as background ) by Charles Bloom:

/** from comment in arithc.c of macm.zip source code **/ FastArith Encoding using the generalized BitQueue encoding is done in the "trivial" manner - i.e. simple arithmetic is done. No handling of underflow or overflow is needed, because we are just doing arithmetic. bits are output as they become invariant (i.e. when MSBit(reglow) == MSBit(reglow+regrange) ) however, we also write a 0 bit out when they still have a chance of becoming a 1 later (aka underflow problem) in order to handle this we keep a queue of bits between the arithcoder and the output, i.e. : arithcoder -> queue -> output thus, if the arithcoder needs to add to a bit it has already sent, this may be done in the queue the queue always has the form: 01111... , i.e. a single zero bit followed by N one bits Qlength counts the number of 1 bits plus the zero bit ( Qlength == 0 is an empty queue , Qlength == 1 is just a zero bit ) a 'carry' is handled by adding 1 to the Queue this changes 01111 to 10000 , at which time the queue may be sent It is a property of arithmetic coding that if a carry reaches a certain position, no later carry may again reach that position. It is this property which allows the Queue to be kept as such a simple form. (btw this property comes very simply from the fact that the 'range' - the number added to the coded - is constantly being shrunk (in our minds, anyway). For the same bit to be reached again, we must add a range of the same value, but since the range is smaller, this cannot happen) note that the decoder is trivially simple, because the bits sent by the queue are identical to those that would have been sent had infinite precision coding been used. note also that it is possible to have a queue of the form 1111 , (i.e. no leading zero) but we need not keep this data in the queue, because no carry-over will ever touch it. Thus, any 1 bits sent to an empty queue may be flushed immediately. (an empty queue is only created by a carry-over, so any 1 bits added to that queue cannot receive a carry because then that carry would be propagated through to a point which had already received a carry). thus we need not track "QueueZeroFlag" as was originally suggested in my VirtualQueue-SkewCoder paper

Notes sent to me by the auther (Mahesh Naik) in email :

=================================================== ARITHMETIC CODING using the coding interval (1/2,1] =================================================== We always work with the full Coding Interval indicated by two of the three values High,Low & CodeRange == ( High-Low+1) where High and Low are ever increasing length bit strings. At each encoding step the CodeRange can be partitioned into 3 regions S,Q & W. The S region is the prefix of High and Low consisting of bits which are identical in both the S region is followed by the Q region which has a very special pattern in the Q region of High we have the bit pattern 10000...(i.e 1 followed by 0 or more 0's), in the Q region of Low we have the bit pattern 01111...(i.e. 0 followed by 0 or more 1's.) The bits in the Q region of Low are complement of the bits in the corresponding region of High. The Q region may be empty. The length pf this Q region is the QueueLength The Q region is followed by the region W which is of length P,(P for Precision) CodeRange = High-Low+1 = Ql*(2^P) + HighW-LowW where Ql is 1 if the region is present and 0 otherwise HighW is the W region of High LowW is the W region of Low It is the mangement of the Q region in a neat way that is the core of all variants of the arithmetic coding. The decoder and the encoder are in synchronisation about this region partition. Carry Propogation and Queue Reduction: ======================================== When a carry occurs Lowq is changed to Highq i.e the Q region is reduced to 1000.. in both Low and High when a borrow occurs Highq is changed to Lowq i.e the Q region is reduced to 0111.. in both Low and High since the bit patterns are same in Low in High after this reduction the Q region becomes part of the S region. Carry can be detected be different methods. In the version used in this program a bit has been reserved for this purpose. Alternately if the bit is too precious another dirty method can be used based on the identity that if a+b generates a carry and the hardware truncates on overflow the the result c=a+b is < both a and b. The second method is very easy to use in assembly language implementations ass most current logic units report it anyway. Range Normalisation: ==================== the CodeRange can be always doubled by appending a 1 bit to High and 0 bit to Low This process can be carried out as long as CodeRange <= (2^P) as bits shifted into the Q region from the W region must have the special pattern illustrated above. It is not necessary to always normalise. In fact the IBM literature does normalisation only if CodeRange < ( 2^P) CWR (CACM!) does normalisation only if after normalisastion the most significant bit of HIGHW is 0 of LOWW is 1 . ( They used some tricky identities to do arithmetic, by complementing the leading bit ( in both HIGHW and LOWW) before further arithmetic ... ..more of it in another article .... !) Their bits_to_follow is our QueueLength Because they don't always normalise their interval is (1/4,1] after normalisation There normalisation interval is (1/4,1]

Charles Bloom / cb at my domain

Send Me Email

The free web counter says you are visitor number