首页 > 笔记, 信息论 > 从挖地雷到分布式文件存储(删去编码)

从挖地雷到分布式文件存储(删去编码)

erasure channel一般翻译为删去信道或消去信道,Erasure code一般翻译为删去编码或者存疑编码。

(1)删去信道

删去信道是会以一定概率丢失比特或者信包packet的信道。例如二进删去信道Binary erasure channel。输入信号符号是{0,1},输出符号是{0,1,e},e代表信号丢失。对下图BEC,信道容量是1-pe

信道容量的证明:以1-p的概率,传一次就成功。如不成功,再传一次成功,概率为p(1-p),也就是用2次。这样,要以极小出错概率传输,需要传

(1-p)+p(1-p)2+p^2(1-p)*3+….

这个无穷级数收敛于1/(1-p)。也就是说,在单位时间里,可以传输1-p个比特。

(2) 里德-所罗门码Reed–Solomon (RS) codes

“Polynomial Codes over Certain Finite Fields.” (Reed & Solomon 1960)

原理见Wikipedia: erasure code Example: Err-mail (k=2)

基本原理是对信号做过采样:“编码过程首先在多个点上对这些多项式求冗余,然后将其传输或者存储。对多项式的这种超出必要值得采样使得多项式超定(过限定)。当接收器正确的收到足够的点后,它就可以恢复原来的多项式,即使接收到的多项式上有很多点被噪声干扰失真。” (Wikipedia中文

“RS码的两种定义方式有着非常大的区别,而它们的等价关系并不是显而易见的。在第一种定义中,码字是多项式的值,而在第二种定义中,码字是多项式的系数。另外,第一种定义要求多项式具有特定的比较小的幂次,而在第二种定义中,多项式需要有特定的根。这两种定义的等价性可以通过有限域上的离散傅立叶变换来证明。”(Wikipedia中文)【注意,傅立叶变换是一种线性变换】

联想:这种多项式分解,似乎可以类比为傅立叶分解。如果根据某种准则(和语义相关)使个多项式系数重要性不同,则有可能实现有损语义压缩。一般的,我们认为高阶项系数相对不重要。

(3)低密度奇偶检查码 low-density parity-check (LDPC) code 

汉明码(Hamming Code)的检查码和原比特位的每一位都相关。比如(7,4)码,3位检查码中每一位和4位数据码的每一位相关。如果只和一小部分相关,就是LDPC。

(4)喷泉码 Fountain code

对k个原始数据码,喷泉编码器会产生无数多编码序列,只要其中>=k个序列被接收,就可以恢复原始数据。这有很多用处,比如分布式文件存储:把文件分为很多小块,只要收集的足够多的任意小块,就可以恢复原始文件。

具体的例子包括:Luby transform (LT) codesRaptor codes (线性时间) and Online codes。参考Mackay书第50章。

Online编码图示如下,其他喷泉码类似:

LT码其实非常简单:

  1. 假设原始数据有K个包,编码后的数据有N个包。实践中证明,N比K大5%就够了
  2. 取一个随机整数d。随机取原始包中d个包。把这d个包做XOR(异或),得到一个新的包。注意,这里的随机是伪随机,也就是解码器和编码器都知道这个“随机”序列。
  3. 做第2步N次。

解码过程类似挖地雷游戏,进行约束推理。

有些角上的方块,标记只有一个“1”(周围只有一个地雷),那可以肯定确定那个角是地雷。由此第次推理,可以发现越来越多的地雷。但是有些情况,有无地雷都可能,那就是不能唯一解码了。又有时,一个“1”都没有,那连解码都没法开始了。

关键在如何选择d的分布,使在极大的概率下,解码可以开始,而且可以确定性地恢复所有的原始包。

参考:喷泉编码(百度百科)

(5) 结论

(Mackay, p596):The best solution to the communication problem is: combine a simple, pseudo-random code with message-passing decoder.

Advertisements
分类:笔记, 信息论
  1. 还没有评论。
  1. No trackbacks yet.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: