MACM-96 : Multi-precision Arithmetic Coder Module

A Virtual Queue Based General Arithmetic Encoder

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

contact at: or

MACM related resources on this page:

MACM-96 source code

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 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
  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
   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
     There normalisation interval is (1/4,1]

Charles Bloom / cb at my domain

Send Me Email

Back to the Index

The free web counter says you are visitor number