ldpc码bp算法

A. 请问LDPC译码中的BP和BF算法有什么区别，谢谢

BP是belief-propagation，指得是置信传播法。
BF是Bit-Flipping，指得是比特翻转法。
两者的思想都是通过信息传递迭代判断最可能错误的点。但BP在计算中使用了先验概率和后验概率作为判断的依据。而BF则是根据传递的信息评估某位是1或0的可能性，不同值超过50%则1变0，0变1。
其实，可以把BF看成一种特殊条件下的BP。

B. LDPC码的简介

任何一个(n，k)分组码，如果其信息元与监督元之间的关系是线性的，即能用一个线性方程来描述的，就称为线性分组码。
低密度奇偶校验码图（LDPC码）本质上是一种线形分组码，它通过一个生成矩阵G将信息序列映射成发送序列，也就是码字序列。对于生成矩阵G，完全等效地存在一个奇偶校验矩阵H，所有的码字序列C构成了H的零空间 (null space)，即。
LDPC仿真系统图DLPC 码的奇偶校验矩阵H是一个稀疏矩阵，相对于行与列的长度，校验矩阵每行、列中非零元素的数目(我们习惯称作行重、列重)非常小，这也是LDPC码之所以称为低密度码的原因。由于校验矩阵H的稀疏性以及构造时所使用的不同规则，使得不同LDPC码的编码二分图(Taner图)具有不同的闭合环路分布。而二分图中闭合环路是影响LDPC码性能的重要因素，它使得LDPC码在类似可信度传播(Belief ProPagation)算法的一类迭代译码算法下，表现出完全不同的译码性能。
当H的行重和列重保持不变或尽可能的保持均匀时，我们称这样的LDPC码为正则LDPC码，反之如果列、行重变化差异较大时，称为非正则的LDPc码。研究结果表明正确设计的非正则LDPC码的性能要优于正则LDPC。根据校验矩阵H中的元素是属于GF(2)还是GF(q)(q=2p)，我们还可以将LDPC码分为二元域或多元域的LDPC码。研究表明多元域LDPC码的性能要比二元域的好。

C. LDPC码的发展现状

