State Key Laboratory of Integrated Services Networks 国家重点实验室 Polar Codes 西安电子科技大学SN 白宝明 2017.11.13
State Key Laboratory of Integrated Services Networks Polar Codes 西安电子科技大学ISN 白宝明 2017.11.13
N 国家重点实验室 Outline o Introduction o Channel Polarization o Construction Encoding Decoding o Performance o Open Problems 2
Outline Introduction Channel Polarization Construction Encoding & Decoding Performance Open Problems 2
国家重点实验室 Introduction Polar codes,invented by Erdal Arikan in 2008, are the first codes to provably achieve capacity 。特点： >Capacity-achieving for symmetric binary-input memoryless channels(包括Bl-AWGN,BSC,BEC) >Low encoding and decoding complexity:O(Nlog N) >Block error probability is roughly O(2-N) And this performance guarantee is analytical. >For symmetric channels,code construction is deterministic. That is,the above statements are true not only for ensembles of codes,but also for individual polar codes
Introduction Polar codes, invented by Erdal Arikan in 2008, are the first codes to provably achieve capacity. 特点： Capacity-achieving for symmetric binary-input memoryless channels (包括BI-AWGN, BSC, BEC) Low encoding and decoding complexity: Block error probability is roughly And this performance guarantee is analytical. For symmetric channels, code construction is deterministic. That is, the above statements are true not only for ensembles of codes, but also for individual polar codes. 3 ON N ( log ) (2 ) N O −
国家重点实验室 核心思想 o Channel Polarization >Create extreme channels:Either noiseless or useless. o Channel coding problem trivial for these two types of channels >Perfect channels:C(W)=1,the output Y determines the input X Useless channels:C(W)=0,the output Y is independent of the input X o Channel polarization is a technique to convert any binary-input channel into a mixture of binary-input extreme channels 。极化方法 >信道合并与分裂（由编译码共同完成） 4
核心思想 Channel Polarization Create extreme channels: Either noiseless or useless. Channel coding problem trivial for these two types of channels Perfect channels: C(W)=1, the output Y determines the input X Useless channels: C(W)=0, the output Y is independent of the input X Channel polarization is a technique to convert any binary-input channel into a mixture of binary-input extreme channels 极化方法 信道合并与分裂（由编译码共同完成） 4
N The Channel 国家重点实验室 Let w:be a binary-input discrete-memoryless channel X W >Input alphabet:=0,1 >Transition probabilities:W(ylx),x∈X,y∈y o Two independent uses of the channel W xi>w →Y xw→g Nindependent copies of W:WN:XN->YN w')=IIwG,I) 5
The Channel Let be a binary-input discrete-memoryless channel Input alphabet: Transition probabilities: , , Two independent uses of the channel W N independent copies of W: 5 X1 Y1 X2 Y2 W W W : → ={0,1} Wyx ( ) | x∈ y ∈ : NN N WX Y → 1 1 1 ( | ) (|) N N N N i i i W y x Wy x = =∏