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

Question

给定两个设备之间的时钟控制的三级(-1,0,+1)信道，如何以最高效的方式将比特流转换为通道表示并从中转换？目前的方法是将3个二进制位转换为两个三进制数。我认为这浪费了11%的通道能力(因为9种可能性中有1种从未使用过)。我怀疑分组可能会减少这种浪费，但这个项目使用的是8位设备，所以我的分组大小受到限制。我想使用divmod-3，但我没有在任何一个点上拥有整个二进制流。是否有一种可以从LSB开始的“增量”divmod3方法？作为一个未经训练的猜测，我推测应该有一种“分析下一个3位，去掉一个位，改变一个位”的方法——但我还没有找到可行的方法。

- frLich

---

我的组大小受限制是什么意思？ - lijie

似乎将数据分组成越来越大的块（例如，64位分成40个三进制数）可以节省效率，但这些操作会很昂贵。 - frLich

Answer 1

尝试将11位（2048个代码）打包到7个trit（2187个代码）中，你将得到不到1％的开销。有几种方法。第一种是直接的查找表。第二种是divmod-3。第三种是像下面这样的一些位/ trit操作。

第一阶段：使用3位到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% 的开销），但似乎有点超支。

- Vovanium

---

哇，这看起来非常棒 - 你能指出一些关于这种方法背后的原因吗？此外，看起来我可以重新排序一下，以便更早地发送“ZZ”而不是“mn”。 - frLich

这似乎是一种经验主义方法。我看到了 IEEE 十进制浮点数的制作方式，从中推出了一些东西。我的“算法”是：确保目标代码空间足够大；为尽可能大的码空间子集建立映射；为剩余代码做同样的事情。我不知道背后有什么高深的数学知识... - Vovanium

当前的方法会在结果中引入偏差；包含 Z 的三进制数比其他数更不可能出现，因为相比之下，包含 Z 符号的编码更大部分都未被使用。您是否有关于如何编码三进制数以保持随机分布的想法？ - Joost

Answer 2

你能从http://en.wikipedia.org/wiki/Arithmetic_coding中借鉴一些思路吗？

- mcdowella

---

三个符号概率为1/3的例子看起来很有趣。是否有任何适用于固定概率的快捷方式 - 算术编码似乎具有较高的符号成本。 - frLich

你最终是否使用算术编码来攻击它了？我正在处理类似的情况（比特流到三元组流），并且正在调查它是否可以有效地应用。 - Joost