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
