1、Polar碼的編碼原理,王俊南 107551500910,所講內(nèi)容：,1.Polar碼簡介 2.信道極化 2.1信道組合 2.2信道分解 2.3信道極化定理 2.4極化速率 3.Polar碼編碼,1.Polar碼簡介 1948 年，Shannon 在他的開創(chuàng)性論文“通信的數(shù)學理論”中第一次提出了在有噪信道中實現(xiàn)可靠通信的方法，提出了著名的有擾信道編碼定理，奠定了糾錯編碼的基礎(chǔ)。20 世紀 50 年代初，漢明（Hamming）、斯列賓（Slepian）、普蘭奇（Prange）等人在香農(nóng)的基礎(chǔ)上，設(shè)計出了一系列的性能優(yōu)異的編譯碼方案，并以此為基礎(chǔ)得出了編碼信道下各種信道情況的香農(nóng)限。香農(nóng)限作為通信

2、系統(tǒng)中的性能極限，具有非常重要的意義。糾錯碼的快速發(fā)展，促使了編碼下的香農(nóng)限的提出，也帶動了通信領(lǐng)域中設(shè)計和構(gòu)造逼近香農(nóng)限的糾錯碼的研究。目前研究成果最多、比較成熟的逼近香農(nóng)限的糾錯碼是 LDPC 碼和 Turbo 碼；雖然兩種碼字的性能已十分優(yōu)異，但人們一直堅持尋找性能更加好，可以達到香農(nóng)限并且編譯碼簡單的編碼方法。 Polar碼是由E. Arikan于2007年基于信道極化理論提出的一種線性信道編碼方法，該碼字是迄今發(fā)現(xiàn)的唯一一類能夠達到香農(nóng)限的編碼方法，并且具有較低的編譯碼復雜度，當編碼長度為N時，復雜度大小為 O ( NlogN)。Polar碼的核心思想就是信道極化理論，不同的信道對應(yīng)

3、的極化方法也有區(qū)別。Polar碼自從提出以來，就一直吸引了眾多學者的興趣，是這幾年信息領(lǐng)域研究的熱點。,2.1 信道極化 Polar 碼的理論基礎(chǔ)就是信道極化。信道極化包括信道組合和信道分解部分。當組合信道的數(shù)目趨于無窮大時，則會出現(xiàn)極化現(xiàn)象：一部分信道將趨于無噪信道，另外一部分則趨于全噪信道，這種現(xiàn)象就是信道極化現(xiàn)象。無噪信道的傳輸速率將會達到信道容量 I (W )，而全噪信道的傳輸速率趨于零。Polar 碼的編碼策略正是應(yīng)用了這種現(xiàn)象的特性，利用無噪信道傳輸用戶有用的信息，全噪信道傳輸約定的信息或者不傳信息。 1、信道組合 信道組合就是對給定的B-DMC（Binary-input Disc

4、rete Memotyless Channel）信道W利用遞歸的方法，來構(gòu)造一個組合信道 。當n=0，W 1= W；當n=1，就是利用兩個相互獨立的信道W 1遞歸組合成信道 ，如圖2.1所示。,信道W2對應(yīng)的傳輸概率為： （1.1） 當n=2時，利用兩個獨立的W2信道來組合成W4信道： ，組合步驟如圖2.2，對應(yīng)的傳輸概率公式為： （1.2）,在圖2.2中，R4是把序列(s1,s2,s3,s4)映射成v =(s1,s2,s3,s4)的排列操作。信道W4的輸入序列u 到信道W 的輸入序列X 的映射關(guān)系u x 可以表示為：,并且， 。所以，可以得出W4的轉(zhuǎn)移概率表達式為 （1.4） 依此類推，可以

