Polar碼的編碼原理課件

Polar碼的編碼原理王俊南107551500910Polar碼的編碼原理王俊南1所講內(nèi)容：1.Polar碼簡(jiǎn)介2.信道極化2.1信道組合2.2信道分解2.3信道極化定理2.4極化速率3.Polar碼編碼所講內(nèi)容：1.Polar碼簡(jiǎn)介21.Polar碼簡(jiǎn)介

1948年，Shannon在他的開(kāi)創(chuàng)性論文“通信的數(shù)學(xué)理論”中第一次提出了在有噪信道中實(shí)現(xiàn)可靠通信的方法，提出了著名的有擾信道編碼定理，奠定了糾錯(cuò)編碼的基礎(chǔ)。20世紀(jì)50年代初，漢明（Hamming）、斯列賓（Slepian）、普蘭奇（Prange）等人在香農(nóng)的基礎(chǔ)上，設(shè)計(jì)出了一系列的性能優(yōu)異的編譯碼方案，并以此為基礎(chǔ)得出了編碼信道下各種信道情況的香農(nóng)限。香農(nóng)限作為通信系統(tǒng)中的性能極限，具有非常重要的意義。糾錯(cuò)碼的快速發(fā)展，促使了編碼下的香農(nóng)限的提出，也帶動(dòng)了通信領(lǐng)域中設(shè)計(jì)和構(gòu)造逼近香農(nóng)限的糾錯(cuò)碼的研究。目前研究成果最多、比較成熟的逼近香農(nóng)限的糾錯(cuò)碼是LDPC碼和Turbo碼；雖然兩種碼字的性能已十分優(yōu)異，但人們一直堅(jiān)持尋找性能更加好，可以達(dá)到香農(nóng)限并且編譯碼簡(jiǎn)單的編碼方法。Polar碼是由E.Arikan于2007年基于信道極化理論提出的一種線性信道編碼方法，該碼字是迄今發(fā)現(xiàn)的唯一一類能夠達(dá)到香農(nóng)限的編碼方法，并且具有較低的編譯碼復(fù)雜度，當(dāng)編碼長(zhǎng)度為N時(shí)，復(fù)雜度大小為O(NlogN)。Polar碼的核心思想就是信道極化理論，不同的信道對(duì)應(yīng)的極化方法也有區(qū)別。Polar碼自從提出以來(lái)，就一直吸引了眾多學(xué)者的興趣，是這幾年信息領(lǐng)域研究的熱點(diǎn)。1.Polar碼簡(jiǎn)介3

2.1信道極化Polar碼的理論基礎(chǔ)就是信道極化。信道極化包括信道組合和信道分解部分。當(dāng)組合信道的數(shù)目趨于無(wú)窮大時(shí)，則會(huì)出現(xiàn)極化現(xiàn)象：一部分信道將趨于無(wú)噪信道，另外一部分則趨于全噪信道，這種現(xiàn)象就是信道極化現(xiàn)象。無(wú)噪信道的傳輸速率將會(huì)達(dá)到信道容量I(W)，而全噪信道的傳輸速率趨于零。Polar碼的編碼策略正是應(yīng)用了這種現(xiàn)象的特性，利用無(wú)噪信道傳輸用戶有用的信息，全噪信道傳輸約定的信息或者不傳信息。1、信道組合信道組合就是對(duì)給定的B-DMC（Binary-inputDiscreteMemotylessChannel）信道W利用遞歸的方法，來(lái)構(gòu)造一個(gè)組合信道。當(dāng)n=0，W1=W；當(dāng)n=1，就是利用兩個(gè)相互獨(dú)立的信道W1遞歸組合成信道，如圖2.1所示。2.1信道極化4信道W2對(duì)應(yīng)的傳輸概率為：（1.1）當(dāng)n=2時(shí)，利用兩個(gè)獨(dú)立的W2信道來(lái)組合成W4信道：，組合步驟如圖2.2，對(duì)應(yīng)的傳輸概率公式為：（1.2）信道W2對(duì)應(yīng)的傳輸概率為：5在圖2.2中，R4是把序列(s1,s2,s3,s4)映射成v=(s1,s2,s3,s4)的排列操作。信道W4的輸入序列u到信道W的輸入序列X的映射關(guān)系ux可以表示為：→在圖2.2中，R4是把序列(s1,s2,s3,s4)映射成v6并且，。所以，可以得出W4的轉(zhuǎn)移概率表達(dá)式為（1.4）依此類推，可以得出信道組合的一般遞推關(guān)系，如圖2.3，由兩個(gè)獨(dú)立的信道組成信道。的輸入序列首先會(huì)被轉(zhuǎn)化成序列，對(duì)應(yīng)的關(guān)系為，（1.5）其中，1≤i≤N/2。代表一種翻轉(zhuǎn)操作，作用于序列作為信道的輸入序列。（1.4）（1.4）7Polar碼的編碼原理ppt課件8圖2.3中從信道到信道的映射是線性的，定義矩陣表示這種映射關(guān)系，矩陣稱為生成矩陣。則可以推到出之間的轉(zhuǎn)移概率關(guān)系為：（1.6）其中，是比特翻轉(zhuǎn)操作，核心矩陣，符號(hào)?代表Kronecker積（張量積）。對(duì)于矩陣A與B的張量積定義為。假設(shè)A，B分別是m×n，r×s的矩陣，，則（1.7）則，

