Ideal-real arithmetic interval coding for a fixed block

Fix a finite full-support source $p=(p_1,\dots ,p_m)$, its symbol order $1<\cdots <m$, and a public block length $n\ge 1$. The ideal-real arithmetic interval of the empty prefix is $[0,1)$. If a prefix has interval $[a,b)$ and the next symbol is $i$, assign the extended prefix the half-open subinterval $[a+(b-a){\sum }_{j<i}{p}_j,a+(b-a){\sum }_{j\le i}{p}_j)\mathrm{.}$ This subdivision is performed exactly over the real numbers.

Each subdivision multiplies the interval width by the positive probability of the next symbol. Thus a completed block $x^n$ has width $w={\prod }_{t=1}^n{p}_{x_t}=p^n(x^n)\in (0,1]$.

Use the base-two logarithm convention of Information units and logarithm-base convention. Its positive denominator and the strict increase of $\ln$ from Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm make ${\log }_2$ strictly increasing; Change of base and inversion of the positive-base real exponential gives ${\log }_2(2^u)=u$ and $2^{{\log }_{2}x}=x$. Every floor is the integer part specified by Integer part: for every real $x$ there is exactly one integer $m$ with $m\le x<m+1$.

For a completed block $x^n$, let $I(x^n)=[a,b)$ be its resulting interval, put $w=b-a$, and define $r=\lfloor -{\log }_{2}w\rfloor ,s=r+2,k=\lfloor 2^s\frac{a+b}{2}\rfloor \mathrm{.}$ The dyadic cell represented by an $s$-bit index $k$ is $J_{s,k}:=[k{2}^{-s},(k+1)2^{-s})$. The ideal-real codeword is the $s$-bit binary representation of $k$, with leading zeros. Each encoding frame contains exactly one length-$n$ source block; the decoder knows $p$ and $n$. A stream uses an externally known number of such frames. No finite-register or finite-precision implementation is specified by this definition.

Since $0<w\le 1$, the logarithm conventions above give $r\ge 0$ and hence $s\ge 2$. The interval midpoint lies in $[0,1)$, so the integer-part property gives $0\le k<2^s$; the stated $s$-bit representation therefore exists.