The Davey-MacKay Coding Scheme for Channels With Dependent Insertion, Deletion, and Substitution Errors

Abstract

In this paper, we propose a new channel model which introduces dependent insertion, deletion, and substitution (DIDS) errors. This channel model mimics the write channel found in bit-patterned media recording (BPMR) systems. It consists of a ternary Markov state channel and a two-state binary symmetric channel (BSC). The ternary Markov state channel produces data-dependent and paired insertion-deletion errors while the two-state BSC produces random substitution errors, as well as burst-like substitution errors in the vicinity of insertions and deletions. In addition, we modify the inner decoder of the Davey-MacKay (DM) coding scheme for the proposed channel model. For the case where there are no burst-like substitution errors, computer simulations show that our modified inner decoder (which takes into account the dependencies between synchronization errors) yields superior frame error rate (FER) performance compared to that when the symbol-level inner decoder by Briffa (which ignores the dependencies between synchronization errors) is used. As the (computational) complexity of our inner decoder increases with the length of the burst-like substitution errors, we further propose a reduced-complexity variant of our inner decoder to handle these errors. Computer simulations show that under iterative decoding, FERs below 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-5</sup> can be achieved with the reduced-complexity variant and a code of rate 0.71, when the insertion/deletion rates are low (≤10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-3</sup> ) and the burst-like error lengths before and after a synchronization error are short (≤5).