Chavet / Coussy Advanced Hardware Design for Error Correcting Codes

2015
ISBN: 978-3-319-10569-7
Verlag: Springer Nature Switzerland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 197 Seiten

This book provides thorough coverage of error correcting techniques. It includes essential basic concepts and the latest advances on key topics in design, implementation, and optimization of hardware/software systems for error correction. The book's chapters are written by internationally recognized experts in this field. Topics include evolution of error correction techniques, industrial user needs, architectures, and design approaches for the most advanced error correcting codes (Polar Codes, Non-Binary LDPC, Product Codes, etc). This book provides access to recent results, and is suitable for graduate students and researchers of mathematics, computer science, and engineering.• Examines how to optimize the architecture of hardware design for error correcting codes;• Presents error correction codes from theory to optimized architecture for the current and the next generation standards;• Provides coverage of industrial user needs advanced error correcting techniques.Advanced Hardware Design for Error Correcting Codes includes a foreword by Claude Berrou.

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.

Autoren/Hrsg.

Chavet, Cyrille

Coussy, Philippe

Inhaltsverzeichnis

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