タイトル： Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
著者名： Ryan Gabrys, Venkatesan Guruswami, Joao Ribeiro, Ke Wu
アクセス： https://arxiv.org/pdf/2112.09971.pdf
Abstract： We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with
nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations…
タイトル： Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound
著者名： G Wang, DM Xu, FW Fu
ジャーナル： Advances in Mathematics of Communications, 2021
アクセス： https://www.aimsciences.org/article/doi/10.3934/amc.2021065
Abstract： Codebooks with small maximum cross-correlation amplitudes are used to distinguish the signals from different users in code division multiple access communication systems. In this paper, several classes of codebooks are introduced, whose maximum cross-correlation amplitudes asymptotically achieve the corresponding Welch bound and Levenshtein bound. Specially, a class of optimal codebooks with respect to the Levenshtein bound is obtained. These classes of codebooks are constructed by selecting certain rows deterministically from circulant matrices, Fourier matrices and Hadamard matrices, respectively. The construction methods and parameters of some codebooks provided in this paper are new.
