Camera-Drop 冗余设计新方案

旧方案

Camera-Drop 最开始所采用的冗余编码方案被淘汰掉了。

• 旧的方案是：一帧图像里有很多 RS 块，如果一个块坏了，全部的块都要丢掉。

原来的想法

“如果把校验放到 RS 块里，就能定位出错误块的位置，这样就只需丢这一块，而不必丢掉整个包。这样做看似丢的东西减少了，但我们的传输模型需要改变（图片不再是个包，而是若干包），会增加冗余比例且实现并不容易，故丢掉整个包应是更好的选择。”

除了上面这段话外，当时的我还这么想：RS 码只负责块级纠错，应对误码；Fountain 码只负责包级纠错，应对丢包。如果 RS 码纠不回来，就说明图片太糊了嘛，当成丢包处理也无可厚非。我过于乐观，低估了信道的复杂性。实际测试下来，一整张图片中，有某个 RS 块无法纠错的概率并不低，因为这个块导致整个图片的信息要全部丢失，显然是无法接受的。不如说，这种设计纯粹是在人为增加丢包率。

因此，需要设计一套高效、稳健的新方案。

新方案

旧方案的失败给了我一个教训：在这种复杂的实际问题中，“俺寻思之力”是不可靠的。我们需要真实的建模与准确的推导。

首先，块级的纠错肯定还是要仰仗 Reed-Solomon 编码，“拖后腿” 的 Fountain 码是否还需要保留？或者说，通过“浪费”几万个字节、且多发~% 的包，只是为了求“稳一点”，是否值得？虽然这个冗余比例看起来有点大，但如果反过来想：假设没有 Fountain 码，那只要某个 RS 块坏了，我们就无法解出原文件。尽管课程项目并没有要求我们要做到零误码率，但这与我们一开始的目标背道而驰。想让全部的 RS 块都不会坏，是不太现实的，故使用 Fountain 码来兜底是有必要的。

因此，我决定继续使用 Reed-Solomon + Fountain 码。

建模

• 设字节正确率（acc）为定值，也就是误码率。
• 设最大文件大小为。
• 设 RS 块大小为，块内有效数据大小为，则校验大小，能纠正的错误数。
• 设一个喷泉码包含个 RS 块，喷泉码的冗余系数为。

目标：在误码率不超过的前提下，最大化“有效传输率”。

---

确定 RS 码的参数,

先求 RS 块的“存活率”，显然服从二项分布：

二项分布不容易处理，想到用正态分布近似：

根据法则，为了让达到极高，我们要覆盖加上个标准差的范围，即：

取。

RS 校验位，有效数据大小。

记得判一下是不是正的，如果非正，说明太大了，这种信道环境是传不了数据的。

---

确定喷泉码冗余系数

一个喷泉块由个 RS 块组成，必须全活才算合法块。设全活的概率为，它和一样服从二项分布的累计分布函数（CDF）：

因为不大，所以可以考虑展开算。为了防止乘法溢出，对这个和式取一下对数，而 cmath 库已经提供了对数伽马函数 std::lgamma，求和后最后再取个 std::exp 就能得到了。

考虑到喷泉码有% 的解码开销，最终取。

这个数大概在左右。

实际上，如果文件大小很大，这个比例是可以往小了调的，但为了求稳，还是先设为吧。

---

确定每个喷泉码块含有的 RS 块数

这个不能随便取。

wirehair.h 库要求喷泉码块数满足：，故会有一个下限。

先把下限求出来。

然后，为了不浪费图像空间，最好是图像可编码字节数的约数。枚举，求出让 浪费的字节数 最小的即可。

注

越大，越小，即越大；与此同时 Fountain 块数越少，用到的 Fountain 元信息和 CRC32 校验码就越少。这二者的权衡似乎不易考虑，那我就直接不考虑。

要在求之前先确定（废话）。

---

求有效传输率

以下参数已知：

• 误码率。
• RS 块大小。
• 用于校验的字节数。
• RS 码的传输效率。
• 喷泉码有个字节的头部，个字节的校验码，共“浪费”个字节。
• 喷泉码传输效率。

综上：

这个式子几乎没有参考价值，推着好看而已。

看这张表直观感受一下（在单帧编码字节数为的情况下所求）：

acc	RS(N, K, P)	M	R	Effective Data
90.00%	RS(186, 122, 64)	50	1.096	6086	65.44%
91.00%	RS(186, 128, 58)	50	1.120	6386	68.67%
92.00%	RS(186, 132, 54)	25	1.074	6572	70.67%
93.00%	RS(186, 138, 48)	25	1.086	6872	73.89%
94.00%	RS(186, 142, 44)	25	1.072	7072	76.04%
95.00%	RS(186, 148, 38)	25	1.080	7372	79.27%
96.00%	RS(186, 154, 32)	25	1.088	7672	82.49%
97.00%	RS(186, 160, 26)	25	1.093	7972	85.72%
98.00%	RS(186, 166, 20)	25	1.088	8272	88.95%
99.00%	RS(186, 174, 12)	25	1.129	8672	93.25%
99.90%	RS(186, 182, 4)	25	1.074	9072	97.55%

---

交织编码（Interleaving）

值得指出的是，上述推导的假设都是背景白噪声，即随机独立错误。但实际中并非如此，拍照所导致的错误往往是有聚集性（Burst Error）的。为了让这些聚集性错误在解码层“分散开”，在把数据写入图像前，要先做交织编码。

我懒得去设计什么矩阵交错、矩阵转置，直接固定一个随机数种子，生成一个随机排列，和原数据的索引做个一一映射，搞定。这样不仅简单，而且能保证很强的随机性。

---

结论

相比开坑时的模糊想法，现在我给出了一个更具体、更准确的编码方案。尽管其稳定性有待实测检验，其参数设置可能并非最优，但有了这个模型后，我们仅需提前测出图像识别模块的准确率，就能用它自动配置各种参数，并马上得知传输效率的上限。这毫无疑问是个显著的进步。此外，从这个表格中可以看出，我们的传输效率是非常乐观的。在误码率不超过% 的条件下，能做到bytes/frame 的传输效率。后续如果扩大编码图像的长、宽，这个数字还能再提升，达到KB/frame 以上完全不是问题。