蛋蛋表白地铁女孩与闪存纠错编码

原创内容,转载请注明:  [http://www.ssdfans.com]  谢谢!

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

编码距离

还记得蛋蛋表白的时候,信息为“我 喜 欢 你”四个字,为了防止女神听不到,他添加了冗余信息。经过蛋蛋添加冗余后变为了“我 我 我 喜 喜 喜 欢 欢欢 你 你 你”,其实女神收到的信号为(我 我 饿 T x x 欢 花 欢 x x 里),其中x表示为邻座大妈的霸气的笑声,女神是如何正确的捕捉到蛋蛋的意图呢?显然女神在这方面很有经验,识破了蛋蛋重复三遍的伎俩,电光火石间,在她脑海里飞速搜索比对推理,得出一个通顺而有意义的结论。换句话说,在女神的词典中,有意义的语句全都列出来,发现跟蛋蛋发出声音最相似的就是:“我我 我 喜 喜 喜 欢 欢 欢 你 你 你“

女神的词典可以看成所有可能编码的集合,如何衡量这个编码集合中,容易混淆的程度呢?这个参数就是编码距离。什么是距离呢,这里指的是汉明距离,指的是两个信号之间有多少bit 不同。比如信号(0,1,1)与(0,0,0)的距离为2,(1,1,1)与(0,0,0)的距离为3.

蛋蛋有4个信息,为00,01,10,11. 现在如何插入冗余呢?

首先想到的是重复法:

q 00 变为 00 00 00 00

q 01 变为 01 01 01 01

q 10 变为 10 10 10 10

q 11 变为 11 11 11 11

现在接收到信号 为 00 01 00 00, 我们发现跟这个信号最相似的是 00 00 00 00,距离为1.

一个编码集合里,大家不一定是均匀分布的,有些编码之间距离比较近,有些比较远,编码距离指的是最近的两个编码之间距离。

解码的时候,一个最暴力的方法就是一一比较接收到的信号和所有有效编码之间的编码距离,选择编码距离最小的。所以编码距离的重要作用是可以指示编码可以纠错的bit个数。蛋蛋和阿呆住在不同的地方,相距为d,蛋蛋养了一群羊,阿呆也养了一群羊。羊会乱跑,显然只要羊跑的距离小于d/2 距离,就可以判断羊属于蛋蛋还是阿呆。所以对纠错码而言,编码距离为d,只要bit翻转个数小于d/2,我们可以根据离得谁近就归谁的原则去纠错(赶羊回家 )。

线性纠错码的基石——奇偶校验(parity-Check)

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

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

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

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

image

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

对于n bit 二进制信号:

image

例如长度为16的二进制数据:1000100111011011,其中1的个数为9,故CR = 1。

判断信号里的1的个数为奇还是偶,有非常简单的方法。在二进制里,有一种异或

(即xor)运算,符号为 ,运算方式先进行加法运算,然后运算结果对2取余数(mod(2)),或者更简单的记忆为“相加不进位”:

image

图1-1 异或运算表达式

可以验证只要把二进制的每一个bit依次进行xor运算,奇数个bit 1的结果为1,偶数个bit 1的结果为0,与bit 0的个数无关。

所以,用 表示第bit i的值(0或1),有

image

利用奇偶校验可以构造最简单的校验码——单bit校验码SPC(即single bit parity check code)。

把长度为n的二进制信息,增加1 bit 变成y’,使得:

image

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

显然,y’中任意一个bit如果发生bit反转,无论从0到1,还是1到0,校验方程 CR = 1 。

SPC 可以探知任意单bit的反转。对于偶数个bit 反转SPC无法探知。而且校验方程并无法知道是bit反转的位置,所以无法纠错。

一个自然的想法是,增加SPC的个数,增加冗余的校验信息。同一个bit被好几个校验方程保护,当它出现错误时候,就不会被漏掉。

后面的文章中,用 + 代替image

校验矩阵H 和 生成矩阵G

蛋蛋的丈母娘,在女儿结婚前对未来女婿有一个要求列表,前五条是1)一定是博士学位,2)脾气要好,3)人要长得帅,4)会做家务, 5)财政上交


(欲知蛋蛋如何搞定丈母娘和纠错算法,扫描下图二维码,阅读原著和以上大图。)

_wechat_thumb2_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb_thumb

分类目录 金士顿SSD评测.
扫一扫二维码或者微信搜索公众号ssdfans关注(添加朋友->点最下面的公众号->搜索ssdfans),可以经常看到SSD技术和产业的文章(SSD Fans只推送干货)。
ssdfans微信群介绍
技术讨论群 覆盖2000多位中国和世界华人圈SSD以及存储技术精英
固件、软件、测试群 固件、软件和测试技术讨论
异构计算群 讨论人工智能和GPU、FPGA、CPU异构计算
ASIC-FPGA群 芯片和FPGA硬件技术讨论群
闪存器件群 NAND、3D XPoint等固态存储介质技术讨论
企业级 企业级SSD、企业级存储
销售群 全国SSD供应商都在这里,砍砍价,会比某东便宜20%
工作求职群 存储行业换工作,发招聘,要关注各大公司招聘信息,赶快来
高管群 各大SSD相关存储公司高管和创始人、投资人

想加入这些群,请微信扫描下面二维码,或搜索nanoarchplus,加阿呆为微信好友,介绍你的昵称-单位-职务,注明群名,拉你进群。SSD业界需要什么帮助,也可以找阿呆聊。