Polar Codes: From Theory to Practice(IEEE Series on Digital & Mobile Communication)

Understand a cutting-edge new class of error correction codes with this introduction Channel coding is a pivotal technique employed to account for potential errors due to channel noise or interference by adding layers of redundancy to information prior to transmission or storage. Should errors appear in the transmitted sequence upon reaching its destination, they can be corrected with reference to the redundant layers. Polar codes are a new class of error correction codes that provably achieve the capacity of binary discrete memoryless channels. Their distinct advantages have led to their incorporation in the logical control channels of the fifth generation of wireless communications (5G). Possessing robust and competitive error correction capabilities for short and medium-length codes positions them strategically to fulfill a pivotal role in various communication systems as we move towards the sixth generation of wireless communication (6G) and beyond. Polar Codes provides a thorough, accessible overview of this new class of codes and its applications. Beginning with the foundational theories underlying polar codes, it guides readers through the construction of polar codes, their variants, and their encoding and decoding processes. The result is a must-have for coding researchers and professionals looking to develop an edge in the wireless communications of the future. Polar Codes readers will also find: Continuous connections between discussed concepts and current 5G standards Snippets of code in MATLAB/Python to illustrate key tools End of chapter problems and bibliographical notes to facilitate learning and provide references for further reading. Polar Codes is ideal for graduate students and researchers in coding and information theory, as well as engineers working in communications and related industries.

