Designs, Codes and Cryptography Прикладные компьютерные науки

More on codes for combinatorial composite DNA

Zuo Ye, Omer Sabary, Ryan Gabrys, Eitan Yaakobi, Ohad Elishco
Springer Nature · 2025-05-15 · DOI 10.1007/s10623-025-01634-8

Аннотация

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}$$ X be an $$m \times n$$ m × n binary matrix in which each row has Hamming weight w . If at most t rows of $$\mathcal {X}$$ X contain errors, and in each erroneous row, there are at most e occurrences of $$1 \rightarrow 0$$ 1 → 0 errors, we say that a ( t , e )-composite-asymmetric error occurs in $$\mathcal {X}$$ X . 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)$$ ( t - 1 ) log ( m ) + O ( 1 ) , 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))$$ ( t - 1 ) log ( m ) - O ( log ( m ) ) . To further increase the code size, we introduce a combinatorial object called a weak $$B_e$$ B e -set. When $$e = w$$ e = w , 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)$$ log ( m ) + O ( 1 ) .

Читать у издателя →