圖2.3中從信道到信道的映射9（1.8）2、信道分解在完成組合信道之后，信道極化的下一個(gè)步驟是信道分解，把信道分解成N個(gè)二進(jìn)制輸入信道，對(duì)應(yīng)的轉(zhuǎn)移概率定義為（1.9）其中，。由公式（2.9）可知，當(dāng)N=2時(shí)，信道分解的情況為

Polar碼的編碼原理ppt課件10對(duì)應(yīng)的轉(zhuǎn)移概率公式為（1.10）（1.11）當(dāng)N=2時(shí)的信道分解圖如圖2.4所示。圖2.5、2.6分別對(duì)應(yīng)N=4，N=8時(shí)的信道分解方式。從這三幅圖中可以看出，分解過(guò)程也是一個(gè)遞歸的過(guò)程。當(dāng)N=4時(shí)首先被分解成兩個(gè)相互獨(dú)立的信道,然后再將W2分解成兩個(gè)相互獨(dú)立的W。當(dāng)N=8時(shí)，也可依此類推。對(duì)應(yīng)的轉(zhuǎn)移概率公式為11Polar碼的編碼原理ppt課件12Polar碼的編碼原理ppt課件13Polar碼的編碼原理ppt課件14（1.12）（1.13）（1.14）（1.12）15當(dāng)基本信道W是BEC信道的特殊情況下，在滿足一些定理前提下,可通過(guò)如下遞推公式計(jì)算，

（1.15）

（1.16）2.2Polar碼編碼為了利用信道極化的效果，構(gòu)造了一種能夠達(dá)到對(duì)稱信道容量I(W)的編碼方法，稱為Polar碼。Polar碼的基本思想就是：能夠單獨(dú)處理每一個(gè)信道并且使用趨于零的信道來(lái)傳輸信息。那么如何選擇好的信道來(lái)傳輸信息就是Polar碼編碼的關(guān)鍵。當(dāng)基本信道W是BEC信道的特殊情況下，在滿足一些定理前提下,16Polar碼是一種線性分組碼，有效信道的選擇也就對(duì)應(yīng)著生成矩陣的行的選擇。下面首先詳細(xì)介紹Polar碼的編碼過(guò)程。Polar碼是一種線性分組碼，編碼公式與別的線性分組碼類似，由信息序列乘以生成矩陣，具體公式如下，（1.17）其中，是將要傳輸?shù)男畔⑿蛄?，就是生成矩陣，。假設(shè)A是集合的任意子集，公式（1.17）可以寫(xiě)成如下形式，（1.18）其中，矩陣是由A決定的矩陣的子矩陣，是去掉的矩陣，也是的矩陣。如果固定A和，但是任意變量，那么就可以把源序列映射到碼字序列，這種映射關(guān)系稱為陪集編碼（CosetCode）。Polar碼就是陪集碼的例子，由四個(gè)參數(shù)共同決定的陪集碼，N表示碼字的碼長(zhǎng)，K表示信息位的長(zhǎng)度；Polar碼是一種線性分組碼，有效信道的選擇也就對(duì)應(yīng)著生成17A對(duì)應(yīng)著生成矩陣中用來(lái)傳輸有用信息的行，即中的行，并且A中元素個(gè)數(shù)等于K；稱為凍結(jié)位，用來(lái)傳輸固定的信息，即對(duì)應(yīng)著性能較差的比特信道；碼率R=K/N。例，Polar碼的編碼參數(shù)為，則具體的編碼映射關(guān)系為

（1.19）給定源信息序列，則對(duì)應(yīng)的碼字為。由以上Polar碼的編碼理論可知，最重要的就是尋找性能好的信道，即對(duì)應(yīng)值較小的信道，也是序列A中元素的值。下面以N=16為例來(lái)說(shuō)明如何來(lái)選擇信道的。A對(duì)應(yīng)著生成矩陣中用來(lái)傳輸有用信息的行，即18（1.20）（1.20）19取初值，由