A Practical Introduction to Polar Codes

1 A Practical Introduction to Polar Codes (A very simple tutorial for beginners)Harish Vangala, Yi Hong, and Emanuele ViterboMonash University, Australia23 February, 2016 This presentation, and other useful resources such as MATLAB modules can be found (Or, )Harish et al. (Monash Uni.)A Practical intro to PC23-Feb-20161 / 31 Recall: The Coding ProblemHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN 0 1 0 1 1 0 0 1| K |Harish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][1 1 0 0 1]| K |Harish et al.

2 (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][1 1 0 0 1]| K |The Uncoded SystemHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] [1 1 0 0 1][1 1 0 0 1][1 1 0 0 1] [1 1 0 0 1 1 0 1]Harish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimate[1 1 0 0 1]Kbits NbitsHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimate[1 1 0 0 1]Kbits NbitsThe EncodingHarish et al.

3 (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimateThe Decoding[1 1 0 0 1]Kbits NbitsThe EncodingHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimateThe Decoding[1 1 0 0 1]Kbits NbitsThe EncodingThe Coding Systemto achieveShannon capacityHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimateThe Decoding[1 1 0 0 1]Kbits NbitsThe EncodingThe Coding Systemto achieveShannon capacity The Polar Coding System (originally for BI-DMS)1 Encoding2 Decoding3 code -constructionHarish et al.

4 (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimateThe Decoding[1 1 0 0 1]Kbits NbitsThe EncodingThe Coding Systemto achieveShannon capacity The Polar Coding System (originally for BI-DMS)1 Encoding2 Decoding3 code -constructionHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimateThe Decoding[1 1 0 0 1]Kbits NbitsThe EncodingThe Coding Systemto achieveShannon capacity The Polar Coding System (originally for BI-DMS)1 Encoding2 Decoding3 code -constructionHarish et al.

5 (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Recall: The Coding ProblemBI-DMS,BPSK+AWGN [ ][ ] Kbits estimateThe Decoding[1 1 0 0 1]Kbits NbitsThe EncodingThe Coding Systemto achieveShannon capacity The Polar Coding System (originally for BI-DMS)1 Encoding2 Decoding3 code -constructionHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20162 / 31 Polar Codes : A Brief Background First everprovablycapacity achieving Codes [1] Invented by Erdal Ar kan[2], eventually in 2009, using:Channel PolarizationLet a BI-DMS channel with capacity 0 C 1. When a codeword is Tx inNchannel-uses, the channel polarization converts,1 Cfraction of theNbit-channels asnoiseless( their capacity 1)2(1 C) remaining asextremely-noisy( , their capacity 0)}asymptotically, asN Attractive features:1 Fixed, low, and deterministicO(Nlog2N) encoding and decoding2 Explicit construction3 Easy to implement[1] On Symmetric, Binary Input, and Discrete Memoryless Channels (BI-DMS) and later extended to many other channels.

6 [2] Erdal Ar kan, Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Mem-oryless Channels , IEEE Trans. IT, et al. (Monash Uni.)A Practical intro to PC23-Feb-20163 / 31A simplified list of pros and consAdvantagesChallengesSimple encoding & decoding (N) latencyExplicit constructionPoorer performance under SCDcompared to LDPC Codes , at finiteNEasy to implement and high h/w efficiencySolutions are costlier for improvingperformance, comparable to LDPC, atfiniteNHas the best available performanceunder advanced decodersNo error floors in BSC/BECH arish et al.

7 (Monash Uni.)A Practical intro to PC23-Feb-20164 / 31A Practical Introduction to Polar Codes (A very simple tutorial for beginners)Harish Vangala, Yi Hong, and Emanuele ViterboMonash University, Australia23 February, 2016 This presentation, and other useful resources such as MATLAB modules can be found (Or, )Harish et al. (Monash Uni.)A Practical intro to PC23-Feb-20165 / 31A Practical Introduction to Polar Codes1 code Construction2 Encoding3 DecodingHarish et al. (Monash Uni.)A Practical intro to PC23-Feb-20166 / 31A Practical Introduction to Polar Codes1 code Construction2 Encoding3 DecodingHarish et al.

8 (Monash Uni.)A Practical intro to PC23-Feb-20167 / Construction of Polar Codes Simply the selection ofKout ofNindices {0,..,N 1},N= 2n Many algorithms exist, the simplest is to use the recursion:z {2z z2,z2}(its use is justified in[1]and illustrated next) The channel:Additive White Gaussian Channel(AWGN)with zero-mean and varianceN02.(Used for the purposes of illustrations here throughout) With modest changes, the following discussion holds for anycommonly used channel such as BEC, BSC etc.[1] H. Vangala, Y. Hong, and E. Viterbo, A Comparitive Study of Polar code Constructions for the AWGN channel , , 2015 Harish et al.

9 (Monash Uni.)A Practical intro to PC23-Feb-20168 / Construction of Polar Codes [ Ec/N02z z22(2z z2) (2z z2)2(2z z2)2z2 1 STOP when the tree hasNleaves, indexed from top0,..,N 12 Find the leaves holdingKleast values, let their indices beJ,3 OutputJNotes:1 The initialzis the Bhattacharyya parameter of the the BPSK modulation of{ Ec}, and noise-varianceN0/2,z= exp ( Ec/N0)Harish et al. (Monash Uni.)A Practical intro to PC23-Feb-20169 / The code varies with SNR and diff. constructions!1 A very important characteristic of Polar Codes The non-universality code can change significantly with different choices ofdesign-SNRs The choice of a good design-SNR is very important[1]2 More accurate construction algorithms exist in many The best achievable performance is approx.]

10 Same for any constructionalgorithm for at least untilN 64K[1][1] H. Vangala, Y. Hong, and E. Viterbo, A Comparitive Study of Polar code Constructions forthe AWGN channel , , 2015 Harish et al. (Monash Uni.)A Practical intro to PC23-Feb-201610 / Matlab session Using the provided matlab code ,[1]one can perform the constructionof Polar Codes in matlab, simply as follows.>> N=128; K=64; Ec=1; N0=2;% Blocklength, message-length, BPSK energy, and AWGN noise ( 2=N02)>> initPC(N,K,Ec,N0);% A global structure of parameters is formed and made implicitlyavailable for encoding/decoding[1] et al. (Monash Uni.)