Table of Contents:
About the Authors xv Preface xvii Acknowledgment xxi 1 Introduction 1 1.1 Reliable Transmission over Noisy Channels 2 1.2 Channel Models 4 1.2.1 Binary Symmetric Channel (BSC) 4 1.2.2 Binary Erasure Channel (BEC) 5 1.2.3 Additive White Gaussian Noise Channel (AWGN) 6 1.2.4 Fading Channel 7 1.3 Fundamentals of Information Theory 7 1.3.1 The Meaning of Information 8 1.3.2 Discrete Entropy 9 1.3.3 Properties of the Discrete Entropy 10 1.3.4 Mutual Information 11 1.3.5 Bhattacharyya Parameter 12 1.4 Channel Capacity and Channel Coding Theorem 13 1.5 Block Error Rate for Finite Length Codes 15 1.6 Shannon Limit on Power Efficiency 17 1.7 Time and Space Complexity 19 1.8 Historical Milestones in Channel Coding 20 1.9 Why Study Polar Codes? 24 1.9.1 How Do Polar Codes Compare with Other Codes? 25 Exercises 26 Bibliographic Notes 27 Bibliography 28 2 Linear Codes 29 2.1 Generator and Parity-Check Matrices 29 2.2 Distance, Weight, and Bounds 32 2.3 Syndrome Decoding 35 2.4 Repetition and Single Parity Check Codes 37 2.5 Reed–Muller Codes 37 2.5.1 Boolean Functions and Boolean Polynomials 38 2.5.1.1 Evaluation of Monomials 38 2.5.1.2 Boolean Products 40 2.5.1.3 Boolean Polynomials 40 2.5.2 Submatrix of Binary Walsh–Hadamard Matrix 41 2.5.3 Plotkin’s Construction 42 2.6 Cyclic Codes 45 2.6.1 Arithmetic of Polynomials 45 2.6.2 Generator Polynomial and Encoding 46 2.6.3 Cyclic Redundancy Check (CRC) for Error Detection 50 2.7 Convolutional Codes 52 2.7.1 Encoding of Convolutional Codes 53 2.7.1.1 Encoding with Sequential Logic 53 2.7.1.2 Impulse Response and Convolution 53 2.7.1.3 Generator Matrix 54 2.7.2 Termination, Truncation, and Tail-Biting 55 2.7.3 Tree and Trellis 56 2.8 Concatenated Codes 58 Exercises 61 Bibliographic Notes 63 Bibliography 63 3 Fundamentals of Soft-Decision Decoding 65 3.1 MAP/ML Decoding and Likelihood 66 3.1.1 Log-Likelihood Ratio (LLR) 68 3.1.2 LLR Algebra 69 3.1.3 Maximum-Likelihood (ML) Bound 70 3.1.4 Union Bound 70 3.2 Reliability-Based Universal Decoding 73 3.3 Recursive Decoding 75 3.4 Message-Passing (MP) Decoding 78 3.4.1 Factorization and Factor Graph 78 3.4.2 Message Passing 79 3.4.3 The Effect of Cycles on Message Passing 82 3.4.3.1 Scenario with Cycles 83 3.5 Tree/Trellis-Based Search Decoding 84 3.5.1 Sequential Decoding 84 3.5.1.1 Fano Algorithm 85 3.5.1.2 Stack Decoding 85 3.5.1.3 Path Metric 86 3.5.1.4 Computational Cutoff-Rate 87 3.5.2 List Decoding 88 3.5.3 Trellis-Based Viterbi Decoding 88 3.5.4 Lattice-Based Sphere Decoding 89 Exercises 89 Bibliographic Notes 89 Bibliography 91 4 Polar Codes 95 4.1 Introduction 96 4.2 Basic Channel Transform 97 4.3 Recursive Channel Transformation 99 4.4 Channel Polarization 103 4.5 Code Construction Based on Z (W(i)N) 107 4.6 G N -Coset Codes 110 4.7 Successive Cancellation (SC) Decoding 110 4.8 Performance of Polar Codes Under SC Decoding 112 Exercises 117 Bibliographical Notes 117 Bibliography 118 5 Properties of Polar Codes 121 5.1 Polar Transform 122 5.2 Permutation Matrix 123 5.3 Generator and Parity Check Matrices 125 5.4 Systematic Polar Codes 126 5.5 Reed–Muller Codes Versus Polar Codes 128 5.6 Partial Order of Sub-channels 129 5.7 Minimum Distance of Polar Codes 132 5.8 Minimum Weight Codewords 133 5.8.1 Construction of Minimum Weight Codewords 133 5.8.1.1 M-Construction 135 5.8.2 Enumeration of Minimum Weight Codewords 139 5.9 Exponent of Polarizing Matrix 140 5.10 Polar Codes with Large and Mixed Kernels 142 5.10.1 Large Kernel Polar Codes 142 5.10.2 Mixed/Multi-Kernel Polar Codes 142 5.11 Properties of SC Decoding 143 5.11.1 Updating Intermediate LLRs 144 5.11.2 Updating Partial Sums 145 5.11.3 Partial Rewind: Updating LLRs and Partial Sums 147 5.12 Partial Sums and Polar Constituent Codes 149 Exercises 150 Bibliographical Notes 151 Bibliography 152 6 Construction of Polar Codes 155 6.1 Code Construction 156 6.2 Channel-Dependent Code Construction 157 6.2.1 Density Evolution 157 6.2.2 Density Evolution with Gaussian Approximation 158 6.3 Channel-Independent Code Construction 161 6.3.1 Universal Partial Order (UPO) 161 6.3.1.1 Nested and Symmetric Properties 163 6.3.2 Polarization Weight (PW) 164 6.4 5G Code Construction 166 6.5 Code Construction for ML Decoding 166 6.5.1 RM-Polar Codes 168 6.6 Pre-transformed Polar Codes 170 6.6.1 CRC-Polar Codes 170 6.6.1.1 CRC Bits in 5G 171 6.6.2 Parity-Check (PC)-Polar Codes 172 6.6.2.1 PC Bits in 5G 173 6.6.3 PAC Codes 174 6.6.3.1 Minimum Distance of PAC Codes 175 6.6.3.2 Invariant Coset 176 6.6.3.3 Lower Bound for Awmin (PG, A) 177 Exercises 178 Bibliographic Notes 178 Bibliography 181 7 Monomial Codes and Permutations 185 7.1 Monomial Codes 185 7.1.1 Evaluation of a Monomial 186 7.1.2 Reed–Muller Codes 187 7.2 Polar Codes as Monomial Codes 188 7.2.1 Codeword as a Polynomial 189 7.3 Decreasing Monomial Codes 190 7.3.1 Partial Order 190 7.4 Permutation Group 192 7.4.1 Symmetric Permutation Group 193 7.4.2 Lower Triangular Affine (LTA) Permutation Group 194 7.4.3 Orbit of a Monomial, Orb(f) 196 7.4.4 Restricted LTA Transform/Permutation Group 197 7.4.5 Block Lower Triangular Affine (BLTA) Permutation Group 199 7.5 Stabilizer Group 202 7.5.1 Stabilizer Group Structure 202 7.6 Permutation Ensemble Decoding 203 7.7 Enumeration of Min-Weight Codewords 207 7.8 Structure of Codewords with Larger Weights 209 Exercises 214 Bibliographical Notes 215 Bibliography 215 8 List Decoding of Polar Codes 217 8.1 SC List Decoding 217 8.1.1 Error Events in SCL Decoding 222 8.1.2 List Size in SCL Decoding 222 8.1.3 List Decoding of CRC-Polar Codes 224 8.1.4 List Decoding of PAC Codes 225 8.2 Iterative SC-Based Decoding 226 8.2.1 Adaptive List Decoding 227 8.2.2 SC Decoding with Bit-Flipping 228 8.2.3 SCL Decoding with Diverse Path-Selection 229 8.2.4 SC/SCL Decoding with Perturbation 229 8.2.5 Partial Rewind of SC and SCL Decoding 230 Exercises 235 Bibliographical Notes 236 Bibliography 237 9 Fast SC-Based Decoding 241 9.1 SC Decoding via Special Nodes 241 9.2 Rate-1 Node 243 9.3 Rate-0 Node 243 9.4 Rate-C Node 244 9.5 Repetition Nodes 244 9.5.1 General Repetition Node 244 9.6 Parity Check Nodes 246 9.6.1 General Parity Check Node 247 9.7 Fast SC List Decodings 250 Exercises 250 Bibliographical Notes 251 Bibliography 251 10 Alternative Decoding Algorithms 253 10.1 Belief Propagation (BP) Decoding 254 10.2 Sequential Decoding 261 10.3 Sphere Decoding 263 10.4 Reliability-Based Generic Decoding 264 10.4.1 Ordered Statistics Decoding (OSD) 264 10.4.2 Guessing Random Additive Noise Decoding (GRAND) 268 Exercises 272 Bibliographical Notes 273 Bibliography 276 11 Rate-Compatible Polar Codes 281 11.1 Modification of Block Codes 282 11.1.1 Shortened Codes 282 11.1.2 Punctured Codes 282 11.2 Punctured Polar Codes 284 11.3 Shortened Polar Codes 285 11.4 Rate-Matching in 5G NR 287 11.4.1 The Mother Code and Rate-Matching Choice 288 11.4.2 Subblock Interleaving 288 11.4.3 Bit-Selection 289 Exercises 290 Bibliographical Notes 290 Bibliography 291 12 Polar-Coded Modulation 293 12.1 Higher-Order Modulation 294 12.1.1 Constellations and Distance Between Signal Points 294 12.1.2 Binary Labeling of Signal Points 296 12.2 Multilevel-Coded Modulation 296 12.2.1 Labeling Signal Points in S by Partition Chain 297 12.2.2 Choosing m Binary Component Codes 298 12.2.3 Interleaving Component Codes and Mapping 299 12.2.4 Multistage Decoding of BCM Codes 301 12.3 Bit-Interleaved Polar-Coded Modulation 302 12.4 Bit-Interleaving in 5G NR 304 Exercises 306 Bibliographical Notes 306 Bibliography 307 13 Performance Comparisons 309 13.1 Error Correction Performance of Polar Codes 309 13.2 Performance Comparison of Turbo, LDPC, and Polar Codes 315 Bibliographical Notes 317 Bibliography 317 14 5G New Radio (NR) Polar Coding with MATLAB ® 319 14.1 Polar Encoding 319 14.1.1 Uplink 320 14.1.2 Downlink 320 14.2 Rate-Matching and Rate-Recovery 322 14.2.1 Modulation and Channel Effect 323 14.3 Polar Decoding 323 14.4 BLER Versus SNR of a Code—Full Script 324 Appendix A Conceptual Channels in 5G New Radio 329 Appendix B Channel Coding from 2G to 5G 335 B. 1 AJourneyfrom2Gto5G 335 B. 2 Channel Coding in 2G 335 B. 3 Channel Coding in 3G 337 B.3. 1 Block Segmentation and Rate Matching 337 B. 4 Channel Coding in 4G 338 B. 5 Channel Coding in 5G 339 Bibliography 340 Appendix C Scripts 341 C. 1 Meta-Converse Bound with a Normal Approximation 341 C. 2 Shannon Limit 342 C. 3 Standard Array in Syndrome Decoding 342 C. 4 Polar Sequence in 5G 343 C. 5 Calculating CRC Bits 345 C. 6 Polar Transform and Its Permutation Matrix 345 C. 7 Polar Code Construction 346 C. 8 Row Structure of Minimum-Weight Codewords 349 C. 9 Closed-Form Weight Enumeration 350 Index 353

About the Author :
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.