整数算术编码与延迟位

E1与E2在两端的最高位相同时送出这个确定的位。E3处理两端分跨1/2、却都落在中间一半的情况。例如8位区间 $[85,140]$ 不能送出共同最高位，但可以把中间范围放大为 $[42,153]$。这时保留的是一次“将来要补一个相反位”的义务。

为什么补相反位？归一化实数映射E3是 $x\mapsto 2x-1/2$。若放大后的未来前缀从0开始，原来跨中点的区间应输出 01…；若从1开始，原来应输出 10…。连续E3把这一义务叠加；后来的E1/E2一旦决定主位，就能一次发出所有反位。这里的underflow是区间挤在中点附近，和浮点数小到变零是不同机制。

仍用 $A:3,B:2,EOF:1$、$w=8$。编码前 $Q=64,M=128$。ABABA EOF每步的“缩后区间 → 操作 → 归一化后区间；累计输出”如下：

• A：$[0,127]\to E1\to [0,255]$；0
• B：$[128,212]\to E2\to [0,169]$；01
• A：$[0,84]\to E1\to [0,169]$；010
• B：$[85,140]\to E3\to [42,153]$，$u=1$；仍是 010
• A：$[42,97]\to E1\to [84,195]$，发0及一个反位1；01001
• EOF：$[177,195]\to E2,E3,E3\to [8,159]$，$u=2$；010011

flush把 $u$ 变成3，因为 $L=8<64$，追加 0111，得到 0100110111。再接8个零guard、6个字节填充零，负载字节为十六进制 4d c0 00。不要把全部24个位都当成算术有效码字：有效码10位，guard8位，字节填充6位。

译码初始取 01001101，故 $V=77$。逐步在各次缩区间前得到 $(L,H,V)$：$(0,255,77)$、$(0,255,155)$、$(0,169,55)$、$(0,169,110)$、$(42,153,92)$、$(84,195,184)$，反算符号为A、B、A、B、A、EOF。第一个scaled值是 $\lfloor (78\cdot 6-1)/256\rfloor =1$，落在A的 $[0,3)$。译到EOF共读取13位，其中3位来自显式guard。

可译性与频数界 ​

归一化停止时 $L<M\le H$，并且不同时满足 $L\ge Q,H<3Q$。于是范围 $R>Q$。频数界 $F\le Q-1$ 保证每个正频数符号的整数子区间至少含一个点。相邻子区间共享相邻整数边界，既无空洞也不重叠。

译码scaled公式恰好反解“$V$ 属于哪一个整数子区间”；其中的 $+1$ 和 $-1$ 来自闭区间，不能换成直觉上的 $\lfloor (V-L)F/R\rfloor$。各次归一化同时仿射变换 $L,H,V$，并把下一位移入，因此保持同一前缀的编码与解码状态对应。EOF归一化停止后，若 $L<Q$，当前区间包含 $[Q,M-1]$，本地前缀 01 及后续零可落入其中；否则必有 $H\ge 3Q$，区间包含 $[M,3Q-1]$，本地前缀 10 可用。flush把此前延迟反位一起兑现，正好选定对应前缀。

若编码全程归一化总次数为 $r$，每轮保持“已发位数 $+u=r$”；flush再加入两位，故有效码长为 $r+2$。译码遇EOF前至多读 $w+r$ 位，所以最多越过有效码尾 $w-2$ 位，显式 $w$ 个零guard足够。严格物理guard是本教学格式的选择，不等同原论文位I/O中容许读取文件外尾位的做法。对固定 $w$，每个符号的归一化次数有界于 $O(w)$。

完整帧还检查声明的原字节数、有效位数和零guard。教学解码器额外重编码已恢复的文本，要求有效位与规定flush完全一致，以拒绝另一种结束写法或被改短的有效位声明；这增加一遍编码工作，却不是密码学完整性验证。有限文件里的bit翻转仍可能把一个合法文件变成另一合法文件。

同样约束寄存器大小的rANS理路rANS的有限整数状态与逆序归一化rANS · Range asymmetric numeral coding · 范围非对称数系编码从商余互逆证明rANS，把逆序编码、有限窗口、位数栈与显式长度封装成可严格读回的文件。改用单一整数状态和位数栈：它逆序编码、编码前提取位数，译码后补入；本页则前向缩区间并处理E1/E2/E3。两种有限实现各有自己的归一化逆关系和结束协议，不能把本页的EOF、guard或flush直接套到rANS。