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
The free web counter
says you are visitor number