From LDPC Block to LDPC Convolutional Codes: Capacity, Stability, and Universality

In his landmark paper "A Mathematical Theory of Communication," the founding father of information theory and coding theory, Claude E. Shannon, established the largest rate at which reliable communication is possible and he revealed that the key to this reliability is coding. Ever since then, researchers from various fields have focused on designing practical coding schemes that can reliably achieve this limit. Seventy years of developments after Shannon's promise have gradually formed a new field, modern coding theory, that aims at constructing provably capacity-achieving codes under low-complexity encoding and decoding algorithms, and seventy years of progress have finally made this goal come true, at least in many communication scenarios of practical interest. To mention two fascinating developments in coding theory, consider spatially coupled codes and polar codes. All these coding techniques are provably capacity-achieving and have efficient encoding and decoding algorithms in many communication scenarios.

Even though Shannon's promise has been seemingly realized, new challenges and emerging frontiers are just opening up. In this thesis, we concentrate on a particular coding scheme, low-density parity-check coding and we investigate three major themes: capacity, stability, and universality.

The first topic is capacity. We introduce a new class of time-invariant low-density parity-check convolutional codes. Such codes can be described by only a handful of integers. The time-invariant character of such codes makes them extremely simple to encode and have linear complexity in time and space. Furthermore, the sparsity of their graphical representations allows for efficient message-passing decoding. We show, via extensive simulations, that such codes exhibit the threshold saturation phenomenon known from spatially coupled codes, revealing that they can approach capacity asymptotically under low-complexity encoding and decoding algorithms. We further perform iterative decoding analysis for these codes, setting up a first step towards rigorously analyzing the performance of iterative message-passing decoding algorithms.

The second topic is stability. We investigate the stability condition of low-density parity-check block codes. More precisely, we determine the stability threshold for low-density parity-check block codes under either blockwise or bitwise maximum a posteriori decoding, when transmission takes place over a generic binary-input memoryless output-symmetric channel. We present how stability can determine an upper bound on the corresponding blockwise or bitwise maximum a posteriori threshold, which reveals the operational significance of the stability threshold of the underlying codes.

The third topic is universality. Designing capacity-achieving codes for various type of channels is of practical importance, since we are often faced with various physical constraints where different channel models are needed. So in practice it is important to design codes that are universally capacity-achieving, where universality refers to the family of channels having the same capacity. In this thesis we show that, under the framework of low-density parity-check block codes, many existing capacity-achieving sequences designed for the binary erasure channel cannot achieve the same capacity for a broad family of channels. The key quantity determining the universality of such sequences are intrinsically related to the stability of them.