New Construction of q-ary Codes Correcting a Burst of at most t Deletions

2024/01/11 by Wentu Song, Song, Wentu, Kui Cai +2 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Engineering · #Coding theory and cryptography #DNA and Biological Computing #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2401.05859

Abstract

In this paper, for any fixed positive integers t and q>2, we construct q-ary codes correcting a burst of at most t deletions with redundancy log n+8loglog n+o(loglog n)+γ_q,t bits and near-linear encoding/decoding complexity, where n is the message length and γ_q,t is a constant that only depends on q and t. In previous works there are constructions of such codes with redundancy log n+O(log qloglog n) bits or log n+O(t²loglog n)+O(tlog q). The redundancy of our new construction is independent of q and t in the second term.

Cited by

• Error Correcting Codes for Segmented Burst-Deletion Channels

Related

• Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes
• Codes Correcting Two Bursts of Exactly b Deletions
• Every Bit Counts: A New Version of Non-binary VT Codes with More Efficient Encoder
• Explicit Construction of q-ary 2-deletion Correcting Codes with Low Redundancy
• Nonlinear Codes with Low Redundancy