Optimal synchronization with binary marker for segmented burst deletion errors

Chen Yi, Jihua Zhou, Tao Zhao, Baoze Ma, Yong Li, Francis C.M. Lau

Research output: Journal article publicationJournal articleAcademic researchpeer-review


In some telecommunication and magnetic/digital recording applications, bits/symbols tend to be lost in the transmission due to the interference. In this paper, we consider a segmented burst deletion channel where in a block of L consecutive bits at most a single burst deletion of length up to D bits exists. Existing synchronization approaches either provide a poor synchronization performance or suffer from a high computational complexity. For example, the reduced state Forward Backward Algorithm (FBA) incurs high time and space complexities, i.e., O(n[Formula presented]) and O(n), respectively, where n denotes the sequence length. In this paper, we discover binary marker patterns which require the minimum D+1 bits redundancy to detect the burst deletion with the length up to D bits for the segmented burst deletion channel, and propose an optimal algorithm to resynchronize the corrupted bit sequence that minimizes the expected bit error rate. As compared to the reduced state FBA, the time and space complexities of our proposed algorithm are reduced to O(n) and O(1), respectively. Theoretical analysis and simulations verify the optimality of our proposed algorithm, and demonstrate that the expected bit error rate introduced in our proposed scheme is lower than that in the existing synchronization error detection schemes and that in the FBA under segmented burst deletion channels.

Original languageEnglish
Article number104449
JournalDigital Signal Processing: A Review Journal
Publication statusPublished - May 2024


  • Marker codes
  • Segmented burst deletions
  • Sequential synchronization

ASJC Scopus subject areas

  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Statistics, Probability and Uncertainty
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal synchronization with binary marker for segmented burst deletion errors'. Together they form a unique fingerprint.

Cite this