Advanced Hardware Design for Error Correcting Codes (eBook)

Cyrille Chavet is an Associate Professor at Associate Professors at Université de Bretagne Sud, Lorient, France. Philippe Coussy is an Associate Professor at Associate Professors at Université de Bretagne Sud, Lorient, France.

Foreword 6
Contents 10
1 User Needs 11
References 16
2 Challenges and Limitations for Very High Throughput Decoder Architectures for Soft-Decoding 17
2.1 Motivation 17
2.2 Architectures for Soft Decision Reed–Solomon Decoders 18
2.2.1 Introduction 18
2.2.2 Information Set Decoding 19
2.2.2.1 Original OSD 19
2.2.2.2 Reduced Complexity Algorithm for Hardware 19
2.2.2.3 HDD Aided Decoding 20
2.2.2.4 Implemented OSD Version 21
2.2.3 Hardware Architecture 21
2.2.3.1 Architecture Overview 21
2.2.3.2 Sorting Unit 22
2.2.3.3 Syndrome Calculation Unit 23
2.2.3.4 Column Generator Unit 23
2.2.3.5 Gaussian Elimination Unit 23
2.2.3.6 Correction Unit 24
2.2.3.7 Hard Decision Decoder 25
2.2.3.8 Fixed Point Quantization Issues 25
2.2.3.9 Pipelining and Latency Issues 25
2.2.4 Implementation Results 25
2.3 Architectures for Turbo Code Decoders 27
2.4 High Throughput Architectures for Low Density Parity Check Decoders 30
2.4.1 LDPC Decoding 31
2.4.2 LDPC Decoder Design Space 32
2.4.3 Exploring a New Dimension in the High Throughput LDPC Decoder Design Space 34
2.4.3.1 Core Duplication 34
2.4.3.2 Unrolling Iterations 35
2.4.4 Comparison of Unrolled LDPC Decoders to State-of-the-Art Architectures 36
2.4.5 Future Work 38
References 39
3 Implementation of Polar Decoders 42
3.1 Introduction to Polar Codes 42
3.1.1 Code Construction 42
3.1.2 Successive-Cancellation Decoding 42
3.1.3 Belief-Propagation Decoding 44
3.2 The Successive-Cancellation Decoder Implementation 44
3.2.1 Processing Elements 44
3.2.2 Partial-Sum Update Logic 45
3.2.3 Memory 45
3.2.4 Implementation Results 46
3.3 The Belief-Propagation Decoder Implementation 46
3.4 Simplified Successive-Cancellation Decoding 47
3.4.1 Two-Phase Successive-Cancellation Decoding 48
3.5 Fast-SSC Decoding 49
3.5.1 Node Mergers 50
3.5.2 Overall Decoder Architecture 51
3.5.3 Processing Unit Architecture 51
3.5.4 Implementation Results 53
3.6 Implementation Comparison 53
References 54
4 Parallel Architectures for Turbo Product Codes Decoding 55
4.1 Introduction 55
4.2 TPC Coding and Decoding Principles 56
4.2.1 Product Codes 56
4.2.2 Iterative Decoding of Product Codes 57
4.3 Straightforward Hardware Implementation of a TPC Decoder 59
4.3.1 Global TPC Decoder Architecture 59
4.3.2 Sequential SISO Decoder Architecture 59
4.4 From Parallelism Levels to Parallel Architectures 61
4.4.1 Frame Parallelism 62
4.4.2 Iteration Parallelism 62
4.4.3 Sub-block Parallelism 63
4.4.3.1 Barrel Shifter 63
4.4.3.2 Omega Network 64
4.4.4 Symbol Parallelism 65
4.4.4.1 Memory Merging 65
4.4.4.2 Fully Parallel SISO Decoder 66
4.4.5 Intra-symbol Parallelism 66
4.4.6 Comparison of Parallelism Levels 67
4.5 TPC Decoder Architecture Based on Symbol Parallelism 68
4.5.1 Proposed IM-Free Architecture Using Fully Parallel SISO Decoder 68
4.5.2 Toward a Maximal Parallelism Rate 70
4.6 Architecture of a Fully Parallel Combinational SISO Decoder 70
4.6.1 Algorithmic Parameter Reduction 71
4.6.2 Fully Parallel SISO Decoder Architecture 72
4.6.2.1 Reception Stage 72
4.6.2.2 Test Pattern Processing Stage 74
4.6.2.3 Soft-Output Computation Stage 74
4.7 Comparison with Existing TPC Decoders 75
4.7.1 Logic Synthesis Results of a BCH(32,26) SISO Decoder 75
4.7.2 Comparison with Existing TPC Decoder Architectures 76
References 79
5 VLSI Implementations of Sphere Detectors 80
5.1 Soft Detection 80
5.1.1 Tree Search Algorithms 82
5.2 Breadth-First Detection 84
5.2.1 K-Best Detection 84
5.2.2 Selective Spanning with Fast Enumeration 85
5.2.2.1 Implementation Choices 86
5.2.2.2 VLSI Implementation 88
5.3 Depth-First and Metric-First Detection Algorithm Implementations 90
5.3.1 Algorithm Descriptions 90
5.3.1.1 Depth-First Algorithm 90
5.3.1.2 Metric-First Algorithm 91
5.3.2 Implementation Trade-Offs 92
5.3.3 Architectural Choices 93
5.3.3.1 SEE-LSD 93
5.3.3.2 IR-LSD 95
5.3.4 VLSI Implementation Results 97
5.3.4.1 Detection Rates 98
5.4 Trellis-Search Based MIMO Detection 100
5.4.1 Trellis-Search Algorithm 100
5.4.2 Trellis Model for Iterative MIMO Detection 101
5.4.2.1 Path Reduction 103
5.4.2.2 Path Extension 104
5.4.2.3 LLR Computation 105
5.4.3 VLSI Architecture 106
5.4.4 VLSI Implementation Results 108
References 109
6 Stochastic Decoders for LDPC Codes 112
6.1 Introduction 112
6.2 Overview of LDPC Codes 113
6.2.1 Structure 113
6.2.2 Decoding 114
6.3 Stochastic Computing 116
6.3.1 The Stochastic Stream Representation 116
6.3.2 Computation Circuits 118
6.4 Fully Stochastic Decoders 119
6.4.1 A Simple Stochastic Decoder 119
6.4.2 Stochastic Decoders Using Successive Relaxation 121
6.4.2.1 The Role of Successive Relaxation 121
6.4.2.2 Circuit Implementations of the VN Function 123
6.4.2.3 Tweaking the Probability Domain Representation 124
6.4.2.4 Benchmark Using the IEEE 802.3an Standard 125
6.4.3 The ``Delayed'' Stochastic Decoder 126
6.4.3.1 Simple DS Decoder 126
6.4.3.2 Some Heuristics for Improved Convergence 126
6.4.3.3 Benchmark Using the IEEE 802.3an Standard 127
6.5 Mixing Stochastic and Conventional Computations 127
6.5.1 The RHS Algorithm 128
6.5.2 Domain Conversion: LLR to Stochastic 128
6.5.3 Domain Conversion: Stochastic to LLR 129
6.5.4 Benchmark Using the IEEE 802.3an Standard 132
6.6 Stochastic Decoders for Non-Binary LDPC Codes 132
6.6.1 Message-Passing Decoding 132
6.6.2 Stochastic Decoding Algorithms 133
6.6.3 Results 134
References 135
7 MP-SoC/NoC Architectures for Error Correction 136
7.1 Introduction 136
7.2 Flexibility in the Communication Structure 137
7.2.1 Indirect Networks 138
7.2.2 Direct Networks 140
7.3 Review of Flexible Decoding Architectures 141
7.3.1 Multi-Standard Architectures 141
7.3.2 Fully Flexible Architectures 142
7.4 Improving the Efficiency of NoC-Based Decoders 142
7.4.1 Energy Reduction Techniques 142
7.4.2 Latency Reduction Techniques 145
7.5 Dynamic Reconfiguration 146
7.5.1 The Reconfiguration Task 147
7.5.2 Reconfiguration of ASIP Based Decoders 149
7.5.3 Reconfiguration of NoC Based Decoders 151
References 154
8 ASIP Design for Multi-Standard Channel Decoders 157
8.1 Flexibility Requirement in Channel Decoder Design 157
8.2 ASIP Design Approach 159
8.3 ASIP-Based Decoders for Turbo Codes 160
8.3.1 Hardware-Efficient Decoding Algorithm 161
8.3.2 State-of-the-Art on Turbo Codes Decoders 162
8.3.3 TurbASIP: Highly Flexible ASIP 163
8.3.3.1 Overview of TurbASIP Architecture 164
8.3.3.2 Pipeline Architecture and Instruction-Set 166
8.3.3.3 Results and Architecture Efficiency Definition 167
8.3.4 TDecASIP: Parameterized Area-Efficient ASIP 169
8.3.4.1 Overview of TDecASIP Architecture 169
8.3.4.2 Results and Discussions 173
8.4 Flexibility Increase to Support Multiple Channel Code Classes 175
8.5 Summary 177
References 178
9 Hardware Design of Parallel Interleaver Architectures: A Survey 182
9.1 Motivation 182
9.2 Problem Formulation 185
9.3 An Overview of Memory Access Conflict Solving Approaches 186
9.3.1 Conflict Solving During the Definitionof the Interleaving Law 186
9.3.2 Conflict Solving Through Dedicated Runtime Approaches 188
9.3.3 Conflict Solving Through Dedicated MemoryMapping Approaches 189
9.3.3.1 Unconstrained Memory Mapping Approaches 190
9.3.3.2 Hard-Constrained Memory Mapping Approaches 191
9.3.3.3 Soft-Constrained Memory Mapping Approaches 192
9.3.4 Hybrid Approach: On-chip Memory Mapping Approach 193
Conclusion 193
References 196