Ph.D Thesis

Ph.D StudentWiechman Gil
SubjectTheoretical and Practical Aspects on the Performance
versus Complexity Tradeoff for LDPC-Based Codes
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Igal Sason
Full Thesis textFull thesis text - English Version


Error-correcting codes employing iterative decoding algorithms are now considered state of the art in the field of low-complexity coding techniques. The graphical representation of these codes is used to describe their algebraic structure, and also enables a unified description of their iterative decoding algorithms. These codes closely approach the capacity limit of many standard communication channels under iterative decoding. The outstanding performance of these codes motivates an information-theoretic study of the tradeoff between their performance and complexity, as well as a study of the ultimate limitations of finite-length codes.

We begin our study of the performance versus complexity tradeoff by deriving bounds on the achievable rates and the graphical complexity of binary linear block codes under ML decoding. These bounds are derived under the assumption that the transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are particularized to low-density parity-check (LDPC) codes, and apply to the tradeoff between achievable rates and decoding complexity per iteration under message-passing decoding. Further, we generalize the bounds to the case where the codes are transmitted over a set of independent parallel MBIOS channels. The latter results are applied to ensembles of punctured LDPC codes.

Secondly, we consider the number of iterations required for successful iterative message-passing decoding of graph-based codes. The communication (this time) is assumed to take place over the binary erasure channel, and the analysis refers to the asymptotic case where the block length tends to infinity. We derive rigorous lower bounds on the number of iterations required to achieve a given bit erasure probability under standard message-passing decoding. For several modern code families, we show that the number of iterations scales at least like the inverse of the multiplicative gap to capacity; this matches a previous conjecture and experimental results.

Finally, we consider sphere-packing lower bounds on the decoding error probability of optimal block codes. We focus on modifications to the 1967 sphere-packing (SP67) bounding technique, making it more attractive for finite-length block codes. We derive a new sphere-packing bound targeted at finite-length block codes transmitted over symmetric memoryless channels. This part of the work facilitates the assessment of the fundamental limitations of finite-length block codes, and is therefore very applicative for the evaluation of practical coded communication systems.