How to adjust Arithmetic Coding parameters in integer form?

80 Views Asked by At

Problem:

I'm using the arithmetic coding model based on this PDF paper, which is in integer form to realize an unbounded precision.

But the application has some problems: all we calculate is the probability in double form, but the api needs frequency count in integer form, so I made a compromise. I multiply the probability by a base ( near 1e9 ).

    double p = calc_prob(i, lap);
    uint64_t f = (uint64_t)( p * base);

It leads to a problem: the value of probability in double form varies, when the base is too small (e.g., 1e9), smaller values' precision gets lost, but with too big base (e.g., 1e10), the other value overflow.

Then I change the frequency count from uint32_t (4 byte) to uint64_t (8 byte), so as to prevent overflow in uint32_t, but a new problem occurred:

As the base gets bigger, every frequency count (variant f here) becomes larger, too. So the total of frequency count has exceeded the model's upper limit (maximumTotal)

    // Always equal to the sum of 'frequencies'.
    private: std::uint64_t total;
    // Maximum allowed total from a frequency table at all times during coding.
    protected: std::uint64_t maximumTotal;

The probability calculation procedure is irrelevant to this question and can't be released, so I pick up two example values causing problems:

    double pMin = 0.000000000913767;//.15lf format
    double pMax = 0.991924503052654;//.15lf format

The arithmetic coding model is extracted from github

What I've tried:

I find that the maximumTotal is influenced by numBits as following

ArithmeticCoderBase::ArithmeticCoderBase(int numBits) {
    if (numBits < 1 || numBits > 63)
        throw std::domain_error("State size out of range");
    numStateBits = numBits;
    fullRange = static_cast<decltype(fullRange)>(1) << numStateBits;
    halfRange = fullRange >> 1;  // Non-zero
    quarterRange = halfRange >> 1;  // Can be zero
    minimumRange = quarterRange + 2;  // At least 2
    maximumTotal = std::min(std::numeric_limits<decltype(fullRange)>::max() / fullRange, minimumRange);
    stateMask = fullRange - 1;
    low = 0;
    high = stateMask;
}

numBits resetting

I've tried to adjust the numBits(default 32), and the maximum becomes 1,073,741,824 as VC.One mentioned, but the maximumTotal is still far less than calculated total. From the pMax example, it itself exceeds the maximumTotal(multiplied by 1e10).

My current solution is still using base of 1e9, and assign a smallest probability interval to the coded value. Is there any elegant solution to this? Thank you a lot.

0

There are 0 best solutions below