Analog signal processing in forward error correction (FEC) decoders [Elektronische Ressource] / Matthias Mörz

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2007
• Nombre de lectures: 24
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Analog Signal Processing in Forward
Error Correction (FEC) Decoders
Matthias Morz¨
. . . . . .
. . . . . .Lehrstuhl fur¨ Nachrichtentechnik
Analog Signal Processing in Forward
Error Correction (FEC) Decoders
Matthias Morz¨
¨ ¨ ¨Vollstandiger Abdruck der von der Fakultat fur Elektrotechnik und Informationstechnik
der Technischen Universitat¨ Munchen¨ zur Erlangung des akademischen Grades eines
Doktor–Ingenieurs
genehmigten Dissertation.
Vorsitzender: Univ.–Prof. Dr. sc. techn. (ETH) Andreas Herkersdorf
Prufer¨ der Dissertation:
1. Univ.–Prof. Dr.–Ing. Dr.–Ing. E. h. Joachim Hagenauer, i.R.
2. Univ Dr habil. Norbert Wehn,
Technische Universitat¨ Kaiserslautern
Die Dissertation wurde am 18.01.2007 bei der Technischen Universitat¨ Munchen¨ eingereicht
und durch die Fakultat¨ fur¨ Elektrotechnik und Informationstechnik am 21.06.2007 angenom
men.III
Preface
This thesis is a result of my work as research assistant at the Institute for Communications
Engineering (LNT) at the Munich University of Technology (TUM).
First of all, I would like to thank my supervisor Prof. Dr.–Ing. Dr.–Ing. E. h. Joachim Hage
nauer for giving me the opportunity to contribute to such an exciting new area of research and
all the support he provided throughout the last years. I am especially grateful that he made it
possible for me to participate in a joint research project with Bell Labs, Lucent Technologies. I
would also like to thank Prof. Dr.–Ing. Norbert Wehn for acting as co examiner.
At this point, I would also like to express my thanks to Dr. Ran Yan, the former vice
president of Wireless Research at Bell Labs, Lucent Technologies, for supporting more than
three years of this work. It has been a great pleasure for me to spend some time of my work at
Bell Labs in Murray Hill, NJ, in Swindon, the United Kingdom, and in Holmdel, NJ. Within
Bell Labs I am in particular indebted to Thad Gabara, Frank Hrycrnko, Ted Gabara, Cyril
Measson, Sami Hyvonen and Eric Westerwick for their contributions to the successful chip
implementations.
I am also very thankful for the great environment and enjoyable atmosphere at the LNT.
I would therefore like to express my sincere appreciation to all my former colleagues and my
past diploma, master and bachelor students. All of them contributed to this work in one way
or the other. Special thanks to Dr. Andrew Schaefer, James Ghirlando, Pavol Hanus, Andreas
Muller¨ , Janis Dingel, Prof. Dr.–Ing. Reimar Lenz and the former system administrators Dr.
Stephan Baro,¨ Dr. Markus Kaindl, Gunther¨ Liebl and Dr. Johannes Zangl who always kept the
computers up and running. Additional thanks to Dr. Andrew Schaefer and Dr. Reza Karimi for
proof reading parts of my thesis.
Finally, I would like to thank my parents and in particular my wife Silvie for their continuous
support and always encouraging me in my work.
Munchen,¨ January 2007 Matthias Morz¨IV
To my familyContents
1 Introduction 1
2 Fundamentals 4
2.1 Digital Communication System . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Time Discrete Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Forward Error Correction (FEC) . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 Simple Block Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.2 Low Density Parity Check (LDPC) Codes . . . . . . . . . . . . . . . . 10
2.3.3 Convolutional Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.4 Tailbiting Convolutional Codes . . . . . . . . . . . . . . . . . . . . . 14
2.3.5 Parallel Concatenated Convolutional Codes . . . . . . . . . . . . . . . 15
2.4 A primer on analog FEC decoders . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Mutual Information and Channel Capacity . . . . . . . . . . . . . . . . . . . . 17
3 Codes on Graphs 20
3.1 Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Tanner Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1 State Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Generalized Constraint Nodes . . . . . . . . . . . . . . . . . . . . . . 27
3.3.3 Tailbiting Realizations . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Normal Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.1 Conversion of Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.2 Degree Restriction on Nodes . . . . . . . . . . . . . . . . . . . . . . . 32
4 Decoding Based on Graphs 35
4.1 General Decoding Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Message Passing Decoding Algorithm . . . . . . . . . . . . . . . . . 37
4.3 Decoding based on Binary Graphs . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1 Message Representations for Binary Random Variables . . . . . . . . . 39
4.3.2 Binary Constraint Node Processors . . . . . . . . . . . . . . . . . . . 40
4.3.3 Iterative Decoding of LDPC Codes . . . . . . . . . . . . . . . . . . . 41
4.4 Decoding based on Non Binary Graphs . . . . . . . . . . . . . . . . . . . . . 43
4.4.1 Messages Representations for Non Binary Random Variables . . . . . 43
4.4.2 Trellis Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4.3 Generalized Sliding Window Decoding . . . . . . . . . . . . . . . . . 47
4.4.4 Iterative Decoding of Turbo Codes . . . . . . . . . . . . . . . . . . . . 50
4.5 Extrinsic Information Transfer Charts . . . . . . . . . . . . . . . . . . . . . . 52
4.6 Quantization of Soft Information . . . . . . . . . . . . . . . . . . . . . . . . . 53VI Contents
5 Analog Decoding 57
5.1 Simulation of Analog Decoders . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.1 Time Continuous Simulation Model . . . . . . . . . . . . . . . . . . . 59
5.1.2 Time Discrete Model . . . . . . . . . . . . . . . . . . . . . 61
5.1.3 Circuit Level Simulations . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Basic Analog Decoding Networks . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.1 Check Node and Variable Node Decoders . . . . . . . . . . . . . . . . 63
5.2.2 Decoders for Simple Block Codes . . . . . . . . . . . . . . . . . . . . 66
5.2.3 Tailbiting Convolutional Decoders . . . . . . . . . . . . . . . . . . . . 70
5.3 Analog Sliding Window Decoding . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3.1 Basic Concept of the Ring Decoder . . . . . . . . . . . . . . . . . . . 74
5.3.2 Initialization of the Recursions . . . . . . . . . . . . . . . . . . . . . . 79
5.3.3 Offset of Forward and Backward Ring . . . . . . . . . . . . . . . . . . 81
5.4 Decoder Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.4.1 Fully Parallel Turbo Decoder . . . . . . . . . . . . . . . . . . . . . . . 85
5.4.2 Sliding Window Turbo . . . . . . . . . . . . . . . . . . . . . 86
5.4.3 Fully Parallel LDPC Decoder . . . . . . . . . . . . . . . . . . . . . . 91
5.5 On the Possible Equivalence between Analog and Digital Decoding . . . . . . 94
5.5.1 Code Graphs without Loops . . . . . . . . . . . . . . . . . . . . . . . 95
5.5.2 Tailbiting Representations of Codes . . . . . . . . . . . . . . . . . . . 95
5.5.3 Code Graphs with Loops . . . . . . . . . . . . . . . . . . . . . . . . . 95
6 Integrated Circuits for Analog Decoding 97
6.1 Elementary Transistor Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.1.1 Transistor Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.1.2 Differential Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.1.3 Pair of Diode Connected Transistors . . . . . . . . . . . . . . . . . . . 102
6.1.4 Stacked Configuration of Differential Pairs . . . . . . . . . . . . . . . 103
6.1.5 Boxplus Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.1.6 Summation Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.2 Generalized Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2.1 Probability Multiplexor . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2.2 Inverse Probability Multiplexor . . . . . . . . . . . . . . . . . . . . . 108
6.2.3 Generalized Multiplier Circuit . . . . . . . . . . . . . . . . . . . . . . 109
6.2.4 General Block Structure . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3 Interfacing between Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.1 CMOS Voltage Dividing Output Stage . . . . . . . . . . . . . . . . . . 112
6.3.2 CMOS Voltage Shifting Output Stage . . . . . . . . . . . . . . . . . . 113
6.3.3 Bipolar V Stage . . . . . . . . . . . . . . . . . . 113
6.4 Decoder Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4.1 Check Node and Variable Node Decoders . . . . . . . . . . . . . . . . 115
6.4.2 Convolutional Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.4.3 Complexity of Turbo Decoders and LDPC Decoders . . . . . . . . . . 124
7 Manufactured Decoder Chips 127
7.1 Tailbiting Convolutional Decoder . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.1.