This paper tackles two problems that fall under the study of coding for insertions and deletions. These problems are motivated by several applications, among them is reconstructing strands in DNA-based storage systems. Under this paradigm, a word is transmitted over some fixed number of identical independent channels and the goal of the decoder is to output the transmitted word or some close approximation of it. The first part of the paper studies optimal decoding for a special case of the deletion channel, referred by the k-deletion channel, which deletes exactly k symbols of the transmitted word uniformly at random. In this part, the goal is to understand how an optimal decoder operates in order to minimize the expected normalized distance. A full characterization of an efficient optimal decoder for this setup, referred to as the minimum expected distance (MED) decoder, is given for a channel that deletes one or two symbols. For <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$k=1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> it is shown that when the code is the entire space, the decoder is the lazy decoder which simply returns the channel output. Similarly, for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$k=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> it is shown that the decoder acts as the lazy decoder in almost all cases and when the longest run is significantly long (roughly <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(2-\sqrt{2})n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>-</mo> <msqrt> <mn>2</mn> </msqrt> <mo stretchy="false">)</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> when n is the word length), it prolongs the longest run by one symbol. The second part of this paper studies the deletion channel that deletes a symbol with some fixed probability p, while focusing on two instances of this channel. Since operating the MED decoder, in this case, is computationally infeasible, we study a slightly degraded version of this decoder for two channels and study its expected normalized distance. We observe that the dominant error patterns are deletions in the same run or errors resulting from alternating sequences. Based on these observations, we derive lower bounds on the expected normalized distance of the degraded MED decoder for any transmitted q-ary sequence of length n and any deletion probability p. We further show that as the word length approaches infinity and the channel’s deletion probability p approaches zero, these bounds converge to approximately <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\frac{3q - 1}{q - 1} p^2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mrow> <mn>3</mn> <mi>q</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>q</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> <msup> <mi>p</mi> <mn>2</mn> </msup> </mrow> </math></EquationSource> </InlineEquation>. These theoretical results are verified by corresponding simulations.

On the decoding error weight of one or two deletion channels

期刊论文
发表日期：

2026年8月4日

查看全文

Omer Sabary,
Daniella Bar-Lev,
Yotam Gershon,
Alexander Yucovich,
Eitan Yaakobi

摘要

This paper tackles two problems that fall under the study of coding for insertions and deletions. These problems are motivated by several applications, among them is reconstructing strands in DNA-based storage systems. Under this paradigm, a word is transmitted over some fixed number of identical independent channels and the goal of the decoder is to output the transmitted word or some close approximation of it. The first part of the paper studies optimal decoding for a special case of the deletion channel, referred by the k-deletion channel, which deletes exactly k symbols of the transmitted word uniformly at random. In this part, the goal is to understand how an optimal decoder operates in order to minimize the expected normalized distance. A full characterization of an efficient optimal decoder for this setup, referred to as the minimum expected distance (MED) decoder, is given for a channel that deletes one or two symbols. For $k=1$ $k = 1$ it is shown that when the code is the entire space, the decoder is the lazy decoder which simply returns the channel output. Similarly, for $k=2$ $k = 2$ it is shown that the decoder acts as the lazy decoder in almost all cases and when the longest run is significantly long (roughly $(2-\sqrt{2})n$ $(2 - \sqrt{2}) n$ when n is the word length), it prolongs the longest run by one symbol. The second part of this paper studies the deletion channel that deletes a symbol with some fixed probability p, while focusing on two instances of this channel. Since operating the MED decoder, in this case, is computationally infeasible, we study a slightly degraded version of this decoder for two channels and study its expected normalized distance. We observe that the dominant error patterns are deletions in the same run or errors resulting from alternating sequences. Based on these observations, we derive lower bounds on the expected normalized distance of the degraded MED decoder for any transmitted q-ary sequence of length n and any deletion probability p. We further show that as the word length approaches infinity and the channel’s deletion probability p approaches zero, these bounds converge to approximately $\frac{3q - 1}{q - 1} p^2$ $\frac{3 q - 1}{q - 1} p^{2}$ . These theoretical results are verified by corresponding simulations.