(1)
Speciﬁcally, the algorithm updates [a, b) to the following: [a + (b−a)·li(xi), a + (b−a)·hi(xi)),
which is a sub-interval of [a, b). Finally, AC picks a number within the ﬁnal interval that has the
shortest binary representation. This number is encoded as a bitstream representing the codeword of x.
Upon decoding, the symbols {xi}D
i=1 are decoded sequentially: at iteration i, we decode variable
Xi by looking up its value x such that its cumulative probability (i.e., li(x)) matches the subinterval
speciﬁed by the codeword and x1, . . . , xi−1 (Rissanen, 1976); the decoded symbol xi is then used
to compute the following conditional probabilities (i.e., lj(x) for j > i). Despite implementation
differences, computing the cumulative probabilities li(x) and hi(x) are required for many other
streaming codes (e.g., rANS). Therefore, for most streaming codes, the main computation cost of
both the encoding and decoding process comes from calculating li(x) and hi(x).
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS