关于编码:喷泉码浅谈

01、喷泉码简介

喷泉码（Fountain Code）是一种在无线通信、数据传输和网络编码畛域中应用的谬误纠正技术。它与传统的纠错码和编码方法有所不同，喷泉码被设计用于在不确定信道条件下的高效数据传输。传统的纠错码（如海明码、RS 码等）通常须要在发送方对数据进行编码，接管方则应用雷同的编码进行解码和纠错。这些办法个别具备固定的码率（Code Rate），即针对肯定长度的原始数据，编码后的长度是固定的，这些办法在面对不稳固的信道或重大的信道失落时可能成果不佳。相比之下，喷泉码通过在发送方生成随机的冗余数据，而后将其注入到原始数据中，以发明出一个“喷泉”流——相应的码率也也就不固定了。接管方能够从这个流中采样任意数量的数据包，并将它们合并以复原原始数据。喷泉码的一种常见利用是在无线传感器网络中，其中网络节点之间的通信可能受到弱信号、烦扰和多径流传等因素的影响。通过应用喷泉码，节点能够在较差的通信条件下实现牢靠的数据传输。喷泉码另外一个罕用的场景是大量文件或者数据的播送，这种时候每位接受者的丢包率是不确定的，因而固定码率的编码就不实用，喷泉码却能够解决该场景下的问题——丢包率高的接受者多收一些包，丢包率少的接受者则少收一些包。本文会介绍最常见的两种喷泉码实现，LT 编码 和 Raptor 编码。通过这两种编码的介绍和比拟能够比拟好的理解喷泉码的个性和根本的实现原理。

02、LT 编码

LT 编码 是第一个被实现的具备实用价值的喷泉码，该编码在 2002 年被提出，实现记的基本原理也非常简单，即位运算中的 xor 操作。Xor 操作有如下的个性：

1. 两个雷同的数据块 M，它们 Xor 的后果是 0。即 M ^ M = 0。
2. 对一块数据块 M，Xor 两次雷同的数据块 N，最终后果依然为 M。即 M ^ N ^ N = M。
3. 假如两个等长的数据块 M 和 N，M ^ N = L。那么 L ^ M = N 并且 L ^ N = M。

基于上述的个性，LT 编码的形式就能够形容为下列的步骤：

1. 对于长度为 N 的等宽数据块序列，随机选取一个 degree (d)，1 ≤ d ≤ N。
2. 从上述的数据块中选取随机 d 个数据块，将所有选取的数据块进行 xor 操作，最终失去一个编码的数据块。
3. 反复上述步骤 1 和 2，咱们能够失去源源不断的编码数据块，如同“喷泉”一样水流一直。

编码过程很简略，惟一须要留神一下的问题是如何取得等款的数据块。如果总数长度不可能凑巧分成 N 等分，咱们能够通过在后续加 padding 的形式来实现能够 N 等分。解码绝对比较复杂，形容如下：

1. 曾经承受过的反复的编码块抛弃。
2. 如果接管的数据块 d > 1, 将其和 所有已知和该编码块相干的 d = 1 的原始数据块进行 xor 操作，没操作一次 d 减一，如果晓得最初 d > 1，则将后果暂存到队列中，否则将最终失去的原始数据块记录下来。
3. 每当发现一个新的 d = 1 的原始数据块，将该数据块和所有期待数据块中相干的数据块进行 xor 操作，以期待发现更多的 d = 1 的原始数据块。
4. 反复上述操作，直到所有的原始数据块被复原进去。

该过程中的编码数据块个别还是会携带 metadata 信息，蕴含原始数据块的地位信息，例如告知该编码块由 第 1 和 第 3 个原始数据块 xor 而来。LT 编码有其局限性，如果咱们想保障编码块的数量 m 和原始数据块数量 k 十分靠近，且复原的成功率较高，那么均匀每个编码块的生成须要进行 O(log(k)) 次 Xor 操作，须要耗费十分多的计算资源。相同，如果 degree 比拟低，尽管每个编码块的操作数缩小了，然而咱们会须要更多的编码块来复原出全副数据。上述所说的局限性是受到信息论的束缚的，无奈进一步升高。那么咱们有没有方法实现一种形式来升高计算资源的耗费呢？比方咱们如果不须要复原出全副的原始数据呢？受到这个思路的启发 Raptor 算法应运而生。

03、Raptor 算法

Raptor 实质上是一类混合编码方式，联合 LT 编码和 LDPC 编码，同时获取了两种编码的益处。如下图所示：

Raptor 编码首先通过 LDPC 编码进行一次固定码率编码，造成一个两头编码层，而后再对该编码层进行 LT 编码，生成最终的编码数据块。当然 Raptor 编码也会有其余变种，不过原理大同小异，例如下图所示：

该编码具备 三层构造 ，两头编码后果通过了两层固定码率编码，别离是Hamming 编码 和LDPC 编码 ，而后再进行LT 编码 生成最终的编码块。针对 Raptor 编码的解码形式个别有两种。第一种和编码方式齐全相同，首先利用 LT 编码的解码形式复原出局部的两头编码块，而后利用固定编码的解码形式复原出原始的数据块。第二种形式则是将上述所有的多层编码方式都变成一种矩阵运算，针对收到数据后利用矩阵的高斯消元办法解出原始的数据块。现有为人所熟知的 Raptor 编码次要有 RFC 5053 和 RFC 6330 RaptorQ 编码。两者的实现细节有诸多区别，然而外在的思路和上述的办法是相似的，有趣味的读者能够进一步进行浏览和学习。

04、总结

喷泉码是一种无固定码率的编码方式，其中比拟驰名的有 LT 编码和 Raptor 编码。LT 编码算法简略，实现也简略，然而算法效率不高。Raptor 算法联合了 LT 编码和一些固定码率编码，利用混合编码的形式实现了高效的喷泉码。

达坦科技（DatenLord）专一下一代云计算——“天空计算”的基础设施技术，致力于拓宽云计算的边界。达坦科技打造的新一代开源跨云存储平台 DatenLord，通过软硬件深度交融的形式买通云间壁垒，实现数据高效跨云拜访，建设海量异地、异构数据的对立存储拜访机制，为云上利用提供高性能平安存储反对。以满足不同行业客户对海量数据跨云、跨数据中心高性能拜访的需要。

公众 号：达坦科技 DatenLord

DatenLord 官网：www.datenlord.io

知乎账号：

https://www.zhihu.com/org/da-tan-ke-ji

B 站：

https://space.bilibili.com/2017027518