Interleaved LDPC codes, reduced-complexity inner decoder and an iterative decoder for the Davey-MacKay construction

Abstract

The inner decoder of the Davey-MacKay (DM) construction for combating insertions, deletions and substitution errors, has high complexity and produces bursts of output likelihoods of greatest uncertainty in the vicinity of insertions and deletions. We therefore propose (i) a lookup-table-based implementation of the inner decoder to reduce its complexity, (ii) the use of interleaved LDPC codes as outer codes in the DM construction to spread the uncertain likelihoods produced by the inner decoder over several constituent LDPC codewords. Simulation results show that the proposed lookup table approach reduces the complexity of the inner decoder considerably while a significant improvement in frame error rate (FER) performance can be obtained with small interleaving depths. Our lookup table approach culminates in an iterative decoding scheme which yields improved FER performance over its non-iterative counterparts, yet with only a modest increase in decoding complexity, when the insertion/deletion probability is small.