QM coding implementation in Python - is 16 bit word obligatory?

Question

I am trying to implement QM coding for educational purposes. My main resource is chapter 5.11 from Handbook of Data Compression, 5th edition. This is my rough implementation of encoder for now:

def _encode_bit(self, bit):
    if bit == self._lps:
        self._code_lps()
    else:
        self._code_mps()

def _code_mps(self):
    self._a = self._a - self._q_e()
    if self._a < 0x8000:
        self._switch_intervals_if_needed()
        self._renormalize()
        self._p_table.next_mps()

def _code_lps(self):
    self._c = self._c + self._a - self._q_e()
    self._a = self._q_e()
    self._switch_intervals_if_needed()
    self._renormalize()
    self._p_table.next_lps()

def _renormalize(self):
    while self._a < 0x8000:
        #C < 0,5 (0xFFFF / 3)
        if self._c < 0x5555:
            b = 0
            d = 0
        else:
            b = 1
            d = 0x5555
        self._write_bit(b)
        logger.debug("Written '%i' to output", b)
        #C = 2 * (C - D)
        self._c = (self._c - d) << 1
        #A = 2 * A
        self._a <<= 1

I am mapping the interval to integers, since it should be more efficient as I understand. In the book, there is mentioned, that 16 bit word is used for mapping, but since I am doing this in Python I am not sure whether not enforce the 16 bit length of all variables. The problem is that when I run my encoder, the C (self._c in code), which should point to the bottom of MPS interval if I understand it correctly overflows over 16 bit length very quickly, and its value becomes very large. Because of this, the encoded bits is mostly just a string of LPS symbols. Should I enforce the variable length somehow? Or is there other problem in my code? I have spent several days on it already trying to figure out what went wrong...

Answer 1

In any form of arithmetic compression (like QM), one needs to stay within the maximum allowed bits (16 in this case), otherwise you will have all kinds of problems. These problems include roundoff errors because in theory you may need infinite precision. The algorithm itself will round off when necessary and perform a renormalization to maximize use of the bit range. The answer to your question is "Yes".