×

Balanced reconstruction codes for single edits. (English) Zbl 07873235

Summary: Motivated by the sequence reconstruction problem initiated by Levenshtein, reconstruction codes were introduced by Cai et al. to combat errors when a fixed number of noisy channels are available. The central problem on this topic is to design codes with sizes as large as possible, such that every codeword can be uniquely reconstructed from any \(N\) distinct noisy reads, where \(N\) is fixed. In this paper, we study binary reconstruction codes with the constraint that every codeword is balanced, which is a fundamental requirement in the technique of DNA-based storage. For all possible channels with a single edit error and their variants, we design asymptotically optimal balanced reconstruction codes for all \(N\), and show that the number of their redundant symbols decreases from \(\frac{3}{2}\log_2 n+O(1)\) to \(\frac{1}{2}\log_2n+\log_2\log_2n+O(1)\), and finally to \(\frac{1}{2}\log_2n+O(1)\) but with different speeds, where \(n\) is the length of the code. Compared with the unbalanced case, our results imply that the balanced property does not reduce the rate of the reconstruction code in the corresponding codebook.

MSC:

94Bxx Theory of error-correcting codes and error-detecting codes
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

References:

[1] Agrell, E.; Vardy, A.; Zeger, K., Upper bounds for constant-weight codes, IEEE Trans. Inf. Theory, 46, 7, 2373-2395, 2000 · Zbl 0997.94036
[2] Al-Bassam, S.; Bose, B., Design of efficient error-correcting balanced codes, IEEE Trans. Comput., 42, 10, 1261-1266, 1993
[3] Bar-Lev D., Kobovich A., Leitersdorf O., Yaakobi E.: Universal framework for parametric constrained coding (2023). arXiv:2304.01317.
[4] Berge, C., Hypergraphs. Combinatorics of Finite Sets, 1989, Amsterdam: North Holland, Amsterdam · Zbl 0674.05001
[5] Bibak, K.; Milenkovic, O., Explicit formulas for the weight enumerators of some classes of deletion correcting codes, IEEE Trans. Inf. Theory, 67, 3, 1809-1816, 2019
[6] Bitan, S.; Etzion, T., Constructions for optimal constant-weight cyclically permutable codes and difference families, IEEE Trans. Inf. Theory, 41, 1, 77-87, 1995 · Zbl 0823.94023
[7] Blake-Wilson, S.; Phelps, KT, Constant weight codes and group divisible designs, Des. Codes Cryptogr., 16, 1, 11-27, 1999 · Zbl 0945.05011
[8] Cai, K.; Kiah, HM; Nguyen, TT; Yaakobi, E., Coding for sequence reconstruction for single edits, IEEE Trans. Inf. Theory, 68, 1, 66-79, 2021 · Zbl 1489.94056
[9] Cai, K.; Chee, YM; Gabrys, R.; Kiah, HM; Nguyen, T., Correcting a single indel/edit for DNA-based data storage: linear-time encoders and order-optimality, IEEE Trans. Inf. Theory, 67, 6, 3438-3451, 2021 · Zbl 1473.94040
[10] Chee, YM; Kiah, HM; Vardy, A.; Vu, VK; Yaakobi, E., Coding for racetrack memories, IEEE Trans. Inf. Theory, 64, 11, 7094-7112, 2018 · Zbl 1431.94050
[11] Chrisnata J., Kiahy H.M.: Correcting two deletions with more reads. In: Proceedings of IEEE International Symposium on Information Theory, Melbourne, Australia, pp. 2666-2671 (2021).
[12] Chrisnata J., Kiah H.M., Yaakobi E.: Optimal reconstruction codes for deletion channels. In: Proceedings of IEEE International Symposium on Information Theory, Kapolei, USA, pp. 279-283 (2020).
[13] Chrisnata, J.; Kiah, HM; Yaakobi, E., Correcting deletions with multiple reads, IEEE Trans. Inf. Theory, 68, 11, 7141-7158, 2022 · Zbl 1534.94059
[14] Deng, RH; Herro, MA, DC-free coset codes, IEEE Trans. Inf. Theory, 34, 4, 786-792, 1988 · Zbl 0656.94017
[15] Fu, FW; Wei, KW, Self-complementary balanced codes and quasi-symmetric designs, Des. Codes Cryptogr., 27, 3, 271-279, 2002 · Zbl 1022.94024
[16] Gabrys R., Yaakobi E.: Sequence reconstruction over the deletion channel. In: Proceedings of IEEE International Symposium on Information Theory, Barcelona, Spain, pp. 1596-1600 (2016).
[17] Gabrys, R.; Yaakobi, E., Sequence reconstruction over deletion channel, IEEE Trans. Inf. Theory, 64, 4, 2924-2931, 2018 · Zbl 1392.94906
[18] Graham, RL; Sloane, NJA, Lower bounds for constant weight codes, IEEE Trans. Inf. Theory, 26, 1, 37-43, 1980 · Zbl 0441.94012
[19] Györfi, NQAL; Massey, JL, Constructions of binary constant-weight cyclic codes and cyclically permutable codes, IEEE Trans. Inf. Theory, 38, 3, 940-949, 1992 · Zbl 0749.94019
[20] Immink, K.; Cai, K., Properties and constructions of constrained codes for DNA-based data storage, IEEE Acess, 8, 49523-49531, 2020
[21] Jiang, T.; Vardy, A., Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes, IEEE Trans. Inf. Theory, 50, 8, 1655-1664, 2004 · Zbl 1298.94151
[22] Knuth, D., Efficient balanced codes, IEEE Trans. Inf. Theory, 32, 1, 51-53, 1986 · Zbl 0591.94030
[23] Konstantinova E.: Reconstruction of signed permutations from their distorted patterns. In: Proceedings of IEEE International Symposium on Information Theory, Adelaide, Australia, pp. 474-477 (2005).
[24] Konstantinova, E., On reconstruction of signed permutations distorted by reversal errors, Discret. Math., 308, 5-6, 974-984, 2008 · Zbl 1136.05001
[25] Kulkarni, AA; Kiyavash, N., Nonasymptotic upper bounds for deletion correcting codes, IEEE Trans. Inf. Theory, 59, 8, 5115-5130, 2013 · Zbl 1364.94759
[26] Lan, L.; Chang, Y., Two-weight codes: upper bounds and new optimal constructions, Discret. Math., 342, 11, 3098-3113, 2019 · Zbl 1420.94116
[27] Leiss, E.L.: Data integrity in digital optical disks. IEEE Trans. Comput. c-33(9):818-827 (1984).
[28] Lenz, A.; Siegel, PH; Wachter-Zeh, A.; Yaakobi, E., Coding over sets for DNA storage, IEEE Trans. Inf. Theory, 66, 4, 2331-2351, 2020 · Zbl 1448.94145
[29] Levenshtein V.I.: Binary codes capable of correcting deletions, insertions and reversals. Dokl. Akad. Nauk SSSR, 1965, 163(4):845-848, 1965. English translation in Sov. Phys. Dokl., 10(8):707-710. (1966). · Zbl 0149.15905
[30] Levenshtein, VI, Efficient reconstruction of sequences, IEEE Trans. Inf. Theory, 47, 1, 2-22, 2001 · Zbl 1029.94019
[31] Levenshtein, VI, Efficient reconstruction of sequences from their subsequences or supersequences, J. Comb. Theory A, 93, 2, 310-332, 2001 · Zbl 0992.68155
[32] Levenshtein, VI; Siemons, J., Error graphs and the reconstruction of elements in groups, J. Comb. Theory A, 116, 4, 795-815, 2009 · Zbl 1219.05095
[33] Levenshtein, VI; Konstantinova, E.; Konstantinov, E.; Molodtsov, S., Reconstruction of a graph from 2-vicinities of its vertices, Discret. Appl. Math., 156, 9, 1399-1406, 2008 · Zbl 1144.05046
[34] Matoušek, J.; Nešetřil, J., Invitation to Discrete Mathematics, 2009, Oxford: Oxford University Press, Oxford · Zbl 1152.05002
[35] Nguyen, T.; Cai, K.; Immink, K., Efficient design of subblock energy-constrained codes and sliding window-constrained codes, IEEE Trans. Inf. Theory, 67, 12, 7914-7924, 2021 · Zbl 1489.94065
[36] Ordentlich, E.; Roth, RM, Two-dimentional weight-constrained codes through enumeration bounds, IEEE Trans. Inf. Theory, 46, 4, 1292-1301, 2000 · Zbl 1001.94051
[37] Sala, F.; Gabrys, R.; Schoeny, C.; Dolecek, L., Exact reconstruction from insertions in synchronization codes, IEEE Trans. Inf. Theory, 63, 4, 2428-2445, 2017 · Zbl 1366.94453
[38] Schoeny, C.; Wachter-Zeh, A.; Gabrys, R.; Yaakobi, E., Codes correcting a burst of deletions or insertions, IEEE Trans. Inf. Theory, 63, 4, 1971-1985, 2017 · Zbl 1366.94653
[39] Shi, M.; Sepasdar, Z.; Alahmadi, A.; Solé, P., On two-weight \({\mathbb{Z} }_{2^k} \)-codes, Des. Codes Cryptogr., 86, 6, 1201-1209, 2018 · Zbl 1387.94118
[40] Shi, M.; Wang, X.; Solé, P., Two families of two-weight codes over \({\mathbb{Z} }_4\), Des. Codes Cryptogr., 88, 12, 2493-2505, 2020 · Zbl 1483.94071
[41] Sloane N.J.A.: On single-deletion-correcting codes. In: Codes and Designs: Proceedings of Conference Honoring Professor D.K. Ray-Chaudhuri on the Occasion of his 65th Birthday (2000). · Zbl 1021.94530
[42] Sun, Y.; Ge, G., Correcting two-deletion with a constant number of reads, IEEE Trans. Inf. Theory, 69, 5, 2969-2982, 2023 · Zbl 1542.94270
[43] Tilborg, HV; Blaum, M., On error-correcting balanced codes, IEEE Trans. Inf. Theory, 35, 5, 1091-1095, 1989 · Zbl 0683.94016
[44] Wang, XM; Yang, YX, On the undetected error probability of nonlinear binary constant weight codes, IEEE Trans. Commun., 42, 7, 2390-2394, 1994 · Zbl 0806.94029
[45] Wang, Y.; Noor-A-Rahim, M.; Gunawan, E.; Guan, Y.; Poh, CL, Construction of bio-constrained code for DNA data storage, IEEE Commun. Lett., 23, 6, 963-966, 2019
[46] Wei, HJ; Schwartz, M., Sequence reconstruction for limited-magnitude errors, IEEE Trans. Inf. Theory, 68, 7, 4422-4434, 2022 · Zbl 1505.94126
[47] Yaakobi E., Schwartz M., Langberg M., Bruck J.: Sequence reconstruction for Grassmann graphs and permutations. In: Proceedings of IEEE International Symposium on Information Theory, Istanbul, Turkey, pp. 874-878 (2013).
[48] Yazdi, SMHT; Kiah, HM; Garcia-Ruiz, E.; Ma, J.; Zhao, H.; Milenkovic, O., DNA-based storage: trends and methods, IEEE Trans. Mol. Biol. Multi-Scale Commun., 1, 3, 230-248, 2015
[49] Yazdi, SMHT; Kiah, HM; Gabrys, R.; Milenkovic, O., Mutually uncorrelated primers for DNA-based data storage, IEEE Trans. Inf. Theory, 64, 9, 6283-6296, 2018 · Zbl 1401.94063
[50] Ye, Z.; Liu, X.; Zhang, X.; Ge, G., Reconstruction of sequences distorted by two insertions, IEEE Trans. Inf. Theory, 69, 8, 4977-4992, 2023 · Zbl 07883286
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.