1 Introduction↩︎

An \((n,t)\)-break-resilient code (\((n,t)\)-BRC) is a collection of length-\(n\) codewords, each of which can be uniquely recovered when an adversary makes at most \(t\) breaks between adjacent symbols, and the decoder receives only the resulting multiset of at most \(t+1\) fragments. Wang et al. [1] introduced this model and established an \(\Omega(t\log (n/t))\) lower bound over the binary alphabet, together with an explicit binary construction of redundancy \(O(t\log n\log\log n)\). The deterministic block-edit codes of Cheng et al. [2] also imply an explicit binary BRC construction: an unordered collection of at most \(t+1\) fragments can be viewed as a permutation of at most \(t+1\) contiguous blocks, which can be realized by \(O(t)\) block transpositions. Their construction therefore gives redundancy \(O(t\log n\log\log\log n)\).

Yet, both constructions leave a gap to the \(\Omega(t\log (n/t))\) lower bound, and the reason is structural. Both constructions achieve synchronization by decomposing the recovery task into multiple dependent stages. The synchronization information required at each stage is protected separately, rather than being protected once globally. Hence, although the adversary has only a “budget” of \(t\) breaks, each stage must be prepared for the possibility that all \(t\) breaks affect the information needed at that stage. In this sense, the same adversarial budget is effectively paid for repeatedly across the recovery procedure, leading to the extra logarithmic factors in the redundancy.

In this paper, we develop an alternative approach that avoids such a staged recovery routine and achieves the optimal redundancy with a polynomially growing \(t\), i.e., \(t\leq n^{1-\varepsilon}\) for a fixed \(\varepsilon\in(0,1)\). At a high level, the encoder computes a short fingerprint of the message, protects it using an MDS code, and places the encoded header at the start of the codeword. The MDS protection enables the decoder to recover the fingerprint value from the fragmented codeword.

The recovered fingerprint is then used to identify the unique valid ordering of the received fragments. An ordering is retained only if its concatenation begins with the MDS encoding of the recovered fingerprint, and the suffix following this prefix is called a candidate. The fingerprinting function is carefully designed so that, among all candidates, the transmitted message is the unique one whose fingerprint equals the recovered fingerprint value. The decoder can therefore identify the transmitted message without ambiguity.

Related Work↩︎

Coding for unordered fragments has been studied under several models, many of which are motivated by applications in DNA storage. In the sliced-channel model, a codeword is partitioned at prescribed, evenly spaced locations, producing an unordered collection of equal-length substrings [3]–[5]. The torn-paper channel instead places cuts according to a probabilistic process, resulting in unordered fragments of random lengths [6], [7]. An adversarial counterpart was studied in [8] under the restriction that fragment lengths lie between prescribed lower and upper bounds.

In contrast, break-resilient coding [1] constrains only the number of adversarial breaks and imposes no restriction on the lengths of the resulting fragments. The model was subsequently extended to \((t,s)\)-break-resilient codes [9], which additionally tolerate the complete loss of any subset of fragments whose aggregate length is at most \(s\).

Our Contributions↩︎

Our main contribution is an deterministic construction of binary break-resilient codes with order-optimal redundancy in a broad parameter regime. For every fixed \(\varepsilon\in(0,1)\) and parameters satisfying \(t\leq n^{1-\varepsilon}\), the construction has redundancy \[(6t+8) {\lceil\log k\rceil}+(3t+4)\cdot ( {\lceil\log t\rceil}+8)+1 = O(t\log n),\] which matches the information-theoretic lower bound \(\Omega(t\log(n/t))\) up to a constant factor since \(\log(n/t)\geq \varepsilon \log n\). The algebraic fingerprint used in this paper can be seen as an instance of the one-round cover-free recoloring in [10], specialized to the confusion graph defined for the break model.

2 Model and Notation↩︎

