polar code

Polar Code是极化码。2008年在国际资讯理论ISIT会议上，Arikan首次提出了信道极化的概念，基于该理论，他给出了人类已知的第一种能够被严格证明达到信道容量的信道编码方法，并命名为极化码（Polar Code）。Polar码具有明确而简单的编码及解码算法。通过信道编码学者的不断努力，当前Polar码所能达到的纠错性能超过目前广泛使用的Turbo码、LDPC码。

基本介绍中文名：极化码外文名：Polar Code解码算法：SC、SCL首次提出：Arikan简介,原理,简介 2016年10月，华为/海思在葡萄牙首都里斯本，以PPT文档的形式（编号R1-1610667）给出了几种信道编码方案的比较。文档从性能、灵活性、实现的复杂度、时延这几个方面对比了Polar、LDPC、Turbo、TBCC等几种编码方案的特点，原文提案编号如下图所示（华为/海思2016年10月份的原始提案）。从这篇原始文档中可以看到，关于编码方案到底采用哪一种，实际在之前的几次会议中已经有过讨论，但没有定论，可见一篇提案写进标准规范不仅仅是脑力上的付出，也是要拼体力^_^。从原始文档中看到，华为/海思除了基于自己公司的研究成果外（R1-1608864等），还参考了众多其他同行的研究成果，比如中兴通讯（R1-166411等）、展讯（R1-1608922等）、诺基亚（R1-1609583等）、电信研究院（R1-1609578等）、 Intel（R1-167703等）、 MTK（R1-1609336等）等等。可以看到，这篇提案（其它很多提案都类似）集合了众多厂家的研究成果，很难说归属于某一家所有，科学无国界。 2016年11月17日凌晨0点45分，经过一系列的讨论研究，在美国Reno举行的3GPP RAN1 87次会议的5G短码方案讨论中，正式通过了华为/海思主导的Polar Code（极化码）方案这一提案，成为5G控制信道编码最终方案。如图所示正式文档编号为 R1-1613211。需要注意到这项提案的通过，不仅仅是华为/海思的努力，如果没有众多国内外同行的支持也是不行的。值得一提的是，在这份支持的名单中，国内公司除了中兴通讯、移动、电信这类巨头外，还出现了酷派、海能达、展讯、努比亚、OPPO、小米这类发展迅速的企业，这些站在华为背后的厂商，也是国内厂商综合技术实力的表现。虽然现在极化码已经被业界认可，但依然还没有正式被写到5G标准中，因为现在还没有5G标准。根据5G标准进程，2017年3月之前，国际移动通信标准化组织3GPP对于5G标准的制定尚处于研究项目阶段，具体实施时间表需要到2017年3月后才开始商议。从最初的“碾压”、“完爆”到现在的“误读”，科技界的事倒像是娱乐圈的事。原理这里只谈谈arikan发明极化码时所提到的2*2矩阵为核的极化码，只说要点，不说科普。

1.上鞅收敛：构造了一个信道变换，如果不断递归这个变换并随机挑选变换结果的话，则变换结果的巴氏参数(Bhattacharya parameter)构成一个随机过程。arikan证明这个随机过程是一个上鞅，再利用上鞅中的随机变数序列a.s收敛和按期望收敛，证明收敛结果为一个二值随机变数。再证明这个二值随机变数为0的机率是二元离散对称无记忆信道容量I，推断证明码长n无穷的时候可以挑出约nI个巴氏参数逼近0的无失真子信道，这就证明了信道极化是信道容量可达的。Foundation and trends里面polar章节，有另外一种证明方法，初等一些。

2.SC解码：有了好码还需要有好的解码算法。香农和Gallager都已经证明，大部分码都是好码，只缺好的，多项式复杂度的解码算法。arikan使用信道变换中的递归结构，先译“坏”信道的结果，甚至冻结“坏”信道的解码结果为0（降低码率），然后作为“好”信道解码的依据。复杂度是超线性的，非常Nice.

3.性能估计：引用Foundation and trends里面polar章节作者的一种rough说明：每一次递归变换，码长翻倍，而子信道中有1/2子信道的误码率（的上界）e会平方（e<1），1/2子信道的误码率（的上界）e会翻倍（误码率实际值当然小于1，忽略掉上界的不够紧致吧）。设递归变换了m次，随机挑选一个子信道，误码率平方的次数的期望是m/2，所以子信道的误码率期望约是(在指数爆炸面前，忽略掉那些翻倍的系数吧，虽然这样很粗糙)，n是码长。严格的证明则说，码长n无穷的时候，误码率小于的子信道数量逼近nI, I是信道容量（ e的值甚至都不重要了....反正码长n无穷的时候逼近0就好）。比较新的Finite length性能估计出自Guruswami(2010年以后，很多做代数编码的都跑去做极化码了，笔者也算其中一个吧。。)，有兴趣的还可以去网上查查Rate dependent性能估计。

以上3点认为是极化码，在信道编码中，最核心的创新。

OK，本文到此结束，希望对大家有所帮助。