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

Question

给定两个设备之间的时钟 3 级 (-1,0,+1) 通道，将位流转换为通道表示和从通道表示转换为流最有效的方法是什么？

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

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

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

score 2 · Accepted Answer

尝试将 11 位（2048 个代码）打包成 7 个三元组（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 个 bit 打包成 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 -> 11t（~0.1% 开销），84b -> 53t（~0,0035% 开销），但似乎是过冲。

score 1 · Accepted Answer

1

于 2010-12-17T05:35:47.943 回答

2 回答 2