5、得出信道組合的一般遞推關(guān)系，如圖2.3，由兩個獨立的信道 組成信道 。 的輸入序列 首先會被轉(zhuǎn)化成 序列，對應(yīng)的關(guān)系為， （1.5） 其中，1 i N/ 2。 代表一種翻轉(zhuǎn)操作，作用于序列 作為信道 的輸入序列。,（1.4）,圖2.3中從信道 到信道 的映射 是線性的，定義矩陣 表示這種映射關(guān)系，矩陣 稱為生成矩陣。則可以推到出 之間的轉(zhuǎn)移概率關(guān)系為： （1.6） 其中， 是比特翻轉(zhuǎn)操作，核心矩陣 ，符號 代表Kronecker積（張量積）。對于矩陣A與B的張量積定義為 。假設(shè)A，B分別是m n，r s的矩陣， ，則 （1.7） 則 ，,（1.8） 2、信道分解 在完成組合信道 之后，信道極化

6、的下一個步驟是信道分解，把信道 分解成N個二進制輸入信道 ，對應(yīng)的轉(zhuǎn)移概率定義為 （1.9） 其中， 。由公式（2.9）可知，當N=2時，信道分解的情況為,對應(yīng)的轉(zhuǎn)移概率公式為,（1.10） （1.11）,當 N=2 時的信道分解圖如圖 2.4 所示。圖 2.5、2.6 分別對應(yīng) N=4，N=8 時的信道分解方式。從這三幅圖中可以看出，分解過程也是一個遞歸的過程。當 N=4 時 首先被分解成兩個相互獨立的信道 ,然后再將W2分解成兩個相互獨立的W。當 N=8 時，也可依此類推。,（1.12） （1.13） （1.14）,當基本信道W是BEC信道的特殊情況下，在滿足一些定理前提下, 可通過如下遞

7、推公式計算， （1.15） （1.16） 2.2 Polar 碼編碼 為了利用信道極化的效果，構(gòu)造了一種能夠達到對稱信道容量 I (W )的編碼方法，稱為 Polar 碼。Polar 碼的基本思想就是：能夠單獨處理每一個信道 并且使用 趨于零的信道來傳輸信息。那么如何選擇好的信道來傳輸信息就是 Polar 碼編碼的關(guān)鍵。,Polar 碼是一種線性分組碼，有效信道的選擇也就對應(yīng)著生成矩陣的行的選擇。下面首先詳細介紹 Polar 碼的編碼過程。 Polar 碼是一種線性分組碼，編碼公式與別的線性分組碼類似，由信息序列乘以生成矩陣，具體公式如下， （1.17） 其中， 是將要傳輸?shù)男畔⑿蛄校?就是生

8、成矩陣， 。 假設(shè) A 是集合 的任意子集，公式（1.17）可以寫成如下形式， （1.18） 其中，矩陣 是由 A 決定的矩陣 的子矩陣， 是 去掉 的矩陣，也是 的矩陣。 如果固定 A 和 ，但 是任意變量，那么就可以把源序列 映射到碼字序列 ，這種映射關(guān)系稱為陪集編碼（Coset Code）。Polar 碼就是陪集碼的例子，由四個參數(shù) 共同決定的陪集碼，N 表示碼字的碼長，K 表示信息位的長度；,A 對應(yīng)著生成矩陣 中用來傳輸有用信息的行，即 中的行，并且 A 中元素個數(shù)等于 K； 稱為凍結(jié)位，用來傳輸固定的信息，即對應(yīng)著性能較差的比特信道；碼率 R=K/N。 例，Polar 碼的編碼參數(shù)為 ，則具體的編碼映射關(guān)系為 （1.19） 給定源信息序列 ，則對應(yīng)的碼字為 。 由以上 Polar 碼的編碼理論可知，最重要的就是尋找性能好的信道，即對應(yīng) 值較小的信道，也是序列 A 中元素的值。下面以 N=16 為例來說明如何來選擇信道的。,（1.20）,取初值 ，由公式（2.15）和（2.16）可計算出 ，具體各項值是： 。對 序列進