High-Speed Decoders for Polar Codes (eBook)

Preface 6
Origin 6
Scope 6
Organization 8
Audience 9
Acknowledgements 10
Contents 11
Acronyms 14
1 Polar Codes 16
1.1 Construction 16
1.2 Tree Representation 18
1.3 Systematic Coding 18
1.4 Successive-Cancellation Decoding 19
1.5 Simplified Successive-Cancellation Decoding 20
1.5.1 Rate-0 Nodes 20
1.5.2 Rate-1 Nodes 20
1.5.3 Rate-R Nodes 20
1.6 Fast-SSC Decoding 21
1.6.1 Repetition Codes 21
1.6.2 SPC Codes 21
1.6.3 Repetition-SPC Codes 22
1.6.4 Other Operations 22
1.7 Other SC-Based Decoding Algorithms 22
1.7.1 ML-SSC Decoding 23
1.7.2 Hybrid ML-SC Decoding 23
1.8 Other Decoding Algorithms 23
1.8.1 Belief-Propagation Decoding 24
1.8.2 List-Based Decoding 25
1.9 SC-Based Decoder Hardware Implementations 26
1.9.1 Processing Element for SC Decoding 26
1.9.2 Semi-Parallel Decoder 26
1.9.3 Two-Phase Decoder 26
1.9.4 Processor-Like Decoder or the Original Fast-SSC Decoder 27
1.9.5 Implementation Results 28
2 Fast Low-Complexity Hardware Decoders for Low-RatePolar Codes 29
2.1 Introduction 29
2.2 Altering the Code Construction 30
2.2.1 Original Construction 30
2.2.2 Altered Polar Code Construction 31
2.2.3 Proposed Altered Construction 32
2.2.3.1 Human-Guided Criteria 32
2.2.3.2 Example Results 34
2.3 New Constituent Decoders 36
2.4 Implementation 37
2.4.1 Quantization 37
2.4.2 Rep1 Node 37
2.4.3 High-Level Architecture 39
2.4.4 Processing Unit or Processor 39
2.5 Results 40
2.5.1 Verification Methodology 40
2.5.2 Comparison with State-of-the-Art Decoders 41
2.6 Conclusion 43
3 Low-Latency Software Polar Decoders 45
3.1 Introduction 45
3.2 Implementation on x86 Processors 46
3.2.1 Instruction-Based Decoder 47
3.2.1.1 Using Fixed-Point Numbers 48
3.2.1.2 Vectorizing the Decoding of Constituent Codes 48
3.2.1.3 Data Representation 49
3.2.1.4 Architecture-Specific Optimizations 49
3.2.1.5 Implementation Comparison 50
3.2.2 Unrolled Decoder 51
3.2.2.1 Generating an Unrolled Decoder 51
3.2.2.2 Eliminating Superfluous Operations on ?-Values 52
3.2.2.3 Improved Layout of the ?-Memory 52
3.2.2.4 Compile-Time Specialization 52
3.2.2.5 Architecture-Specific Optimizations 53
3.2.2.6 Memory Footprint 54
3.2.2.7 Implementation Comparison 55
3.3 Implementation on Embedded Processors 57
3.4 Implementation on Graphical Processing Units 58
3.4.1 Overview of the GPU Architecture and Terminology 58
3.4.2 Choosing an Appropriate Number of Threads per Block 58
3.4.3 Choosing an Appropriate Number of Blocks per Kernel 59
3.4.4 On the Constituent Codes Implemented 60
3.4.5 Shared Memory and Memory Coalescing 60
3.4.6 Asynchronous Memory Transfers and Multiple Streams 61
3.4.7 On the Use of Fixed-Point Numbers on a GPU 62
3.4.8 Results 62
3.5 Energy Consumption Comparison 63
3.6 Further Discussion 64
3.6.1 On the Relevance of the Instruction-Based Decoders 64
3.6.2 On the Relevance of Software Decoders in Comparison to Hardware Decoders 65
3.6.3 Comparison with LDPC Codes 65
3.7 Conclusion 67
4 Unrolled Hardware Architectures for Polar Decoders 68
4.1 Introduction 68
4.2 State-of-the-Art Architectures with Implementations 69
4.3 Architecture, Operations and Processing Nodes 69
4.3.1 Fully Unrolled (Basic Scheme) 70
4.3.2 Deeply Pipelined 71
4.3.3 Partially Pipelined 72
4.3.4 Operations and Processing Nodes 74
4.3.5 Replacing Register Chains with SRAM Blocks 75
4.4 Implementation and Results 75
4.4.1 Methodology 75
4.4.2 Effect of the Initiation Interval 76
4.4.3 Comparison with State-of-the-Art Decoders 78
4.4.4 Effect of the Code Length and Rate 80
4.4.5 On the Use of Code Shortening in an Unrolled Decoder 83
4.4.6 I/O Bounded Decoding 83
4.5 Conclusion 84
5 Multi-Mode Unrolled Polar Decoding 85
5.1 Introduction 85
5.2 Polar Code Example and its Decoder Tree Representations 86
5.3 Unrolled Architectures 86
5.4 Multi-Mode Unrolled Decoders 87
5.4.1 Hardware Modifications to the Unrolled Decoders 87
5.4.2 On the Construction of the Master Code 88
5.4.3 About Constituent Codes: Frozen Bit Locations, Rate and Practicality 89
5.4.4 Latency and Throughput Considerations 90
5.5 Implementation Results 91
5.5.1 Error-Correction Performance 92
5.5.2 Latency and Throughput 93
5.5.3 Synthesis Results and Comparison with the State of the Art 95
5.6 Conclusion 97
6 Conclusion and Future Work 98
6.1 Future Work 99
6.1.1 Software Encoding and Decoding on APU Processors 99
6.1.2 Software Encoding and Decoding on Micro-Controllers 100
6.1.3 Multi-Mode Unrolled List Decoders 100
References 101
Index 105