We use standard notation for strings. For a positive integer \(n\) and a finite field \(\mathbb{F}_q\), a length-\(n\) string over \(\mathbb{F}_q\) is denoted by \(\mathbf{c}=(c_1,\ldots,c_n)\in\mathbb{F}_q^n\). We write \(|\mathbf{c}|\) for the length of \(\mathbf{c}\) and use \(\circ\) to denote string concatenation. For \(n\in\mathbb{N}\), let \([n]\triangleq\{1,2,\ldots,n\}\). For an interval \(I=\{i,i+1,\ldots,j\}\subseteq[n]\), we denote by \(\mathbf{x}_I\) the substring \(\mathbf{x}_I=(x_i,x_{i+1},\ldots,x_j)\). Throughout this paper, all logarithms are base \(2\) unless otherwise stated.

We next formally define the \(t\)-break channel. Fix integers \(n\ge 1\) and \(0\le t\le n-1\), and a break pattern is a set \[\mathcal{B}=\{b_1,\ldots,b_\tau\}\subseteq[n-1], 0\le\tau\le t, b_1<\cdots<b_\tau .\] Set \(b_0=0\) and \(b_{\tau+1}=n\), and define \[I_{\mathcal{B},i} = \{b_i+1,b_i+2,\ldots,b_{i+1}\}, \qquad i\in\{0,\ldots,\tau\}.\] Thus, \(I_{\mathcal{B},0},\ldots,I_{\mathcal{B},\tau}\) are the consecutive nonempty intervals induced by the break pattern \(\mathcal{B}\).

For an input string \(\mathbf{c}\in{\{0,1\}}^n\), the channel output corresponding to \(\mathcal{B}\) is the unordered multiset \[\mathsf{Frag}_{\mathcal{B}}(\mathbf{c}) \triangleq \{\!\{ \mathbf{c}_{I_{\mathcal{B},0}}, \mathbf{c}_{I_{\mathcal{B},1}}, \ldots, \mathbf{c}_{I_{\mathcal{B},\tau}} \}\!\},\] where \(\{\!\{\cdot\}\!\}\) denotes a multiset. The set of all possible outputs of the \(t\)-break channel on input \(\mathbf{c}\) is \[\mathcal{F}_t(\mathbf{c}) \triangleq \left\{ \mathsf{Frag}_{\mathcal{B}}(\mathbf{c}): \mathcal{B}\subseteq[n-1],\;|\mathcal{B}|\le t \right\}.\] We further define the channel output space as \[\mathcal{F}_{n,t} \triangleq \bigcup_{\mathbf{c}\in{\{0,1\}}^n}\mathcal{F}_t(\mathbf{c}).\]

A binary \((n,t)\)-BRC carrying \(k\) information bits consists of an encoder and a decoder \[\mathsf{Enc}:{\{0,1\}}^k\to{\{0,1\}}^n, \qquad \mathsf{Dec}:\mathcal{F}_{n,t}\to{\{0,1\}}^k,\] such that, for every \(\mathbf{x}\in{\{0,1\}}^k\) and every break pattern \(B\subseteq[n-1]\) with \(|B|\le t\), \[\label{eq:brc-correctness} \mathsf{Dec} \bigl( \mathsf{Frag}_{B}(\mathsf{Enc}(\mathbf{x})) \bigr) = \mathbf{x}.\tag{1}\] The associated codebook is \[\mathcal{C}=\mathsf{Enc}({\{0,1\}}^k)\subseteq{\{0,1\}}^n.\]

3 Code Construction↩︎

In this section, we present our code construction. Throughout, we assume that \(t\ge 1\) and \(k>\max\{t,16\}\), and define \[\label{eq:define-big-var} T= t+1, K= 2T+2,~and~N=K+t.\tag{2}\]

3.1 Preliminaries↩︎

Recall that the adversary may make at most \(t\) breaks in the codeword, after which the decoder receives the resulting unordered multiset of at most \(t+1\) fragments. Since the order of these fragments is lost, decoding must account for all strings that can be obtained by concatenating the fragments. We formalize this collection of possible assemblies as follows.

