This letter presents an iterative soft-in soft-out (SISO) decoding algorithm based on redundant Tanner graphs that is applicable to arbitrary linear block codes. The proposed algorithm utilizes the permutation group of a code in order to efficiently and randomly generate redundant parity-checks.
A number of authors have recently considered iterative soft-in soft-out (SISO) decoding algorithms for classical linear block codes that utilize redundant Tanner graphs. Jiang and Narayanan presented a practically realizable algorithm that applies only to cyclic codes while Kothiyal et al. presented an algorithm that, while applicable to arbitrary linear block codes, does not imply a low-complexity implementation. This work first presents the aforementioned algorithms in a common framework and then presents a related algorithm - random redundant iterative decoding - that is both practically realizable and applicable to arbitrary linear block codes. Simulation results illustrate the successful application of the random redundant iterative decoding algorithm to the extended binary Golay code. Additionally, the proposed algorithm is shown to outperform Jiang and Narayanan's algorithm for a number of Bose-Chaudhuri-Hocquenghem (BCH) codes
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.
Generalized Tanner graphs have been implicitly studied by a number of authors under the rubric of generalized parity-check matrices. This work considers the conditioning of binary hidden variables in such models in order to break all cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tanner graphs are shown to imply optimal SISO decoding algorithms for the first order Reed-Muller codes and their duals - the extended Hamming codes - which are substantially less complex than conventional bit-level trellis decoding. The study of low-complexity optimal SISO decoding algorithms for the family of extended Hamming codes is practically motivated. Specifically, it is shown that exended Hamming codes offer an attractive alternative to high- rate convolutional codes in terms of both performance and complexity for use in very high-rate, very low-floor, serially concatenated coding schemes.
In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner graph. A generalized Tanner graph is constructed from the code's Tanner graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.
We present a soft-input soft-output (SISO) decoding algorithm for binary block codes, based on ordered reliability direct error-pattern testing (ORDEPT) and extended covered space approximation. The method can be used for iterative decoding of product-like and generalized low-density parity-check (GLDPC) codes. Our results obtained for product and GLDPC codes with extended Bose-Chaudhuri-Hocquenghem (BCH) component codes show that the proposed decoder demonstrates improved performance, often achieved with much smaller complexity compared to the state-of-the-art SISO decoders.