LDPC码原理简介

平生不见LDPC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

嫌疑人洪七公                                   嫌疑人萧峰

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

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

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

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

总结一下蛋蛋的思路：

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

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

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

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

还有几个问题，

• 蛋蛋的方法总是有效吗？
• 还有没有更好的方法？