More on codes for combinatorial composite DNA

Abstract In this paper, we focus on constructing unique-decodable and list-decodable codes for the recently studied ( t , e )-composite-asymmetric error-correcting codes (( t , e )-CAECCs). Let $$\mathcal {X}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>X</mml:mi> </mml:math> be an $$m \times n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> binary matrix in which each row has Hamming weight w . If at most t rows of $$\mathcal {X}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>X</mml:mi> </mml:math> contain errors, and in each erroneous row, there are at most e occurrences of $$1 \rightarrow 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>→</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> errors, we say that a ( t , e )-composite-asymmetric error occurs in $$\mathcal {X}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>X</mml:mi> </mml:math> . For general values of m , n , w , t , and e , we propose new constructions of ( t , e )-CAECCs with redundancy at most $$(t-1)\log (m) + O(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where O (1) is independent of the code length m . In particular, this yields a class of (2, e )-CAECCs that are optimal in terms of redundancy. When m is a prime power, the redundancy can be further reduced to $$(t-1)\log (m) - O(\log (m))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . To further increase the code size, we introduce a combinatorial object called a weak $$B_e$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>e</mml:mi> </mml:msub> </mml:math> -set. When $$e = w$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>e</mml:mi> <mml:mo>=</mml:mo> <mml:mi>w</mml:mi> </mml:mrow> </mml:math> , we present an efficient encoding and decoding method for our codes. Finally, we explore potential improvements by relaxing the requirement of unique decoding to list-decoding. We show that when the list size is t ! or an exponential function of t , there exist list-decodable ( t , e )-CAECCs with constant redundancy. When the list size is two, we construct list-decodable (3, 2)-CAECCs with redundancy $$\log (m) + O(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .