纠错码简介

序言

噪声信号充斥着整个世界，不只是打电话催债时对方声嘶力竭的喊道听不清，也可能是还钱时手抖多按了一个0，甚至在生物学领域，基因对的复制偏差，癌细胞的产生，意外突破橡胶屏障的新生命都可以划入噪声信号的范畴。凡是有信息传递的地方就有噪声。我们唯一能做的是，把噪声限制在一定大小的笼子里。

如何建造这样一个笼子，我们看一下历史的经验。

场景是，蛋蛋每天坐地铁都会邂逅一个美丽的女孩。两人日久相熟，经常相视一笑，却默然无语。转眼间，蛋蛋就要离开这个城市，他决定勇敢地表白。

表白的地点，还是那一班地铁。唯一的困难是地铁太吵了，女神能够准确无误的接受到自己爱的呼唤吗。 这难不倒蛋蛋，他采取了以下策略。

1. 扩音器一个。喂喂，喂，音量调高。大声说我爱的就是你。
   
2. 每个字清晰的说三遍。我，我，我，喜，喜，喜，欢，欢，欢，你，你，你。
   
3. 结尾用手比划一个爱心出来。
   

    

利用扩音器的蛋蛋，改善了有效信号和噪声的强度比。为女神准确的接受作了基础建设。每个字说三遍，增加了信息的冗余，即使有少量字没有听清，也不影响表达的内容。结尾一个性感的手势，增加对关键信息的保护，借助大家都懂的意象，盖上爱的印章。

聪明的蛋蛋，揭示了长久以来我们传播信息的诀窍。增强信信号和噪声的强度比比例和信号冗余。前者在不在此讨论，我们只考虑不用扬声器的情况下，如何尽量准确的传递信息。

实际通讯中，我们用Information bits 表示有效信息长度，channel use 表示实际通讯中传输的信息长度。定义

Code rate = （information bits）/(channel use)

举个例子，因为每个字说三遍，所以蛋蛋采用的 Code rate 为1/3。

Code rate 可以反映冗余程度。Code rate 越高，冗余越小，反之冗余越大。Shannon 揭示了，每一种实际的信息传输通道，都有一个参数 C，如果

Code rate < C

有效信息传递的错误的概率可以在理论上趋近于0。但是如何趋近于0，是纠错编码（Error correction codes）要做的事情。

我们后续的讨论只限制在二进制的世界，即所有的信息都是二进制表示，本章主要涉及的内容，包括线性分组码，循环码，bch，LDPC。

最后，如果还有人在关心蛋蛋表白的结局的话，我只能复述女神的原话：我，我，我，也也，也，喜欢欢欢，你你，小结巴。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

通信系统模型

整体通信系统结构

所有的信息传播都少不了通信系统，一个完整的通信系统模型，信息由信息源产生，由发送器发送出信号，通过包含噪声的信号传输通道（Channel），到达接收器，接收器提取出信息发送到目的地。

整个框图如下图所示。

回到蛋蛋跟女神表白的例子，蛋蛋心中所想就是信号源，发送器是神经和肌肉控制的嗓子。声音就是信号。嘈杂的车厢就是Channel。女神的耳朵就是接收器，最终信息反映到女神大脑中。

用户对SSD存入和读出信息也是一个的通信系统。信息是用户写入的原始数据，经过SSD后端的发送器处理后转化为对NAND的program，信号就是NAND上的储存的电荷，电荷存储时会有自身泄露并在读的过程中受到周围电荷的影响，这个对应信号的Channel。接收器的工作对应SSD读NAND中的信号并转换成用户曾经存入信息，完成读取过程。

两种Channel模型—— BSC 和 BEC

在二进制编码的系统中，根据噪声影响方式的不同，有两种Channel模型，BSC和BEC。 BSC全称Binary symmetric channel，BEC的全称Binary erasure channel。一句话区分BSC和BEC：BSC出错BEC丢bit.

BSC 模型如下：

二进制信号由0，1两个bit组成，由于Channel噪声的影响，0，1各有相同的概率p翻转，即0变1，1变0。信号仍然保持不变的概率为1-p。

 

例如一串2进制信号，在经过BSC后的变。

原始信号：101001101010

变为： 111001111000

 

BEC 模型如下：

BEC模型认为在信号传输中，无论bit 0还是1都有一定概率变为一个无法识别的状态。

