A New Construction of Non-Binary Deletion Correcting Codes and their Decoding

Michael Schaller, Beatrice Toesca, Van Khu Vu · 2025

Read A New Construction of Non-Binary Deletion Correcting Codes and their Decoding by Michael Schaller, Beatrice Toesca, Van Khu Vu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13534.txt.

Introduction

Michael Schaller, Beatrice Toesca, and Van Khu Vu build a new kind of error-correcting code in a 2025 paper. The codes guard data stored as symbols beyond plain zero and one, and they must survive deletions, where symbols vanish from the string. The team focuses on codes where every symbol in a codeword is distinct.

Their construction grows out of set codes and permutation codes, two older families with handy structure. They show the new codes can fix several deletions and give a step-by-step method to decode a damaged string back to the original. For one range of settings, their codes are larger than any rival codes of the same type known before. Larger codes mean more messages can be protected at the same length.

Catalog record

CREATORMichael Schaller, Beatrice Toesca, Van Khu Vu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13534

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A New Construction of Non-Binary Deletion Correcting Codes and their Decoding Michael Schaller, Beatrice Toesca, Van Khu Vu Abstract Non-binary codes correcting multiple deletions have recently attracted a lot of attention. In this work, we focus on multiplicity-free codes, a family of non-binary codes where all symbols are distinct. Our main contribution is a new explicit construction of such codes, based on set and permutation codes. We show that our multiplicity-free codes can correct multiple deletions and provide a decoding algorithm. We also show that, for a certain regime of parameters, our constructed codes have size larger than all the previously known non-binary codes correcting multiple deletions. 1 Introduction Codes correcting synchronization errors have a long history from the seminal paper by Levenshtein in 1966 [ 21 ] , where a binary code correcting a single deletion was presented. Levenshtein already established an interesting connection between codes over multiplicity-free sets and ordered partial Steiner systems [ 22 ] . In 1984, Tenengolts presented the first construction of a non-binary code correcting a single deletion [ 32 ] . From a practical point of view, non-binary deletion correcting codes have applications in DNA-based storage systems and racetrack memories. In DNA-based storage systems, quaternary codes correcting multiple deletions are required [ 2 ] . In racetrack memories, the non-binary deletion correcting codes have a large alphabet size depending on the number of read-heads in the racetrack memory. [ 5 , 3 ] . For example, in order to correct over-shift errors in racetrack memories, a non-binary code correcting multiple blocks of deletions was proposed [ 3 ] . Recently, there were numerous breakthrough results both for binary [ 13 , 29 , 27 ] and non-binary [ 16 , 24 , 28 , 31 , 10 , 19 , 6 ] deletion correcting codes. Other papers consider the case that there is a given number of deletions [ 28 , 24 ] or that there is a large number of deletions [ 16 , 23 ] . To explain better some of these results and our contribution to the paper, we introduce some notation. Let q,n be two integers, \Sigma_{q}=\{0,1,\ldots,q-1\} be the alphabet of size q and [n] be the set \{1,2,\ldots,n\} . Let \Sigma_{q}^{n} be the set of all q -ary sequences of length n. For n\leq q , a sequence \boldsymbol{x}=(x_{1},\ldots,x_{n})\in\Sigma_{q}^{n} is called a multiplicity-free sequence of length n in the alphabet \Sigma_{q} if x_{i}\neq x_{j} for any given pair i\neq j . We denote by M_{q}^{n} the set of all multiplicity-free sequences of length n in \Sigma_{q} . Let C(q,n,t) denote a q -ary code of length n that can correct t deletions. We call \log_{2}|\Sigma_{q}^{n}|-\log_{2}|C(q,n,t)| the bit redundancy or redundancy of the code C(q,n,t) . The work in [ 27 , 4 , 10 , 24 ] shows that there are a few families of non-binary codes correcting multiple deletions approaching the Singleton bound for some regime of parameters. In [ 4 , 17 ] , the authors used a sequence of length n of small alphabet size to locate all deletion errors and an erasure correcting code to correct them. In total, they need at least t\log q+\Theta(n) bits of redundancy to construct a non-binary code that can correct t errors. In [ 24 ] , when the alphabet size q is exponential in the code length n , the authors presented a construction of codes approaching the Singleton bound. To the best of our knowledge, in the regime in which the alphabet size q is a power of n , there is no known construction arbitrarily close to the Singleton bound for fixed t . For any q>n , there is a construction of q -ary codes correcting t deletions with at most 30t\log q bits of redundancy [ 28 ] . In the recent preprint [ 18 ] , Hagiwara and Vu provided a construction of codes over multiplicity-free sets with an efficient encoding algorithm. They obtained a family of q -ary codes of length n correcting t deletions with at most 5t\log q bits of redundancy. Our objective is to construct a new class of q -ary codes of length n correcting t deletions for any q>n . The main result provides a new construction of codes over multiplicity-free sets based on results in permutation codes and set codes. In the case of large n and q>n^{2+\varepsilon} for arbitrary positive \varepsilon , our codes have redundancy at most t\log(q)+(3t-1)\log(n)+\delta t+O\left(\frac{1}{n^{\varepsilon}}\right) for arbitrary \delta>0 . The construction we derive is based on a decomposition of a multiplicity-free sequence into a permutation and a set of symbols. We observe that if there is a set code that can correct multiple deletions and a permutation code that can correct multiple unstable deletions, we can obtain a multiplicity-free code that can correct multiple deletions. The idea also works for stable deletions in permutation codes. The paper is structured as follows: In the next section, we review the results on set codes and binary constant weight codes. In Section 3 , we provide definitions and recent results on permutation codes that can correct multiple stable/unstable deletions. In Section 4 , we provide the main results of the paper by combining permutation codes and set codes to obtain a new family of multiplicity-free codes that can correct multiple deletions. In Section 4.2 , we analyze the size of our codes and compare it with previous results in the literature. 2 Set Codes and Binary Constant-Weight Codes 2.1 Set Codes A set A\subset\Sigma_{q} is called an n -subset of the alphabet \Sigma_{q} if it has n elements, that is |A|=n . We denote with \binom{\Sigma_{q}}{n} the set of all n -subsets of \Sigma_{q} . In the following, we introduce the notion of set codes , which will play a crucial role in our construction of non-binary deletion correcting codes. Definition 1 . Given an alphabet \Sigma_{q} , a set code of length n is a family C_{S}(q,n)\subseteq\binom{\Sigma_{q}}{n} . Note that a set code can also be interpreted as an n -uniform hypergraph, where each edge corresponds to a codeword of the set code. Definition 2 . A set code C_{S}(q,n) is said to correct t deletions if there are no two sets in C_{S}(q,n) that result in the same set after at most t deletions. This tells us that after t deletions, the codeword can still be uniquely recovered. Therefore, we are dealing with a partial Steiner system with parameters S(n-t,n,q) . The problem of maximizing the size of a set code correcting deletions, then corresponds to the problem of maximizing the number of blocks in the corresponding partial Steiner system. There are several results on the size of partial Steiner systems, see in particular [ 25 , 20 ] . However, these results give only probabilistic constructions and no decoding algorithms. Moreover, they mainly provide results in the case when the deletion correction capability t is close to the length n of the set code. In the following, we explain the correspondence of set codes with binary constant-weight codes. In Section 2.3 , we will then exploit this correspondence to explicitly create a set code correcting t deletions. 2.2 Correspondence

Read the complete text