Graph Configurations and Decoding Performance

Michael Lunglmayr, Jens Berkmann, Mario Huemer

In this work, we present a new framework for developing decoding algorithms for linear block codes. We define a new graphical model, called configuration graph and show that maximum likelihood (ML) sequence decoding can be performed by finding a maximum vertex packing on a configuration graph. We present examples of low-cost decoding algorithms developed using this graphical model and show that remarkable performance improvements can be achieved especially by combining these algorithms with belief propagation (BP) decoding for Low Density Parity Check (LDPC) codes.

G. David Forney

Fanhui Meng, Yixin Wang, Qianfan Wang +1 more

In this paper, a complex network approach is presented to design the Bernoulli parity-check (BPC) codes with enhanced belief propagation (BP) decoding performance. By investigating the degree correlation between variable and check nodes, we propose the normal graph configuration model (NGCM) to adjust the assortativity coefficient of normal graphs, and investigate the impact of disassortativity on decoding performances. Numerical results demonstrate that, optimizing the disassortativity of normal graphs can significantly enhance the BP decoding performance in both the waterfall and error floor regions. This improvement leads to lower bit-error-rate (BER), frame-error-rate (FER), and decoding complexity. Our study has significant practical and theoretical value, especially for the interdisciplinary research of complex network and coding theory.

Patrick Guy Farrell, Seyed H. Razavi

Mohammad Amin Shokrollahi

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen +2 more

Abstract—In this paper, we extend our work on iterative softinput soft-output (SISO) decoding of high density parity check (HDPC) codes. Edge-local complementation (ELC) is a graph operationwhichcanbeusedtogivestructuralredundancyduring decoding with the sum-product algorithm (SPA). We describe the specific subgraphs required for ELC to not increase the weight of the Tanner graph beyond a specified upper bound. We call this controlled operation weight-bounding ELC (WB-ELC). A generalized iterative SISO HDPC decoder is described, which can be configured to employ different operations; most importantly, ‘flooding ’ SPA, and iterative ‘permutation decoding. ’ The latter is a state-of-the-art decoding algorithm for HDPC codes, using permutations from the automorphism group of the code. We observe performance improvements when the SISO HDPC decoder is configured to use WB-ELC, as compared to using ELC, or even permutation decoding. I.