Algorithms and Hardware for Error Correction Coding with High Coding Gain

The capability of transmitting information from one location to another is a vital part of the technical progress in our modern world. In numerous devices, like radio and TV, optical fiber, mobile telephony and internet, satellite and data storage, to mention just a few, data communication has the task of transmitting information reliably over an unreliable channel.
Devices for error correcting coding are widely used to increase the reliability of links and to correct bit errors introduced by noisy communication channels. Error correcting coding employs
sophisticated decoding algorithms and due to high data rate requirements also efficient hardware implementations for these algorithms.

This thesis addresses error correction coding with very high coding gains. New algorithms, hardware architectures and efficient hardware implementations with low area and high data throughput in FPGA and ASIC are introduced.

This thesis uses mathematical optimization to characterize for the first time rigorously numerous standardized codes regarding their optimal coding gain. Additionally, optimization theory is used to analyse the optimal receiver combining demodulation and decoder in a single optimization problem and to model decoding heuristics. The thesis introduces a new maximum likelihood decoding algorithm to solve these optimization problems by employing sophisticated branch and cut techniques and an advanced simplex algorithm, that outperforms the runtime of state-of-the-art solvers like CPLEX by a factor of 10x-20x.

A new heuristic is presented for soft decision decoding of Reed-Solomon codes, that enables an efficient hardware implementation while having a large coding gain. Different hardware architectures for the building blocks of such a decoder are introduced, including sorting, matrix generation and matrix diagonalization. In three implementation design studies for FPGA the superior performance of this approach is demonstrated. It achieves coding gains of up to 1.3 dB with affordable hardware complexity.

The problem of low coding gain for short LDPC codes is tackled by a new decoding heuristic, that is employed in a special configuration and keeps the average complexity low. The algorithm achieves gains of up to 1.6 dB. Serial and parallel architectures for the approach are introduced and synthesized for 28~nm ASIC technology. The implementation copes efficiently with the challenge of ``dark silicon''.