LDPC码
LDPC ( Low-density Parity-check，低密度奇偶校验）码是由 Gallager 在1963 年提出的一类具有稀疏校验矩阵的线性分组码 (linear block codes)，然而在接下来的 30 年来由于计算能力的不足，它一直被人们忽视。1996年，D MacKay、M Neal 等人对它重新进行了研究，发现 LDPC 码具有逼近香农限的优异性能。并且具有译码复杂度低、可并行译码以及译码错误的可检测性等特点，从而成为了信道编码理论新的研究热点。
Mckay ，Luby 提出的非正则 LDPC 码将 LDPC 码的概念推广。非正则LDPC码 的性能不仅优于正则 LDPC 码，甚至还优于 Turbo 码的性能，是目前己知的最接近香农限的码。
Richardson 和 Urbank 也为 LDPC 码的发展做出了巨大的贡献。首先，他们提出了一种新的编码算法，在很大程度上减轻了随机构造的 LDPC 码在编码上的巨大运算量需求和存储量需求。其次，他们发明了密度演进理论，能够有效的分析出一大类 LDPC 译码算法的译码门限。仿真结果表明，这是一个紧致的译码门限。最后，密度演进理论还可以用于指导非正则 LDPC码 的设计，以获得尽可能优秀的性能。
LDPC水印系统结构框图LDPC码具有巨大的应用潜力，将在深空通信、光纤通信、卫星数字视频、数字水印、磁/光/全息存储、移动和固定无线通信、电缆调制/解调器和数字用户线(DSL)中得到广泛应用。
M.Chiain 等对 LDPC 码用于有记忆衰落信道时的性能进行了评估。B.Myher 提出一种速率自适应 LDPC 编码调制的方案用于慢变化平坦衰落信道，经推广还可用于 FEC-ARQ 系统。
Flarino 开发的集成了 V-DLPC 的 flash-OFDM 移动无线芯片组己可用于基于 IP 的移动宽带网。VOCAL Technologies.Ltd 提出了一种用于 WLAN 的LDPC/Turbo 不对称解决方案，即下行链路采用 LDPC 码，上行链路采用 Turbo码。研究表明采用该方案后用于IEEE802.11 a/b/gWLAN移动终端的电池寿命可延长至原来的4倍。
工业界也己经有 LDPC 编译码芯片问世。其中，处于领先地位的 Flarion公司 推出的基于 ASIC 的 Vector-LDPC 解决方案使用了约 260 万门，最高可以支持 50000的码长，0.9 的码率，最大迭代次数为 10，译码器可以达到 10Gbps 的吞吐量，其性能己经非常接近香农限，可以满足目前大多数通信业务的需求。AHA 公司、Digital Fountain公司也都推出了自己的编译码解决方案。

D. 机情观察室：华为5G polar Code是什么

【IT168 评测】11月18日，在互联网上当所有人都被林丹出轨刷屏的时候，可能许多人并没有注意，在大洋彼岸的拉斯维加斯举行的3GPP RAN1#87次会议上，正式宣布由华为主推的Polar码成为5G eMBB场景下控制信道的短码编码方案。而随后在互联网上，一些诸如“碾压高通”“称霸5G”类似的报道连篇累牍，点燃许多吃瓜群众爱国之情，纷纷在朋友圈、微博上奔走相告好不欢喜。我们今天的机情观察室，就来聊聊Polar码是个什么东西，所谓的华为“拿下”5G又是怎么回事？

LDPC码和Polar码究竟是什么?

首先，无论是LDPC还是polar，都是一种信道编码，并且均为第一次入选3GPP的标准。信道编码是通讯行业中的一个名词，广泛用作表示检测及纠正编码错误的一种术语，常常用于通信及存储领域，是通信系统的核心技术之一。简单的说就是信道编码就是在传输过程中保护数据以及在出错时恢复数据用的一种数字调制方式。

▲信道编码相当于数据的保护盒

因为在无线传输过程中，我们会将比较复杂的模拟信号(含有复杂的数据信息)转化成简单的数字信号(由0和1组成)，这样虽然便于传输但是会影响还原数据的准确性。因为无线数据传输过程中，往往会出现掺杂噪音或者丢失数据的情况。信道编码则是将这些数字信号进行分组，接收存储之后再重复接受并与之前存储的数据进行对比，如果相同分组的数据相同则判断为正确。比如接受存储的数据为1，经过3组对比后该数据全部为1，则判断正确传输数据1。信道编码的作用就像在运快递，有用的数据是你买的东西，但是为了确保东西安全送给你，需要对其包装。本来一车能运100个，现在包完了只能送50个，但是准确率有所提高。

对于5G网络来说，3GPP对5G网络的定义范围包括：eMBB（大流量移动带宽业务）、mMTC（大规模物联网）、URLLC（低延时高可靠的业务，比如自动驾驶）。整个5G网络覆盖的场景对下载速率、时延的要求更加严格。因此，对于信道编码来说，在保证可靠性的前提下，效率显得异常重要。这里的效率，指的是接近信道容量的极限：香农限。简单来说，香农限是指在带宽一定、噪音已知(可以根据通道数据算出来)的情况下，一个传输通道能通过有用的数据量上限能够接近信道所能容纳的最大数据量。目前，能够符合5G网要求的信道编码就只有LDPC和Polar。

▲典型的LDPC

LDPC码：即低密度奇偶校验码。在1963年由MIT的Gallager博士提出，但在当时由于计算过于复杂而被人所忽略。后来经过不断努力，简化LDPC解码算法。之后，有人发现LDPC码可以逼近香农极限，此时的LDPC码又回到大家的视野。LDPC码是一种具有稀疏校验矩阵的线性分组码，具有更低的误码平台，译码过程简单高效，复杂度和时延都比较低，目前已经在广播系统、有线、无线甚至航空航天等通讯系统有所应用，编解码的算法比较成熟。

▲Polar Code的优势

Polar码：即极化码。与有着50多岁高龄的LDPC码相比，Polar码完全算得上少年儿童。Polar码由土耳其教授Erdal Arikan在2008年提出。Polar码基于信道极化理论，在解码时将信道分为无噪信道和全噪信道，将有用的信息分到无噪信道，将垃圾信息分到全噪信道。因此在理论速度上，Polar码可以拥有无限逼近香农极限的速率，相比LDPC码，Polar码在网络性能能更有优势，并且编码和驿码的复杂度也比较低。

LDPC码与Polar在入选5G标准中的差异?

而从3GPP RAN1#87次会议的最终结果来看，eMBB场景下，LDPC码最终成为eMBB成为数据信道编码长码，而Polar码则是控制信道短码编码方案。polar码也并非唯一的标准，而是作为控制信道的短码。因此主要的问题，就在于数据信道与控制信道、长码与短码之间的区别。

简单来说，控制信道主要负责传输指令和同步参数，数据信道主要传输数据。举个例子，比如高速公路，数据信道相当于主路，传输各种主要信息，控制信道相当于应急车道，个中作用大家可想而知。而控制信道中所谓的“长短码”，则是将数字信号所形成的二进制指令进行分组，常用的信息用相对短的二进制位数表示，不常用信息的采用相对长的二进制位数表示。这样做可以在指令不变的情况下更迅速的进行编码(常用码较短，易校对编译，不常用的较长，可以快速的带过并且不会影响数据的准确性)。

因此从会议确定的结果来看，此次华为不仅不是所谓的“拿下5G标准”，甚至在5G的eMBB场景下也不是唯一编码标准。在整个5G eMMB场景中，LDPC拿下数据信道与长码，Polar拿下控制信道与短码，最多算是平分秋色。

Polar码入选5G标准对意味着什么?

▲会议上支持华为的企业

关注手机的人或许听说过一句玩笑：高通就是一家卖基带送处理器的公司。这也从某方面显示出通讯专利对于企业的重要性。此次Polar码入选5G标准，对于以华为为首主导Polar码的中国通讯界，经过多年的努力，终于能在世界通讯标准中立足，尽管只是确立5G标准进程中的一小部分，但也终于实现了中国通讯企业从无到有的一大步，在基础标准领域有了一定的话语权。并且对于主导Polar码的华为以及其它中国企业，其已经积累的研究成果在未来有了落地的可能性。

E. LDPC码的二元域与多元域LDPC码

对LDPC码的定义都是在二元域基础上的，MaKcay对上述二元域的LDPC码又进行了推广。如果定义中的域不限于二元域就可以得到多元域GF(q)上的LDPC码。多元域上的LDPC码具有较二进制LDPC码更好的性能，而且实践表明在越大的域上构造的LDPC码，译码性能就越好，比如在GF(16)上构造的正则码性能己经和Turbo码相差无几。多元域LDPC码之所以拥有如此优异的性能，是因为它有比二元域LDPC码更重的列重，同时还有和二元域LDPC码相似的二分图结构。
假设在域GF(2)和域GF(q)(q=2p)上构造的LDCP码所对应的校验矩阵分别是H2和Hq。H2中的元素是0或1，而Hq是由元素0，1，…，q-1构成，Hq中的每个元素都是H2中p个元素的合成。如果设域GF(q)(q=2p)上的一个值a与一个1*p的二进制向量相关联，那么把这个向量代入Hq中，就可以得到Hq的二进制表示。对于二进制LDPC码来说，如果它的校验矩阵H的列重量足够大，那么它可以任意地接近香农限，但是如果增加列重量会使得二分图中节点之间短圈的数H急剧增加从而使BP算法的性能下降。而在GF(q)域上构造的LDPC可以解决这个矛盾，它的检验矩阵H。可以增加与之对应的二进制校验矩阵HZ中列的平均重量，且它的二分图结构并没有改变，不会造成节点之间短圈数目的增加，从而使得译码性能得到显着的提高。这种多元域上的编码构造会增加译码复杂度，但是相对于译码性能的提高来说这种增加是值得的。

F. 用准循环构造法构造LDPC码的校验矩阵的算法流程

QC LDPC码，可以用代数法和随机方法构造。如果是代数方法，这里很难说清楚，需要找Linshu老师那边的文章看看，方法一般都还算简单，但是需要有限域的知识。

随机构造的话，以802.16e为代表的QC LDPC码，大致过程如下
1：先确定基矩阵的大小，基矩阵大的话，存储需要的空间也会大，但是性能会好些。
2：确定度分布，这个和应用场合有关，一般而言，最大变量度分布大的话，瀑布区性能会好些，但是也还是对存储要求更高。而且如果基矩阵不够大的话，度分布大的话，密度会高，这样会使得环分布优化困难 。
3：确定好基矩阵后，就是利用circulant去替换每个“1”元素了，至于如何选择circulant，就是个试探的过程。原则多种多样。

G. ldpc码的编译码原理是什么ldpc码是如何构造出来的译码算法有哪些

BP是belief-propagation，指得是置信传播法。 BF是Bit-Flipping，指得是比特翻转法。 两者的思想都是通过信息传递迭代判断最可能错误的点。但BP在计算中使用了先验概率和后验概率作为判断的依据。而BF则是根据传递的信息评估某位是1或0的可能性

H. LDPC码的优势和劣势

和另一种近Shannon限的码-Turbo码相比较，LDPC码主要有以下几个优势：
1. LDPC码的译码算法，是一种基于稀疏矩阵的并行迭代译码算法，运算量要低于Turbo码译码算法，并且由于结构并行的特点，在硬件实现上比较容易。因此在大容量通信应用中，LDPC码更具有优势。
2. LDPC码的码率可以任意构造，有更大的灵活性。而Turbo码只能通过打孔来达到高码率，这样打孔图案的选择就需要十分慎重的考虑，否则会造成性能上较大的损失。
Trubo码编码器结构3. LDPC码具有更低的错误平层，可以应用于有线通信、深空通信以及磁盘存储工业等对误码率要求更加苛刻的场合。而Turbo码的错误平层在10量级上，应用于类似场合中，一般需要和外码级联才能达到要求。
4. LDPC码是上个世纪六十年代发明的，现在，在理论和概念上不再有什么秘密，因此在知识产权和专利上不再有麻烦。这一点给进入通信领域较晚的国家和公司，提供了一个很好的发展机会。
而LDPC码的劣势在于：
1. 硬件资源需求比较大。全并行的译码结构对计算单元和存储单元的需求都很大。
2. 编码比较复杂，更好的编码算法还有待研究。同时，由于需要在码长比较长的情况才能充分体现性能上的优势，所以编码时延也比较大。
3. 相对而言出现比较晚，工业界支持还不够。

I. LDPC的译码算法都有哪些 BF,BP 和积算法

置信传播（BP）一类中有：概率BP，LLR BP，APP-Based，UMP BP-Based等算法；
比特翻转（BF）一类中有：KLF加权比特翻转，LP加权比特翻转，IMWBF，RRWBF等算法。