Sequential Decoding of Multiple Sequences for Synchronization Errors

Anisha Banerjee, Andreas Lenz, Antonia Wachter-Zeh

Research output: Contribution to journalArticlepeer-review


Sequential decoding, commonly applied to substitution channels, is a sub-optimal alternative to Viterbi decoding with significantly reduced memory costs. This work describes and analyzes a sequential decoder for convolutional codes over channels prone to insertion, deletion, and substitution errors. Our decoder expands the code trellis by a new channel-state variable, called drift state, as proposed by Davey and MacKay. A suitable decoding metric on that trellis for sequential decoding is derived, generalizing the original Fano metric. The decoder is also extended to facilitate the simultaneous decoding of multiple received sequences that arise from a single transmitted sequence. Under low-noise environments, our decoding approach reduces the decoding complexity by multiple orders of magnitude compared to Viterbi’s algorithm, albeit at slightly higher bit error rates. An analytical method to determine the computational cutoff rate is also suggested. This analysis is supported by numerical evaluations of bit error rates and computational complexity, compared to optimal Viterbi decoding.

Original languageEnglish
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Communications
StateAccepted/In press - 2024


  • Convolutional codes
  • Decoding
  • Hidden Markov models
  • Measurement
  • Symbols
  • Vectors
  • Viterbi algorithm


Dive into the research topics of 'Sequential Decoding of Multiple Sequences for Synchronization Errors'. Together they form a unique fingerprint.

Cite this