剑阁住房和城乡建设厅网站,营销存在的问题及改进,海南网站建设fwlit,wordpress神级插件01、喷泉码简介
喷泉码#xff08;Fountain Code#xff09;是一种在无线通信、数据传输和网络编码领域中使用的错误纠正技术。它与传统的纠错码和编码方法有所不同#xff0c;喷泉码被设计用于在不确定信道条件下的高效数据传输。传统的纠错码#xff08;如海明码、RS码等…01、喷泉码简介
喷泉码Fountain Code是一种在无线通信、数据传输和网络编码领域中使用的错误纠正技术。它与传统的纠错码和编码方法有所不同喷泉码被设计用于在不确定信道条件下的高效数据传输。传统的纠错码如海明码、RS码等通常需要在发送方对数据进行编码接收方则使用相同的编码进行解码和纠错。这些方法一般具有固定的码率Code Rate即针对一定长度的原始数据编码后的长度是固定的这些方法在面对不稳定的信道或严重的信道丢失时可能效果不佳。相比之下喷泉码通过在发送方生成随机的冗余数据然后将其注入到原始数据中以创造出一个“喷泉”流——相应的码率也也就不固定了。接收方可以从这个流中采样任意数量的数据包并将它们合并以恢复原始数据。喷泉码的一种常见应用是在无线传感器网络中其中网络节点之间的通信可能受到弱信号、干扰和多径传播等因素的影响。通过使用喷泉码节点可以在较差的通信条件下实现可靠的数据传输。喷泉码另外一个常用的场景是大量文件或者数据的广播这种时候每位接受者的丢包率是不确定的因此固定码率的编码就不适用喷泉码却可以解决该场景下的问题——丢包率高的接受者多收一些包丢包率少的接受者则少收一些包。本文会介绍最常见的两种喷泉码实现LT 编码 和 Raptor 编码。通过这两种编码的介绍和比较可以比较好的了解喷泉码的特性和基本的实现原理。
02、LT 编码 LT 编码 是第一个被实现的具有实用价值的喷泉码该编码在 2002 年被提出实现记的基本原理也非常简单即位运算中的 xor 操作。Xor 操作有如下的特性
两个相同的数据块 M它们 Xor 的结果是 0。即 M ^ M 0。对一块数据块 MXor 两次相同的数据块 N最终结果仍然为 M。即 M ^ N ^ N M。假设两个等长的数据块 M 和 NM ^ N L。那么 L ^ M N 并且 L ^ N M。
基于上述的特性LT 编码的方式就可以描述为下列的步骤
对于长度为 N 的等宽数据块序列随机选取一个 degree (d)1 ≤ d ≤ N。从上述的数据块中选取随机 d 个数据块将所有选取的数据块进行 xor 操作最终得到一个编码的数据块。重复上述步骤 1 和 2我们可以得到源源不断的编码数据块好像“喷泉”一样水流不断。
编码过程很简单唯一需要注意一下的问题是如何获得等款的数据块。如果总数长度不能够恰巧分成 N 等分我们可以通过在后续加 padding 的方式来实现可以 N 等分。解码相对比较复杂 描述如下
已经接受过的重复的编码块丢弃。如果接收的数据块 d 1, 将其和 所有已知和该编码块相关的 d 1 的原始数据块进行 xor 操作没操作一次 d 减一如果知道最后 d 1则将结果暂存到队列中否则将最终得到的原始数据块记录下来。每当发现一个新的 d 1的原始数据块将该数据块和所有等待数据块中相关的数据块进行 xor 操作以期待发现更多的 d 1 的原始数据块。重复上述操作直到所有的原始数据块被恢复出来。
该过程中的编码数据块一般还是会携带 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官网http://www.datenlord.io
知乎账号
达坦科技DatenLord - 知乎
B站 https://space.bilibili.com/2017027518
