
Trellis and Turbo Coding
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions


Persons
Content
1.1 Modern Digital Communications 1
1.2 The Rise of Digital Communications 4
1.3 Communication Systems 4
1.4 Error Control Coding 7
1.5 Bandwidth, Power, and Complexity 12
1.6 A Brief History - The Drive Towards Capacity 20
2 Communications Basics 27
2.1 The Probabilistic Viewpoint 27
2.2 Vector Communication Channels 29
2.3 Optimum Receivers 31
2.4 Matched Filters 33
2.5 Message Sequences 35
2.6 The Complex Equivalent Baseband Model 39
2.7 Spectral Behavior 44
2.8 Advanced Modulation Methods 46
2.8.1 OFDM 46
2.8.2 Multiple Antenna Channels (MIMO Channels) 48
2.9 A Communications System Case Study 53
2.10 Appendix 2.A 61
3 Trellis-Coded Modulation 67
3.1 An Introductory Example 67
3.2 Construction of Codes 71
3.3 Lattices 80
3.4 Lattice Formulation of Trellis Codes 86
3.5 Rotational Invariance 92
3.6 V.fast 99
3.7 The IEEE 802.3an Standard 101
3.8 Historical Notes 106
4 Trellis Representations 111
4.1 Preliminaries 111
4.2 The Parity-Check Matrix 112
4.3 Parity-Check Trellis Representations 113
4.4 Convolutional Codes and Their Trellis 115
4.5 Minimal Trellises 120
4.6 Minimum-Span Generator Matrices 124
4.7 Systematic Construction of the PC-Trellis 127
4.8 Tail-Biting Trellises 129
4.9 The Minimal Trellis of Convolutional Codes 133
4.10 Fundamental Theorems from Basic Algebra 139
4.11 Systematic Encoders 149
4.12 Maximum Free-Distance Convolutional Codes 151
4.13 The Squaring Construction and the Trellis of Lattices 154
4.14 The Construction of Reed-Muller Codes 161
4.15 A Decoding Example 163
4.16 Polar Codes and Their Relationship to RM Codes 166
Appendix 4.A 171
5 Trellis and Tree Decoding 179
5.1 Background and Introduction 179
5.2 Tree Decoders 181
5.3 The Stack Algorithm 183
5.4 The Fano Algorithm 185
5.5 The M-Algorithm 186
5.6 Maximum Likelihood Decoding 197
5.7 A Posteriori Probability Symbol Decoding 200
5.8 Log-APP and Approximations 207
5.9 Error Analysis and Distance Spectrum 211
5.10 Random Coding Analysis of Optimal Decoding 222
5.11 Random Coding Analysis of Sequential Decoding 232
5.12 Some Final Remarks 238
6 Low-Density Parity-Check Codes 249
6.1 Introduction 249
6.2 LDPC Codes and Graphs 251
6.3 LDPC Decoding via Message Passing 255
6.4 Analysis Techniques 259
6.4.1 (Error) Probability Evolution for Binary Erasure Channels 259
6.4.2 Error Mechanism of LDPCs on BECs 265
6.4.3 Binary Symmetric Channels and the Gallager Algorithms 266
6.4.4 The AWGN Channel 270
6.5 Code Families and Construction 281
6.5.1 Constructions with Permutation Matrices 281
6.5.2 Cycle Reduction Design 286
6.5.3 RS-based Construction 287
6.5.4 Repeat-Accumulate Codes 289
6.6 Encoding of LDPC Codes 291
6.6.1 Triangular LDPC Codes 292
6.6.2 Specialized LDPC Codes 295
6.6.3 Approximate Triangularization 296
Appendix 6.A 298
7 Error Floors 319
7.1 The Error Floor Problem 319
7.2 Dynamics of the Absorption Sets 323
7.3 Code Design for Low Error Floors 331
7.4 Impact of the Decoding Algorithm 335
7.5 Importance Sampling (IS) 336
7.6 Computing Error Rates via Importance Sampling 340
8 Turbo Coding: Basic Principles 351
8.1 Introduction 351
8.2 Parallel Concatenated Convolutional Codes 353
8.3 Distance Spectrum Analysis of Turbo Codes 356
8.4 The Free Distance of a Turbo Code 358
8.5 Weight Enumerator Analysis of Turbo Codes 364
8.6 Iterative Decoding of Turbo Codes 371
8.7 EXIT Analysis 376
8.8 Serial Concatenation 383
8.9 Cascaded Convolutional Codes 383
8.10 Weight Enumerator Analysis of SCCCs 385
8.11 Iterative Decoding and Performance of SCCCs 394
8.12 EXIT Analysis of Serially Concatenated Codes 397
8.13 Viewpoint 401
8.14 Turbo-Trellis-Coded Modulation 402
8.15 Serial Concatenation 406
8.16 EXIT Analysis of Serial TTCM 408
8.17 Differential-Coded Modulation 409
8.18 Concatenated Space-Time Coding 414
8.19 Bit-Interleaved Coded and Generalized Modulation 418
9 Turbo Coding: Applications 431
9.1 Interleavers 431
9.2 Turbo Codes in Telecommunication Standards 439
9.2.1 The Space Data System Standard 439
9.2.2 3G Wireless Standards 440
9.2.3 Digital Video Broadcast Standards 443
9.3 Product Codes and Block Turbo Decoding 446
9.4 Approximate APP Decoding 448
9.5 Product Codes with High-Order Modulations 451
9.6 The IEEE 802.16 Standard 453
9.7 Decoding of Polar Codes 454
9.8 Polar Code Performance and Outlook 458
10 Convolutional LDPC Codes and Spatial Coupling 465
10.1 Capacity: The Ultimate Limit 465
10.2 Low-Density Parity-Check Convolutional Codes 467
10.2.1 New LDPC Codes from Old 467
10.2.2 Decoding Convolutional LDPC Codes 472
10.3 Spatial Coupling: A General View 474
10.4 Spatial Coupling: Convergence Analysis 482
10.4.1 Problem Setup 482
10.4.2 Lyapunov Approach 483
Chapter 1
Introduction
1.1 Modern Digital Communications
With the advent of high-speed logic circuits and very large scale integration (VLSI), data processing and storage equipment has inexorably moved towards employing digital tech-niques. In digital systems, data is encoded into strings of zeros and ones, corresponding to the on and off states of semiconductor switches. This has brought about fundamental changes in how information is processed. While real-world data is primarily in "analog form" of one type or another, the revolution in digital processing means that this analog information needs to be encoded into a digital representation, e.g., into a string of ones and zeros. The conversion from analog to digital and back are processes which have become ubiquitous. Examples are the digital encoding of speech, picture, and video encoding and rendering, as well as the large variety of capturing and representing data encountered in our modern internet-based lifestyles.
The migration from analog communications of the first half of the 20-th century to the now ubiquitous digital forms of communications were enabled primarily by the fast-paced advances in high-density device integration. This has been the engine behind much of the technological progress over the last half century, initiated by the creation of the first inte-grated circuit (IC) by Kilby at Texas Instruments in 1958. Following Moore's informal law, device sizes, primarily CMOS (Complementary Metal-Oxide Semiconductors), shrink by a factor two every two years, and computational power doubles accordingly. An impression for this exponential growth in computing capability can be gained from Figure 1.1, which shows the number of transistors integrated in a single circuit and the minimum device size for progressive fabrication processes - known as implementation nodes.
While straightforward miniaturization of the CMOS devices is becoming increasingly more difficult, transistor designers have been very creative in modifying the designs to stay on the Moore trajectory. As of 2015 we now see the introduction of 3-dimensional transistor structures such as thin FETs, double-gated FETs, and tunnel FETs, and it is expected that carbon nanotube devices may continue miniaturization well into the sub-10 nm range. In any case, the future for highly complex computational devices is bright.
Figure 1.1: Moore's law is driving progress in electronic devices. Top left: A basic CMOS switching structure. Bottom left: Moore observed his "doubling law" in 1965 and predicted that it would continue "at least another 10 years."
One such computational challenge is data communications: in particular data integrity, as discussed in this book. The migration from analog to digital information processing has opened the door for many sophisticated algorithmic methods. Digital information is treated differently in communications than analog information. Signal estimation becomes signal detection; that is, a communications receiver need not look for an analog signal and make a "best" estimate, it only needs to make a decision between a finite number of discrete signals, say a one or a zero in the most basic case. Digital signals are more reliable in a noisy communications environment; they can usually be detected perfectly, as long as the noise levels are below a certain threshold. This allows us to restore digital data, and, through error correcting techniques, correct errors made during transmission. Digital data can easily be encoded in such a way as to introduce dependency among a large number of symbols, thus enabling a receiver to make a more accurate detection of the symbols. This is the essence of error control coding.
Finally, there are also strong theoretical reasons behind the migration to digital pro-cessing. Nyquist's sampling theorem, discussed in Section 1.3, tells us that, fundamentally, it is sufficient to know an analog signal at a number of discrete points in time. This opens the door for the discrete time treatment of signals. Then, Shannon's fundamental chan-nel coding theorem states that the values of these discrete time samples themselves, can contain only a finite amount of information. Therefore, only a finite amount of discrete levels are required to capture the full information content of a signal.
The digitization of data is convenient for a number of other reasons too. The design of signal processing algorithms for digital data is much easier than designing analog signal processing algorithms, albeit not typically less complex. However, the abundance of such digital algorithms, including the error control and correction techniques discussed in this book, combined with their ease of implementation in very large scale integrated (VLSI) circuits has led to the plethora of successful applications of error control coding we see in practice today.
Error control coding was first applied in deep-space communications where we are confronted with low-power communications channels with virtually unlimited bandwidth. On these data links, convolutional codes (Chapter 4) are used with sequential and Viterbi decoding (Chapter 5), and the future will see the application of turbo coding. The next successful application of error control coding was to storage devices, most notably the compact disk player, which employs powerful Reed-Solomon codes [21] to handle the raw error probability from the optical readout device which is too large for high-fidelity sound reproduction without error correction. Another hurdle taken was the successful application of error control to bandwidth-limited telephone channels, where trellis-coded modulation (Chapter 3) was used to produce impressive improvements and push transmission rates towards the theoretical limit of the channel. Nowadays, coding is routinely applied to satellite communications [41, 49], teletext broadcasting, computer storage devices, logic circuits, semiconductor memory systems, magnetic recording systems, audio-video, and WiFi systems. Modern mobile communications systems like the pan-European TDMA digital telephony standard GSM [35], IS 95 [47], CDMA2000, IMT2000, and the new 4-th generation LTE and LTE-A standards [63, 64] all use error control coding.
1.2 The Rise of Digital Communications
Modern digital communication theory started in 1928 with Nyquist's seminal work on telegraph transmission theory [36]. The message from Nyquist's theory is that finite bandwidth implies discrete time. That is, a signal whose bandwidth is limited can always be represented by sample values taken at discrete time intervals. The sampling theorem of this theory then asserts that the band-limited signal can always be reconstructed exactly from these discrete-time samples.1 Only these discrete samples need to be processed by a receiver since they contain all the necessary information of the entire waveform.
The second pillar to establish the supremacy of digital information processing came precisely from Shannon's 1948 theory. Shannon's theory essentially establishes that the discrete-time samples which are used to represent a bandlimited signal, could be ade-quately described by a finite number of amplitude samples, the number of which depended on the level of the channel noise. These two theories combined state that a finite num-ber of levels taken at discrete time intervals are completely sufficient to characterize any bandlimited signal in the presence of noise, that is, in any communication system.
With these results, technology has moved towards a complete digitization of commu-nications systems, with error control coding being the key to realize the sufficiency of discrete amplitude levels. We will study Shannon's theorem in more detail in Section 1.5.
1.3 Communication Systems
Figure 1.2 shows the basic configuration of a point-to-point digital communications link. The data to be transmitted over this link can either come from some analog source, in which case it must first be converted into digital format (digitized), or it can be a digital information source. If this data is a speech signal, for example, the digitizer is a speech codec [22]. Usually the digital data is source encoded to remove unnecessary redundancy from the data, i.e., the source data is compressed [14]. Source encoding has the effect that the digital data which enters the encoder has statistics which resemble that of a random symbol source with maximum entropy, i.e., all the different digital symbols occur with equal likelihood, and are statistically independent. The channel encoder operates on this compressed data and introduces controlled redundancy for transmission over the channel. The modulator converts the discrete channel symbols into waveforms which are transmitted through the waveform channel. The demodulator reconverts the waveforms back into a discrete sequence of received symbols, and the decoder reproduces an estimate of the compressed input data sequence, which is subsequently reconverted into the original signal or data sequence.
Figure 1.2: System diagram of a complete point-to-point communication system for digital data. The forward error control (FEC) block is the topic of this book.
An important ancillary function at the receiver is the synchronization process. We usually need to acquire carrier frequency and phase synchronization, as well as symbol timing synchronization in order for the receiver to be able to operate. Synchronization is not a topic of this...
System requirements
File format: ePUB
Copy protection: Adobe-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Install the free reader Adobe Digital Editions prior to download (see eBook Help).
- Tablet/smartphone (Android; iOS): Install the free app Adobe Digital Editions or the app PocketBook before downloading (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (not Kindle).
The file format ePub works well for novels and non-fiction books – i.e., „flowing” text without complex layout. On an e-reader or smartphone, line and page breaks automatically adjust to fit the small displays.
This eBook uses Adobe-DRM, a „hard” copy protection. If the necessary requirements are not met, unfortunately you will not be able to open the eBook. You will therefore need to prepare your reading hardware before downloading.
Please note: We strongly recommend that you authorise using your personal Adobe ID after installation of any reading software.
For more information, see our ebook Help page.