algorithm - 将流式数据转换为三元(base-3)

Question

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

目前的方法是取 3 个二进制位，然后转换成两个 trits。我相信这会浪费 11% 的信道容量(因为 9 对中有 1 对从未使用过)。我怀疑分组可能会减少这种浪费，但这个项目使用的是 8 位设备，所以我的组大小受到限制。

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

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

Answer 1

尝试将 11 位(2048 个代码)打包成 7 个 trits(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 个 trits 和 2 位打包成 7 个 trits:

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 -> 11t(~0.1% 开销)，84b -> 53t(~0,0035% 开销)，但似乎超调了。