Polar Code（極化碼）具體原理是怎樣的？

01-02

Polar Code系列研究筆記，內容涉及從Arikan Polar到SCL、CA-SCL解碼演算法，到Poalr Code在3GPP標準化進展。

Polar Code信道編碼

Polar Code（1）概述

Polar Code（2）編碼原理

Polar Code（3）編碼實例

Polar Code（4）編碼之極化信道可靠性估計

Polar Code（5）編碼之信道轉移概率

Polar Code（6）SC解碼演算法

Polar Code（7）SCL解碼演算法

Polar Code（8）高斯近似

Polar Code（9）CA-SCL解碼演算法

Polar Code（10）速率適配的鑿孔極化碼

Polar Code（12）B-DMC對稱容量

Polar Code（13）信道極化

Polar Code（18）比特信道的選擇

Polar Code（19）當我們談論design-snr時我們在談論什麼

Polar Code（20）Beta-expansion

Polar Code（24）小結

Answer-Polar Code-定義錯誤概率

Answer-Polar Code-高斯近似之φ(x)反函數

Polar Code之5G標準化

Polar Code（11）3GPP標準化進展

Polar Code（14）3GPP RAN1#88bis

Polar Code（15）3GPP RAN1#89

Polar Code（16）3GPP RAN1 adhoc#2

Polar Code（21）3GPP RAN1#90

Polar Code（22）3GPP RAN1 adhoc#3

Polar Code（23）3GPP RAN1#90bis

我老師招我讀研究生的時候說：你們來求學的，就像信道極化一樣，讀的時間足夠長的話，差的學生大部分會跌到谷底，好的學生大部分會飛向雲巔，這個比例就是中國人的普遍勤勞程度。。。

這裡只談談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，所以子信道的誤碼率期望約是 $e^{2^{frac{m}{2} } } approx e^{sqrt{n} }$ (在指數爆炸面前，忽略掉那些翻倍的係數吧，雖然這樣很粗糙)，n是碼長。嚴格的證明則說，碼長n無窮的時候，誤碼率小於 $e^{sqrt{n} }$ 的子信道數量逼近nI, I是信道容量（ e的值甚至都不重要了....反正碼長n無窮的時候 $e^{sqrt{n} }$ 逼近0就好）。比較新的Finite length 性能估計出自Guruswami(2010年以後，很多做代數編碼的都跑去做極化碼了，筆者也算其中一個吧。。)，有興趣的還可以去網上查查Rate dependent性能估計。

以上3點，個人認為是極化碼，在信道編碼中，最核心的創新。當然非點對點通信，信源編碼，保密通信那些領域極化碼的使用，筆者就不怎麼了解了。有問題就問我吧，這個東西我也希望能在國內能找到人討論。

可以上github上搜一些開源的代碼，然後從IEEE上下載一些相關文獻，http://www.polarcodes.com/ || http://ipgdemos.epfl.ch/polarcodes/

請問如果需要研究polar，有推薦的權威教材或學習資料嗎

2008年在國際資訊理論ISIT會議上，Arikan首次提出了信道極化的概念，基於該理論，他給出了人類已知的第一種能夠被嚴格證明達到信道容量的信道編碼方法，並命名為極化碼（Polar Code）。Polar碼具有明確而簡單的編碼及解碼演算法。通過信道編碼學者的不斷努力，當前Polar碼所能達到的糾錯性能超過目前廣泛使用的Turbo碼、LDPC碼。

各位前輩，小弟本科。極化碼的解碼結構是不是基於信道拆分過程，看他們結構圖，差不多。不對的話，希望前輩們指出，並幫小弟回答下，謝謝各位。

朱元說的很形象，我補充一下，極化碼推理論時針對BSC信道和BEC信道，有非普適性的特性，採用SC解碼，List Decoding誤碼率更低，但複雜度更高。整體來說效果不如LDPC.