Sequential decoding of convolutional codes under insertion and deletion errors

Abstract

Synchronisation errors pose a major challenge to classical error-correcting decoding algorithms, which typically assume perfect alignment between transmitted and received sequences. Such errors arise in modern communication and storage systems, including packet-based networks and DNA-based storage where maintaining symbol synchronisation cannot be guaranteed. This dissertation addresses this challenge by implementing a Stack sequential decoder tailored for the Binary Substitution, Insertion and Deletion (BSID) channel and by integrating it as a new module within the SimCommSys simulation framework. The decoder works with convolutional codes and incorporates three path-metric formulations drawn from literature: a joint-distribution based metric; a conditional probability based metric and a weighted Levenshtein distance (WLD) based metric, allowing a unified comparison of their performance under synchronisation errors. Simulation results confirm that the implemented decoder operates correctly across a wide range of error conditions and convolutional codes. The implementation matches or closely replicates reference results from literature, validating the correctness of the metrics and the decoding logic. Among the three metrics, the joint-distribution based metric demonstrated the most robust overall performance after a detailed comparison of decoding performance and complexity with different convolutional codes. Overall, this work provides both a practical contribution with a fully functional sequential decoder for synchronisation errors and a comparative study that clarifies the strengths of three different metric formulations. The decoder serves as a foundation for future developments and research in sequential decoding under synchronisation errors.