Fully programmable LDPC decoder hardware architectures [Elektronische Ressource] / von Christiane Maja Beuschel

Sujets

• Informatik

Informations

• Publié par: universitat_ulm
• Publié le: 01 janvier 2010
• Nombre de lectures: 24
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Fully Programmable LDPC Decoder
Hardware Architectures
DISSERTATION
zur Erlangung des akademischen Grades eines
DOKTOR–INGENIEURS
(DR.–ING.)
der Fakult¨at fu¨r Ingenieurwissenschaften
und Informatik der Universit¨at Ulm
von
CHRISTIANE MAJA BEUSCHEL
¨AUS WANGEN IM ALLGAU
Gutachter: Prof. Dr.-Ing. Hans-J¨org Pfleiderer
Prof. Dr.-Ing. Norbert Wehn
Amtierender Dekan: Prof. Dr.-Ing. Michael Weber
Ulm, 22.04.2010Fully Programmable LDPC Decoder
Hardware Architectures
Abstract
In recent years, the amount of digital data which is stored and transmitted for private
and public usage has increased considerably. To allow a save transmission and storage of
data despite of error-prone transmission media, error correcting codes are used. A large
variety of codes has been developed, and in the past decade low-density parity-check
(LDPC) codes which have an excellent error correction performance became more and
more popular. Today, low-density parity-check codes have been adopted for several stan-
dards, and efficient decoder hardware architectures are known for the chosen structured
codes. However, the existing decoder designs lack flexibility as only few structured codes
can be decoded with one decoder chip. In consequence, different codes require a redesign
of the decoder, and few solutions exist for decoding of codes which are not quasi-cyclic or
which are unstructured.
In this thesis, three different approaches are presented for the implementation of fully
programmable LDPC decoders which can decode arbitrary LDPC codes. As a design
study, the first programmable decoder which uses a heuristic mapping algorithm is real-
ized on an field-programmable gate array (FPGA), and error correction curves are mea-
sured to verify the correct functionality. The main contribution of this thesis lies in the
development of the second and the third architecture and an appropriate mapping algo-
rithm. The proposed fully programmable decoder architectures use one-phase message
passing and layered decoding and can decode arbitrary LDPC codes using an optimum
mapping and scheduling algorithm. The presented programmable architectures are in
fact generalized decoder architectures from which the known decoders architectures for
structured LDPC codes can be derived.Contents
1 Introduction 1
2 Background 5
2.1 Channel Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Digital Communication System . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Performance Measure . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 Log-Likelihood Algebra . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Low-Density Parity-Check Codes . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Definition of LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Classes of LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Encoding of LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Decoding of LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Decoding in a Cycle Free Graph . . . . . . . . . . . . . . . . . . . . 17
2.4.2 Belief Propagation Decoding . . . . . . . . . . . . . . . . . . . . . . 18
2.4.3 Scheduling for Belief Propagation Decoding . . . . . . . . . . . . . 21
2.4.4 Reduced Complexity Decoding . . . . . . . . . . . . . . . . . . . . 22
3 Classification of LDPC Decoder Architectures 25
3.1 Node Processing and Message Routing . . . . . . . . . . . . . . . . . . . . 26
3.1.1 Parallel and Sequential Node Processing . . . . . . . . . . . . . . . 26
3.1.2 Message Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Fully Parallel Architecture for one Specific Code . . . . . . . . . . . . . . . 28
3.3 Partly Parallel Architectures for Structured Codes . . . . . . . . . . . . . . 28
3.3.1 Decoders for Special Regular LDPC Code Ensembles . . . . . . . . 30
3.3.2 Quasi-Cyclic LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.3 Protograph LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.4 LDPC Codes in Communication Standards . . . . . . . . . . . . . . 36
3.4 Fully Programmable Architectures. . . . . . . . . . . . . . . . . . . . . . . 36
3.4.1 Classification of Decoder Architectures . . . . . . . . . . . . . . . . 36
3.4.2 Programmable Architectures with Heuristic Memory Mapping . . . 38
3.4.3 Programmable Architecture with Optimum Memory Mapping . . . 44
3.4.4 Parallelism in Fully Programmable Decoder Architectures . . . . . 48
4 Hardware Design for Programmable LDPC Decoders 51
4.1 Node Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.1 Variable Node Functional Unit. . . . . . . . . . . . . . . . . . . . . 51
4.1.2 Check Node Functional Unit . . . . . . . . . . . . . . . . . . . . . . 53ii Contents
4.1.3 Quantization and Reduced Complexity Decoding . . . . . . . . . . 56
4.2 Memory Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2.1 Control Memory for Parity-Check Matrix . . . . . . . . . . . . . . . 61
4.2.2 Data Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Flexible Interconnect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 Permutation Network . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.2 Barrel Shifter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.3 Complexity Comparison . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 FPGA Implementation of a Programmable LDPC Decoder . . . . . . . . . 65
4.4.1 Architectural Hardware Design . . . . . . . . . . . . . . . . . . . . 66
4.4.2 Mapping and Scheduling Algorithm . . . . . . . . . . . . . . . . . . 71
4.4.3 Implementation of Decoder and Communication System . . . . . . 73
4.4.4 Verification by Error Correction Performance. . . . . . . . . . . . . 75
4.4.5 Design Study Results . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5 Programmable LDPC Decoders with Optimum Memory Mapping 79
5.1 Programmable One-Phase Flooding Schedule Decoder . . . . . . . . . . . . 80
5.1.1 Decoder Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.2 Scheduling of Node Computations . . . . . . . . . . . . . . . . . . . 82
5.2 Study of Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.1 Study of Memory Access for Check Node Processing. . . . . . . . . 83
5.2.2 Study of Memory Access for Variable Node Processing . . . . . . . 85
5.2.3 Permutation Networks . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Collision-Free Memory Access Scheduling . . . . . . . . . . . . . . . . . . . 86
5.3.1 Mapping and Scheduling Algorithm . . . . . . . . . . . . . . . . . . 86
5.3.2 Memory Access Scheduling on Decoder Architecture . . . . . . . . . 91
5.4 Programmable Layered Decoder . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4.1 Decoder Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4.2 Error Correction Performance of Modified Layered Schedule . . . . 97
5.4.3 Memory Access Scheduling on Layered Decoder Architecture . . . . 99
5.5 Pipelining and Data Throughput . . . . . . . . . . . . . . . . . . . . . . . 101
5.5.1 Pipelining and Writing of Sum Values. . . . . . . . . . . . . . . . . 101
5.5.2 Simulation Results for Pipelining . . . . . . . . . . . . . . . . . . . 102
5.5.3 Data Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.6 ASIC Synthesis Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.6.1 Basic Building Blocks. . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.6.2 Data Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.6.3 Control Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.6.4 Summary of Synthesis Results for Programmable Decoders . . . . . 112
5.6.5 Comparison with Other Designs . . . . . . . . . . . . . . . . . . . . 114
6 Comparison and Generalization of Decoder Architectures 117
6.1 Comparison of Programmable and Fixed Decoders . . . . . . . . . . . . . . 117
6.1.1 Comparison of Decoder Architectures . . . . . . . . . . . . . . . . . 117
6.1.2 Comparison of Control Complexity . . . . . . . . . . . . . . . . . . 119
6.1.3 Summary of Comparison . . . . . . . . . . . . . . . . . . . . . . . . 120
6.2 Generalization of the Programmable Approach . . . . . . . . . . . . . . . . 121Contents iii
7 Conclusion and Outlook 123
A Alternative Formulations of the BP Decoding Algorithm 127
A.1 Log-Likelihood Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
A.2 Belief Propagation Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . 128
A.3 Performance Loss for Quantization . . . . . . . . . . . . . . . . . . . . . . 130
B Implementation Details 133
B.1 Variable Node Functional Unit . . . . . . . . . . . . . . . . . . . . . . . . . 133
B.2 Check Node Functional Unit . . . . . . . . . . . . . . . . . . . . . . . . . . 134
B.3 Shift Register of Variable Length . . . . . . . . . . . . . . . . . . . . . . . 135
C Mapping Function 137
C.1 Equiva