Polar Codes

Mohammad Rowshan, PhD, (Member, IEEE) received the B.Eng. degree (Hons.) in electrical engineering from the University of Nottingham in 2015 (ranked 1), the M.Sc. degree in electrical engineering from The Hong Kong University of Science and Technology in 2016, and the Ph.D. degree in electrical engineering from Monash University in 2021. He is currently an Engineering ECA Fellow with the School of Electrical Engineering and Telecommunications, University of New South Wales, Sydney, Australia, where he serves as a Researcher, a Lecturer, and a Supervisor/Mentor. He also serves as a reviewer of IEEE conferences and journals, and a TPC member of conferences. Emanuele Viterbo, PhD, is Professor in the Department of Electrical and Computer Systems Engineering, Monash University, Melbourne, Australia. He is a Fellow of the IEEE and an ISI Highly Cited Researcher (2009, Thompson Reuters). He has published extensively on a range of subjects related to channel coding and wireless communication.

• About the Authors xvPreface xviiAcknowledgment xxi1 Introduction 11.1 Reliable Transmission over Noisy Channels 21.2 Channel Models 41.2.1 Binary Symmetric Channel (BSC) 41.2.2 Binary Erasure Channel (BEC) 51.2.3 Additive White Gaussian Noise Channel (AWGN) 61.2.4 Fading Channel 71.3 Fundamentals of Information Theory 71.3.1 The Meaning of Information 81.3.2 Discrete Entropy 91.3.3 Properties of the Discrete Entropy 101.3.4 Mutual Information 111.3.5 Bhattacharyya Parameter 121.4 Channel Capacity and Channel Coding Theorem 131.5 Block Error Rate for Finite Length Codes 151.6 Shannon Limit on Power Efficiency 171.7 Time and Space Complexity 191.8 Historical Milestones in Channel Coding 201.9 Why Study Polar Codes? 241.9.1 How Do Polar Codes Compare with Other Codes? 25Exercises 26Bibliographic Notes 27Bibliography 282 Linear Codes 292.1 Generator and Parity-Check Matrices 292.2 Distance, Weight, and Bounds 322.3 Syndrome Decoding 352.4 Repetition and Single Parity Check Codes 372.5 Reed–Muller Codes 372.5.1 Boolean Functions and Boolean Polynomials 382.5.1.1 Evaluation of Monomials 382.5.1.2 Boolean Products 402.5.1.3 Boolean Polynomials 402.5.2 Submatrix of Binary Walsh–Hadamard Matrix 412.5.3 Plotkin’s Construction 422.6 Cyclic Codes 452.6.1 Arithmetic of Polynomials 452.6.2 Generator Polynomial and Encoding 462.6.3 Cyclic Redundancy Check (CRC) for Error Detection 502.7 Convolutional Codes 522.7.1 Encoding of Convolutional Codes 532.7.1.1 Encoding with Sequential Logic 532.7.1.2 Impulse Response and Convolution 532.7.1.3 Generator Matrix 542.7.2 Termination, Truncation, and Tail-Biting 552.7.3 Tree and Trellis 562.8 Concatenated Codes 58Exercises 61Bibliographic Notes 63Bibliography 633 Fundamentals of Soft-Decision Decoding 653.1 MAP/ML Decoding and Likelihood 663.1.1 Log-Likelihood Ratio (LLR) 683.1.2 LLR Algebra 693.1.3 Maximum-Likelihood (ML) Bound 703.1.4 Union Bound 703.2 Reliability-Based Universal Decoding 733.3 Recursive Decoding 753.4 Message-Passing (MP) Decoding 783.4.1 Factorization and Factor Graph 783.4.2 Message Passing 793.4.3 The Effect of Cycles on Message Passing 823.4.3.1 Scenario with Cycles 833.5 Tree/Trellis-Based Search Decoding 843.5.1 Sequential Decoding 843.5.1.1 Fano Algorithm 853.5.1.2 Stack Decoding 853.5.1.3 Path Metric 863.5.1.4 Computational Cutoff-Rate 873.5.2 List Decoding 883.5.3 Trellis-Based Viterbi Decoding 883.5.4 Lattice-Based Sphere Decoding 89Exercises 89Bibliographic Notes 89Bibliography 914 Polar Codes 954.1 Introduction 964.2 Basic Channel Transform 974.3 Recursive Channel Transformation 994.4 Channel Polarization 1034.5 Code Construction Based on Z (W(i)N) 1074.6 G N -Coset Codes 1104.7 Successive Cancellation (SC) Decoding 1104.8 Performance of Polar Codes Under SC Decoding 112Exercises 117Bibliographical Notes 117Bibliography 1185 Properties of Polar Codes 1215.1 Polar Transform 1225.2 Permutation Matrix 1235.3 Generator and Parity Check Matrices 1255.4 Systematic Polar Codes 1265.5 Reed–Muller Codes Versus Polar Codes 1285.6 Partial Order of Sub-channels 1295.7 Minimum Distance of Polar Codes 1325.8 Minimum Weight Codewords 1335.8.1 Construction of Minimum Weight Codewords 1335.8.1.1 M-Construction 1355.8.2 Enumeration of Minimum Weight Codewords 1395.9 Exponent of Polarizing Matrix 1405.10 Polar Codes with Large and Mixed Kernels 1425.10.1 Large Kernel Polar Codes 1425.10.2 Mixed/Multi-Kernel Polar Codes 1425.11 Properties of SC Decoding 1435.11.1 Updating Intermediate LLRs 1445.11.2 Updating Partial Sums 1455.11.3 Partial Rewind: Updating LLRs and Partial Sums 1475.12 Partial Sums and Polar Constituent Codes 149Exercises 150Bibliographical Notes 151Bibliography 1526 Construction of Polar Codes 1556.1 Code Construction 1566.2 Channel-Dependent Code Construction 1576.2.1 Density Evolution 1576.2.2 Density Evolution with Gaussian Approximation 1586.3 Channel-Independent Code Construction 1616.3.1 Universal Partial Order (UPO) 1616.3.1.1 Nested and Symmetric Properties 1636.3.2 Polarization Weight (PW) 1646.4 5G Code Construction 1666.5 Code Construction for ML Decoding 1666.5.1 RM-Polar Codes 1686.6 Pre-transformed Polar Codes 1706.6.1 CRC-Polar Codes 1706.6.1.1 CRC Bits in 5G 1716.6.2 Parity-Check (PC)-Polar Codes 1726.6.2.1 PC Bits in 5G 1736.6.3 PAC Codes 1746.6.3.1 Minimum Distance of PAC Codes 1756.6.3.2 Invariant Coset 1766.6.3.3 Lower Bound for Awmin (PG, A) 177Exercises 178Bibliographic Notes 178Bibliography 1817 Monomial Codes and Permutations 1857.1 Monomial Codes 1857.1.1 Evaluation of a Monomial 1867.1.2 Reed–Muller Codes 1877.2 Polar Codes as Monomial Codes 1887.2.1 Codeword as a Polynomial 1897.3 Decreasing Monomial Codes 1907.3.1 Partial Order 1907.4 Permutation Group 1927.4.1 Symmetric Permutation Group 1937.4.2 Lower Triangular Affine (LTA) Permutation Group 1947.4.3 Orbit of a Monomial, Orb(f) 1967.4.4 Restricted LTA Transform/Permutation Group 1977.4.5 Block Lower Triangular Affine (BLTA) Permutation Group 1997.5 Stabilizer Group 2027.5.1 Stabilizer Group Structure 2027.6 Permutation Ensemble Decoding 2037.7 Enumeration of Min-Weight Codewords 2077.8 Structure of Codewords with Larger Weights 209Exercises 214Bibliographical Notes 215Bibliography 2158 List Decoding of Polar Codes 2178.1 SC List Decoding 2178.1.1 Error Events in SCL Decoding 2228.1.2 List Size in SCL Decoding 2228.1.3 List Decoding of CRC-Polar Codes 2248.1.4 List Decoding of PAC Codes 2258.2 Iterative SC-Based Decoding 2268.2.1 Adaptive List Decoding 2278.2.2 SC Decoding with Bit-Flipping 2288.2.3 SCL Decoding with Diverse Path-Selection 2298.2.4 SC/SCL Decoding with Perturbation 2298.2.5 Partial Rewind of SC and SCL Decoding 230Exercises 235Bibliographical Notes 236Bibliography 2379 Fast SC-Based Decoding 2419.1 SC Decoding via Special Nodes 2419.2 Rate-1 Node 2439.3 Rate-0 Node 2439.4 Rate-C Node 2449.5 Repetition Nodes 2449.5.1 General Repetition Node 2449.6 Parity Check Nodes 2469.6.1 General Parity Check Node 2479.7 Fast SC List Decodings 250Exercises 250Bibliographical Notes 251Bibliography 25110 Alternative Decoding Algorithms 25310.1 Belief Propagation (BP) Decoding 25410.2 Sequential Decoding 26110.3 Sphere Decoding 26310.4 Reliability-Based Generic Decoding 26410.4.1 Ordered Statistics Decoding (OSD) 26410.4.2 Guessing Random Additive Noise Decoding (GRAND) 268Exercises 272Bibliographical Notes 273Bibliography 27611 Rate-Compatible Polar Codes 28111.1 Modification of Block Codes 28211.1.1 Shortened Codes 28211.1.2 Punctured Codes 28211.2 Punctured Polar Codes 28411.3 Shortened Polar Codes 28511.4 Rate-Matching in 5G NR 28711.4.1 The Mother Code and Rate-Matching Choice 28811.4.2 Subblock Interleaving 28811.4.3 Bit-Selection 289Exercises 290Bibliographical Notes 290Bibliography 29112 Polar-Coded Modulation 29312.1 Higher-Order Modulation 29412.1.1 Constellations and Distance Between Signal Points 29412.1.2 Binary Labeling of Signal Points 29612.2 Multilevel-Coded Modulation 29612.2.1 Labeling Signal Points in S by Partition Chain 29712.2.2 Choosing m Binary Component Codes 29812.2.3 Interleaving Component Codes and Mapping 29912.2.4 Multistage Decoding of BCM Codes 30112.3 Bit-Interleaved Polar-Coded Modulation 30212.4 Bit-Interleaving in 5G NR 304Exercises 306Bibliographical Notes 306Bibliography 30713 Performance Comparisons 30913.1 Error Correction Performance of Polar Codes 30913.2 Performance Comparison of Turbo, LDPC, and Polar Codes 315Bibliographical Notes 317Bibliography 31714 5G New Radio (NR) Polar Coding with MATLAB ® 31914.1 Polar Encoding 31914.1.1 Uplink 32014.1.2 Downlink 32014.2 Rate-Matching and Rate-Recovery 32214.2.1 Modulation and Channel Effect 32314.3 Polar Decoding 32314.4 BLER Versus SNR of a Code—Full Script 324Appendix A Conceptual Channels in 5G New Radio 329Appendix B Channel Coding from 2G to 5G 335B. 1 AJourneyfrom2Gto5G 335B. 2 Channel Coding in 2G 335B. 3 Channel Coding in 3G 337B.3. 1 Block Segmentation and Rate Matching 337B. 4 Channel Coding in 4G 338B. 5 Channel Coding in 5G 339Bibliography 340Appendix C Scripts 341C. 1 Meta-Converse Bound with a Normal Approximation 341C. 2 Shannon Limit 342C. 3 Standard Array in Syndrome Decoding 342C. 4 Polar Sequence in 5G 343C. 5 Calculating CRC Bits 345C. 6 Polar Transform and Its Permutation Matrix 345C. 7 Polar Code Construction 346C. 8 Row Structure of Minimum-Weight Codewords 349C. 9 Closed-Form Weight Enumeration 350Index 353