On a reduced-complexity inner decoder for the Davey-MacKay construction

Abstract

The Davey-MacKay construction is a promising concatenated coding scheme involving an outer 2k-ary code and an inner code of rate k/n, for insertion-deletion-substitution channels. Recently, a lookup table (LUT)-based inner decoder for this coding scheme was proposed to reduce the computational complexity of the inner decoder, albeit at the expense of a slight degradation in word error rate (WER) performance. In this letter, we show that negligible deterioration in WER performance can be achieved with an LUT as small as 7·2 k+n-1, but no smaller, when the probability of receiving less than n-1 or greater than n+1 bits corresponding to one outer code symbol is at least an order of magnitude smaller than the WER when no LUT is used. © 2012 ETRI.