Project FLUID: Finite-length iterative decoding: fundamental limits, practical constructions and inference


Shannons channel capacity establishes the largest information rate at which data can be reliably transmitted over a noisy channel; in this context, reliability is attained by using codes that add redundancy to the information message. Recently, a number of code families have been recently shown to perform close to the channel capacity. Among them, low-density parity-check (LDPC) codes have been adopted in many modern standards. The decoders of such codes are based on the belief propagation (BP) principle, an efficient algorithm to solve inference problems by iteratively passing local messages. The current analysis of BP iterative decoding algorithms focuses on their infinite-length performance. However, due to delay and complexity constraints, practical communication schemes transmit information in finite-length packets. Even if a coding scheme can be shown to asymptotically achieve capacity, it may perform far from the theoretical limit at finite blocklength. This can be attributed either to the code itself or to the poor performance of BP when loops in the associated graph shorten as the parity-check matrix becomes denser. Nowadays, there are no theoretical tools characterizing these two effects in a unified manner. In this project, we will provide an information-theoretic analysis of iterative decoding. Then, we will define design criteria for finite-length Generalized LDPC (GLDPC) codes that approach the corresponding fundamental limits. We shall also propose novel beyond-BP decoders based on recent advances in expectation propagation (EP) approximate inference for discrete distributions. Implementation constraints will be taken into account. In particular, we shall consider quantization methods for iterative decoders based on the theories of rate-distortion and mismatched decoding.

The iterative decoding principle extends to modern receivers, where general soft-input soft-output algorithms for receiver blocks such as multiple-input multiple-output detectors or turbo equalizers play a central role. In this context, optimal solutions are computationally unaffordable and BP fails as approximate inference approach. We shall extend the novel EP approach developed for channel coding into a soft-input soft-output algorithm receiver coupled to the decoder.

This project aims at building an ambitious theoretical framework for iterative approximate inference with focus on the finite-length regime. Specific project contributions are the following. First, the theoretical characterization, in terms of tradeoffs between rate, block length, and error probability, of short-length transmission under iterative decoding. Second, original GLDPC coding schemes under state-of-the-art decoding to approach these limits. Third, novel techniques to improve approximate inference in iterative decoders and detectors. And fourth, comprehensive experimental scenarios and toolboxes to evaluate code performance as a trade-off between computational complexity and gap to capacity limits, including realistic implementation constraints.