Next, we briefly review the definition of mutually uncorrelated (MU) codes that will be used in the code construction. A code \(\mathcal{C}_{\mathrm{MU}}\) is mutually uncorrelated (MU) if, for any two (not necessarily distinct) codewords \(\mathbf{x},\mathbf{y}\in\mathcal{C}_{\mathrm{MU}}\), no non-empty proper prefix of \(\mathbf{x}\) is equal to a suffix of \(\mathbf{y}\). Equivalently, no two codewords in \(\mathcal{C}_{\mathrm{MU}}\) can overlap with each other at a nontrivial shift.

For a string \(\mathbf{u}\), let \(\mathrm{zr}(\mathbf{u})\) denote the length of its longest run of zeros. Define a collection of words \[\label{eq:define-c-mu} \mathcal{C}_{\mathrm{MU}} = \left\{ 0^{ {\lceil\log k\rceil}-1}\circ 1\circ\mathbf{u}\circ 1 \mid \mathbf{u}\in{\{0,1\}}^{ {\lceil\log t\rceil}+4},~\mathrm{zr}(\mathbf{u}) < {\lceil\log k\rceil}-1 \right\}.\tag{3}\] The next lemma verifies that this construction yields sufficiently many mutually uncorrelated words.

The above lemma allows us to define markers, which are \(N\) distinct MU codewords \[\label{eq:define-markers} \mathbf{m}_0,\mathbf{m}_1,\ldots,\mathbf{m}_{N-1}\in\mathcal{C}_\mathrm{MU}\subset {\{0,1\}}^{n_\mathrm{MU}},~where~n_\mathrm{MU}= {\lceil\log k\rceil}+ {\lceil\log t\rceil}+5.\tag{4}\]

3.2 Encoding↩︎

The encoder maps an information word \(\mathbf{x}\in{\{0,1\}}^k\) to an \((n,t)\)-break-resilient codeword \(\mathbf{c}\in{\{0,1\}}^n\). Specifically, the information word \(\mathbf{x}\in{\{0,1\}}^k\) is first mapped to a marker-free binary string \(\mathbf{y}\in{\{0,1\}}^{k+1}\) of length \(k+1\), to which a sketch is then prepended to construct the final output codeword \(\mathbf{c}\).

The marker-removal transform draws heavily on the techniques presented in [11] and [12], which iteratively replace a marker from the original string with its identity information and positional information. To streamline the presentation, the transform, as well as its inverse, is presented in Appendix 6.

