LDPC码原理简介

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

LDPC码原理简介

平生不见LDPC

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

本节涉及的主要话题有:LDPC基础,Bitflip,SoftBitflip。

引子,从单身狼人杀人事件到LDPC

话不多聊,在说LDPC之前,先讲一个真事改编的故事。

回到老家的蛋蛋,立即被当地的警察带到了警局。原来,最近小镇又发生了凶手案。 而蛋蛋多年前用数学知识破获一起拐卖妇女儿童案件,在侦探界名声大作,此次,只是请他协助探案。案发现场在巨星阿呆的巡回演唱会内。并无视频监控和目击证人。嫌疑犯多达几百人。上头限期破案,警力不足的警察局一筹莫展。蛋蛋专门查验了死者的尸体,发现与狼人作案的手法高度吻合。

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

  • 狼人,白日人形,分散在人群中,夜晚可随意化作狼身,击杀人类。
  • 据说狼人到了晚上脾气都很暴躁,嗜血,必杀。两个狼人一旦接近,就会相互感应,湮灭狼性,变成普通人,有效期为一夜。所以偶数个狼人相遇的晚上就是平安夜。奇数个狼人,晚上必有人类死伤。

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

  • 据法医鉴定,死者都非人类所伤。
  • 这不是第一次演唱会凶手案了,在全国范围内,跟巨星阿呆的巡回演唱会相关的就有十几起。
  • 至今为止,并没有抓获住凶手。每次嫌犯人数高达上百人。
  • 统计每个嫌疑人都大致均匀参加过几次阿呆的各个演唱会。
  • 每次演唱会参加的嫌疑人大致随机。并没有出现团队连续参加演唱会的。
  • 谣传很多狼人都是长脸型。

蛋蛋陷入了深深的思考,案子应该从哪里着手呢?针对警方的信息,蛋蛋做了以下推断:

  • 杀人者应该是狼人。
  • 阿呆演唱会是一个突破口,凶手有可能是阿呆的粉丝。阿呆本人已经获证排除,阿呆粉丝数十万,需要线索快速甄别。

 

蛋蛋顺手在黑板上画了一个图。

 

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

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

然后,蛋蛋又画了两个示意图,第一个是狼人假定的洪七公,指向他的红色箭头表示初始狼人推断,射出三条红色箭头表示他以狼人身份去参加了三场演唱会。第二个是拥有人类(指向它的蓝色箭头)峰的示意图,三条蓝色箭头指向他以人类身份参加的全部演唱会。

 

嫌疑人洪七公                                   嫌疑人萧峰

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

 

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

 

与真实场景相符的推断                           获得最多投票的嫌疑人

如果该次演唱会实际上有凶杀案发生,和从嫌疑人角色推断的结论相符,不做任何投票。所有的演唱会检查下来,找到一个收到翻转投票最多的嫌疑人,洪七公被认为是推断错误概率最高的人。翻转他的角色。然后重新再检查所有的演唱会,重新投票,直到没有嫌疑人收到反对票,则认为狼人全部找到。

总结一下蛋蛋的思路:

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

最后,在蛋蛋和警察的共同努力工作下,他们编写一个程序,当天下午就把目标锁定在萧峰和萧远山以及贾科布等一众狼人,经过蹲点排查终于确认他们的狼人身份。

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

 

 

故事讲完了,蛋蛋在这里用到的断案方法借鉴了LDPC里面bitflip的思想。

还有几个问题,

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

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