Dealing with Underflow in Adaptive Arithmetic Coding

Question

I've been implementing the PPM compression algorithm in python and have had some difficulty dealing with underflow with the adaptive arithmetic coder (when maintaining integers L and H for a finite-precision implementation).

From research, the solution is to detect when L = 01xxxx and H = 10yyyy and then rescale to make L = 0xxxx0 and H = 1yyyy1. A counter cntr is maintained and incremented every time this occurs and if the MSBs of L and H are equal it is output (as is normal), followed by cntr 0s if the MSB was 1 or cntr 1s if the MSB was 0. Cntr is then reset to 0 and encoding continues. Here is my code for encoding and decoding.

precision = 32
a = 0
b = 2**precision - 1
cntr = 0

def arithmetic_coder(low_cum_freq, high_cum_freq):
    global a, b, cntr
    old_a = a
    ret = ""
    w = b - a + 1
    a = a + math.floor(w * low_cum_freq)
    b = old_a + math.floor(w * high_cum_freq) - 1
    a_bin = np.binary_repr(a).zfill(precision)
    b_bin = np.binary_repr(b).zfill(precision)
    if a_bin[0] == b_bin[0]:
        ret += a_bin[0]
        if cntr > 0:
            if a_bin[0] == "0":
                ret += '1' * cntr
            else:
                ret += '0' * cntr
            cntr = 0
        a_bin = a_bin[1:] + "0"
        b_bin = b_bin[1:] + "1"
    while a_bin[0] == b_bin[0]:
        ret += a_bin[0]
        a_bin = a_bin[1:] + "0"
        b_bin = b_bin[1:] + "1"
    while a_bin[0] == "0" and a_bin[1] == "1" and b_bin[0] == "1" and b_bin[1] == "0":
        a_bin = a_bin[0] + a_bin[2:] + "0"
        b_bin = b_bin[0] + b_bin[2:] + "1"
        cntr += 1
    a = int(a_bin, 2)
    b = int(b_bin, 2)
    return ret

    precision = 32

And the decoder:

a = 0
b = 2**precision - 1
decode_pos = 0

def arithmetic_decoder(frequencies):
    global a, b, decode_pos, cntr
    w = b - a + 1
    old_a = a
    frequencies = [0] + frequencies
    for i in range(1, len(frequencies)):
        frequencies[i] += frequencies[i - 1]
    index = math.floor(((int(enc[decode_pos : decode_pos + precision], 2) - a + 1) * frequencies[-1] - 1) / w)
    char = 0
    for i in range(len(frequencies)):
        if frequencies[i] > index:
            char = i - 1
            break
    a = old_a + math.floor(w*frequencies[char]/frequencies[-1])
    b = old_a + math.floor(w*frequencies[char + 1]/frequencies[-1]) - 1
    a_bin = np.binary_repr(a).zfill(precision)
    b_bin = np.binary_repr(b).zfill(precision)
    while a_bin[0] == b_bin[0]:
        a_bin = a_bin[1:] + "0"
        b_bin = b_bin[1:] + "1"
        decode_pos += 1
    a = int(a_bin, 2)
    b = int(b_bin, 2)
    return char

When I encode then decode a text file, the output of the decoder is correct up to a point (where the underflow corrector first activates) and from then on it is gibberish.

Is there something that needs to change with the decoder or am I simply not understanding underflow correction with arithmetic coding?

Thanks.

Dealing with Underflow in Adaptive Arithmetic Coding

0 Answers