将流数据转换为三进制（base-3）

Question

给定两个设备之间的时钟 3 级 (-1,0,+1) 通道，将比特流与通道表示形式相互转换的最高效的流方式是什么？

当前的方法是取3个二进制位，并转换成两个trit。我相信这浪费了 11% 的通道能力（因为 9 个可能的对中的 1 个从未被使用过）。我怀疑分组可能会减少这种浪费，但该项目使用 8 位设备，因此我的组大小受到限制。

我想使用 divmod-3，但我在任何时候都没有可用的整个二进制流。是否有一种可以从 LSB 开始的“增量”divmod3 方法？

作为未经训练的猜测，我推测应该有一种“分析接下来的 3 位，删除一位，更改一位”形式的方法 - 但我还没有找到可行的方法。

Answer 1

尝试将 11 位（2048 个代码）打包成 7 个 trit（2187 个代码），您将获得不到 1% 的开销。有几种方法。第一个很简单：查找表。第二个是divmod-3。第三是一些位/三点主运算，如下所示。

第一阶段：使用 3-bit-to-2-trit 方案打包前 9 位：

abc def ghi jk => mn pq rs jk (mn, pq, rs are trit pairs)

bits   trits
0ab -> ab
10a -> Za
11a -> aZ (i'll use Z is for -1 for compactness)

状态 ZZ 将进一步使用

第二阶段：使用更复杂的逻辑将 6 个 trit 和 2 位打包为 7 个 trit：

mn pq rs 0k -> mn pq rs k
mn pq rs 10 -> mn pq rs Z
mn pq rZ 11 -> mn pq ZZ r
mn pq r0 11 -> mn ZZ pq r
mn pq r1 11 -> ZZ mn pq r

未使用的代码将是：

ZZ ZZ xx x
ZZ xx ZZ x
xx ZZ ZZ x

UPD另一种合适的包装关系是19b->19b-> 11t（~0.1% 开销），84b -> 53t（~0,0035% 开销），但似乎超出了。

Answer 2

你能从http://en.wikipedia.org/wiki/Arithmetic_coding中摘取一些想法吗？