例如一串2进制信号，在经过BC后的变。

原始信号：101001101010

变为： 1x10011x10x0 （x 表示未知状态）

最后，对于SSD里的Channel模型一般采用BSC，即认为NAND信号发生了一定概率的bit翻转。

 

Channel和编码

为了使得信息从源头（source）在经过噪声的Channel后能够准确的到达目的地（sink）我们要对信息进行编码，通过增加冗余的方式保护信息。

基本流程为：

Source发出的信息可用k bit的信息x，经过编码器（Encoder）转化为n bit 信号c。

发送器把信号发送出去，经过Channel后，接收器收到信号n bit 信号y，经过解码器(Decocer) 转成k bit 信息 。

如下图所示：

 

 

 

 

 

 

 

 

 

 

 

纠错编码的核心思想

 

纠错编码的核心设计思想是通过增加冗余信息，使得原始信息的编码之间有足够大的区别

编码距离

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

纠错码的基石——奇偶校验（parity-Check）

收钱的阿姨狐疑地拿起蛋蛋递过来的皱巴巴的100块钱，迎着灯光仔细打量过后，又取出了紫外线灯从头到尾照了一下，终于把钱放进钱盒子里，找了蛋蛋99块5。阿姨担心收到假币，她检查钞票可不敢马虎。

阿姨检查钞票的行为叫做信号校验，信号校验的基本模型是：

对信号进行某种特定的处理后，得到期望的结果是为校验通过，否则校验失败。

这里信号用表示，特定的处理用表示，表示对信号y进行了处理。处理结果用CR表示。

在二进制的世界里，最基础的校验方法是奇偶校验即parity-Check。

对于n bit 信号:

长度为16的二进制数据：1000100111011011， 其中1的个数为9，故CR = 1。

判断信号里的1的个数为奇还是偶，有非常简单的方法。在二进制里，有一种异或(即xor)运算，符号为，运算方式与整数加法完全一致，并且满足：

可以验证只要把二进制的每一个bit依次进行异或运算，运算结果就是CR。

例如表示第bit i的值。

利用奇偶校验可以构造最简单的校验码——单bit校验码（SPC，即single bit parity check code）

把长度为k的二进制信息，增加1 bit 变成y’，使得：

（a）

现在y’构成了y的单bit校验码。（a）又叫做奇偶校验方程。

显然，y’中任意一个bit如果发生bit反转，则校验方程 CR = 1 。

SPC 可以探知任意单bit的反转。对于多个bit 反转，SPC无法探知。而且校验方程无法知道是哪一个bit反转，所以无法纠错。

如何把SPC用来构造纠错码呢？

举一个单bit纠错的例子。

 

校验矩阵H

下面把

从SPC的效果看，

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LDPC码原理简介

平生不见LDPC

在纠错码的江湖里，LDPC 就是大侠陈近南般的存在，没有听说过LDPC的工程师很少， 他的名字似乎代表了纠错码的最高境界。本结带领大家一睹大侠的风采。

引子，从单身狼人杀人事件

最近小镇发生了狼人凶手案，请来侦探蛋蛋协办。案发现场在巨星阿呆的巡回演唱会内。并无视频监控和目击证人。嫌疑犯多达几百人。上头限期破案，警力不足的警察局一筹莫展。

蛋蛋想起了有关狼人的传说：

两个狼人一旦接近，就会相互感应，湮灭狼性，变成普通人，有效期为一夜。落单的狼人每夜必杀人。所以偶数个狼人相遇的晚上就是平安夜。奇数个狼人，晚上必有人类死伤。

经过调查，警察把收集的信息汇总如下。

1. 这不是第一次演唱会凶手案了，在全国范围内，跟巨星阿呆的巡回演唱会相关的就有十几起。
   
2. 至今为止，并没有抓获住凶手。每次嫌犯人数高达上百人。
   
3. 统计每个嫌疑人都大致均匀参加过少数次阿呆的各个演唱会。
   
4. 狼人数目不多。
   
5. 谣传很多狼人都是长脸型。
   

听完警方的信息，蛋蛋陷入了深深的思考，案子应该从哪里着手呢？蛋蛋顺手在黑板上画了一个图。

 

并解释到，这个只是局部的示意图。整个图将包含全国所有嫌疑人和全部的阿呆演唱会。每一个嫌疑人都用一个圆圈表示，每一个方块表示一场阿呆的演唱会。连线表示，嫌疑人参加了这场演唱会。

蛋蛋提议到，结合目前的调查，给每个嫌疑人是不是狼人做个初始假定。警察们很快一致假定所有的长脸型都是狼人。蛋蛋继续说道，把线画成红色表示假定为狼。蓝色表示假定为人。

比如，第一个是狼人假定的洪七公，指向他的红色箭头表示初始狼人推断，射出三条红色箭头表示他以狼人身份去参加了三场演唱会。第二个是拥有人类（指向它的蓝色箭头）萧峰的示意图，三条蓝色箭头指向他以人类身份参加的全部演唱会。

 

图 1 嫌疑人洪七公

图 2 嫌疑人萧峰

 

根据有奇数个狼人参加的结果应该有凶杀案，偶数个为平安夜。现在每个嫌疑人的身份确定下来了，接下来按照假定可以推演出每场演唱会是否有凶杀案。如果与现实不符，则对参加演唱会的嫌疑人角色推断中至少有一个错误。

 

比如上图表示，某一场演唱会，因为推断出两个狼人参加。所以推断得出此演唱会应当没有凶杀案发生，与现实不符。如果碰到与事实不符的情况，而且对嫌疑人进行翻转投票。上图中黑色虚线表示对嫌疑人的投票。

与真实场景相符的推断

同样的如果在某个演唱会上推断和事实相符时候，比如，如果该次演唱会实际上有凶杀案发生，和从嫌疑人角色推断的结论相符，不做任何投票。

所有的演唱会检查下来，找到一个收到翻转投票最多的嫌疑人，翻转他的角色。比如嫌疑人慕容复现在得票数最高，被认为是推断错误概率最高的人。初始假定为好人，现在改为狼人。

 

 

然后重新再检查所有的演唱会，做第二轮重新投票。重新选出票数最多的嫌疑人，更改推断。直到没有嫌疑人收到反对票，则认为狼人全部找到。

总结一下蛋蛋侦探的思路：

1. 做一个给所有人的先验推断，此处靠脸。
   
2. 根据推断去演唱会接受事实的校验。
   
3. 民主的选出最错误的推断，并翻转该嫌疑人的推断，转到第二步。如果已经全部没有错误的推断，就认为推断正确。
   

最后，在蛋蛋编写了一个程序，当天下午就把目标锁定在萧峰和萧远山以及贾科布等一众狼人。

事后，蛋蛋坦言，能够找到这一批狼人也有有运气的成分，比狼人的长脸型推断起到了非常重要的预判作用。

还有几个问题，

1. 蛋蛋的方法总是有效吗？
   
2. 还有没有更好的方法？
   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

草稿。。。。。。

 

 

 

 

 

LDPC 基础

早在1960年，Gallager 在他的博士论文里提出了LDPC。他的纠错性能优异，逼近Shannon极限。但一度被认为计算量太大，实用性不强，并没有世人被看好，沉寂多年。现如今，随着计算能力的普遍增强，LDPC重新回到大众的视野。

LDPC 的全称叫 Low-Density Parity-Check Codes 即低密度奇偶校验码。

什么是Parity-Check Code？

二进制的编码有一序列的0，1组成。纠错码的设计思想是在信息中刻意的增加冗余，使得原来相近的信息得以很大区分，即使一条信息中有少量错误也可以与它信息区分出来。

对于二进制而言，Parity-Check code（奇偶校验码）首先是一个线性分组码（请参考线性分组码章节）。其次，编码还要满足一定数目的奇偶校验方程。

举一个bit的奇偶校验的例子。编码 c 由8 bit 表示,其中前7 bit 表示ASCII 码，第8bit是前7 bit的校验码。

c = [c1 c2 c3 c4 c5 c6 c7 c8]

其中，c_i 是0或者1。

满足：

c1 ⊕ c2 ⊕ c3 ⊕ c4 ⊕ c5 ⊕ c6 ⊕ c7 ⊕ c8 = 0

 

 

 

LDPC的特性体现在它的校验矩阵中：

1. 矩阵 H很大（一般10000 x 20000的规模）
   
2. 稀疏，校验矩阵中只有很小一部份是1.
   

   （TODO 此处插入校验矩阵）