Let \(Q\) be a power of \(2\) such that \[\label{eq:define-q} k\cdot |\mathcal{B}_T(\mathbf{y})|\leq k\cdot (k+1)^{T}\cdot (T+1)^2 \leq Q <2\cdot k\cdot (k+1)^{T}\cdot (T+1)^2 .\tag{5}\] For the constrained string \(\mathbf{y}=y_0y_1\cdots y_k\), define the polynomial \[p_\mathbf{y}(z) = \sum_{i=0}^k y_iz^i\in\mathbb{F}_Q[z].\] We fix an arbitrary ordering of the elements of \(\mathbb{F}_Q\). Following this ordering, the encoder chooses the first \(\alpha\in\mathbb{F}_Q\) such that \[\label{eq:define-alpha} p_\mathbf{y}(\alpha)\neq p_{\mathbf{y}'}(\alpha)for every \mathbf{y}'\in\mathcal{B}_T(\mathbf{y})\setminus\{\mathbf{y}\}.\tag{6}\] The fingerprint of \(\mathbf{y}\) is then defined as \[\label{eq:define-fingerprint} \mathtt{fp}_\mathbf{y}=\operatorname{bin}(\alpha)\circ \operatorname{bin}(p_\mathbf{y}(\alpha))\in{\{0,1\}}^{2\log Q}.\tag{7}\]

The encoder slices \(\mathtt{fp}_\mathbf{y}\) into \(K\) chunks, each of length \[{\lceil\frac{2\log Q}{K}\rceil}\leq {\lceil 2\cdot\frac{1+(T+1)\log(k+1)+2\log(T+1)}{2(T+1)} \rceil}\leq {\lceil \log(k+1)\rceil}+ {\lceil\frac{1+2\log(T+1)}{(T+1)} \rceil}\leq {\lceil\log k\rceil} +3.\] The encoder then pads each chunk with zeros and treats them as field elements in \(\mathbb{F}_{2^{ {\lceil\log k\rceil}+3}}\), and generates \(N\) MDS blocks \[\mathbf{r}_0,\mathbf{r}_2,\ldots,\mathbf{r}_{N-1}\in{\{0,1\}}^{ {\lceil\log k\rceil}+3}\] using a \([N,K]\) MDS code such that any \(K\) MDS blocks recover \(\mathtt{fp}_\mathbf{y}\). The output codeword is then \[\label{eq:define-codeword} \mathbf{c}=\mathbf{s}\circ\mathbf{y},~where~\mathbf{s}=\mathbf{r}_0\circ\mathbf{m}_0\circ\mathbf{r}_1\circ\mathbf{m}_1\circ\cdots\circ\mathbf{r}_{N-1}\circ\mathbf{m}_{N-1}.\tag{8}\]

3.3 Decoding↩︎

Let \(\mathbf{c}=\mathbf{s}\circ\mathbf{y}\) be the codeword generated from the message \(\mathbf{x}\) using the procedure described in Section 3.2. Decoding begins by identifying markers from fragments and recovering \(\mathtt{fp}_\mathbf{y}\).

The decoder learns \(\alpha\) and \(\beta=p_\mathbf{y}(\alpha)\), i.e., the evaluation of the polynomial \(p_\mathbf{y}\) at \(\alpha\), from the recovered \(\mathtt{fp}_\mathbf{y}\). Then, for all possible assemblies of the received fragments whose prefixes match \(\mathbf{s}\), define \(\mathcal{W}\) as the collection of their suffixes, which serve as candidates for the true \(\mathbf{y}\). We now show that \(\mathbf{y}\) is the only candidate that satisfies the condition \(\beta=p_\mathbf{y}(\alpha)\).

First, Theorem 4 shows that every candidate \(\mathbf{w}\in\mathcal{W}\setminus\{\mathbf{y}\}\) belongs to the \((t+1)\)-break ball of \(\mathbf{y}\). The proof is deferred to Appendix 7 to streamline the flow of presentation.

Then, by the definition of \(\alpha\), the uniqueness of \(\mathbf{y}\) follows immediately.

The decoder examines every candidate \(\mathbf{w}\in\mathcal{W}\), evaluating \(p_\mathbf{w}(\alpha)\) until it finds \(\mathbf{y}\). Finally, it outputs the unique candidate \(\mathbf{x}\) by inverting the marker-removal transform, which concludes the decoding procedure.

4 Analysis↩︎

In this section, we analyze the redundancy and computational complexity of the construction presented in Section 3.

5 Conclusion↩︎

We presented an deterministic binary break-resilient code with redundancy \[(6t+8) {\lceil\log k\rceil}+(3t+4)\cdot ( {\lceil\log t\rceil}+8)+1 = O(t\log n).\] For every \(t\leq n^{1-\varepsilon}\), this matches the information-theoretic lower bound up to a constant factor in the regime \(t\leq n^{1-\varepsilon}\).

6 Marker-Removal Transform↩︎

For fixed integers \(l,k>0\), denote a set of \(0\)-prefixed markers by \[\mathbf{m}_0,\ldots,\mathbf{m}_{l-1}\in 0\circ{\{0,1\}}^{m-1},~where~m> {\lceil\log k\rceil}+ {\lceil\log l\rceil}+1.\] We describe a transform from an arbitrary message \(\mathbf{x}\in{\{0,1\}}^k\) to a marker-free string \(\mathbf{y}\in{\{0,1\}}^{k+1}\), as well as its inverse.

6.1 Transform↩︎

The encoder first appends a sentinel bit \(1\) to \(\mathbf{x}\) and initializes \[\mathbf{z}=\mathbf{x}\circ 1.\] While \(\mathbf{z}\) contains a marker, let the leftmost occurrence be \(\mathbf{m}_j\), and write \(\mathbf{z}\) as \[\mathbf{z}=\mathbf{z}'\circ\mathbf{m}_j\circ\mathbf{z}''~where~|\mathbf{z}''|=d.\] Let \(\operatorname{bin}_{{\mathrm{id}}}(j)\in{\{0,1\}}^{ {\lceil\log l\rceil}}\) and \(\operatorname{bin}_{{\mathrm{pos}}}(d)\in{\{0,1\}}^{ {\lceil\log k\rceil}}\) denote the binary representation of marker identity and right offset of \(\mathbf{m}_j\), respectively. Note that \(d\) is the distance of the deleted marker from the right end, rather than its absolute position in \(\mathbf{z}\).

During each step, the encoder deletes \(\mathbf{m}_j\) from \(\mathbf{z}\), and appends a pointer, defined as the identity and position information of \(\mathbf{m}_j\) followed by a sentinel bit \(0\). Specifically, \(\mathbf{z}\) is updated as \[\mathbf{z}\gets\mathbf{z}'\circ\mathbf{z}'' \circ\operatorname{bin}_{{\mathrm{id}}}(j) \circ\operatorname{bin}_{{\mathrm{pos}}}(|\mathbf{z}''|) \circ 0.\] The encoder repeats this step until \(\mathbf{z}\) is marker-free; the termination is guaranteed in the following lemma.

At termination, the resulting \(\mathbf{z}\) is marker-free, but may be shorter than \(k+1\). The encoder then prepends a run of \(1\)’s to it, and outputs \[\mathbf{y}=1^{k+1-|\mathbf{z}|}\circ\mathbf{z}\in {\{0,1\}}^{k+1}.\] Since every marker is \(0\)-prefixed, prepending a run of \(1\)’s does not introduce a new marker occurrence. Therefore,

6.2 Inverse↩︎

The inverse mapping recovers \(\mathbf{x}\) from the marker-free \(\mathbf{y}\) by reversing the aforementioned replacement steps in the opposite order. The decoder initializes \(\mathbf{z}=\mathbf{y}\). The last bit of \(\mathbf{z}\) informs the decoder whether the suffix of \(\mathbf{z}\) is a pointer. While it is \(0\), the decoder learns from suffix the marker identity \(\mathbf{m}_j\) and marker position \(d\). Recall that \(d\) is the distance of \(\mathbf{m}_j\) from the right end; this design enables the decoder to insert the marker without knowing the number of padded \(1\)’s on the left of \(\mathbf{y}\).

The decoder then removes the suffix pointer from \(\mathbf{z}\), and obtains the intermediate string \[\mathbf{z}'\circ\mathbf{z}'',~where~|\mathbf{z}''|=d.\] It recovers the deleted marker by setting \[\mathbf{z}\gets \mathbf{z}'\circ\mathbf{m}_j\circ\mathbf{z}''.\]

Once the last bit of \(\mathbf{z}\) is \(1\), all replacement steps have been reversed, and the current string is \[\mathbf{z}=1^{|\mathbf{z}|-k-1}\circ\mathbf{x}\circ 1.\] The decoder removes the final sentinel bit \(1\) and iteratively removes the leading \(1\)’s until the string length is \(k\), thereby recovering the original information word \(\mathbf{x}\). Hence,

7 Proof of Theorem 4↩︎

Let \(r=|\mathbf{s}|\) and \(m=|\mathbf{y}|=|\mathbf{w}|\). We first split the fragment that crosses the boundary between the prefix \(\mathbf{s}\) and the suffix \(\mathbf{y}\) in \(\mathbf{c}\), and the fragment that crosses the boundary between the prefix \(\mathbf{s}\) and suffix \(\mathbf{w}\) in \(\mathbf{c}'\), if it exists. Now, every fragment either resides entirely in the prefix or entirely in the suffix in \(\mathbf{c}\). Meanwhile, every fragment either resides entirely in the prefix or entirely in the suffix, in \(\mathbf{c}'\). See Figure 1 (a) for an illustrative example.

The split process makes at most \(2\) extra breaks to the fragments. Let \(p\) denote the number of prefix fragments in \(\mathbf{c}\), and let \(s\) denote the number of suffix fragments in \(\mathbf{c}\), and we have \[\label{eq:bound-fragments} p+s\leq t+3.\tag{9}\]

Since \(\mathbf{c}'\) is a permuted assembly of the fragments that partition \(\mathbf{c}\), it naturally defines a permutation \(\varphi:[n]\to[n]\), where \(\varphi(i)\) is the coordinate in \(\mathbf{c}'\) occupied by the bit which originally occupied coordinate \(i\) in \(\mathbf{c}\). Formally, \[\label{eq:j-phi-j} c_j=c'_{\varphi(j)}~for~j\in[n].\tag{10}\] Note that this permutation \(\varphi\) is order-preserving within the range of a fragment. That is, for coordinates \(i,j\) such that the bits \(c_i,c_j\) lie in one fragment, \[i<j\Longrightarrow \varphi(i)<\varphi(j).\] Moreover, since \(\mathbf{c}\) and \(\mathbf{c}'\) share the common prefix \(\mathbf{s}\), we have \[\label{eq:common-prefix} c_j=c'_{j}~for~j\in[r].\tag{11}\]

Let \(\mathcal{P}=[r]\), \(\mathcal{S}=\{r+1,\ldots,n\}\), and for every \(j\in\mathcal{S}\), define the first-return time \[u(j)=\min \{l>0\mid \varphi^{l}(j)\in \mathcal{S}\}.\] It is well-defined since the cycle of \(\varphi\) containing \(j\) eventually returns to \(j\). Equivalently, \(u(j)\) is the distance between coordinate \(j\in\mathcal{S}\) and the next coordinate that is also in \(\mathcal{S}\) within this cycle of \(\varphi\). Define \[\label{eq:define-psi} \psi(j)= \begin{cases} j, &j\in\mathcal{P},\\ \varphi^{u(j)}(j), &j\in\mathcal{S}. \end{cases}\tag{12}\] We first verify that \(\psi\) is a permutation in the following lemma.

Lemma 6 allows us to permute bits \(\mathbf{c}\) with \(\psi\), and leads to the following lemma.

We now describe a procedure of constructing \(\mathbf{c}'=\mathbf{d}\) by permuting not the individual bits, but fragments in \(\mathbf{c}\) with \(\psi\). Starting from prefix fragments, their positions remain unchanged and they partition the prefix region. Then, for every suffix fragment, we iteratively permute it using \(\varphi\). During each application of \(\varphi\), if the image in \(\mathcal{P}\) crosses an internal boundary between two prefix fragments, split the fragment at the boundary and and continue with the resulting pieces separately. The iteration continues until every piece reaches \(\mathcal{S}\).

Although the fragments are repeatedly being split during the procedure, the number of such splits is bounded.

Finally, since the procedure has introduced at most \(p-1\) splits to the suffix fragments in \(\mathbf{c}\), there are at most \[s+p-1 \overset{\eqref{eq:bound-fragments}}{\leq} t+2\] fragments in the suffix region after the procedure; they form a multiset that partitions both \(\mathbf{y}\) and \(\mathbf{w}\). Therefore, \(\mathbf{w}\) can be obtained by breaking \(\mathbf{y}\) at most \(t+1\) times, i.e., \(\mathbf{w}\in\mathcal{B}_{t+1}(\mathbf{y})\).

References↩︎

---

1. Canran Wang is an independent researcher (email: crwang1209@gmail.com).↩︎